# Solving a counting problem

1. Nov 19, 2014

we have to make n with k integers.k integers will have to be choosen from k ranges.Every range has a minimum value and a maximum value.In how many ways we can make n
according to the conditions.For example,k=4,n=10
and the ranges are :
1 1
2 2
3 3
4 4

we can make n in only one way.

Another example is

k=2,n=10
and the ranges are:
1 10
1 10
Here,the result will be 9

How can I find the number of ways by using inclusion-exclusion principle.Can anyone give me hints with better explanation?

2. Nov 24, 2014

### Greg Bernhardt

Thanks for the post! This is an automated courtesy bump. Sorry you aren't generating responses at the moment. Do you have any further information, come to any new conclusions or is it possible to reword the post?

3. Nov 25, 2014

### Staff: Mentor

What does "make n" mean here? If you take one number from each range and add them together, you get 1 + 2 + 3 + 4 = 10. I suppose this is what you mean.
Or more clearly (I think), there are 9 ways: 1 + 9, 2 + 8, 3 + 7, 4 + 6, 5 + 5, 6 + 4, 7 + 3, 8 + 2, and 9 + 1 for the 9 ways.
For some problems, the answer is zero. For example, if k = 3 and n = 10 with these ranges:
1 1
2 2
3 3
The only possible sum is 1 + 2 + 3 = 6
For a solution to exist it must be the case that $\sum_k \text{range minima} \leq n \leq \sum_k \text{range maxima}$.

4. Nov 25, 2014

### Joffan

So, if I may put some notation around this problem, we are trying to find the number of ways to specify a set of k integers $\{s_i\}$ such that each $s_i$ lies within its specified interval, $a_i \leq s_i \leq b_i$, and $\sum s_i = m$. The problem specification implies that the values are ordered by claiming 9 solutions (rather than 5) for the second case, so {9,1} is a different solution to {1,9}.

Obviously a solution is only possibly if $\sum a_i \leq m \leq \sum b_i$. If $m = \sum a_i$ or $m = \sum b_i$ there is only one set of choices for S

I also considered changing the problem a little, defining $r_i = b_i - a_i$ and $m' = m - \sum a_i$ and then one needs to find $\{t_i\}$ with $0 \leq t_i \leq r_i$ and $\sum t_i = m'$. This can be regarded as problem of distributing $m'$ identical balls into an ordered set of cups of limited size. If all the $r_i > m'$ then the limits do not come into play and the number of options is just $C^{m'+k-1}_{k-1}$. This is obviously a maximum in any case.

5. Nov 27, 2014

### Joffan

6. Nov 27, 2014

### Joffan

Here's a worked example:
Determine how many ways can you choose 3 integers, $a$, $b$, $c$, such that $a+b+c=24$ and with $6 \leq a \leq 14$, $3 \leq b \leq 10$, $1 \leq c \leq 6$

The general approach is as follows:
• Transform the ranges so that they all run zero to $r_i$ and find the modified sum $m'$
• Check for an easy answer (1 or 0)
• Calculate the number of combinations $A$ as if there were no top limits
• As above this is $C^{m'+k-1}_{k-1}$, in this case $k=3$ so $A = C^{m'+2}_{2}$
• Calculate the number of combinations, $B(x)$, that break the constraint for each single variable
• if u is the upper limit on the variable, u+1 breaks the constraint, so preallocate u+1 to that variable and count combinations for the allocation of the remaining units
• $B(x) = C^{m'-(u+1)+2}_{2}$
• Total these up
• Calculate the number of combinations that break the constraint for pairs of variables, $B(x\cup y)$
• These have been double counted above so need removing
• As above but preallocate multiple constraint-breaking numbers (if possible), $C^{m'-(u+1)-(v+1)+2}_{2}$
• Calculate the number that break the constraint for all three variables
• In principle this was triple counted and then triple removed, so needs adding back in, but there won't be any
• Combine the above results according to the inclusion-exclusion rules
• Result $= A - (B(a)+B(b)+Br(c)) + (B(a\cap b)+B(a\cap c)+B(b\cap c)) - B(a\cap b\cap c)$
$a'=a-6$
$b'=b-3$
$c'=c-1$
Total of lower limits $= 6+3+1 = 10$
Revised total $m' = 24-10 = 14$
Revised upper limits $r_i = {8,7,5}$
$\sum r_i = 20$ ∴ no easy answer
Combinations disregarding upper limits $C^{14+3-1}_{3-1}= C^{16}_2 = 120$
Combinations breaking 1-variable constraint
$B(a') = C^7_2 = 21$
$B(b') = C^8_2 = 28$
$B(c') = C^{10}_2 = 45$
Total $21+28+45=94$
Combinations breaking 2-variable constraint
$B(a'\cap b')$ not possible (9+8>14)
$B(a'\cap c)$ not possible (9+6>14)
$B(b'\cap c')=C^2_2 = 1$ (8+6=14)
Total $1$
Reconcile on inclusion-exclusion
Result $=120-94+1 = 27$

Last edited: Nov 27, 2014