Information theory/Permutations and combinations

Contents

1. #Rule of product and counting the number of possible messages: $i$ options followed by $j$ options yields $ij$ options. Examples we explore include:
   • 2-letter messages using A and/or B: Two options for the first letter followed by two options for the second letter yields $4$ options: AA, AB, BA, BB
   • The rule of product should not be used for two kinds of counting problems:
   1. Outcomes are defined so that two different choice paths lead to the same result
   2. It is not possible to make an a priori count of all possible options.
   • Introduction to entropy: The number of messages that can be sent using a moderate supply of letters is so large that it is common to take the logarithm.
2. #Permutations of a set of distinct symbols
3. #Footnotes and contents

Rule of product and counting the number of possible messages

Template:EquationRef How many outcomes?

	$\sin$	$\cos$	$\tan$	$\cot$
0°	$0$	$1$	$0$	$\mathrm{\infty }$
30°	$\frac{1}{2}$	$\frac{\sqrt{3}}{2}$	$\frac{\sqrt{3}}{3}$	$\sqrt{3}$
45°	$\frac{\sqrt{2}}{2}$	$\frac{\sqrt{2}}{2}$	$1$	$1$
60°	$\frac{\sqrt{3}}{2}$	$\frac{1}{2}$	$\sqrt{3}$	$\frac{\sqrt{3}}{3}$
90°	$1$	$0$	$\mathrm{\infty }$	$0$

Template:See The rule of product is the intuitive idea that if there are $x$ ways of doing something and $y$ ways of doing another thing, then there are $x\cdot y$ ways of performing both actions. A thorough understanding of this rule is essential to counting permutations and combinations. We are especially interested in how to ascertain when this counting principle can be used. To that end, we pose the following question:

• How many ways can four trigonometric functions be evaluated at five different angles?

Exact definitions can be essential important in mathematical communication, and the vague nature of this question can be used to explain two conditions that must be met before the Rule of product can be used.

The most obvious answer to the questions is, $4\times 5$$=20$ evaluations. This is accomplished by counting the elements in the 4 by 5 grid in Template:EquationNote. The decisions can be made in either order: One can count the angles first (5 rows in the figure), and then count the functions (4 columns). Or one can count the functions first.

But precise definitions can be essential in mathematics. There are valid reasons to disapprove of the use of the infinity symbol $(\mathrm{\infty })$ in this table. While the statement, $\cot (0)=\mathrm{\infty }$, has a certain validity, strictly speaking, the cotangent cannot be evaluated at zero. An entirely different vagueness involves what it means to count "evaluations" . Under some circumstances, one might define $\sin 0$ and $\tan 0$ to be the "same evaluation", since both are numerically equal to zero. Both of these ambiguities can be used to highlight two conditions must be satisfied if the rule of counting can be used:

a) The number of choices must be the same for any given level

A violation of condition-a arises in Template:EquationNote if we adopt the convention that the ratio $1/0$ does not exist. If we declare the two instances of $\mathrm{\infty }$ Template:EquationRef as "forbidden" choices, then it is inappropriate to apply the product rule using $4\times 5$$=20.$ What went wrong? If we select the angle first, there are 5 possible choices. But after the angle is chosen, there is no unique value to the number of choices. There are 4 possible choices if either le was 30°, 60°, or 90° were selected at the first level. But if 0° or 90° was selected, then only two functions can be evaluated (since $1/0$ is certainly not a "number".)

b) All final outcomes must be distinct

A violation of condition-b arises in Template:EquationNote if we define an "outcome" in such a way that not all outcomes are distinct. While the table in Template:EquationNote lists 20 outcomes, the set of all numerical values contains only seven elements: $\{0,$ $1/2,$ $\sqrt{3}/3,$ $\sqrt{2}/2,$ $1/2,$ $\sqrt{2},$ $\sqrt{3},$ $\mathrm{\infty }\}$. Defined in this fashion, the outcomes are not distinct.

Examples

2 cases where product rule cannot be used

