3
$\begingroup$

Fix positive integers $n$ and $k$. Find the number of $k$-tuples $(S_1, S_2,\dots, S_k)$ of subsets $S_i$ of $\{1, 2, \dots , n\}$ with the $S_i$’s pairwise disjoint.

I am looking for a way to find this combinatorially, instead of generating functions/recursion. The balls and boxes idea seems like the way to go, but the fact that every box needs one ball except the "unused numbers" box is causing me difficulty.

$\endgroup$
  • 1
    $\begingroup$ What do you mean, "every box needs one ball"? Are the subsets $S_i$ required to be nonempty? Where does it say that in the problem you quoted? $\endgroup$ – bof Feb 3 '16 at 5:30
  • 2
    $\begingroup$ If the sets $S_i$ are required to be nonempty, then you want to add two numbers: the number of surjections from $\{1,\dots,n\}$ to $\{1,\dots,k\}$ (no "unused numbers"), and the number of surjections from $\{1,\dots,n\}$ to $\{1,\dots,k+1\}$ (one or more "unused numbers"). To count the surjections, use either Stirling numbers (of the "second kind"), or the in-and-out formula ("Principal of Inclusion and Exclusion"). $\endgroup$ – bof Feb 3 '16 at 5:37
  • $\begingroup$ I thought they couldnt be empty because they had to be pairwise disjoint, but that may not actually be the case, are two empty sets considered disjoint? $\endgroup$ – user310322 Feb 3 '16 at 5:54
  • 1
    $\begingroup$ There is only one empty set, and it is disjoint from everything, including itself. I would interpret the quoted problem as allowing $S_1=S_2=\cdots=S_k=\emptyset$ as a possibility. $\endgroup$ – bof Feb 3 '16 at 6:00
3
$\begingroup$

We count the number of $(k+1)$-tuples of pairwise disjoint subsets whose union is all of $\{1,\dots,n\}$. This is the number of functions from the set $\{1,\dots,n\}$ to the set $\{1,\dots,k,k+1\}$. There are $(k+1)^n$ such functions.

The "extra box" $k+1$ gets the elements of $\{1,\dots,n\}$ that are not in any of the $S_i$.

$\endgroup$
  • $\begingroup$ The OP's last sentence seems to imply that the subsets $S_i$ have to be nonempty, although the formal problem statement in the first paragraph does dot seem to make that requirement. I'm trying to get the OP to clarify the question. $\endgroup$ – bof Feb 3 '16 at 5:40

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.