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

Table 1 How many outcomes?

	${\color {red}{\sin }}$	${\color {red}{\cos }}$	${\color {red}{\tan }}$	${\color {red}{\cot }}$
0°	$0$	$1$	$0$	$\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$	$\infty$	$0$

See also: w:Rule of product and b:Probability/The_Counting_Principle

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 Ftrig. 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 $(\infty )$ in this table. While the statement, $\cot(0)=\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 Ftrig if we adopt the convention that the ratio $1/0$ does not exist. If we declare the two instances of $\infty$ Ttrig 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 Ftrig if we define an "outcome" in such a way that not all outcomes are distinct. While the table in Ftrig 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}},$ $\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"

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

Fascii The 95 printable ASCII characters includes the invisible space, shown above E

See also: w:Infinite monkey theorem and Information theory/Shannon entropy

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,

Ekhatn     $\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:

Elog     $H=\log _{b}\Omega =n\log _{b}k,$

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

Introduction to entropy

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

Esterb:   $\log _{b}(n!)\sim n\log _{b}n$

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

---

Permutations of a characters in a string

F6per: The 3!=6 permutations of ABC.

See also: w:Permutation and w:s:Permutation

F6per 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,

Eperm       $\Omega _{\text{words}}=n!$

Eperm 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 F2coin, 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$.

See also: w:Tree diagram (probability theory), w:Tree (data structure), and w:Tree (disambiguation)

Click "Expand" in the box shown below for more help with understanding why Eq. 1 is true.

Making 3!=6 strings from the set {A,B,C}

Consider the case, n=3, 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 Figure 1. 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 The first selection can be any of the 3 objects (A, B, or C). This yields n choices. The second selection can be any of the 2 objects (you can't select the same letter twice.). This yields 2 choices. There is no option regarding the third letter (having selected two letters, you must select the one not yet selected. This yields 1 choices. After taking the product of the number of choices, that there are 3×2×1 = 6 ways to permute the letters A, B, and C

---

F24per: The 4!=24 permutations of ABCD.

Combinations

See also: w:Combination and w:Binomial coefficient

Eperm 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

Fbinstr

FcomTree: 5-take-3 tree diagram

Fbinstr 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 F2coin

Tree diagram for spelling words with 3 "C"s and 2 "R"s at FcomTree 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

${\binom {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

F53Big

Temporary equation and figure links

Use to test links to equations and figures

{Lorem ipsum|5}}|} Tables Ttrig File:Tabela de Relações Trigonométricas.PNG Figures Fbinstr File:Combinations_bins_versus_strings.svgconnects 134 to crccr F6per File:3-el permutation counting decisions.svg The 3!=6 permutations of ABC. F24per File:4-el permutation counting decisions.svg The 4!=24 permutations of ABCD. Fascii [[:File:Printable ASCII characters.svg]File:Printable ASCII characters.svg] Printable ASCII characters FcomTree File:5-choose-3 product rule.svg 5-take-3 tree diagram FC53big File:5-choose-3 tree proof.svg File:5-choose-3_tre The plan is not to use F2coin 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 Estera:   $\ln(n!)\sim n\ln n-n$ Esterb:   $\log _{b}(n!)\sim n\log _{b}n$ What is this template? Footnotes and contents 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 F24per. As $n\to \infty$ the growth $n!$ is more rapid than exponential.