If we can choose $k$ elements from $k$ given sets (exactly one element from each set) such that these elements are different from each other, we say these $k$ sets are "good". Let $f(n,k)$ be the number of "good" $k$ sets, with each set being a nonempty subset of $\{1, \cdots, n\}$. Note that the order of sets matters; if not considering the "good" condition, the number of $k$ sets is $(2^n-1)^k$. I'd like to ask how to calculate $f(n,k)$?

This problem is related to the Hall's marriage theorem. FYI, for some small $k$, I've found some generating functions:

$f(x,1) \ (x \geq 1): \frac{1}{(2x-1)(x-1)}$

$f(x,2) \ (x \geq 2): \frac{-10x+7}{(x-1)^2(2x-1)(4x-1)}$

  • $\begingroup$ If I understand you correctly, $f(n,1) = 2^n - 1$, right? Did you derive the generating function from this, or were you using some other technique? I guess my real question is: how is the generating function useful for this question? $\endgroup$ – antkam May 26 at 21:29
  • $\begingroup$ I just give some examples for you to check the results. $\endgroup$ – Hang Wu May 27 at 0:06

Your Answer

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

Browse other questions tagged or ask your own question.