4
$\begingroup$

Farmer has 7 pigs and 180 potatoes. How many combinations of distributing those 180 potatoes there are? Order does not matter. Each pig can get from zero to 180 potatoes, but all 7 pigs must get exactly 180 potatoes (no less). How to tackle this problem generally: How many combinations of K sets exist which sum up exactly to N?

I would like to apply the solution in the field of election math for calculation of probability of election reversal. Philosophizing what would happen if invalid ballots (potatoes) were valid and if they were distributed among competing candidates (farmers).

Here is something similar but without the condition that all potatoes must be eaten. https://stackoverflow.com/questions/4588429/number-of-ways-to-add-up-to-a-sum-s-with-n-numbers Moreover, it has been solved with recursive function, not an elegant formula.

$\endgroup$
  • 1
    $\begingroup$ I like the idea of translating election to example with pigs eating potatoes -- very illustrative! :) $\endgroup$ – Tim Mar 29 '16 at 7:54
  • $\begingroup$ If you give exactly 180 potatoes to pigs, then all the possible combinations will sum up to 180 -- or am I missing something..? $\endgroup$ – Tim Mar 29 '16 at 7:57
  • $\begingroup$ @Tim Each combination sums up to 180. The question is how many those combinations are! $\endgroup$ – Przemyslaw Remin Mar 29 '16 at 8:05
  • $\begingroup$ The generating function is $(1+t+t^2+\cdots+t^n+\cdots)^7=(1-t)^{-7}$. The Binomial Theorem immediately gives $(-1)^{180}\binom{-7}{180}$ as the answer. $\endgroup$ – whuber Aug 28 '16 at 16:38
6
$\begingroup$

Loooking at your problem other way around: you have $k$ pigs and you are drawing with replacement $n$ of them, giving a potato to the pig each time it is drawn. So the distribution of potatoes divided between the pigs follows a multinomial distribution with equal probabilities for each pig.

As about number of combinations of such sets, this is a stars-and-bars problem about combinations in multisets, so there are

$$ \left(\!\!\binom{n+1}{k-1}\!\!\right)=\binom{n+k-1}{n} $$

such combinations.

The classical stars-and-bars problem can be describes as following: you have $n$ stars to be divided into $k$ multisets. This can be thought as adding to the stars $k-1$ additional bars that mark boundaries of the groups and then randomly shuffling all the objects, e.g.

$$ \star \star \star \star || \star | \star \star | $$

now you just need to count the number of re-arrangements of $n+k-1$ objects.

$\endgroup$
  • $\begingroup$ Great approach! :-) $\endgroup$ – Przemyslaw Remin Mar 29 '16 at 9:04
  • $\begingroup$ What is the purpose of double parentheses on the left side of the equation? ((n+1 choose k-1)) If there would not be double parentheses then Left<>Right. $\endgroup$ – Przemyslaw Remin Mar 29 '16 at 9:28
  • $\begingroup$ @PrzemyslawRemin double parenthesis is a notation for multiset coefficient (see the links I provided). $\endgroup$ – Tim Mar 29 '16 at 9:33
  • $\begingroup$ Probably it is not discovery of America that COMBIN(n+k-1,n) = COMBIN(n+k-1,k-1) which allows to use smaller numbers. $\endgroup$ – Przemyslaw Remin Oct 11 '16 at 8:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.