Information theory/Permutations and combinations

Contents

  1. #Rule of product and counting the number of possible messages: options followed by options yields 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 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

edit
Table 1 How many outcomes?
       
       
30°        
45°        
60°        
90°        

The rule of product is the intuitive idea that if there are   ways of doing something and   ways of doing another thing, then there are   ways of performing both actions.[1] 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,    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   in this table.[2] While the statement,  , 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   and   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

edit

A violation of condition-a arises in Ftrig if we adopt the convention that the ratio   does not exist. If we declare the two instances of   Ttrig as "forbidden" choices, then it is inappropriate to apply the product rule using    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   is certainly not a "number".)

b) All final outcomes must be distinct

edit

A violation of condition-b arises in Ftrig if we define an "outcome" in such a way that not all outcomes are distinct.[3] While the table in Ftrig lists 20 outcomes, the set of all numerical values contains only seven elements:                . Defined in this fashion, the outcomes are not distinct.

Examples

edit

2 cases where product rule cannot be used

edit
 
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"

edit
 
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

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   symbols, taken from an alphabet of   symbols. If multiple repetitions of each symbol are permitted, the number of possible symbols is,

Ekhatn      

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      

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

Introduction to entropy
edit

START HERE Estera:    

Esterb:    

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


Permutations of a characters in a string

edit
 
F6per: The 3!=6 permutations of ABC.

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. [6] If exactly   distinct characters are used to create a string,[7] the number of possible strings that can be created is,

Eperm        

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[8] to writing the first four non-negative integers in base 2:  .

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,  . Our goal is to verify that there are   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:

  1. The first selection can be any of the 3 objects (A, B, or C). This yields n choices.
  2. The second selection can be any of the 2 objects (you can't select the same letter twice.). This yields 2 choices.
  3. 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

edit

Eperm establishes that   permutations (or different strings) of length   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
edit
 
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

edit

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   and   levels the next letter can be either "C" or "R". But when the   is encountered, it is not possible to select "R" after RR has been selected. Hence the number of nodes for   does not increase as 2.4.8, but instead 2.4.7 Working definition of 5-choose-3

 



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

edit
 
F53Big
edit
Use to test links to equations and figures
{Lorem ipsum|5}}|}
Tables
edit
  1. Ttrig File:Tabela de Relações Trigonométricas.PNG
Figures
edit
  1. Fbinstr File:Combinations_bins_versus_strings.svgconnects 134 to crccr
  2. F6per File:3-el permutation counting decisions.svg The 3!=6 permutations of ABC.
  3. F24per File:4-el permutation counting decisions.svg The 4!=24 permutations of ABCD.
  4. Fascii [[:File:Printable ASCII characters.svg]File:Printable ASCII characters.svg] Printable ASCII characters
  5. FcomTree File:5-choose-3 product rule.svg 5-take-3 tree diagram
  6. FC53big File:5-choose-3 tree proof.svg File:5-choose-3_tre

File:5-choose-3 product rule.svg

Equations
edit
  1. Estera:    
  2. Esterb:    



What is this template?


Footnotes and contents

edit
  1. w:special:permalink/1061913371
  2. For example   seems to suggest that  .
  3. 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
  4. more than sufficient by a wide margin:  
  5. See Special:Permalink/2369340#Labeling_every_proton_in_the_universe
  6. 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.
  7. If include empty space as a character an entire paragraph can be considered to be a string
  8. 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}.


scrapbook

edit

Let "strings" of length   created from an "alphabet" consisting of   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   the growth   is more rapid than exponential.