Guichard-Combinatorics-Graph-Theory · Problem 1.4.5

Fundamentals

Mathematics — Probability · bell-numbers-partitions

Problem

Let

A_n

be the number of partitions of

\{1, 2, \ldots, n+1\}

in which no consecutive integers are in the same part of the partition. For example, when

n = 3

these partitions are

\{\{1\},\{2\},\{3\},\{4\}\}

\{\{1\},\{2,4\},\{3\}\}

\{\{1,3\},\{2\},\{4\}\}

\{\{1,3\},\{2,4\}\}

\{\{1,4\},\{2\},\{3\}\}

, so

A_3 = 5

. Let

A(n,k)

be the number of partitions of

\{1, 2, \ldots, n+1\}

into exactly

k

parts, in which no consecutive integers are in the same part of the partition. Thus

A_n = \sum_{k=2}^{n+1} A(n,k).

Find a recurrence for

A(n,k)

and then show that

A_n = B_n