Question

You have `n` pieces of pie to be given out to `k` people, and all `n` pieces are given out. How do you find a formula for the total number of ways to give out pie?

Each person gets at least one piece of pie, but every person gets at least as many pieces of pie as the person in front of them.

Answer 1

`((n+(k-1))!)/(n! (k-1)!)` NB! Incorrect answer. I failed to read the additional information about the question. Please edit the answer.

Explanation:

Assume that the pieces of pie are indistinguishable, but that the `k` people can be distinguished. For instance, giving `2` pieces to Bob and `1` piece to Alice is not equivalent to giving `1` piece to Bob and `2` pieces to Alice.

Under these assumptions, the problem of handing out `n` pieces of pie to `k` people can be framed as a problem of putting `1`s in the spaces between `0`s in a string of `0`s.

Let `0` represent a piece of pie, and `1` represent a "wall" between boxes containing `0`s. For instance,
`1 0 0 1 0 0 0 1`
describes a situation with `2` boxes (/people) with walls placed such that person `1` gets `2` pieces of pie and person `2` gets `3` pieces. But the walls on the far ends are always fixed, so since we are only concerned with possible choices we should instead represent the situation with the end walls removed, as
`0 0 1 0 0 0`.

Now, with `5` pieces of pie and `2` persons, we have the freedom to choose at which one out of (5+1) possible positions to place the `1` wall. This can be done in
`((5+1)!)/(1!( (5 + 1) - 1)!) = ((5+1)!)/(1!( 5!)) = 6`
ways (check!).

In general, we have to distribute `(k-1)` walls over `(n + (k-1))` possible positions. This can be done in
`((n+(k-1))!)/((k-1)!(n + (k-1) - (k-1))!) = ((n+(k-1))!)/(n! (k-1)!)`
ways.

Additional note:
Using the notation `m = k-1`, the number of ways can be written succinctly as
`((n+m)!)/(n! m!)`,
which we may recognise as a multinomial distribution, that tells us how to distribute `(n+m)` items (pieces of pie and separators) into two bins containing `n` and `m` objects respectively.

Answer 2

This is a partitions problem, and so the number is found by `p(n)` if the amount of extra pie is less than the number of people. If there is more extra pie than people, then additional work would be needed.

Explanation:

This may not be the most efficient way to reach the answer, but here we go...

The first thing to realize is that we're really talking about distribution of the excess pieces of pie (the amount of pie that is up and above the minimum one piece per person). We can express this as `n-k` and for convenience I'll set the Extra as `E=n-k`.

The next thing to realize is that we can distribute `E` in a number of ways, but there are a couple of base ways to do it:

• we can give all of `E` to the last person in line
• we can give one piece of `E` to each person, up to `E` people
• we can give some number of `E` to some number of people, following the rule of each person getting at least as much as the person in front of them

Take for instance when `E=4`, we can hand out `E` (listing this out as last person first in the list), as:

`4`
`3,1`
`2,2`
`2,1,1`
`1,1,1,1`
which sums to 5 ways (I'll use `W` for Ways and so `E=4, W=5`)

It turns out that this is a simple case within the vast mathematical world of partitions - in this case, the number of ways a number can be added up to (in our current case, 4) where each number in the sum is a natural number `(x_i in NN)` (in our current case, 4, 3, 2, 1).

The notation for partitions is `p(n)`.

Rather than try to explain something I don't understand, I'll simply say that the below link has a brief explanation of what partitions are and how they work, plus list the first 30 or so (and so, for example, if `E=15, W=135`):

https://en.wikipedia.org/wiki/Partition_(number_theory)

And a video from one of my favourite youtube channels, Numberphile:

And here's a calculator:

http://www.wolframalpha.com/widgets/view.jsp?id=ca10ab4a89d9f0f6f378b89881f63ba3

I'll add that this only works if `E < k`. For instance, if you have 4 extra pieces of pie when there is only 1 person to accept them (`E=4` and `k=1), W=1` and not 5. And so there would need to be additional work done in those instances.