Keyboard: Next K > right arrow, Previous K > left arrow, Pause/Resume > P
Number of Paths in a Quincunx
We have encountered the quincunx, or Galton Board, in which balls released from the top hit
pegs in each of several rows, bouncing left or right each time. The graphic shows the number of
paths leading to different positions at the bottom.
Begin with the default setting of \(n=24\) rows.
The total number of paths that a ball could take to reach the bottom is
\(2\times 2\times \cdots \times 2 = 2^{24} = 16{,}777{,}216\) by the counting principle,
because there are \(2\) choices for each of \(24\) rows.
The number of paths that reach position \(k=0\) at the bottom left is
\(\binom{24}{0}=1\), because there must be \(0\) right deflections. The lone path reaching
\(k=0\) is shown by the red line corresponding to left deflections at every row. The
percentage of paths that reach \(k=0\) is
\((1/16{,}777{,}216)\times100\% = 6.0\times10^{-6}\%\), which is shown at the bottom
under “%”.
Now press “Next K” to see the number of paths leading to position \(k=1\)
at the bottom. The shaded area that paths must remain in to reach \(k=1\) enlarges. There
must be \(23\) left deflections and \(1\) right deflection. The lone right deflection could
occur in any of the \(24\) rows, hence there are \(\binom{24}{1}=24\) such paths. Watch the
interactive demonstration to see the ball traversing those paths. Pressing
“Pause” allows you to see the current path. The percentage of paths reaching
\(k=1\) is \((24/16{,}777{,}216)\times100\% = 1.4\times10^{-4}\%\), shown at the bottom
under “%”.
Now press “Next K” to see the \(\binom{24}{2}=276\) paths leading to
position \(k=2\) at the bottom, because the \(2\) right deflections could occur in any
\(2\) of the \(24\) rows. Such paths must remain within the shaded area, which has grown.
The percentage of paths leading to \(k=2\) at the bottom is
\((276/16{,}777{,}216)\times100\% = 0.002\%\).
Continue pressing “Next K” until you reach the middle position at
\(k=12\). Notice that the shaded area is very large and there are
\(\binom{24}{12}=2{,}704{,}156\) paths leading to it. This represents \(16.118\%\) of all
\(16{,}777{,}216\) paths.
Now press “Next K” to see that the shaded area decreases as we move from
\(k=12\) to \(k=13\). The number of paths leading to \(k=13\) at the bottom is
\(\binom{24}{13}=2{,}496{,}144\), representing \(14.878\%\) of all paths.
Continue pressing “Next K” until you reach the rightmost position,
\(k=24\), at the bottom. Notice that the shaded area and number of paths continue to
decrease after passing the midway point, \(k=12\). The number and percentage of paths
reaching \(k=24\) are \(\binom{24}{24}=1\) and \(6.0\times10^{-6}\%\), respectively.
Notice that the numbers of paths reaching \(k=0\) and \(k=24\) are the same, as are the
numbers of paths reaching \(k=1\) and \(k=23\), as are the numbers reaching \(k=2\) and
\(k=22\), and so on.
Repeat the above exercise after changing \(n\), the number of rows, and hitting
“Restart”. You will see the same patterns as above. Note that when \(k\) is odd,
there is no middle position. Instead, there are two middle positions, each producing the
largest number of paths.
Summary
The number of paths leading to position \(k\) after the ball passes through \(n\) rows
is \(\binom{n}{k}\), and the total number of paths leading to the bottom is
\(\sum_{k=0}^{n}\binom{n}{k}=2^{n}\).
The number of paths leading to position \(k\) at the bottom, \(\binom{n}{k}\), is
smallest at the extreme left (\(k=0\)) or extreme right (\(k=n\)) and becomes progressively
larger as we move toward the center.
If we place bars whose heights represent the numbers of paths reaching the different
values of \(k\) at the bottom, the graph has a bell shape.