Milkshakes, Beads, and Pascal’s Triangle

Note: This is the first part of the Binomial Theorem Series

Binomial Theorem I: Milkshakes, Beads, and Pascal’s Triangle

Binomial Theorem II: The Binomial Expansion

*************************************

The Milk Shake Problem

Problem 1: Issa went to a shake kiosk and want to buy a milkshake. The shake vendor told her that she can choose plain milk, or she can choose to combine any number of flavors in any way she want. There are four flavors to choose from: Apple, Banana, Chico, and Durian.

How many possible combinations can Issa create?

It is clear that Issa can choose her milk shake to have no flavor (pure milk shake), one flavor, two flavors, three flavors, or four flavors. The possible combinations are shown below.

Table 1

If we want to find the number of combinations of 2 flavors taken from 4 flavors, we have learned from Introduction to Combination post that it is the same as “the combination of 4 objects taken 2 at a time.” If we are going to use the initial letter of the names of the fruits, then the possible combinations of 4 taken 2 at a time are AB, AC, AD, BC, BD and CD or the fruits in the third column in Table 1.

We can also see that there is 1 combination with zero flavor, 4 possible combinations with one flavor, 6 possible combinations with two flavors, 4 combinations of three flavors, and 1 possible combination with four flavors. Using the combination notation, we can also see that the total number of combinations is

\displaystyle\binom 4 0 + \binom 4 1 + \binom 4 2 + \binom 4 3 + \binom 4 4 = 1 + 4 + 6 + 4 + 1 = 16

***

The Falling Beads Problem

Problem 2: Beads are dropped in a Galton Board containing hexagonal pegs as shown in Figure 1. In which of the five bins at the bottom of the board will the beads likely fall?

Figure 1

At first glance, it is quite tempting to say that the beads will equally likely fall in the five bins, but first let us examine more closely.  When a bead hits a hexagonal peg, it may either fall to the left or right of it.  There are four rows of hexagons; we will call them A, B, C and D (see Figure 2). When the bead hits the peg in row A , there are two possible paths — right or left. If it falls to the left, it will still hit the peg in Row B, and again may fall either to the left or right of it.  This goes on until it reaches row D and eventually the bins. This means that there are two possible choices in each row, and by the multiplication principle there are 2^4=16 possible paths until a bead reaches the bottom.

For the sake of brevity, let us code a bead path to the left of a hexagonal peg 0 and right 1. Consequently, the first diagram in Figure 2 will be coded as 0000, and the second diagram will be coded as 0101. This means that to be able us to enumerate all the paths, we must exhaust all the possible arrangements of 0s and 1s in groups of 4.

Figure 2

The tree diagrams in Figure 3 show all the possible paths of the bead. The green numbers mean that the bead fell to the left in the first row, to the right in the second row and to left in both the third and the fourth rows (Can you locate this path in the Galton board?). The green numbers codes the path 0100 and the orange numbers denote the path 1010. It is also clear from the diagram the 16 possible paths that we have mentioned earlier (Can you see why?).

Figure 3

The possible combinations of 1s and 0s may also be placed in a table systematically. The interpretations can be applied to the problems of milk shakes and beads. In the milkshake problem, we can consider the 0s as flavors which are not present and 1s as the flavors which are present. Hence, the number 1010 denotes an apple-chico milk shake. In the beads problem, we can replace 1 with R (right) and 0 with L (left), so the number 1010 is coded as LRLR. The details of the interpretation are shown in Table 3.

Table 2

If we only have two rows, for example, the only paths to the left is 00, to the center are 01 and 10, and to the right is 11.  Hence, we have a 1, 2, 1 path: 1 path to the left, 2 paths to the center and 1 path to the right.

If we only have three rows, it is easy to see that the number of paths can be coded as 1,3,3,1. In the milkshake problem, this means that we only have three fruits, say, Apple, Banana and Chico. If so, it means that we have 1 milkshake with no flavor, 3 milkshakes with one flavor (apple, banana, chico), 3 milkshakes with 2 flavors (apple-banna, apple-chico, banana-chico), and 1 milkshake containing all the three flavors.

The numbers 1, 4, 6, 4, 1 are the number of paths located in Row D, before the beads enter the bins. We can interpret these numbers as follows:

  • the number of paths before a bead can reach the first, second, third, fourth and fifth partition respectively;
  • the number combinations of 1s and 0s with no 1s, one 1s, two 1’s, three 1’s and four 1’s respectively;
  • the number of milk shakes with no flavors, one flavor, two flavors, three flavors and four flavors respectively.

From our interpretations above, we can place the number of paths in each path in the Galton board as shown in Figure 4.

Figure 4

It is also worthy to note that the numbers in the first diagram in Figure 4 is equivalent the number of paths or the combinations of 1s and 0s, or n fruit flavors taken k at a time .  Thus, the number in the first diagram is equivalent to the numbers in the second diagram. This answers our question above: it is more likely that the beads will fall to the center of the Galton board since there more possible paths.

Looking at Figure 4, it is clear that a number is the sum of the two numbers in the adjacent path just right above it. For example, 1 + 1 = 2, 1 + 2 = 3, 2 + 1 = 3 and so on.  If we are going to generalize using combinatorial notation, let 3 = n \choose k then, 1 = {n-1} \choose {k-1} and  2 = {n-1} \choose k. With our observation above, we can make the following conjecture:

Conjecture 1: {{n \displaystyle\choose k}} = {{n-1} \choose {k-1}}+ {{n-1} \choose {k}}

It is also evident that the numbers are symmetric. This means that we can also have the following conjecture.

Conjecture 2: {n \displaystyle\choose k} = {n \displaystyle\choose n-k}.

The reader is encouraged to show that these conjectures are true. Hint: {n \displaystyle\choose k} = \displaystyle\frac{n!}{(n-k)!k!} where k! = k(k-1)(k-2) \cdots (3)(2)(1).

The numbers, shown in Figure 4, arranged in triangular shape is called Pascal’s triangle in honor of the French mathematician Blaise Pascal.

In the next post, we are going to examine how is Pascal’s triangle connected to the Binomial Expansion.

Leave a Reply