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$?

$\endgroup$

2 Answers 2

4
$\begingroup$

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<i\leq H$, 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<...<i_j\leq H}{\sum}|A_{i_1}\cap...\cap A_{i_j}|$$ 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}$$

$\endgroup$
3
  • $\begingroup$ Hey! Thanks a lot! I wonder if this sum shouldn't be from 1 to H, because if j=0 then we can't have (-1)! Am i missing something ? $\endgroup$ Jun 27, 2011 at 17:58
  • 1
    $\begingroup$ When $j=0$, $\binom{H-1}{j-1}=0$ by definition, and $\binom{H-1}{j}=1$. $\endgroup$ Jun 28, 2011 at 5:46
  • $\begingroup$ Ok thanks a lot, everything is now clear ! $\endgroup$ Jun 28, 2011 at 13:23
0
$\begingroup$

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

Hint 2: Combinations with replacement.

$\endgroup$
4
  • $\begingroup$ What do you mean by red herring ? Never heard about it. $\endgroup$ Jun 27, 2011 at 14:31
  • 1
    $\begingroup$ @Chris: "red herring" is an idiom refering to a statement that is used to divert attention from what is truly important, but is not important itself. Yuval is saying that the restriction about the first element doesn't matter. $\endgroup$ Jun 27, 2011 at 16:27
  • $\begingroup$ But, the restriction about the first element does matter, doesn't it? $\endgroup$ Jun 28, 2011 at 4:40
  • $\begingroup$ Sure, but you can get rid of it. $\endgroup$ Jun 28, 2011 at 4:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .