A partition of a set \( A \) is a family of non-empty subsets of \( A \), such that any two distinct subsets in the family are disjoint, and the union of all subsets equals \( A \). We say that a partition of a set of integers \( B \) is separated if each subset in the partition does not contain consecutive integers. Prove that, for every positive integer \( n \), the number of partitions of the set \( \{1, 2, \dots, n\} \) is equal to the number of separated partitions of the set \( \{1, 2, \dots, n+1\} \). For example, \( \{\{1,3\}, \{2\}\} \) is a separated partition of the set \( \{1,2,3\} \). On the other hand, \( \{\{1,2\}, \{3\}\} \) is a partition of the same set, but it is not separated since \( \{1,2\} \) contains consecutive integers.
Problem
Source: Brazilian Mathematical Olympiad 2024, Level 3, Problem 2
Tags: partition, Set partition, combinatorics, induction, bijection
12.10.2024 22:31
I heard there's a easy bijection proof, I established a "pascal" like recurrence
12.10.2024 23:39
I think this follows by inducting on the fact that the number of separated partitions on $[n+1]$ with $k+1$ parts is the same as the number of partitions on $n$ with $k$ parts.
12.10.2024 23:43
Not exactly this... It's the number of separated partitions of $[n+1]$ with $k+1$ parts... But yeah, it does
13.10.2024 00:02
Let $X_{n}$ be the number of partitions of \( \{1, 2, \dots, n\} \), $Y_{n}$ the number of separated partitions of \( \{1, 2, \dots, n\} \), $A_{n,k}$ the number of subsets in the $k-th$ partition of \( \{1, 2, \dots, n\} \) and $B_{n,k}$ the number of subsets in the $k-th$ separated partition of \( \{1, 2, \dots, n\} \) (We will order the partitions starting with the one with the smallest number of subsets and ending with the one with the largest number of subsets). It's easy to check that $X_{n}= \sum \limits _{k=1}^{X_{n-1}} A_{n-1,k}+1$, because each $k-th$ partition of \( \{1, 2, \dots, n-1\} \) can have $n$ in each subset, and it can be alone, therefore each $k-th$ partition of \( \{1, 2, \dots, n-1\} \) forms $A_{n-1,k}+1$ partitions of \( \{1, 2, \dots, n\} \). Similarly we have that $Y_{n}= \sum \limits _{k=1}^{Y_{n-1}} B_{n-1,k}$. Let $P_{A, T, n}$ be the number of values $k$ such that $A_{n,k} = T$, we can easily see that $P_{A, T, n+1} = P_{A, T, n}T + P_{A, T-1, n}$. Similarly define $P_{B, T, n}$ as the number of values $k$ such that $B_{n,k} = T$, we can easily see that $P_{B, T, n+1} = P_{B,T, n}(T-1) + P_{B,T-1, n}$. Now, we will prove by induction that if $X_{n} = Y_{n+1}$ and $A_{n, k}+1= B_{n+1, k}$ for $1 \leq k \leq X_{n}$ then $X_{n+1} = Y_{n+2}$ and $A_{n+1, k}+1= B_{n+2, k}$ for $1 \leq k \leq X_{n+1}$ (The base case can be checked by hand). First, notice that $X_{n+1}= \sum \limits _{k=1}^{X_{n}} A_{n,k}+1 = \sum \limits _{k=1}^{X_{n}} B_{n+1,k} = \sum \limits _{k=1}^{Y_{n+1}} B_{n+1,k} = Y_{n+2} \implies X_{n+1} = Y_{n+2}$ Now, using the facts that $P_{B, T, n+1} = P_{B,T, n}(T-1) + P_{B,T-1, n}$, $P_{A, T, n+1} = P_{A, T, n}T + Q_{A, T-1, n}$ and $A_{n, k}+1= B_{n+1, k}$ for $1 \leq k \leq X_{n}$, we can see that $P_{B, T, n+2} = P_{B,T, n+1}(T-1) + P_{B,T-1, n+1} = P_{A, T-1, n}(T-1) + P_{A, T-2, n} = P_{A, T-1, n+1} \implies A_{n+1, k}+1= B_{n+2, k}$ for $1 \leq k \leq X_{n+1}$ so we are done.