# Restricted Compositions

Number Composition studies the number ways of compositing a number.

I wanna know the number of compositions of $m$ with $n$ parts with the size of the max part equal to or less than $k$.

Is there a closed form for this problem?

-
Are the parts ordered or not? – Yuval Filmus Feb 12 '11 at 7:38
The parts are ordered, if not it is called number partition. – Fan Zhang Feb 12 '11 at 8:25

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.

-

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.

-

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

-