Combinatorics Problem : Additional Clause

50 Views Asked by At

A firm needs to obtain 5 van loads of mineral. The five vans available can go to any of 11 places of mineral. The basic question is how many possible ways this can be achieved. The 11 places all have different kinds of elements in the mineral, so it is always important how many van loads come from which place. Find the number of ways in each case.

1) It does not matter which van brings which kind of mineral, and any places can be used by any number of vans. --> 15C5

Unordered selections with repetition is given by : C(n+r-1,r)

The conditions above hold, but additionally there is one of the places that may only be used at most twice due to lack of supply. (The other places are unrestricted).

I'm not sure about how to proceed with the additional clause.

1

There are 1 best solutions below

11
On BEST ANSWER

For positive integers $n,r$, by the Stars-and-Bars formula, there are exactly $$\binom{r+n-1}{n-1}$$ $n$-tuples $(x_1,...,x_n)$ of nonnegative integers satisfying $$x_1+\cdots +x_n=r$$

For $i\in\{1,...,11\}$, let $x_i$ be the number of vans which load at the $i$-th supply source.

Then for the first question we get the equation $$x_1+\cdots +x_{11}=5$$ so by the Stars-and-Bars formula, the number of solutions is $$ \binom{5+11-1}{11-1}=\binom{15}{10}=\binom{15}{5} $$ matching your answer.

For the second question, we can just subtract the count for those solutions with $x_1\ge 3$.

Writing $x_1=3+y_1$, we get the equation $$y_1+(x_2+\cdots +x_{11})=2$$ so by the Stars-and-Bars formula, the number of solutions with $x_1\ge 3$ is $$ \binom{2+11-1}{11-1}=\binom{12}{10}=\binom{12}{2} $$ hence the number of solutions with $x_1\le 2$ is $$ \binom{15}{5}-\binom{12}{2} $$