Every time I come home from grocery shopping and unload all the groceries, I have a bunch of empty plastic bags to take to recycling. So I take one bag and stuff the rest into it. But there is more than one way to accomplish this. For example, if I had three bags, I could stuff one into a second one, then stuff that one into the third. Or, I could just stuff two of them into the third without either one being inside the other. (The bags are indistinguishable.) So there are two ways I could stuff three bags.
How many ways could I stuff 10 bags?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
I contributed this problem to the New York Times' "Numberplay" column . My solution (reproduced here) is in the Comments section.
Suppose the stuffing had already occurred. If we looked into the outermost bag, we would see the other nine bags, in one or more smaller "stuffings." So Step 1 is to determine all the ways those nine bags could be partitioned into smaller groups. For example, they could be split into 5 and 4, or into 3, 3, 2, and 1, or into 7, 1, and 1, or even into 9 (all 9 bags stuffed together).
I won't list them all here, but there are 30 ways to partition 9 bags.
Then for each of those partitions, we must determine the number of ways they can happen. What makes this tricky is that it requires that we know how many ways to stuff 9 bags, 8 bags, 7 bags, etc. We'll assume that we do know those numbers. (The method described here can be used to find them.)
For example, in the 3, 3, 2, 1 case mentioned above, each of the 3's could be one of the two possible 3-stuffings. This can happen 3 ways ( A , A ; A , B ; B , B ) . There is only one possible 2-stuffing, and one possible 1-stuffing, so the number of ways that the 3, 3, 2, 1 partition can happen is 3 × 1 × 1 = 3 .
If you calculate this value for each of the 30 stuffings, and add the results together, you get 719.
Here is a link to a PDF I supplied them, with some more mathematical detail, and some Mathematica code I used.