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.

I 'm stuck in to this problem and I really need your help. Sorry if the title is not very informative. It is really hard for me to explain it in one sentence. I do my best in explaining it:

There exists these two natural integers:

m $\in \mathbb{N}$
$a_i \in \mathbb{N}$ for $i=1 \cdots m$

and some object with which I create a structure like this:
$$\matrix{ 1_1 & 1_2 & ... & 1_m \\ 1_1,2_1&1_2,2_2&...&1_m,2_m \\ 1_1,2_1,3_1 &1_2,2_2,3_2 & \ldots & 1_m,2_m,3_m \\ \vdots & \vdots & \vdots & \vdots \\ 1_1,2_1,...,a_1 & 1_2,2_2,...,a_2, &\ldots & 1_m,2_m,...,a_m\\ }$$

We can create new object by placing objects of different columns beside each other. All possible combinations has a general format like this:

$$(1_1),(1_2),...,(1_m)\\ (1_1),(1_2,2_2),...,(1_m)\\ ...\\ (1_1),(1_2),...,(1_m,2_m)\\ (1_1,2_1),(1_2),...,(1_m)\\ (1_1,2_1),(1_2,2_2),...,(1_m)\\ ...\\ (1_1,2_1),(1_2),...,(1_m,2_m)\\ ...\\ ...\\ (1_1,2_1,...,a_1),(1_2,2_2,...,a_2),...,(1_m,2_m,...,a_m)$$

I added the parenthesizes to make it more clear. Order is not important

In other words, I create all the combination of the objects in the first, second and ... and $a_1-th$ rows on the first column with the the first, second and ... and $a_2-th$ rows of the second column and so on. I each of these combinations there is an element from each and every column.

I think all possible combinations is $a_1 \times a_2 \times ... \times a_m$.

But, There is a restriction on number of objects in each of these combinations. let it be $$h\in \mathbb{N}$$ Number of objects in a combination can not be greater that $h$.

Now, the question is:
how many combinations do exist that satisfy this condition? (Order is not important)

Thanks for your helps.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

The problem is equivalent to the following. Let $N_k=\{1,\dots,a_k\}$ for $k=1,\dots,m$. Let $$G=\left\{\langle i_1,\dots,i_m\rangle\in\prod_{k=1}^mN_k:\sum_{k=1}^mi_k\le h\right\}\;;$$ you want to know $|G|$ in terms of $h,m$, and the numbers $a_k$ for $k=1,\dots,m$.

This is equivalent to asking for the number of solutions to the equation

$$x_1+\ldots+x_m+x_{m+1}=h-m\tag{1}$$

in non-negative integers subject to the upper bounds $x_k\le a_k-1$ for $k=1,\dots,m$: a solution $\langle x_1,\dots,x_{m+1}\rangle$ corresponds to $\langle x_1+1,\dots,x_m+1\rangle\in G$, with $x_{m+1}=h-\sum_{k=1}^mi_i$. Without the upper bounds this is a standard stars-and-bars problem, and $(1)$ has $\binom{h}m$ solutions in non-negative integers.

To account for the upper bounds, an inclusion-exclusion calculation is necessary. Replacing $x_k$ by $y_k=x_k-a_k$ and counting solutions in non-negative integers to

$$x_1+\ldots+x_{k-1}+y_k+y_{k+1}+\ldots+x_{m+1}=h-m-a_k$$

gives the number of solutions to $(1)$ that exceed the upper bound on $x_k$; by the stars-and-bars calculation that number is $\binom{h-a_k}m$. Subtracting these from $\binom{h}m$ gives the approximation $$\binom{h}m-\sum_{k=1}^m\binom{h-a_k}m\;.\tag{2}$$

This still isn’t correct, however, since it’s possible that some solutions to $(1)$ exceed more than one upper bound, and any such solution has been subtracted twice in $(2)$. If $1\le i<k\le m$, the number of solutions to $(1)$ that exceed the upper bounds on both $x_i$ and $x_k$ is $\binom{h-a_i-a_k}m$, and each of these numbers must be added back in to $(2)$ to yield the next approximation, $$\binom{h}m-\sum_{k=1}^m\binom{h-a_k}m+\sum_{1\le i<k\le m}\binom{h-a_i-a_k}m\;.$$ Continue in this fashion, alternately adding and subtracting the corrections. If we let $[m]^k$ denote the collection of $k$-element subsets of $\{1,\dots,m\}$, the final result is

$$\sum_{k=0}^m(-1)^k\sum_{S\in[m]^k}\binom{h-\sum\limits_{i\in S}a_i}m\;.\tag{3}$$

That’s a bit ugly, but if $h$ isn’t too large in comparison with the bounds $a_i$, most of the terms of $(3)$ will be $0$, since the upper number in the binomial coefficients will be non-positive for all but small values of $k$.

share|improve this answer

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.