Combinations involving distinct sets of variables

Question

Let's say I have two entirely distinct groupings of things that I wish to combine. The first set contains three items: $A, B, C$, while the second set contains five items: $V, W, X, Y, Z$. Now let's suppose that I have to combine items from these sets to form groups of 3 items, ensuring that 1 and only 1 item from the first set is present, with no repetition allowed. So $A, V, Y$ would not be considered distinct from $A, Y, V$. The basics of permutations and combinations are easy enough to grasp, and even this problem can be approached with reasonable efficiency by treating it as a combination of two elements from the second set, then multiplying the outcome by the number of distinct items in the first set. But what if we were given a range?

Say, for example, that now I say the set of 3 items needs to have 'at least' one item from the first set, but could potentially have more? If more than two distinct sets are introduced and I'm asked to come up with combinations between those, or for larger sets, it gets more complicated still.

These problems keep coming up for me lately, and I'm in need of a scaleable approach.

Answer 1

As shown in the comment, it is about applying many times simple operations.

I will work a larger example, using species and e.g.f. Suppose there are two sorts, M and W and we have 15 M and 17 W. We have to form a team of 3....5 M and say, 6....9 W.

The species formula is:

$E(M)\cdot[E_3(M)+E_4(M)+E_5(M)] \cdot [E_6(W)+E_7(W)+E_8(W)+E_9(W)]\cdot E(W)$

The first two factors means that our structure is a subset of size 3 or 4 or 5 and the last two factors means that we have a subset of size 6, or 7, or 8, or 9 for the sort W.

Then we write the e.g.f.

$exp(m).(\frac {m^3}{3!} + \frac {m^4}{4!}+ \frac {m^5}{5!}) . (\frac {w^6}{6!} + \frac {w^7}{7!}+ \frac {w^8}{8!} + \frac {w^9}{9!} ) . exp(w) $

I personally use the maple mtaylor function to truncate exp(x) to a suitable size that covers the biggest cardinals that occur.

Now we are interested in the coefficient of $\frac{m^{15}}{15!} \frac{w^{17}}{17!}$ in the above e.g.f. because it represents the answer.

Caution, working with species and e.g.f. is somehow like tightrope walking - it needs some precautions.

Answer 2

You question is probably best considered as two different types of questions.

1. If the constraint is a closed range, for example 'between 1 and 3 items from the first set", and
2. If the constraint is a half-open range. For example, 'at least 1 item from the first set.

(Suppose in both scenarios, I use the notation that the $k$-th set, $S_k$ has $n_k$ items.)

Type 1. Closed Range constraints. ('between')

The solution to these questions can best be obtained by considering each of the integer options in the range separately. That is, 'between 1 and 3 items from the first set' corresponds to

• exactly 1 set from S_1, and m-1 from S_2, which is $\binom{n_1}{1}\binom{n_2}{m-1}$, or

• exactly 2 items from S_1 and m-2 from S_2, $\binom{n_1}{2}\binom{n_2}{m-2}$, or

• exactly 3 items from S_1 and m-2 from S_2, $\binom{n_1}{3}\binom{n_2}{m-3}$.

Then the final answer is the combine (sum) of these three components. That is, $$\binom{n_1}{1}\binom{n_1}{m-1} + \binom{n_1}{2}\binom{n_1}{m-2} + \binom{n_1}{3}\binom{n_1}{m-3}$$

You should be able to see how this easily generalises.

Type 2. Half open constraints. ('at least')

The key to solving these questions is to break it up into two stages.

1. Find the number of combinations that fulfil the each of the minimum constraint(s), and then
2. Select the remaining balls freely.

That is, in your case, suppose the first set has $n_1$ items and the second set has $n_2$, and you need to select a total of $m$ items, where at least $k_1$ items are from the first set.

Then, first select the $k_1$ items from this first set. This can be done in in $\binom{n_1}{k_1}$ways.

Then select the remaining $m-k_1$ items. These can be selected without restriction and so can be from either set, so the number of combinations is $\binom{n_1+n_2}{m-k_1}$.

Then combine (multipy) these to get the total number of combinations. $$ \binom{n_1}{k_1} \binom{n_1+n_2}{m-k_1} $$

This naturally generalizes to an arbitrary number of sets. For example, suppose you need to select a total of $m$ items, where at least $k_1$ items are from the first set, $k_2$ items are from the second set and $k_3$ items are from the third set.

Then following the same method, the final answer is $$ \binom{n_1}{k_1} \binom{n_2}{k_2} \binom{n_3}{k_3} \binom{n_1+n_2+n_3}{m-k_1-k_2-k_3} $$