3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.