0

Assuming I don't know that $S(n,1)=1$ and $S(n,2)=2^{n-1} - 1$, how do I find these numbers? For the first one, the only explanation I can come up with is that a set of n elements can be broken into n partitions that are consisted of one element in only one way. As for the second one, I couldn't really come up with anything.

Any help and comments would be appreciated, thank you :)

Prime Mover
  • 5,005
mathematics
  • 21
  • 1
    If you see Stirling numbers of the second kind as counting ways of putting $n$ labelled items into $k$ unlabelled buckets each with at least one item, then $S(n,1)+S(n,2)$ will be $2^{n-1}$ since with two buckets you can put the first item into a bucket and then distribute the other $n-1$ items between the two buckets. Since $S(n,1)=1$ (you put everything into the initial bucket used, in which case the other bucket stays empty) you get $S(n,2)= 2^{n-1}-1$ – Henry Jun 30 '21 at 09:52
  • Thank you. But what if I want to look at only S(n,2) without using the fact that S(n,1)=1? – mathematics Jun 30 '21 at 10:14
  • Ignoring $S(n,1)=1$ might not be a sensible approach: almost like using inclusion-exclusion without using exclusion – Henry Jun 30 '21 at 10:59
  • Makes sense, I was just wondering if it was possible to ignore that fact. Thank you so much! :) – mathematics Jun 30 '21 at 11:15

0 Answers0