[Math] Total k combinations with at least one element from each set.

combinatoricselementary-set-theory

Given $n$ sets the total amount of ways k of the elements can be combined is given by $$C(|S_1|+|S_2|+…+|S_n|,k)$$

Now suppose we wanted to find the total combinations possible when at least one element from each set must be included. This imposes the following restriction $n \le k$.There are $|S|$ ways of choosing a single element out of $S$. Then through the product rule we know that if we choose only one element from each set all the possible combinations is:
$$\prod_{x=1}^{n}{|S_x|}$$

After selecting one element from each set the total amount of elements that are left to select from is given by: $$\sum_{x=1}^{n}{|S_x|-1}$$

Selecting k elements is thus given by:
$$C\left(\sum_{x=1}^{n}{|S_x|-1},k\right)$$

To ensure that each combination will have at least one element from each set we know each combination out of the remaining elements will only fit into $k – n$. Therefore total combinations of the remaining elements is:
$$C\left(\sum_{x=1}^{n}{|S_x|-1},k – n\right)$$

The next step I'm unsure of I would think that the total combinations possible is equal to:
$$\left(\prod_{x=1}^{n}{|S_x|}\right)C\left(\sum_{x=1}^{n}{|S_x|-1},k – n\right)$$

Because this is the total combination of one element from each set multiplied by the total combinations of the remaining elements, however this seems to be incorrect. If anyone could point me in the right direction that would be great! Thanks.

Best Answer

suppose that the sets are {1,2},{3,4},{6,7,8} and we want to make combinations of 4 elements. Then one way to assign one element to each one is 1,3,6 and then we additionally select 7. Another way to construct the same set is to first take 1,3,7 and then add 6. In other words this construction "constructs the some elements more than once.(what is true is that it constructs all of the combinations).

let $ W_k(f)$ be the number of combinations with at least one element from each set of a family of sets called f. Then we have that $W_k(f)=\frac{x!}{(x-k)!}{k!}- \sum_{i=1}^{2^n-1}W_k(Pi)$ where the union of all $P_i$'s is all of the proper subsets of f.