Probability/Combinatorics


What is combinatorics?Edit

Combinatorics involves the counting and enumeration of elements of sets and similar structures such as sequences and multisets. We have discussed set theory in the chapter about set theory, and we will briefly discuss what is sequence and multiset.

Roughly speaking, a sequence is like a set, but ordering of elements matters, and a multiset is also like a set, but repetition of an element is allowed.

Sequence corresponds to the discussion about ordered selection without replacement, while multiset corresponds to the discussion about unordered selection with replacement.

Fundamental counting principlesEdit

Theorem.

 
Venn diagram illustrating inclusion-exclusion principle when   (area of each (intersection of) set can be interpreted as its cardinality).

(Inclusion-exclusion principle) For each finite set  ,

 

Proof. Idea:

  • To find the cardinality of the union of   sets:
  1. Include the cardinalities of each of the   sets.
  2. Exclude the cardinalities of the pairwise intersections (if needed).
  3. Include the cardinalities of the triple-wise intersections (if needed).
  4. Exclude the cardinalities of the quadruple-wise intersections (if needed).
  5. Include the cardinalities of the quintuple-wise intersections (if needed).
  6. Continue, until the cardinality of the  -tuple-wise intersection is included (if   is odd) or excluded (if   is even).

 

Remark.

  • The formula can be written more compactly as
     
  • The definition of   will be discussed later in this chapter.
  • The formula is usually used for the case   and  .
  • When  , the formula becomes  .
  • When  , the formula becomes  .
  • The name 'inclusion-exclusion principle' comes from the idea that the principle is based on over-generous inclusion, and then followed by compensating exclusion.

Example. Among 140 people, 110 of them speak at least one of English, French and German. Given that

  • 90, 30, 42 of them speak English, French, German respectively;
  • 23 speak English and French;
  • 25 speak English and German;
  • 16 speak French and German.

Then, the no. of people that speak English, French and German is  .

Proof. Let  ,  ,   be the set containing people speaking English, French and German respectively. Then, by inclusion-exclusion principle,

 
and the result follows.

Venn diagram

*----------------*
|90-13-12-11=54  | <---- E
|      *---------*--------------*
|      |25-12=13 |42-13-12-4=13 | <--- G
*------*---------*--------------*-----*
|      |   12    |16-12=4       |     |
|      *---------*--------------*     | <--- F
|  23-12=11      |  30-11-12-4=3      |
*----------------*--------------------*
  140-110=30

 

Exercise.

1 Calculate the no. of people that speak (a) English only; (b) French only; (c) German only.

(a) 90; (b) 30; (c) 42
(a) 54; (b) 13; (c) 3
(a) 54; (b) 11; (c) 3
(a) 54; (b) 3; (c) 11
None of the above.

2 Suppose   people among the 140 people now learn to speak English. Calculate   such that 123 of them speak at least one of English, French and German, and 20 people speak English, French and German now.

20
21
22
23
None of the above.

3 Continue from previous question. Calculate the no. of people who speak English and French now.

23
31
36
44
None of the above.



Theorem. (Multiplication counting principle) If trial   has   possible outcomes respectively, then the   trials have   possible outcomes.

Proof. First, consider the case for  : we can enumerate each possible outcomes using ordered pair, as follows:

 
Then, we can count that there are   possible outcomes (by considering the rows (or columns) one by one).

After establishing the case for  , we can establish the case for positive integer   inductively, e.g.:

 
then we can count that there are   outcomes (by considering the rows (or columns) one by one), and we can prove the remaining cases inductively.

 

Remark.

  • It is also known as rule of product.

Example.

 
Figure 3. In set theory, this is called the Cartesian product
of two sets, with cardinality,  ]]

The tree diagram of Figure 3 illustrates this for  ,  , and  . The number of possible outcomes is  

Exercise.

1 Determine the number of possible outcomes if   and   instead.

1
2
3
6
12

2 Suppose   now. Given that the number of possible outcomes is still 6 without changing other conditions given in the example, calculate  .

1
2
3
6
12



Remark.

  • this might be visualized by imagining a flip of three-sided die (with three outcomes, e.g. 1,2,3), followed by a flip of a two-sided coin (with two outcomes, e.g. A,B).


Counting the number of elements in a power setEdit

Example. (Number of elements in a power set) The number of elements in a power set of set   with   elements is  .

