## Partition Permutation Distribution

Partition Permutation Distribution is authored in the NetLogo modeling-and-simulation environment. The model is part of ProbLab, a curricular unit designed to enrich student understanding of the domain. The online unit package will include a suite of models, student worksheets, and a teacher guide. Below is an applet of Partition Permutation Distribution. You can interact with this model by changing the slider values and switch settings and then pressing Setup and Go to run this model under different settings. For more details, please see the model itself in the NetLogo library. Note that this model is still under development and is yet to undergo our rigorous checkout procedure.

CM ProbLab: Partition Permutation Distribution -- Addend frequencies are reciprocal to their sizes
Don't see nothin'?

Gist

In how many different ways can you add up to 20? Well, there's just [20], then there's [19 + 1], [18 + 2], [18 + 1 + 1], [17 + 3], [17 + 2 + 1], [17 + 1 + 1 + 1], etc. all the way to [1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1], and that's without caring for the partitions' order. If we figured out all the different combinations, which number would occur most often? It looks like '1' wins easily. But how ubiquitous is it? How many more '1's are there as compared to, say, 7's? This model randomly generates many partition combinations of a target-total. If enough combinations are generated, the shape of the graphs stabilizes to show the relative frequencies of the addends.

Note that the sample space out of which the simulation selects randomly is NOT the space of all possible partition combinations. If it did so, then the combination [20] would be as likely to occur as the combination [1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1]. Rather, each addend is drawn independently. The simulation chooses randomly out of the space of integers between 1 and the target-total, for instance, out of the space 1, 2, 3,..., 20. So, whereas the chance of getting a [20] is 1/20, there is a ridiculously low chance of getting the long string (the chance is 1/20!, so please don't stay up waiting for this to happen).

Note that under the default setting of the model, the addend is drawn from an ever-diminishing space (the switch DIMINISHING-SAMPLE-SPACE? is "On"). For instance, once '13' is drawn randomly from the sample space of integers between 1 and 20, the next draw is from the range of 1 through 7 (the remaining difference to 20). Under the alternative setting of this model (DIMINISHING-SAMPLE-SPACE? is set to "Off"), the model will ignore the remaining difference up to the target total. For instance, once it is at 13, going on 20, it will select from a range between 1 and 20 and will keep dumping addends that are bigger than 7. These discarded choices do not become part of the sum, but the monitors and histograms keep a record of these choices as well as those that are kept in the sum.

Riddles

• Riddle #1: If you run the experiment over many totals, with DIMINISHING-SAMPLE-SPACE? set to "On," an interesting relation emerges between the heights of adjacent columns in the "ADDENDS" histogram (see Figure, above, representing 10,000 runs up to the total of 100). The second column is 1/2 as tall as the first column, the third column is 2/3 as tall as the second column, the fourth column is 3/4 as tall as the third column, etc. In other words, the second column is 1/2 as tall as the first, the third column is 1/3 as tall as the first, the fourth column is 1/4 as tall as the first, etc. This monotonic decreasing function, 1/n, behaves differently from the histogram in Shuffle Board, where we counted 'attempts until success' ("waiting time"). Can you explain why we get a '1/n' function here? Perhaps induction could help.

Questions to Ponder
• If you run the experiment with a TARGET-TOTAL of 3, is the chance of getting [1 2] the same as the chance of getting [2 1]?

• If you run the experiment over many totals, with DIMINISHING-SAMPLE-SPACE? at "On," the #ADDENDS PER TOTAL distribution is sloped down to the right just like in the Shuffle Board histogram ATTEMPTS UNTIL SUCCESS. Is this a coincidence?

• If you run the experiment over many totals, with DIMINISHING-SAMPLE-SPACE? at "Off," the monitor MEAN #ADDENDS PER TOTAL converges on a value that is the same as the value of TARGET TOTAL. Why is that?

• If you run the experiment over many totals, with DIMINISHING-SAMPLE-SPACE at "On," the monitor MEAN #ADDENDS PER TOTAL converges on some value. What can you say about that value? How is it related to values of other variables in this model? Can you discover a function here? What can we say about the distribution of #ADDENDS PER TOTAL as seen in the histogram on the bottom right?

• [Last updated April 7, 2005]