Combinatorics: How many ways are there to join unique sets of unique items to create a specified set of items?

Question

We have all possible sets of $s$ distinct colors out of $r$ distinct colors, so overall ${r \choose s}$ sets. We want to join $y$ sets so that the unified set of colors will be a specified set of $k$ colors ($s <= k <= r$). How many options do we have?

For example:

$r=5$, the colors are $\{1,2,3,4,5\}$, and $s=2$, so each initial set has 2 colors. The specified output set is $(1,2,3,4)$ with size $k=4$.

The initial sets are: $$ (1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5) $$

We want to join $y$ sets to get the specified output set.

The options for $y=2$ are:

$(1,2),(3,4)$ or

$(1,3),(2,4)$ or

$(1,4),(2,3)$

So- 3 options.

For $y=3$:

$(1,2),(3,4),(1,3)$ or

$(1,2),(3,4),(1,4)$ or

$(1,2),(3,4),(2,3)$ or

$(1,2),(3,4),(2,4)$ or

$(1,2),(1,3),(1,4)$ or

$(1,2),(1,3),(2,4)$ or

$(1,2),(1,4),(2,3)$ or

$(1,2),(2,3),(2,4)$ or

$(3,4),(1,3),(2,3)$ or

$(3,4),(1,3),(2,4)$ or

$(3,4),(1,4),(2,3)$ or

$(3,4),(1,4),(2,4)$ or

$(1,3),(1,4),(2,3)$ or

$(1,3),(1,4),(2,4)$ or

$(1,3),(2,3),(2,4)$ or

$(1,4),(2,3),(2,4)$

So- 16 options.

Of course, the number of options will be the same for any specified output set of size $k=4$.

I've been trying to get the general formula to compute the number of options. This is what I have:

For $y=1$, obviously the number of options is $1$ if $k=s$ and $0$ otherwise.

For $y=2$, I think the number of options is:

$\frac{{k \choose s}{s \choose 2s-k}}{2!}$ for $s<k<=2s$

$0$ otherwise

Explanation: ${k \choose s}$ is for choosing the first set. Then, the rest of the $k$ colors will have to appear in the second set. So we are left with $2s-k$ open spots in the second set, which should be filled with any of the $s$ colors in the first set- which explains ${s \choose 2s-k}$. Then, we should divide this by $2!$ to account for different permutations of the same choice of sets.

While I can continue with this line of thought for larger values of $y$, it becomes increasingly complicated, so I'm looking for a more elegant method.

What is the source of the problem? Actually, I'm trying to expand the inclusion-exclusion formula for the case of the union of all intersections of size $s$. So my initial-initial sets are the colors, And each set $s$ is an intersection of $s$ colors. And, following the original inclusion-exclusion formula, I have intersections of $y$ sets, where $1<=y<={r \choose s}$. So I'm trying to figure out the final coefficients of every intersection of colors.

Another way to think about this:

We have an unlimited number of balls of all colors $\{1,2,3,4,5\}$. How many ways are there to create $y$ different* buckets with $s$ unique colors each such that each color of a specified output set of colors of size $k$ will appear in at least one of the buckets?

• different buckets = a combination of colors that exists in one bucket cannot repeat itself in another bucket.

Answer 1

Notice that $r$ doesn't actually matter. We can start with just the $k$ numbers. Let's use inclusion-exclusion and define for $j \in [k]$ ($:=\{1,\dots , k\}$) the sets

$$A_j = \{ \{S_1, S_2, \dots, S_y \} | S_m\text{'s are different } s\text{-subsets of } [k]\setminus \{j\} \}.$$

We're after the quantity (here complement is taken in the space of all possible $y$-subsets of $s$-subsets of $[k]$)

$$f(k,s,y) := \left| \left(\bigcup_{j=1}^k A_j\right)^C \right|.$$

For any index-subset $J\subset \{1,\dots k\}$ the size of the intersection

$$\left| \bigcap_{j\in J} A_j \right| = {{{k-|J|\choose s}}\choose{y}}.$$

This is because we're choosing $y$ subsets of the possible ${k-|J|\choose s}$ subsets (there are $k-|J|$ numbers left when we don't allow any in the index set $J$). Hence we can group the $J$'s of size $t$ and according to inclusion-exclusion we get the formula

$$f(k,s,y) = \sum_{t=0}^k (-1)^t {k\choose t}{{{k-t\choose s}}\choose{y}}.$$

Here's a SageMath code to test with brute force:

fBrute = lambda k,s,y: sum(1 for C in Subsets(Subsets(range(k),s),y)
                           if len(set().union(*C))==k)

f = lambda k,s,y: sum((-1)^r*binomial(k,r)*binomial(binomial(k-r,s), y)
                      for r in range(k+1))

#test
print([fBrute(n, 3, 4) for n in range(8)])    
print([f(n, 3, 4) for n in range(8)])