Proof. Consider the   elements in   one by one. For each of them, we can either include or do not include it in a subset of  . Then, there are   steps involved to construct a subset of  , and each step has two outcomes. It follows from the multiplication counting principle that the   steps have   outcomes. That is, there are   possible (distinct) subsets of  . Since power set contains all subsets of   by definition, it follows that the power set has   elements.

 

Exercise.

Determine the number of elements in   (i.e. power set of empty set).

0
1
2
4
It is undefined.



Remark.

  •   is arbitrary nonnegative integer

The counting principle misusedEdit

 
Figure 4. The counting principle is not useful when the number of choices at each step is not unique.
 
Figure 5. The counting principle only applies if the outcomes are defined such that   (i.e. order matters).

Figures 4 and 5 illustrate the fact that the counting principle is not always useful. Figure 4 calculates the ways the three integers can be added to five, if the integers are restricted to the set  . Since these three integers are choices (decisions), it is convenient to label the choice indices with capital letters:  

E.g.,   means the second choice is the integer 3.

We cannot apply the counting principle to figure 4 because   depends on   In our case,   and   and   This leads us to an important caveat about using the counting principle:

  • the counting principle cannot be used if the number of outcomes at each step cannot be uniquely defined

Figure 5 exams two flips of a coin. It calculates the correct number of outcomes to be,    but only if we carefully define the outcome. The counting principle is valid only if heads followed by a tails (HT) is a different outcome than tails followed by heads (TH). In other words:

  • when counting outcomes it is important to understand the role that order (enumeration) plays in defining outcomes

