# Number of subsets containing particular elements

I was tutoring a student in discrete math and came across a simple problem: How many subsets of $\{a, b, c, d, e\}$ contain at least one vowel and one consonant? This is easy enough, but I came up with a generalization that I have been unable to solve:

Let $A_1, \dots, A_n$ be disjoint finite sets, and for each $i\in \{1,\dots, n\}$, let $c_i$ be an integer with $0<c_i\leq|A_i|$. How many subsets $S$ are there of $\cup_{i=1}^n A_i$ such that $|S| = k$ for some $k$ and $|S\cap A_i|\geq c_i$ for each $i$?

Every method I've tried has just resulted in over counting, so I'm not quite sure how to proceed.

## 1 Answer

Suppose you choose exactly $a_i$ elements from $A_i$; there are $$\binom{|A_1|}{a_1}\cdots\binom{|A_n|}{a_n}$$ ways to do this. Now sum over all choices of $a_i$ with $c_i\le a_i\le |A_i|$ for each $i$, and $\sum_i a_i=k$.

This is admittedly unsatisfying, but it's unlikely you can do better. For $n=2$, we get a sum of the form $$\sum_{a_1}\binom{|A_1|}{a_1}\binom{|A_2|}{k-a_1},$$ which can be represented in terms of hypergeometric functions, but nothing nicer.