Draft:Information theory/Permutations and combinations

THIS DRAFT IS BEING USED TO HELP ME EDIT Information theory/Permutations and combinations. DO NOT DELETE

The rate at which Template:Math increases for large Template:Math boggles the mind: Template:Math, and Template:Math But Template:Math $\approx 3 \times 1 0^{80}$ , which likely outnumbers the number of atoms in the visible universe.

Suppose you have with the following collection of animal crackers: Two are Elephants, three are Crows, and two are Rats. How many seven-letter words can you make?

Combinations

Template:See also The traditional view of combinations focuses on selecting k items from a collection (or set) of n items. In this discussion, the Template:Math items are positive integers, i.e., the set: ${1, 2, 3, . . ., n}$ . Rules of set theory^[1] permit us to change the order of these Template:Math objects.^[2] However for our purposes, these Template:Math objects (integers) are generally listed in the proper order because the integers denote the order in which the "letters" of a message are presented. In keeping with a parallel discussion of Shannon entropy, we associate the bins with Crow and Rat, using the notation Template:Math () and Template:Math (). These refer to "letters" in a binary alphabet.^[3]

Permute "Bin labels", not the order of the letters in the word

Instead of placing the members of the set

{1, 2 \dots N}

into "bins"

{C, R \dots}

, we shall instead permute

N

"bin-labels" and attach them to the set Template:Math}

Simple example: 3-choose-2

This is equivalent to finding 3-choose-1. Our goal is to well to counting all the three-letter words that use Template:Math twice and Template:Math once. For reasons that will be understood later, we solve this problem attaching labels to letter that is used twice: $(C_{1}, C_{2}) .$ As shown in the left-most column in Template:EquationNote, we begin by counting all Template:Math permutations of $(C_{1} C_{2} R) .$

The stationary columns represent Template:Math}, which are the order in which the letters appear. Equivalently Template:Math} represent the 3 distinguishable objects to be placed in either the C or R bins. The other two columns in the figure illustrate that there there is a two-fold redundancy in that each of the three combinations appears twice.^[4]

Multinomial coefficients for non-binary alphabets

Application of the binomial theorem for Template:Nobreak, with Template:Math and Template:Math leads to the familiar result:

Template:EquationRef Template:Spaces $(\binom{n}{k}) = \frac{n!}{k! (n - k)!} = \frac{3!}{2! 1!}$

If more than two "bins" are involved, we define, $n_{1} = k$ and $n_{2} = n - k .$ This results in a formula that is easier to remember and can be generalized to include counting the words that can be written with three or more letters:

Template:EquationRef Template:Spaces $\frac{(n_{1} + n_{2})!}{n_{1}! n_{2}!} \Rightarrow \frac{(n_{1} + n_{2} + n_{3})!}{n_{1}! n_{2}! n_{3}!} \Rightarrow \frac{(\sum_{j} n_{j})!}{\prod_{j} (n_{j}!)}$

Larger numbers: 5-choose-3

Template:EquationNoteillustrates how one can visualize the counting of 5-choose-3. As before, we begin with the 120 permutations of the 5 subscripted letters ${C_{1} C_{2} C_{3} R_{1} R_{2}} .$ The goal is to organize these permutations in such a way that the duplicates associated with dropping the subscripts are accounted for. With 3-choose-1 the only duplicates involved the order of Crows ( $C_{1} C_{2}$ versus $C_{2} C_{1}$ ).

With 3 Crows and 2 Rats, we have $3! = 6$ ways to permute the Crows and $2! = 2$ permutations for the Rat. It is instructive to first consider how many of the 120 permutations are associated with a single word. Consider, for example all the ways subscripts can be added to the word that starts with two $R$ s, namely the word: $R R C C C$ :

well

