1
$\begingroup$

Given $a_1, a_2, \cdots, a_N$ such that $a_1+a_2+\cdots +a_N = S$ for some given $S$, find the number of ways such that someone is $\geq T$.

The question is solved using Inclusion Exclusion in the following way :

$\displaystyle\sum_{i=1}^N \left((-1)^{i+1} {N \choose i} { s - iT + p-1 \choose p-1}\right)$

1) Please tell me if the question is : only one or at least one of the $a_i$'s is $\geq T$.

2) Explain me how the inclusion exclusion works here.

$\endgroup$
0
$\begingroup$

I'm understanding your question as follows, using the bins and balls: If you have N distinguishable bins, distribute S indistinguishable balls.

We first count by stars and bars.

There will be $\binom{N+S-1}{S}$ ways, before applying the restriction.

Now, applying the restriction that (at least) one bin is greater than T, we choose 1 bin from N to have T in it, and distribute the remaining N-T balls: $\binom{N}{1}\binom{(N-T)+S-1}{S}$ ways where at least one bin contains T balls.

Now we arrive at Inclusion Exclusion; How many bins may contain T balls? that is, for what k is $kT > N$? As an example, suppose k=3; that is, there may be at most two bins with at least T balls, and we want to count: first, the number of ways with at least 1 bin with T balls, then the number of ways with exactly 1 bin with T balls, and finally, let's count the number of ways with no bin higher than T.

The number of ways with at least 1, we have already found: $\binom{N}{1}\binom{(N-T)+S-1}{S}$.

The number of ways with exactly 1, subtracting out the number of ways that (exactly) two bins have at least T balls: $\binom{N}{1}\binom{(N-T)+S-1}{S} - \binom{N}{2}\binom{(N-2T)+S-1}{S}$

Finally, if we want to count the number of ways without any bins greater than T, we take PIE again:

N-(at least 1)+ (at least 2)

=$\binom{N+S-1}{S} - \binom{N}{1}\binom{(N-T)+S-1}{S} + \binom{N}{2}\binom{(N-2T)+S-1}{S}$

To answer your question more concisely: Since the iterator starts at 1, and we are subtracting out the number of ways to get two bins to T, and adding and subtracting and so on, we're counting exactly the number of ways to get to 1 bin greater than or equal to T.

$\endgroup$
  • $\begingroup$ 'If you have N distinguishable balls, distribute S indistinguishable balls'. I'm sorry what does that statement mean? $\endgroup$ – Mathejunior Dec 30 '18 at 19:44
  • $\begingroup$ Bins and balls. They originate from the canonical 12-fold way method of counting, due to Richard Stanley. Distinguishability is a way of thinking, if I permute the elements, will it change the number of ways? en.wikipedia.org/wiki/Twelvefold_way $\endgroup$ – Thor Kamphefner Dec 30 '18 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.