Unconquerable Word Problem

[just1question]

After a trip around the neighborhood on Halloween, we have lots of jelly beans. There are many ways of distributing the jelly beans among us. For example, if we have four beans, we could give one apiece to four people (we can denote this by 1,1,1,1); we could give two to one person and one to two others (2,1,1); we could give two apiece to two people (2,2); we could give three to one person and one to another (3,1); or we could give all four to one person (4). That makes a total of five different ways to share the jelly beans.
We have 100 jelly beans to distribute.

a.) How many ways can this be done?
b.) How many ways can this be done if all the groups are of different sizes (for example, a group of 30 people, or a group of 75 people)?
c.) How many ways can this be done if all groups must contain an odd number of beans?

 

[tkhunny]

The EASY part is counting all the ways that they can be distributed, without regard to whether you already counted a particular way.

Ponder C(n), where C(n) is the number of ways n objects can be distributed

Let's say C(1) = 1 - The number of ways 1 item can be distributed.
Then, C(2) can be constructed in two steps. Add a "1" to each of the elements of C(1) and than add 2,0
So, C(2) = C(1) + 1 = 2
Now for C(3). This time, it takes three steps. Add a '1' to each element of C(2), add a '2' to each element of C(1), and then add 3,0,0
So, C(3) = C(1) + C(2) + 1 = 1 + 2 + 1 = 4
Let's guess that C(4) = C(3) + C(2) + C(1) + 1 = 8

We see a theme, which can be proven without much trouble \(\displaystyle C(n) = 2^{n-1}\)

Unfortunately, this disregards that there may be duplicates.

From these C(n), it is not too hard to count a few duplicates:

For n = 3, {0, 1, 2} occurs twice, so we fall 1 short of C(3)
For n = 4, {0, 1, 1, 2} occurs thrice and {0, 0, 1, 3} occurs twice, so we fall 3 short of C(4)
It's looking temptingly simple, isn't it? Guessing, perhaps we'll fall 6 short of C(5)? 6 would be the next triangular number!
For n = 5, {0, 1, 1, 1, 2} gets 4, Looking good. {0, 0, 1, 2, 2} gets 3. Excellent. {0, 0, 1, 1, 3} gets 3 - DRAT!!! That blows the theory. Further, {0, 0, 0, 2, 3} and {0, 0, 0, 1, 4} each get 2. We fall 9 short of C(5).
Similarly, we fall 21 short of C(6)

We have so far, 1, 2, 3 , 5, 7, 11.
The only thing we still have going for us is the first differences. Through n = 6, we have 1, 1, 2, 2, 4. Well, if n = 7 adds 4 more (up to 15 total), we may have something.

Well, that's how fun exploration is. Keep at it. You'll stumble on something.