Exercise · ZW-STIRLING-NUMBER-OF-THE-SECOND-KIND-010 · ★★★ Advanced
Prove that \(S(n,2)=2^{n-1}-1\) for \(n\ge 1\) and check with \(n=4\). State the value of \(S(4,2)\).
Choose one option.
Show answer
- B. 7
Explanation
Each partition into two blocks corresponds to a nonempty proper subset, up to swapping the blocks, giving (2^n-2)/2=2^(n-1)-1. For n=4 this is 2^3-1=7. The value 8 forgets to subtract the trivial case, and 15 counts nonempty subsets without dividing by two.
Review the concept: Stirling number of the second kind
The Stirling number of the second kind S(n,k) counts the partitions of a set of n elements into k nonempty, indistinguishable blocks.
\[S(n,k)=kS(n-1,k)+S(n-1,k-1)\]
More practice problems: stirling number of the second kind
- ZW-STIRLING-NUMBER-OF-THE-SECOND-KIND-001 How many partitions of a 3-element set into 2 nonempty blocks exist?
- ZW-STIRLING-NUMBER-OF-THE-SECOND-KIND-002 State the value of S(n,n) for any n≥1.
- ZW-STIRLING-NUMBER-OF-THE-SECOND-KIND-003 State what the Stirling number S(n,k) counts.
- ZW-STIRLING-NUMBER-OF-THE-SECOND-KIND-004 What is the value of S(n,1) for n≥ 1?
- ZW-STIRLING-NUMBER-OF-THE-SECOND-KIND-005 What is S(n,k) when k>n?
- ZW-STIRLING-NUMBER-OF-THE-SECOND-KIND-006 Use the recurrence to compute S(4,2).
- ZW-STIRLING-NUMBER-OF-THE-SECOND-KIND-007 Compute S(4,3) using S(n,k)=kS(n-1,k)+S(n-1,k-1) and S(3,3)=1.
- ZW-STIRLING-NUMBER-OF-THE-SECOND-KIND-008 Add the values S(3,k) for k=1,2,3 and state which Bell number this is.