0
$\begingroup$

I know that we can distribute $n$ chocolates among $k$ children in ${n+k-1 \choose k-1}$ ways which is the stars and bars problem. But what if the chocolates should be given in increasing order? I mean the 1st boy gets less chocolates than the second boy and so on.

If $a_1+a_2+a_3+\cdots+a_k=n$, then in how many ways can we distribute $n$ such that $a_1<a_2<a_3<\cdots<a_k$?

If such a numerical problem is given, we can reduce $n$ to a smaller number and build various cases to solve it. But is there some generalized method to solve this kind of problems?

Improve this question
$\endgroup$
  • 2
    $\begingroup$ Let $x_1=a_1, x_2=a_2-a_1, x_3 = a_3-a_2,\dots, x_k=a_k-a_{k-1}$. We equivalently have that $kx_1+(k-1)x_2+(k-2)x_3+\dots+2x_{k-1}+x_k=n$, but now the only restriction is $x_1\ge 0$ and $x_i>0$ for $i=2,\dots,k$. With a little more finagling, that reduces to this previously asked question: math.stackexchange.com/questions/2053319/…. $\endgroup$ – Mike Earnest May 10 '19 at 3:55
  • $\begingroup$ $<$ (strictly increasing) or $\le$ (in order)? $\endgroup$ – Peter Taylor May 10 '19 at 12:23
  • $\begingroup$ @PeterTaylor, strictly increasing. $\endgroup$ – tomriddle99 May 10 '19 at 14:33
1
$\begingroup$

The search term you need is partitions of $n$ into $k$ distinct parts".

The easy way to calculate them is a 3-variable recursion with $n$, $k$, and an upper bound on the largest part.

As a starting point for a literature search you could take https://core.ac.uk/download/pdf/82124189.pdf

Improve this answer
$\endgroup$

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.