But, if we instead are counting the outcomes in a fashion such that HT and TH are considered to be the same, then a formula such as   cannot be used:

  • the counting principle does not hold if two different decision paths lead to the same final outcome (in the theorem, we say 'trial  , which implicitly assumes that the order matters in the outcomes for the   trials)

Example. Suppose we throw two six-faced dice, with colors red and blue respectively. The number of possible distinct pairs of number facing up is  .

Proof. Since the dice are distinguishable, we can use multiplication principle of counting. To be more precise, we can let the possible numbers facing up of red dice to be the possible outcomes in 'trial 1', and that of blue dice to be the possible outcomes in 'trial 2'. Since each trial has six outcomes, it follows that the number of outcomes (i.e. possible distinct pairs) is  .

 

Exercise.

Suppose the red dice becomes a blue dice, such that the two dices are not distinguishable anymore. Calculate the number of possible distinct pairs of number facing up.

6
15
18
21
36




Number of ways to select some objects from distinguishable objectsEdit

In this section, we will discuss number (no.) of ways to select some objects from distinguishable objects, in four types, classified by whether the selection is ordered, and whether the selection is with replacement.

Before discussing these four types of selection, we will introduce some preliminary mathematical concepts used in the following.

Preliminary mathematical conceptsEdit

Definition. (Factorial) For each nonnegative integer  , the factorial of  , denoted by  , is

 

More generally, we have gamma function.

Definition. (Gamma function) The gamma function is

 
in which  .

Proposition. (Relationship between gamma function and factorial) For each nonnegative integer  ,  .

Proof. Using integration by parts,

 
Since
 
 
for each nonnegative integer  .

 

Remark.

  • The infinity in the proof can be regarded as extended real number, or be in limit sense.
  • Another more general result shown in the proof is that   for each positive  .

Definition. (Binomial coefficient) The binomial coefficient, indexed by nonegative integers   and   such that  . denoted by  , is

 

Theorem. (Binomial series theorem) For each real number  ,

 
in which  .

Remark. The following are some special cases of this theorem:

  •  ;
  •  ;
  •   (negative binomial series);
  •   (binomial series).

Theorem. (Binomial theorem) For each nonegative integer  ,

 

Proof. It can be proved combinatorially or inductively. Complete proof is omitted.

 

The binomial theorem can be illustrated by Pascal's triangle:

   

Ordered selection without replacementEdit

Theorem. The no. of ways for ordered selection of   objects from   distinguishable objects without replacement is  

Proof. Consider an equivalent situation: selecting   objects from   distinguishable objects to be put into   ordered boxes, labelled box  , in which each box contains at most one object. By considering the   boxes from box 1 to box   ,

  • for box 1, there are   choices of object to be put into it
  • for box 2, there are   choices of object to be put into it, since the object put into box 1 cannot be simultaneously put into box 2
  • ...
  • for box  , there are   choices of object to be put into it, since each of the   objects put into box   cannot be simultaneously put into box  

Thus, by multiplication principle of counting, the desired no. of ways is

 

 

Remark.

  •   is often denoted by   (read n p r).

Example. The no. of distinct ways to select 3 objects to be put into 3 boxes, labelled   and   from 5 objects, labelled   and   is  

Exercise.

1 After putting the 3 objects into the 3 boxes, 2 of them are taken out and put into 2 boxes, labelled   and  . Calculate the no. of distinct ways to do this.

3
6
60
180
360

2 Continue from previous question. Suppose only 1 of them is taken out and put into 1 box, labelled  , now. Calculate the no. of distinct ways to do this.

3
6
60
180
360



Example. (Competition) There are   candidates for a competition. The no. of ways to award winner, 1st and 2nd runners-up is  

If, Amy and Bob are among the   candidates, and it is given that Amy is awarded 1st runner-up, while Bob does not receive any award, the no. of ways to award winner, 1st and 2nd runners-up becomes  . In particular, Amy and Bob cannot be awarded winner or 2nd runner-up.

Exercise.

1 Suppose Chris is also among the   candidates. Given that Amy, Bob and Chris receive an award from the competition, calculate the no. of ways to award winner, 1st and 2nd-runners up.

1
3
6
32
96

2 Continue from previous question. Given that Amy, Bob and Chris do not receive any award from the competition, calculate the no. of ways to award winner, 1st and 2nd-runners up.

1716
2496
3354
3357
3359




A special case of ordered selection without replacement is when the no. of selected objects equals the no. of objects to be selected. In this case, this selection is called permutation, and the no. of ways for permutation of   objects (i.e. ordered selection of   objects from   objects) is  .

Example.

 
Figure 6. 3!=3·2·1= 6 permutations of {1,2,3}.

The 6 ways to permute the string 123 are shown in Figure 6.

Unordered selection of distinguishable objects without replacementEdit

Theorem. The no. of ways for unordered selection to select   objects from   distinguishable objects without replacement is  .

Proof. There are two ways to prove this.

First, consider an equivalent situation: selecting   objects from   distinguishable objects without replacement to be put into one box [1]. Then, we consider the no. of ways to do this in order, and then remove some ways that are regarded to be the same for unordered selection (i.e. regarded as the same when we put the objects into one box). The no. of ways to do this in order is   (choice   means the  th selection of objects to be put into the box)

Among these ways, putting the same   objects into the box in different orders counts as different ways, and we need to merge them together, into one way. To merge them, we consider how many different ways are counted for putting the same   objects into the box in different orders. Indeed, this is permutation (ordered selection of   objects from   distinguishable objects), so the no. of different ways is  . So, we count   extra times of no. of ways (i.e. scale up the no. of ways by a factor  ) , and thus we need to scale down the no. of ways, by dividing the no. by  . Thus, the desired no. of ways is  .

Second, we use the notion of generating function, by encoding the selection process into a binomial series, and then use the coefficients to determine the desired no. of ways. To be more precise, recall a special case of binomial series theorem:

 
By encoding each selection to each of  , through treating the   and   in the  th   as not selecting the object and selecting the object respectively, the coefficient of   is the desired no. of ways, since it is the no. of ways to build  , through selecting   in    's, and selecting 1 in other  's (i.e. selecting   objects, regardless of the order). Thus, the desired no. of ways is  .

 

Remark.

  • The unordered selection without replacement is also known as combination.
  •   is read as 'n choose r', or 'n c r'.

Example.

 
Figure 8:   is shown for   and   The dotted ellipses remind us that these are sets, where order is not important.

For combination, the order in which the items are selected are not important, so each selection from a set can be regarded as a subset of the original set. Figure 8 illustrates for the set   The number of elements in this set is   From our earlier discussion of the power set, we know that the total number of subsets is  . All 8 subsets are shown in the figure, organized by how many items are in each subset (for example, the subset in the upper-left corner contains 3 elements, while all subsets with 2 elements occupy the lower-right corner.) Let   denote the number of elements "chosen" to be in each of the 8 subsets of set   (where the number of elements in   is,  .)

  •   set has   elements. It is the empty set:  .
  •   sets have   element. They are  , ,and  .
  •   sets have   elements. They are  , ,and  .
  •   set has   elements. It is the set itself:  .

Example.

 
Figure 9: combinations.    

No. of ways to select 2 objects from 4 distinguishable objects without considering the order is  

Example. (Competition) There are 16 candidates for a competition. The no. of ways to select 3 candidates to enter final is  

Exercise.

1 Amy, Bob and Chris are among the   candidates. Calculate the no. of ways to select them to enter final.

1
3
6
32
96

2 Continue from the previous question. Calculate the no. of ways to select candidates other than Amy, Bob and Chris to enter final.

220
286
554
557
559



Special cases worth rememberingEdit

The formula for counting combinations has special cases that are worth remembering:

  •   (There is only one way to pick no thing and only one way to pick all   things.)
  •   (there are n ways to pick one thing or to leave one thing out)
  •   (There are the same number of ways of picking   of   things as there are of leaving out   of   things)

Ordered selection of distinguishable objects with replacementEdit

Theorem. The no. of ways for selecting   objects from   distinguishable objects in order, with replacement is  .

Proof. Consider the equivalent situation: selecting   objects from   types of objects, in which each type of the objects has unlimited stock, to be put into   ordered boxes (the same object may be selected more than once). Then, the no. of ways is  , since for each box, there are   types of objects that can be selected to be put into it.

 

Remark.

  •   can be greater than  .

Example. (Setting password) The number of ways to set a password with 6 characters, with the following rules:

(R1) numbers are allowed
(R2) alphabets are allowed, and they are case-sensitive [2]
(R3) special characters (i.e. all characters other than numbers and alphabets) are not allowed

is  

Proof. For each of the 6 positions available for the password, there are   choices of characters. Also, the characters can be repeated in more than one positions, and order matters. So, this is a case of ordered selection of distinguishable objects with replacement. Thus, the desired number is  

 

Exercise.

1 Suppose a machine can have   password guesses per second. Approximate the maximum time needed for the machine to guess the six-character password correctly using the formula

 
(correct to two decimal places)

0.00 seconds
0.15 seconds
0.16 seconds
6.16 seconds
369.72 seconds

2 Suppose the password is safe if the maximum time needed for the machine to guess the password correctly, using the same formula in the previous question, is greater than or equal to 100 years (i.e.   seconds). The minimum number of characters needed for the password (with the same rules) to be safe is

not greater than 10.
greater than 10 but not greater than 15.
greater than 10 but not greater than 20.
greater than 20 but not greater than 25.
greater than 25.




Unordered selection of distinguishable objects with replacementEdit

This type of selection is probably the most complicated.

Theorem. The number of ways for unordered selection of   objects from   distinguishable objects with replacement is  .

Proof. There are two ways to prove this.

First, consider an equivalent situation: selecting   objects from   types of objects, in which each type of the objects has unlimited stock, to be put into one box (the same object may be selected more than once). Then, we use the stars and bars notation: e.g.

*|**|*|...|*||**|*

in which  th gap created by the bars corresponds to the  th type of object (the leftmost gap made by one bar is the 1st gap, the rightmost gap made by one bar is the last gap), and the number of * in each gaps represents the number of objects selected for the corresponding type of objects. E.g., 2 * in 2nd gap represents the 2 objects are selected from the 2nd type of objects. Then, the desired no. of ways is the no. of arrangements of   * and   bars [3], which is the no. of ways to select   from   positions for * [4] (order does not matter), calculated by  .

Second, we use the notion of generating function, by encoding the selection as follows:

  • encoding the selection of each type of objects to  , by treating  ,  ,  , etc. (up to   in the   th   as selecting 0, 1, 2, etc. (up to  ) objects from the   th type respectively

Then, the desired no. is the coefficient of   in

 
[5] By binomial series theorem, the coefficient of   is
 

 

Remark.

  •   can be greater than  .
  •   is often denoted by   (read 'n h r')

Example. There are 8 distinct food or drink items, namely hamburger, egg, fries, cake, apple pie, apple juice, orange juice and coke. The number of distinct 4-item combos that must consist of distinct items (unordered selection without replacement) is  , and that without restrictions (particularly, may consist of more than one same item) (unordered selection with replacement) is  .

Exercise.

1 Calculate the no. of distinct 4-item combos that must consist of 3 food items (which may be the same) and 1 drink item.

12
35
38
105
330

2 Calculate the no. of distinct 4-item combos that contain no drinks.

5
70
126
280
330

3 Suppose each food or drink item only has 2 left in the stock. Calculate the no. of distinct 4-item combos without restrictions. (Hint:  )

19
45
183
266
330

4 Suppose each food costs $10, while each drink costs $5. Calculate the no. of distinct $20 combos without restrictions. (Hint: calculator should be used to ease the calculation)

15
30
60
121
225

5 Amy loves eating hamburger very much, so she must choose two hamburgers when she chooses the items for the 4-item combos. Calculate the no. of distinct ways for Amy to order a 4-item combo without restriction.

6
15
28
36
210



Example. (Number of integer solutions of a equation) The number of solutions to

 
in which   are nonegative integers, is  .

Proof. Consider the following stars and bars graph:

|**|*|**|*|**|**

in which the no. of stars is 10, corresponding to the number at RHS of the equation, and no. of gaps created by the bars is 7, corresponding to the number of unknowns at LHS of the equation. The no. of stars in each gap represents the (nonnegative) number assigned to that unknown. So, the number of solutions is the no. of arrangements of these stars and bars, namely  

Alternatively, we can interpret there are 10 (no. at RHS) balls selected from 7 (no. of unknowns at LHS) types of balls, labelled  , with unlimited stock, to be put into a box, in which the number of balls labelled   in the box represents the number assigned for the unknowns   respectively. Then, the no. of solutions is the no. of ways to do this, namely  .

 

Exercise.

1 Calculate the number of solutions if   are positive integers instead. (Hint: letting  , then   is a nonnegative integer)

28
56
84
560
5005

2 Calculate the number of solutions if the ' ' sign is changed to ' ' sign, i.e. the number of solutions to   in which   are nonnegative integers. (Hint: add one more positive integer unknown to LHS, so that the ' ' sign becomes ' ' sign)

3003
5005
6435
11440
19448



SummaryEdit

Selecting  [6] objects from   distinguishable objects
with replacement without replacement
ordered
 
 
unordered
 
 

Exercise. Try to prove each of the above formulas, without looking the previous subsections. After that, you can compare your proofs against the proofs in the previous subsections.


PartitionsEdit

Theorem. The number of ways to partition   distinguishable objects into   groups with group   containing exactly   objects respectively (order does not matter) is  .

Proof. There are two ways to prove this.

First, consider an equivalent situation: putting   objects selected from   distinguishable objects into box   respectively.

Then, consider the boxes one by one:

  • box 1:   objects selected from   distinguishable objects to be put into it, so no. of ways is  
  • box 2:   objects selected from   distinguishable objects [7], so no. of ways is  
  • ...
  • box  :   objects selected from   [8] to be put into it, so no. of ways is  

By multiplication principle of counting, the no. of ways for the whole process is

 

Second, we use the notion of generating function, by encoding the partition process as follows:

  • in the  th  ,   represents the  th object is put into box   respectively

Then, the desired no. of ways is the coefficient of   in  , which is  , by multinomial theorem (generalized version of binomial theorem) [9].

 

Remark.

  • partitioning objects into two groups is the same as unordered selection without replacement [10]
  •   is called the multinomial coefficient, and is denoted by  


Example. (Sequence of dice outcomes) A six-faced dice is rolled nine times. The number of distinct sequences in which 1,3 and 5 each comes up three times is .

Proof. Consider this situation as the partition of the nine (ordered) outcomes from the die to three groups, which represents 1,3 and 5 comes up in that outcome respectively. The three groups contains 3 outcomes each, so that each odd number comes up three times. It follows that the number of ways to partition the outcomes is  .

For each partition of outcomes into different groups, we obtain a unique sequence of outcomes. [11]

 

Exercise.

1 Calculate the number of distinct sequences in which 2,4 and 6 each comes up three times instead.

840
1680
3360
6720
361200

2 Suppose we throw the die 12 times instead. Calculate the number of distinct sequences in which each number comes up two times.

2520
5040
113400
369600
7484400



Example. (Arrangement of letters) The number of letter arrangements of the word PROBABILITY is  .

Proof. The word PROBABILITY has 2 letter B's and 2 letter I's. For other letters, they appear only once. So, we partition the 11 letter positions in the word into 9 groups, representing letter P,R,O,B,A,I,L,T and Y, respectively, and the group representing letter B and I contain 2 letter positions each, and other groups contain 1 letter position each.

 

Exercise.

1 Calculate the number of letter arrangements of the word EXERCISE.

28
56
3360
6720
20160

2 Calculate number of number arrangements of the number 171237615, such that the number formed is a odd number.

6720
11760
13440
23520
161280



Example. (Walking path) Consider the following diagram.

 
Suppose we are initially located at  , and that we can only walk either one cell rightward or one cell downward for each step. The number of distinct sequence of steps such that we can walk from   to   is  

Proof. First, observe that we need 6 and only 6 steps to walk from   to   [12], consisting 4 steps of walking rightward ( ) and 2 steps of walking downward ( ).

Thus, the number of distinct sequence of steps is equivalent to the number of distinct sequence of 4  's and 2  's.

A way to calculate this is to consider this as a partition problem: partition the 6 step positions into 2 groups, one of them represents   (and contains 4 step positions), another represents   (and contains 2 step positions).

Alternatively, we can consider this as combination: unordered selection of 4 step positions for   (then the remaining is for  ).

The result follows.

 

Exercise.

1 Calculate the number of distinct sequence again if we can also walk one cell leftward.

15
35
90
105
none of the above

2 Calculate the number of distinct sequence if we also need to walk through   in the walking process from   to   (Hint: consider this as walking from   to  , then from   to  ).

9
10
11
12
none of the above

3 Calculate the number of distinct sequence if we cannot walk through   in the walking process.

7
8
9
10
none of the above

4 Suppose Amy and Bob is initially located at   and   respectively. Calculate the number of distinct sequence of steps for Amy such that Amy and Bob meet at  , given that Amy can only walk 1 cell rightward or 1 cell downward for each step, while Bob can only walk 1 cell leftward or 1 cell downward for each step.

3
6
9
12
none of the above



ExercisesEdit

Lottery ticketsEdit

Example. (Pick 3 Texas Lottery) The Texas Lottery game Pick 3 is easy to play. A player must pick three numbers from zero to nine, and choose how to play them: exact order, or any order. The Pick 3 balls are drawn using three air-driven machines. These machines use compressed air to mix and select each ball.

The probability of winning while playing the exact order is

 

The probability of winning while playing any order depends on the numbers selected. If three distinct numbers are selected then the probability of winning is 3/500. If a number is repeated twice, the probability of winning is 3/1000. While, if the same number is selected three times, the probability of winning becomes 1/1000.

Example. (Mega Millions Texas Lottery) To play the Mega Millions game, a player must select five numbers from 1 to 56 in the upper white play area of the play board, and one Mega Ball number from 1 to 46 in the lower yellow play area of the play board.

All drawing equipment is stored in a secured on-site storage room. Only authorized drawings department personnel have keys to this door. Upon entry of the secured room to begin the drawing process, a lottery drawing specialist examines the security seal to determine if any unauthorized access has occurred. For each drawing, the Lotto Texas balls are mixed by four acrylic mixing paddles rotating clockwise. High speed is used for mixing and low speed for ball selection. As each ball is selected, it rolls down a chute into an official number display area. We wish to compute the probability of winning the Mega Millions Grand Prize, which require the correct selection of the five white balls plus the gold Mega ball. The probability of winning the Mega Millions Grand Prize is

 


References and footnotesEdit

  1. since we put the objects into one box, the order of putting the objects does not matter (we only know which   objects are put into the box, but do not know in what order)
  2. e.g., A   a
  3.   bars create   gaps
  4. or select   from   positions for bars, and the no. of ways for these two are the same
  5. the terms with order higher than  , e.g.  , do not affect the coefficient of  , since there is not term with negative power. So, for convenience, we can include those terms with higher orders without affecting the result.
  6. with value such that the following terms are defined
  7. the objects put into box 1 cannot be simultaneously to be put into it
  8. the objects put into boxes   cannot be simultaneously to be put into it
  9. the theorem itself is not our main focus here
  10. one group contains the objects selected, and another group contains the objects unselected
  11. E.g. if we put 1st, 2nd and 4th outcomes to the group representing 1 coming up, 5th, 7th and 9th outcomes to the group representing 3 coming up, and the remaining outcomes are put to the group representing 5 coming up, then the sequence obtained is: (1st outcome) 1,1,5,1,3,5,3,5,3 (9th outcome) in this order.
  12. this can be observed from the diagram, and the assumption that we can only walk one cell rightward or one cell downward is important