View source for Information theory/Permutations and combinations

Contents
#'''[[#Rule of product and counting the number of possible messages]]''': <math>i</math> options followed by  <math>j</math> options yields <math>ij</math> 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 <math>4</math>  options: ''AA, AB, BA, BB''
#* The rule of product should not be used for two kinds of counting problems:
##Outcomes are defined so that two different choice paths lead to the same result
## It is not possible to make an [[w:A priori and a posteriori|''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.
#'''[[#Permutations of a set of distinct symbols]]''' 
#'''[[#Footnotes and contents]]'''


==Rule of product and counting the number of possible messages==
{|class="wikitable floatright"; style="text-align: center";
|+ {{EquationRef|Ttrig|Table 1}} How many outcomes? 
|style='background: white'|
|style='background: #FF9' |<math>{\color{red}{\sin}}</math>
|style='background:#FF9' |<math>{\color{red}{\cos}}</math>
|style='background: #FF9' |<math>{\color{red}{\tan}}</math>
|style='background: #FF9' |<math>{\color{red}{\cot}}</math>
|-
|style='background: #9FF' |0&deg;
|style="background: #CF6;"|<math>0</math>
|style="background: #CF6;"|<math>1</math>
|style="background: #CF6;"|<math>0</math>
|style="background: #CF6;"|<math>\infty</math>
|-
|style='background: #9FF' |30&deg;
|style="background: #CF6;"|<math>\frac{1}{2}</math>
|style="background: #CF6;"|<math>\frac{\sqrt 3}{2}</math>
|style="background: #CF6;"|<math>\frac{\sqrt 3}{3}</math>
|style="background: #CF6;"|<math>\sqrt 3</math>
|-
|style='background: #9ff' |45&deg;
|style="background: #CF6;"|<math>\frac{\sqrt 2}{2}</math>
|style="background: #CF6;"|<math>\frac{\sqrt 2}{2}</math>
|style="background: #CF6;"|<math>1</math>
|style="background: #CF6;"|<math>1</math>
|-
|style='background: #9ff' |60&deg;
|style="background: #CF6;"|<math>\frac{\sqrt 3}{2}</math>
|style="background: #CF6;"|<math>\frac{1}{2}</math>
|style="background: #CF6;"|<math>\sqrt 3</math>
|style="background: #CF6;"|<math>\frac{\sqrt 3}{3}</math>
|-
|style='background: #9ff' |90&deg;
|style="background: #CF6;"|<math>1</math>
|style="background: #CF6;"|<math>0</math>
|style="background: #CF6;"|<math>\infty</math>
|style="background: #CF6;"|<math>0</math>
|}
{{See|w:Rule of product|b:Probability/The_Counting_Principle}}
The '''rule of product''' is the intuitive idea that if there are <math>x</math> ways of doing something and <math>y</math>  ways of doing another thing, then there are <math>x\cdot y</math> ways of performing both actions.<ref>[[w:special:permalink/1061913371]]</ref> A thorough understanding of this rule is essential to counting [[w:special:permalink/994283739|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 [[w:Rule of product|''Rule of product'']] can be used.

The most obvious answer to the questions is, <math>4\times 5</math><math> = 20</math> evaluations. This is accomplished by counting the elements in the 4 by 5 grid in  {{EquationNote|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 <math>(\infty)</math> in this table.<ref>For example <math>1/0=\infty=2/0</math> seems to suggest that <math>1=2</math>.</ref>  While the statement, <math>\cot(0)=\infty</math>, 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 <math>\sin 0</math> and <math>\tan 0</math> 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 {{EquationNote|Ftrig}} if we adopt the convention that the ratio <math>1/0</math> does not exist.  If we declare the two instances of <math>\infty</math> {{EquationRef|Ttrig}} as "forbidden" choices, then it is inappropriate to apply the product rule using <math>4\times 5</math><math> = 20.</math> 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&deg;,  60&deg;, or  90&deg; were selected at the first level.  But if  0&deg; or 90&deg; was selected, then only two functions can be evaluated (since <math>1/0</math> is certainly not a "number".)

==== b) All final outcomes must be distinct ====
A violation of condition-b arises in {{EquationNote|Ftrig}} if we define an "outcome" in such a way that not all outcomes are distinct.<!--
--><ref name="distinct">As explained in [[w:Equality (mathematics)]], "distinct" means 'not the same'. For example, it is customary to list each element of a set only once, i.e. in a fashion so that each element is distinct</ref><!--
--> While the table in {{EquationNote|Ftrig}} lists 20 outcomes, the set of all numerical values contains only seven elements: <math>\{0,</math> <math>1/2,</math> <math>\sqrt 3/3,</math> <math> \sqrt 2/2, </math> <math>1/2, </math> <math>\sqrt 2,</math> <math> \sqrt 3,</math> <math>\infty\}</math>.  Defined in this fashion, the outcomes are not distinct.

===Examples===
====2 cases where product rule cannot be used====
[[File:Tree diagram sum 5 by three numbers.svg|thumb|left|160px|Summing to 5]][[File:Colored circles head tails 2 coins.svg|thumb|Colored circles head tails 2 coins|280px]]
 SAY SOMETHING ABOU QUIZBANK
#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?
#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"====
[[File:Chimpanzee seated at typewriter.jpg|left|thumb|{{EquationRef|Monkey}} It is technically wrong, but [[w:Infinite monkey theorem|perhaps not unreasonable]] to state that it would take an infinite number of monkeys to type Shakespear's ''Hamlet''.]]
[[File:Printable ASCII characters.svg|thumb|{{EquationRef|Fascii}} The 95 printable [[w:ASCII|ASCII]] characters includes the invisible space, shown above '''E''']]
{{See|w:Infinite monkey theorem|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 [[w:Alphabet (formal languages)|"alphabet"]] to permit an almost unlimited number of different messages. Consider a string of <math>k</math> symbols, taken from an alphabet of <math>n</math> symbols.  If multiple repetitions of each symbol are permitted, the number of possible symbols is,

{{EquationRef|Ekhatn}}{{spaces|5}}<math>\Omega = k^n,</math>

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

{{EquationRef|Elog}}{{spaces|5}}<math>H=\log_b\Omega = n\log_b k,</math>

where <math>H</math> is one of several symbols commonly used to denote [[w:Entropy|entropy]].

=====Introduction to entropy=====
START HERE
{{EquationRef|Estera}}: &nbsp;&nbsp;<math>\ln (n!) \sim n\ln n - n</math>

{{EquationRef|Esterb}}: &nbsp;&nbsp;<math>\log_b (n!) \sim n\log_b n</math>

Permutation of the 94 printable characters shown in {{EquationNote|Fascii}} are more than sufficient<ref>more than sufficient by a wide margin: <math>10^{148}>>10^{80}</math></ref> to label [[w:Eddington number|every proton, neutron, and electron in the visible universe]].<ref>See [[Special:Permalink/2369340#Labeling_every_proton_in_the_universe]]</ref>
-----

==Permutations of a characters in a string==
[[file:3-el_permutation_counting_decisions.svg|thumb|160px|text-top|{{EquationRef|F6per}}: The 3!=6 permutations of ABC.]]
{{See also|w:Permutation|w:s:Permutation}}

{{EquationNote|F6per}} depicts a [[w:Tree diagram (probability theory)|tree diagram]] that shows how the letters in  ABC can be arranged to create 3!=6  different "words".  A collection of items is called "[[w:Equality (mathematics)|distinct]]" of no two elements are the same. <ref>In set theory it is customary to list each element of a set only once.  The elements of a set listed in this way is an example of a collection of "distinct" objects.</ref>  If exactly <math>n</math> distinct characters are used to create a string,<ref>If include empty space as a character an entire paragraph can be considered to be a string</ref>  the number of possible strings that can be created is,

{{EquationRef|Eperm}} {{spaces|5}} <math>\Omega_\text{words}=n!</math>

{|
! colspan="4" |{{EquationNote|Eperm}} illustrated for n = 1,2, and 3
|-
|0! = 1
| &nbsp; { }
|-
|1! = 1
| &nbsp; {A}
|-
|2! = 2×1=2
| &nbsp;  {AB, BA}
|-
|3!=3×2×1=6
| &nbsp;  {ABC, ACB, BAC, BCA, CAB, CBA}
|}

In the language[[w:Combinatorics|combinatorics]], this is called counting the [[w:Permutation|permutations of a set]]. A simple case is shown in {{EquationNote|F2coin}}, where a [[w:Tree (data structure)|tree diagram]] verifies the outcome of two coins represents four different possible messages.  This corresponds exactly<ref>The only difference between the sets {HH,HT,TH,TT} and {00,01,10,11} is the choice of "letters".  One uses {H,T} and the other {0,1}.</ref> to writing the first four non-negative integers in base 2: <math>00, 01, 10, 11</math>.  

{{See
|w:Tree diagram (probability theory)
|w:Tree (data structure)
|w:Tree (disambiguation)
}}

Click "Expand" in the box shown below for more help with understanding why {{EquationNote|Eperm|Eq. 1}} is true.

{{cot|''Making 3!{{=}}6 strings from the set {A,B,C}''}}
Consider the case, {{math|n{{=}}3}}, and let the three letters be, <math>\{A,B,C\}</math>. Our goal is to verify that there are <math>3!=3\cdot 2\cdot 1 = 6,</math> different permutations, using {{EquationNote|Figure 1}}.  This figure is type of [[w:Tree diagram (probability theory)|decision tree]]. To count the number of possible permutations, we count the number of choices made at each decision and apply the [[w:Rule_of_product|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 {{math|3}} objects (A, B, or C).  '''This yields {{math|n}} choices.''' 
#The second selection can be any of the {{math|2}} objects (you can't select the same letter twice.).  '''This yields {{math|2}} choices.''' 
#There is no option regarding the third letter (having selected two letters, you must select the one not yet selected. '''This yields {{math|1}} choices.''' 

After taking the product of the number of choices, that there are '''{{math|3}}&times;{{math|2}}&times;{{math|1}} = {{math|6}} ways to permute the letters A, B, and C'''
{{cob}}

-----
[[File:4-el permutation counting decisions.svg|thumb|left|220px|{{EquationRef|F24per}}: The 4!=24 permutations of ABCD.]]

==Combinations==
{{See also|w:Combination|w:Binomial coefficient}}
{{EquationNote|Eperm}} establishes that <math>n!</math> permutations (or different strings) of length <math>n</math> can occur of each character is unique.  Here we relax the uniqueness constraint. This leads to the counting of [[w:Combinations|combinations]] if only two characters are involved.  If three or more characters are used, it is necessary to use the closely related
[[w:Binomial coefficient|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=====
[[File:Combinations bins versus strings.svg|thumb|100px|{{EquationRef|Fbinstr}}]]
[[File:5-choose-3 product rule.svg|thumb|260px|right|{{EquationRef|FcomTree}}: 5-take-3 tree diagram]]
{{EquationNote|Fbinstr}} permits us to connect two key interpretations of the [[w:Combination|combination]] known as ''5-choose-3''.  
#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.
#The creation of strings using only the letters, with "C" used [[wikt:thrice|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 [[w:Set (mathematics)|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 {{EquationNote|F2coin}} 

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

<math>\binom{5}{2,3}=10</math>




 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===
[[file:5-choose-3 tree proof.svg|center|800px|{{EquationRef|F53Big}}]]

==Temporary equation and figure links==
{{cot|Use to test links to equations and figures}}{Lorem ipsum|5}}{{cob}}

=====Tables=====
#{{EquationNote|Ttrig}} [[:File:Tabela de Relações Trigonométricas.PNG]]
=====Figures=====
#{{EquationNote|Fbinstr}} [[:File:Combinations_bins_versus_strings.svg]]connects 134 to crccr 
#{{EquationNote|F6per}} [[:File:3-el permutation counting decisions.svg]] The 3!=6 permutations of ABC. 
#{{EquationNote|F24per}} [[:File:4-el permutation counting decisions.svg]] The 4!=24 permutations of ABCD.
#{{EquationNote|Fascii}} [[:File:Printable ASCII characters.svg]File:Printable ASCII characters.svg] Printable ASCII characters 
#{{EquationNote|FcomTree}} [[:File:5-choose-3 product rule.svg]] 5-take-3 tree diagram
#{{EquationNote|FC53big}} [[:File:5-choose-3 tree proof.svg]] File:5-choose-3_tre

*The plan is not to use {{EquationNote|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=====


#{{EquationNote|Estera}}: &nbsp;&nbsp;<math>\ln (n!) \sim n\ln n - n</math>
#{{EquationNote|Esterb}}: &nbsp;&nbsp;<math>\log_b (n!) \sim n\log_b n</math>


-----
What is this template?
{{Information theory/Permutations and combinations}}
-----
==Footnotes and contents==
{{References}}
__TOC__
<references />

==scrapbook==
Let  [[w:String_(computer_science)|"strings"]] of length <math>n</math> created from an [[w:Alphabet (formal languages)|"alphabet"]] consisting of <math>k</math> 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 {{EquationNote|F24per}}. As <math>n\to\infty</math> the growth <math>n!</math> is more rapid than exponential.

[[Category:Information theory]]