k=0 5. This problem is about proving several identities for the Bell numbers B(n

Question

k=0 5. This problem is about proving several identities for the Bell numbers B(n) (a.) Prove that for all non-negative integer n, i-0 (b.) Let P(n) be the number of partitions of In] with no singleton block. Construct a (c.) Let Bk(n) be the number of partitions of [n] such that if i and j are in the same (d.) (Optional) Can you give a combinatorial proof to the result in part (a) using the bijection to show that B(n)- P(n) + P(n +1) block, then li -jl> k. Prove that Be(n)-B(n - k) for all n2 k. rook model in the previous problem?

Explanation / Answer

Say that a partition of [n]is good if it has no singleton blocks and bad otherwise. Bn the n-th Bell number, is the total number of partitions of [n]. If b(n) is the number of bad partitions of [n], F(n)=Bn?b(n). As usual, a little data can’t hurt. By direct enumeration of F(n) and b(n) and a table of the Bell numbers I, we should find:

n F(n) b(n) B(n)

0 0 1 1

1 0 1 1

2 1 1 2

3 1 4 5

4 4 11 15

suppose first that ? is a bad partition of [n]; then we can form a good partition of [n+1] by gathering all of the singletons of ? into a single block and putting n+1 into that block. Conversely, if ? is a good partition of [n+1], we can form a bad partition of [n]by taking the block of ? containing n+1, throwing away n+1 and converting the rest of the block to singletons. These operations are clearly inverses of each other and thus establish a bijection between bad partitions of [n] and good partitions of [n+1]

That implies that F(n+1) = b(n) for all n >= 1

This immediately gives us the recurrence F(n+1)=Bn?F(n)

=> B(n) = F(n)+F(n+1).

Related Questions

Navigate

• Browse (All)
• Browse K
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.