Show that the number of subsets of $S_1 \cup \dots \cup S_t$ that contain at most one element from each $S_i$ is $(a_1 + 1)(a_2 + 1) \dots (a_t + 1)$.

Question

I found this problems on Aigner's: A course in enumeration:

1.1 We are given $t$ disjoint sets $S_i$ with $|Si| = a_i$. Show that the number of subsets of $S_1 \cup \dots \cup S_t$ that contain at most one element from each $S_i$ is $(a_1 + 1)(a_2 + 1) \dots (a_t + 1)$.

And I thought about solving it using a generating function, I tried these:

• $(x)(x+x^2)(x+x^2+x^3)\dots\tag{1}$

• $(ax)(bx+bx^2)(cx+cx^2+cx^3)\dots\tag{2}$

But in $(1)$, I have no clue in which of the coefficients the answer would be. And $(2)$ isn't revealing at all to me.

Answer 1

For each $S_i$, there are $a_i + 1$ actions that we can take: we can choose exactly one of the $a_i$ elements in $S_i$, or we can choose no elements at all. Making this choice for each $S_i$ will yield a unique subset of $S_1 \cup \cdots \cup S_t$ with the desired property. Thus, there are exactly $(a_1 + 1) \cdots (a_t + 1)$ such subsets.

You could also use a generating function, although I'm not sure it provides much greater understanding here. Consider the polynomial $$P(x) =(1+a_1 x)(1+a_2 x) \cdots (1+a_t x)$$ The coefficient of $x^k$ in its expansion is the number of size $k$ subsets of $S_1 \cup \cdots \cup S_t$ with at most one element from each $S_i$. So the total number of such subsets is $P(1)$, as desired.

Answer 2

If $A$ is such a subset of $S_1 \cup \dotsb \cup S_t$, then $|A\cap S_i|$ is zero or one. If it is one, how many possibilities for $A\cap S_i$ are there? And does $S_i$'s contribution to $A$ affect $S_j$'s, for $j \ne i$?

Edit: I am suggesting the following bijection. Letting $\binom{S}{k}$ denote the set of all size-$k$ subsets of some set $S$, we have $$\{A\subseteq\bigcup_{i=1}^t S_i\text{ : }|A\cap S_i|\le 1\} \leftrightarrow \prod_{i=1}^t \left( \{\varnothing\} \cup \binom{S_i}{1}\right).$$