Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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.

share|cite|improve this answer
up vote 3 down vote accepted

I found the solution in the following paper:

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.

share|cite|improve this answer

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 
share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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