Summing to 5

Colored circles head tails 2 coins

SAY SOMETHING ABOU QUIZBANK

1. Shown to the left is a tree diagram that there are 6 ways to sum three positive integers five. The product rule does not apply here. Which of the two requirements is violated?
2. Shown to the right is a tree diagram that correctly counts the outcomes if two coins are thrown. But the product does not apply if the outcomes are redefined so that a heads followed by a tail is equivalent to a tails followed by a head. Which requirement (a or b) is violated in this case?

Number strings from a given "alphabet"

Template:EquationRef It is technically wrong, but perhaps not unreasonable to state that it would take an infinite number of monkeys to type Shakespear's Hamlet.

Template:EquationRef The 95 printable ASCII characters includes the invisible space, shown above E

Template:See The product rule can involve more than two choices, and this example involving just 10 choices illustrates the power of an "alphabet" to permit an almost unlimited number of different messages. Consider a string of $k$ symbols, taken from an alphabet of $n$ symbols. If multiple repetitions of each symbol are permitted, the number of possible symbols is,

Template:EquationRefTemplate:Spaces$\mathrm{\Omega }=k^n,$

Here, we use the Greek Omega to denote a value that often turns out to be so large that it is preferable to deal with its logarithm:

Template:EquationRefTemplate:Spaces$H={\log }_b\mathrm{\Omega }=n{\log }_{b}k,$

where $H$ is one of several symbols commonly used to denote entropy.

Introduction to entropy

START HERE Template:EquationRef:   $\ln (n!)\sim n\ln n-n$

Template:EquationRef:   ${\log }_b(n!)\sim n{\log }_{b}n$

Permutation of the 94 printable characters shown in Template:EquationNote are more than sufficient to label every proton, neutron, and electron in the visible universe.

---

Permutations of a characters in a string

Template:EquationRef: The 3!=6 permutations of ABC.

Template:EquationNote depicts a tree diagram that shows how the letters in ABC can be arranged to create 3!=6 different "words". A collection of items is called "distinct" of no two elements are the same. If exactly $n$ distinct characters are used to create a string, the number of possible strings that can be created is,

Template:EquationRef Template:Spaces ${\mathrm{\Omega }}_{\text{words}}=n!$

Template:EquationNote illustrated for n = 1,2, and 3
0! = 1	{ }
1! = 1	{A}
2! = 2×1=2	{AB, BA}
3!=3×2×1=6	{ABC, ACB, BAC, BCA, CAB, CBA}

In the languagecombinatorics, this is called counting the permutations of a set. A simple case is shown in Template:EquationNote, where a tree diagram verifies the outcome of two coins represents four different possible messages. This corresponds exactly to writing the first four non-negative integers in base 2: $00,01,10,11$.

Click "Expand" in the box shown below for more help with understanding why Template:EquationNote is true.

Template:Cot Consider the case, Template:Math, and let the three letters be, $\{A,B,C\}$. Our goal is to verify that there are $3!=3\cdot 2\cdot 1=6,$ different permutations, using Template:EquationNote. This figure is type of decision tree. To count the number of possible permutations, we count the number of choices made at each decision and apply the rule of product. A more complete discussion on how and when to apply this rule, visit:

• Wikibooks:Probability/Combinatorics#Fundamental_Counting_Principle

