Closed form solution to number of combinations of n variables with percentage weights that must add to 100%

43 Views Asked by At

Is there a closed form solution for the number of combinations in which $n$ variables (e.g. $20$ or $50$) can be assigned integer percentage weights (ie $0\%, 1\%, 2\%, ... 99\% , 100\%$), under the condition that all variables sum to $100\%$?

I've been able to brute force the problem up to $n = 8$, and with extrapolation I get $4.9*10^{21}$ for $n = 20$, and $6.7*10^{39}$ for $n = 50$.

Is there a closed form solution? And if not, are the estimates correct?

1

There are 1 best solutions below

2
On BEST ANSWER

TLDR Assuming order matters (i.e. $40+60$ and $60+40$ are both counted), then

$$ {n+99 \choose n-1} $$

is such a formula.


Suppose I have $m$ star-shaped cookies and I want to divide them between $n$ ravenous children. (You are of course interested in $m = 100$.)

$$ \underbrace{\star \star \star \star \cdots \star}_{m} $$

Suppose there are $n = 3$ children and $m = 7$ cookies. Then one way I could divide the cookies would be

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

Whether the bars indicate that the first child gets $2$ cookies, the second $4$, and the third $1$. For the moment, assume each child gets at least one cookie. Then I claim the number of ways assigning cookies to children is exactly the same as the number of ways of placing bars between stars with at most one bar between any two stars. Since there are $n-1$ bars and $m-1$ places to put the bars, there are

$$ {m-1 \choose n-1} $$

ways of assigning the cookies to each child.

In your example, the "cookies" are the percentage points and the children are your $n$ variables.The only problem is that each variable can be $0$, having no cookies.

But this problem is easily solved. Imagine we add $n$ extra phantom cookies to our pile, we then count the number of ways of dividing then $n+m$ real and phantom cookies between the $n$ children,

$$ {n+m-1 \choose n-1} $$

by our formula with each child having at least one cookie. We then remove one cookie from each child. We have now distributed $m$ cookies to $n$ children with each child have $0$ or more cookies and we're done. Thus, substituting $m = 100$, the formula is

$$ {n+99 \choose n-1} $$