# Counting Nonempty Sets with Distinct Hitting Elements

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)}$$

• 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? – antkam May 26 at 21:29
• I just give some examples for you to check the results. – Hang Wu May 27 at 0:06