1. The first selection can be any of the Template:Math objects (A, B, or C). This yields Template:Math choices.
2. The second selection can be any of the Template:Math objects (you can't select the same letter twice.). This yields Template:Math choices.
3. There is no option regarding the third letter (having selected two letters, you must select the one not yet selected. This yields Template:Math choices.

After taking the product of the number of choices, that there are Template:Math×Template:Math×Template:Math = Template:Math ways to permute the letters A, B, and C Template:Cob

---

Template:EquationRef: The 4!=24 permutations of ABCD.

Combinations

Template:See also Template:EquationNote establishes that $n!$ permutations (or different strings) of length $n$ can occur of each character is unique. Here we relax the uniqueness constraint. This leads to the counting of combinations if only two characters are involved. If three or more characters are used, it is necessary to use the closely related binomial coefficient to count the number of possible strings. In both cases it is necessary to specify how many times each character appears in the string.

bins versus strings

Template:EquationRef

Template:EquationRef: 5-take-3 tree diagram

Template:EquationNote permits us to connect two key interpretations of the combination known as 5-choose-3.

1. The placement of 5 distinct objects (1,2,3,4,and 5) into two bins, with three objects in the "C" bin and two in the "R" bin.
2. The creation of strings using only the letters, with "C" used thrice and "R" used twice.

There are 10 distinct ways to select three integers for the "C" bin: {1,2,3}, {1,2,4}, {1,2,5}, {1,3,5}, {1,3,4}, {1,4,5}, {2,3,4}, {2,3,5}, {2,4,5}, and {3,4,5}. It is important to know that these bins are actually sets, where the order in which elements are listed is not important. For example, {1,2,3} and {2,1,3} represents only one way to choose 3 from 5 objects.

The strings are generated attaching bin labels ("R" or "C") to all the integers, while always listing them in the same order. The 10 strings associated with 5-choose-3 are: CCCRR, CCRCR, CCRRC, CRCRC, CRCCR, CRRCC, RCCCR, RCCRC,RCRCC, and RRCCC.

Combinations

a Template:EquationNote

Tree diagram for spelling words with 3 "C"s and 2 "R"s at Template:EquationNote It is possible to rigorously prove that xxx establishes that there exactly 10 strings can be constructed. For example, at the $\alpha$ and $\beta$ levels the next letter can be either "C" or "R". But when the $\gamma$ is encountered, it is not possible to select "R" after RR has been selected. Hence the number of nodes for $\alpha .\beta .\gamma$ does not increase as 2.4.8, but instead 2.4.7 Working definition of 5-choose-3

$(\genfrac{}{}{0ex}{}{5}{2,3})=10$

bring up the tree diagram for 5 take 3 and explain why a tree diagram seems useless
introduce the huge tree diagram for 5 take 3 at file:5-choose-3 tree proof.svg
add abstract that explains this turn of events.  Try and tie in to information theory, distintion between pure and applied mathematics, noting that proofs can be informal in applied math

Huge tree diagram

Template:EquationRef

Temporary equation and figure links

Template:Cot{Lorem ipsum|5}}Template:Cob

Tables

1. Template:EquationNote File:Tabela de Relações Trigonométricas.PNG

Figures

1. Template:EquationNote File:Combinations_bins_versus_strings.svgconnects 134 to crccr
2. Template:EquationNote File:3-el permutation counting decisions.svg The 3!=6 permutations of ABC.
3. Template:EquationNote File:4-el permutation counting decisions.svg The 4!=24 permutations of ABCD.
4. Template:EquationNote [[:File:Printable ASCII characters.svg]File:Printable ASCII characters.svg] Printable ASCII characters
5. Template:EquationNote File:5-choose-3 product rule.svg 5-take-3 tree diagram
6. Template:EquationNote File:5-choose-3 tree proof.svg File:5-choose-3_tre

• The plan is not to use Template:EquationNote File:Colored_circles_head_tails_2_coins.svg Simple example of the product rule: Flipping two coins

File:5-choose-3 product rule.svg

Equations

1. Template:EquationNote:   $\ln (n!)\sim n\ln n-n$
2. Template:EquationNote:   ${\log }_b(n!)\sim n{\log }_{b}n$

---

What is this template? Template:Information theory/Permutations and combinations

---

scrapbook

Let "strings" of length $n$ created from an "alphabet" consisting of $k$ characters if each is used exactly one time?

Adding one more letter will significantly increase the number of possible permutations, from 6 permutations for ABC, to 24 permutations for ABCD, as shown in Template:EquationNote. As $n\to \mathrm{\infty }$ the growth $n!$ is more rapid than exponential.