Let $[n]=\{1,2,\dots,n\}$ and fix $r\in[n]$. Define the set $\mathcal{B}_{n,r}$ as the set of all set partitions of $[n]$ into disjoint non-empty blocks such that each block $B$ satisfies:

$\,\,\,\,\,\,\,\,\,\,$ either $\vert B\vert=1$, or $r\in B$, or there exist $i,j\in B$ such that $i<r<j$.

For example, there are $5$ set partitions of $\{1,2,3\}$, namely $$\{1,2,3\}; \{1\},\{2,3\}; \{2\},\{1,3\}; \{3\},\{1,2\}; \{1\}, \{2\},\{3\}.$$ If $r=1$, then we have $\vert\mathcal{B}_{3,1}\vert=4$ since $$\mathcal{B}_{3,1}=\{\{\{1,2,3\}\}, \{\{2\},\{1,3\}\}, \{\{3\},\{1,2\}\} \{\{1\},\{2\},\{3\}\}\}$$

Question. Is there any study of these sets $\mathcal{B}_{n,r}$ or their enumeration $\vert\mathcal{B}_{n,r}\vert$, directly or equivalently?


2 Answers 2


Here is an alternative approach to what is proposed by Brendan.

The key idea is to notice that the only forbidden parts in the set partitions are non-singleton subsets of $\{1,2,\dots,r-1\}$ and $\{r+1,r+2,\dots,n\}$, which enables one to employ the inclusion-exclusion principle to enumerate the set partitions without such forbidden parts.

First, we consider the associated Stirling numbers of second kind (A008299), which enumerate set partitions without singleton parts: $$S'(n,k) = \sum_{j=0}^k (-1)^j\cdot \binom{n}{j}\cdot S(n-j,k-j),$$ where $S(\cdot,\cdot)$ are the conventional Stirling numbers of second kind.

Now, we can claim that $$\begin{split}|\mathcal B_{n,r}| &= \sum_{p=0}^{r-1} \sum_{q=0}^{n-r} B_{n-p-q}\cdot \binom{r-1}{p}\cdot \binom{n-r}{q}\cdot \sum_{i=0}^{\lfloor p/2\rfloor} \sum_{j=0}^{\lfloor q/2\rfloor} (-1)^{i+j}\cdot S'(p,i)\cdot S'(q,j)\\ &=\sum_{p=0}^{r-1} \sum_{q=0}^{n-r} B_{n-p-q}\cdot \binom{r-1}{p}\cdot \binom{n-r}{q}\cdot {\bar B}_{p+1}\cdot {\bar B}_{q+1}, \end{split}$$ where $B_{m}$ are Bell numbers (A000110), ${\bar B}_{m}$ are complementary Bell numbers (A000587), $i$ and $j$ stand for the number of forbidden parts from $\{1,2,\dots,r-1\}$ and $\{r+1,r+2,\dots,n\}$ respectively, and $p$ and $q$ stand for the size of the unions of these forbidden parts.

  • $\begingroup$ Max: Thank you for the alternative approach. $\endgroup$ Feb 26, 2017 at 18:01

The number can be expressed as a sum, though it isn't too enlightening. Let $m$ be the number of cells of the third type (there exists $i,j\in B$ such that $i\lt r\lt j$). Let $k_A$ be the number of elements $\lt r$ covered by such cells and $k_B$ be the number of elements $\gt r$ covered by such cells.

The number of possibilities for the cells of the third type with parameters $m,k_A,k_B$ is $$ \binom{r-1}{k_A} \binom{n-r}{k_B} S(k_A,m)S(k_B,m) m!,$$ where $S(N,R)$ is the Stirling number of the second kind. The idea is to take a partition with $m$ cells covering the $k_A$ points, a partition with $m$ cells covering the $k_B$ points, then combine them in $m!$ ways to make $m$ cells of the third type.

Now $k_A+k_B$ points have been covered. Choose the cell containing $r$ in $2^{n-k_A-k_B-1}$ ways. Finally, cover everything else with singeltons. So the total is $$ \;\sum_{0\le k_A\le r-1} \;\sum_{0\le k_B\le n-r} \; \sum_{0\le m\le \min(k_A,k_B)} \binom{r-1}{k_A} \binom{n-r}{k_B} 2^{n-k_A-k_B-1} S(k_A,m)S(k_B,m) m!\,.$$ Maybe it can be simplified a bit; I'm not sure.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.