Information theory/Permutations and combinations

From Wikiversity
Jump to navigation Jump to search

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 | edit source]

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 | edit source]

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 | edit source]

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 | edit source]

2 cases where product rule cannot be used[edit | edit source]

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 | edit source]

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 | edit source]

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 | edit source]

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 | edit source]

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 | edit source]
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 | edit source]

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 | edit source]

F53Big

Multinomials[edit | edit source]

b

Summary[edit | edit source]

c

Temporary equation and figure links[edit | edit source]

Use to test links to equations and figures
{Lorem ipsum|5}}


Tables[edit | edit source]
  1. Ttrig File:Tabela de Relações Trigonométricas.PNG
Figures[edit | edit source]
  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 | edit source]
  1. Estera:   
  2. Esterb:   



What is this template?


Footnotes and contents[edit | edit source]

  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 | edit source]

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.