I have the following question:
Let $q_0 = 1$ and, for $n \geq 1$, let $q_n$ denote the number of
equivalence relations on a set $X$ with $n$ elements. By considering
the possible equivalence classes of the $(n+1)$th element, show that$$q_{n+1} = \sum_{k=0}^n \binom{n}{k}q_{n-k}$$
As for what I've tried, I'm struggling to even know where to get started with this question. Clearly there's only $1$ way to partition the empty set, likewise there's only $1$ equivalence relation on a set with $1$ element, so I can see how the bell numbers are true, but deriving the recurrence relation, not so much.
Thanks!
Best Answer
Call $n+1$-th element $e_{n+1}$. What shall the equivalence class of $e_{n+1}$ be?
Maybe $e_{n+1}$ will be in an equivalence class all by itself. Then by definition the other $n$ objects can be divided into equivalence classes in $q_n$ ways. For consistency with later stuff we say that there are $\binom{n}{0}q_n$ ways to divide our set of $n+1$ elements into equivalence classes so that $e_{n+1}$ is a loner.
Maybe $e_{n+1}$ will have only $1$ other object in its equivalence class, there will be only one other object in the family of $e_{n+1}$. Which object? It can be chosen in $\binom{n}{1}$ ways. For every one of these ways, the remaining $n-1$ objects can be divided into equivalence classes in $q_{n-1}$ ways, giving a total of $\binom{n}{1}q_{n-1}$ divisions of our set for which the equivalence class of $e_{n+1}$ contains only one object other than $e_{n+1}$.
Maybe $e_{n+1}$ will have $2$ other objects in its equivalence class. Which $2$ objects? They can be chosen in $\binom{n}{2}$ ways. For every one of these ways, the remaining $n-2$ objects can be divided into equivalence classes in $q_{n-2}$ ways, giving a total of $\binom{n}{2}q_{n-2}$ of this type.
Maybe $e_{n+1}$ will have $3$ other objects in its equivalence class. These objects can be chosen in $\binom{n}{3}$ ways. For every one of these ways, the remaining $n-3$ can be "split up" in $q_{n-3}$ ways.
Continue. The expression of the problem basically summarizes the analysis given above.
To use the notation of the formula, the equivalence class of $e_{n+1}$ will contain $k$ objects other than $e_{n+1}$, where $k$ is any of $0$, $1$, $2$, and so on up to $n$. The number of ways to have the equivalence class of $e_{n+1}$ have $k$ objects other than $e_{n+1}$ is $\binom{n}{k}$ (choose the rest of the family) times $q_{n-k}$ (split the others into families). Now sum over all $k$.