Calculating the Number of Ways to Make n with k Integers from Given Ranges

[Awlad Hossain]

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 9How can I find the number of ways by using inclusion-exclusion principle.Can anyone give me hints with better explanation?

 

[Mark44]

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.

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.

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

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.

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

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

 

[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.

 

[Joffan]

Here is a good exploration of using the inclusion-exclusion principle in the hard cases remaining where the $r_i$ defined above do not fall into one of the easy cases.

 

[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)$

Spoiler: Transform & check

$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

Spoiler: Solve combinations

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$