2
$\begingroup$

With a given set $A=\{{0,...,N\}}$ we can choose only $H$ numbers from it (we can pick same number many times), And put them in a row. The sum of those numbers has to be some given $X$. The first element in any row can't be $0$.
For example for the set $A=\{{0,1,2,3\}}$, $X=3$ and $H=4$ we can have such variations:

1110 1011 1101 1200 1020 1002 3000 

But we can't form: $0003$ and other silimar.
How many such variations can we produce from given $X$, $N$ and $H$?

2 Answers 2

4

It's like distributing $X$ balls into $H$ cells when each cell can contain at most $N$ balls and the first cell contains at least 1 ball (the number of balls in each cell is the number in that place in the row). Then put 1 ball into the first cell. You are left with $X-1$ balls to distribute into $H$ cells, with cap of at most $N$ balls in all cells but the first, and at most $N-1$ balls in the first. Now use exclusion-inclusion principle:
Denote by $A_i$ the set of all distributions with more than $N$ balls in the $i$'th cell for $1, and more than $N-1$ balls in the first cell, for $i=1$. Then:
All distributions without limitations: $s_0=\binom{X-1+H-1}{H-1}$.
$|A_1|=\binom{X-1-N+H-1}{H-1}, \hspace{5 pt} |A_i|=\binom{X-1-(N+1)+H-1}{H-1}$ (For all $i\neq 1$). Hence $s_1=\sum|A_i|=\binom{X-1-N+H-1}{H-1}+(H-1)\binom{X-1-(N+1)+H-1}{H-1}$.
From here you continue: $s_j=\underset{1\leq i_1<... Then you have: the desired number of variations you need is: $\begin{eqnarray} e_0=\sum_{j=0}^H(-1)^js_j=\sum_{j=0}^H(-1)^j && \left[\binom{H-1}{j-1}\binom{X-1-N-(j-1)(N+1)+H-1}{H-1}\right. \nonumber \\ &+& \left.\binom{H-1}{j}\binom{X-1-j(N+1)+H-1}{H-1}\right] \nonumber \end{eqnarray}$

  • 0
    Ok thanks a lot, everything is now clear !2011-06-28
0

Hint 1: The restriction about the first element is a red herring.

Hint 2: Combinations with replacement.

  • 0
    Sure, but you can get rid of it.2011-06-28