\begin{matrix} positive \\ permutations \\ of C_{1} C_{2} C_{3} \end{matrix} \overset{R_{1} R_{2} R_{2} R_{1}}{\overset{⏞}{{\begin{matrix} R_{1} R_{2} C_{1} C_{2} C_{3} & R_{2} R_{1} C_{1} C_{2} C_{3} \\ R_{1} R_{2} C_{2} C_{3} C_{1} & R_{2} R_{1} C_{2} C_{3} C_{1} \\ R_{1} R_{2} C_{3} C_{1} C_{2} & R_{2} R_{1} C_{3} C_{1} C_{2} \end{matrix}}}

Template:Spaces

Template:EquationRef

\begin{matrix} negative \\ permutations \\ of C_{1} C_{2} C_{3} \end{matrix} \underset{R_{1} R_{2} R_{2} R_{1}}{\underset{⏟}{{\begin{matrix} R_{1} R_{2} C_{3} C_{2} C_{1} & R_{2} R_{1} C_{3} C_{2} C_{1} \\ R_{1} R_{2} C_{2} C_{1} C_{3} & R_{2} R_{1} C_{2} C_{1} C_{3} \\ R_{1} R_{2} C_{1} C_{3} C_{2} & R_{2} R_{1} C_{1} C_{3} C_{2} \end{matrix}}}

Counting the words in Template:EquationNote, we see that there are 12 ways to attach our subscripts to Template:Math It can be shown that all words involving 3 Template:Maths and 2 Template:Maths can be subscripted in 12 different ways.

The product rule

It is instructive to closely examine how Template:EquationNoteenumerates the Template:Math ways that subscripts can be assigned to repeated letters in any given word. The Template:Math words are listed in two columns of six rows each. The first column places $R_{1}$ before $R_{2}$ , while the second column presents the Template:Maths in reverse order. Each of the six rows represents one of the Template:Math permutations of the subscripts Template:Math that are assigned to the Crows (these permutations were presented in Template:EquationNote.)^[5]

The fact that all (six) ways to assign to subscripts to the three Crow letters is multiplied by all (two) ways to assign subscripts to the two Rat letters is known as the product rule.

This same $(2 \times 6 = 12)$ element array of possible subscripts for Crow and Rat is also shown in Template:EquationNote. The boxed element at Template:Nobreak tells us the order in which the subscripted letters appear. The top three digits Template:Math informs us that the subscripted Crows follow the order $C_{2} . . C_{1} . . C_{3}$ . Meanwhile the lower pair Template:Math informs us that $R_{1}$ precedes $R_{2}$ .

Recap on efforts to count 5-choose-3

Template:See also

We know from counting the permutations of Template:Math symbols that there are Template:Math ways to arrange the five subscripted letters $C_{1} C_{2} C_{3}$ .
For any given five letter word (involving Template:Maths and Template:Maths) there are Template:Math ways to to separately^[6] attach subscripts to the letters. Since these Template:Math versions of the word are identical if the subscripts are removed, we shall refer to these as duplicates of the word.

This is all we need to calculate Template:Math.

Geometric "proof"

Template:EquationNoteillustrates how one can arrange the Template:Math permutation this collection. Taking the height to be an unknown, we create the box by stacking rectangles of Template:Math duplicates for each word. Since $12 \times 10 = 120$ , we conclude that Template:Math is our desired result:

Template:EquationRef Template:Spaces $(\binom{5}{3}) = \frac{5!}{3! 2!} = 10$

Algebraic proof and multinomial theorem

It is not difficult to extend the geometric argument associated with Template:EquationNoteto arbitrary values on Template:Math and Template:Math as as stated at Template:EquationNote. On the other hand, an important restriction results from using a three-dimensional box to account for duplicate words^[7]. However, counting the words one can create with more than

On the other hand,

stophere

$(\binom{n}{k_{1}, k_{2}, \dots, k_{m}})$

Template:Clear

There are Template:Math ways to permute^[8] the subscripted version of RRCCC.
Each combination (of 5-take-3) is duplicated 12 time if the subscripts are removed.

∴ The value of 5-take-3 is Template:Math

For reasons soon to be discussed, we express these ways as the product, $6 \times 2 = 12$ . Since there there are Template:Math ways to permute the subscripted version of

Multinomials

Although the value of Shannon entropy is independent of how many letters are contained in the "alphabet", some users might wish to count how many words can be created by a non-binary alphabet. There are a number ways to do it

THIS SECTION NEEDS TO BE MOVED TO ANOTHER PAGE (MyOpenMath?)

File:Multinomial theorem mississippi.svg

Appendix

↑ In addition to Wikiversity's page Set theory, other wikis with good introductory pages are w:Simple:Set, b:Set Theory/Sets, and b:Discrete Mathematics/Set theory
↑ e.g., ${1, 2, 3}$ and ${2, 1, 3}$ are identical sets.
↑ Following the convention of Information theory/Shannon entropy the next "letter" would be E ()
↑ ... depending on whether $C_{1}$ precedes or follows $C_{2}$ .
↑ In addition, Table 1 also distinguised between the even and odd permutations of 123 (see w:Parity of a permutation)
↑ By "separately" we mean subscripts {1,2,3) for Crow and (1,2) for Rat.
↑ i.e., words with the same letters but different subscripts
↑ Recall that "permute" means to rearrange the order. For example RCRRC is a permutation of RRCCC.

[1] In addition to Wikiversity's page Set theory, other wikis with good introductory pages are w:Simple:Set, b:Set Theory/Sets, and b:Discrete Mathematics/Set theory

[2] .g., ${1, 2, 3}$ and ${2, 1, 3}$ are identical sets.

[3] Following the convention of Information theory/Shannon entropy the next "letter" would be E ()

[4] ... depending on whether $C_{1}$ precedes or follows $C_{2}$ .

[5] In addition, Table 1 also distinguised between the even and odd permutations of 123 (see w:Parity of a permutation)

[6] By "separately" we mean subscripts {1,2,3) for Crow and (1,2) for Rat.

[7] .e., words with the same letters but different subscripts

[8] Recall that "permute" means to rearrange the order. For example RCRRC is a permutation of RRCCC.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Draft:Information theory/Permutations and combinations

Contents