Restricted Compositions

Solution 1:

I found the solution in the following paper:

http://www.fq.math.ca/Scanned/14-5/abramson.pdf

P441 Formula(E) is the just the solution.

But I have another question about how to calculate the formula, when n and k is big, say n=2^24, k= 10,000, is there some approximation to the formula, the preciser, the better.

Solution 2:

You want the coefficient of $x^m$ in $$ \left(\frac{x^{k+1}-x}{x-1}\right)^n = x^n\left(\frac{x^k-1}{x-1}\right)^n. $$ The asymptotics really depend on $m,n,k$: you can start with the formula for \emp{all} "compositions", and multiply it by the probability that a composition has all its numbers bounded. In the regime where the maximum is usually less than $k$, you can approximate the probability by $1$; otherwise it gets more complicated... the formula you quote can be used here by estimating the relative magnitude of the terms, but doing it in general is probably a bit laborious. If you have some $m,n,k$ in mind, try punching the numbers and look which of the summands is significant: probably the order of magnitude is only determined by a few of them.

Solution 3:

For big $N$, $K$, an coarse approximation can be obtained by a probabilistic argument. I get

$$C(N,M,K) \approx \left( 1 - \left( 1- \frac{K}{N}\right)^M \right)^K {N-1 \choose K-1}$$

The approximation is good if the first factor (which represents the restriction) is not very small (say, $>0.1$)

Some examples: (exact and approximate values

 N   K   M      exact        approx      factor
 40  20  5    3.556E+010   3.653E+010    0.523
 40  20  8    6.610E+010   6.373E+010    0.924
 40  20  3    3.774E+008   4.770E+009    0.069