Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers

up vote 4 down vote accepted

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

share|improve this answer
    
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 ? –  Chris Jun 27 '11 at 17:58
1  
When $j=0$, $\binom{H-1}{j-1}=0$ by definition, and $\binom{H-1}{j}=1$. –  Dennis Gulko Jun 28 '11 at 5:46
    
Ok thanks a lot, everything is now clear ! –  Chris Jun 28 '11 at 13:23
add comment

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

Hint 2: Combinations with replacement.

share|improve this answer
    
What do you mean by red herring ? Never heard about it. –  Chris Jun 27 '11 at 14:31
1  
@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. –  Arturo Magidin Jun 27 '11 at 16:27
    
But, the restriction about the first element does matter, doesn't it? –  Gerry Myerson Jun 28 '11 at 4:40
    
Sure, but you can get rid of it. –  Yuval Filmus Jun 28 '11 at 4:51
add comment

Your Answer

 
discard

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.