The *ordered Bell numbers* (also known as *Fubini* numbers, sequence A000670 in OEIS) count the number of ordered partitions of an n-element set. Experimentally I have found the following expression for the n-th ordered Bell number $a\_n$:


$$a\_n = \sum\_{\sigma \in S\_n}\prod\_{i=1}^n \binom{i}{\sigma(i)-1}$$ where the sum ranges over all permutations of $\{1,2,\ldots,n\}$. Even though there are $n!$ terms in the sum, only $2^{n-1}$ are non-zero.


More generally, letting $S\_n^m$ denote the set of permutations of $\{1,2,\ldots,n\}$ with exactly $m$ fixed points, I believe the following is also true: the number of ordered partitions of an n-element set having exactly $m$ blocks of cardinality one is given by


$$\sum\_{\sigma \in S\_n^m}\prod\_{i=1}^n \binom{i}{\sigma(i)-1}$$. For example, for $m=0$ the formula appears to yield OEIS sequence A032032.


Is this known? Any ideas how to prove it or references to an existing proof?



Ordered Bell numbers
I would accept Sam's and lambda's comments as the answer. For the record, I'll just flesh it out a bit for the first formula.


In terms of compositions of $n$, the following is all but self-evident


$$a\_n = \sum\_{n\_1+n\_2+\ldots+n\_k=n} \binom{n}{n\_k}\binom{n-n\_k}{n\_{k-1}}\binom{n-n\_k-n\_{k-1}}{n\_{k-2}}\ldots \binom{n-n\_k-n\_{k-1}-n\_{k-2}-\ldots-n\_2}{n\_1}$$


where the sum is over all compositions of $n$. Now define a mapping from the compositions of $n$ to the permutations $\sigma$ with $\sigma(i) \le i+1$ for $1 \le i \le n$ as follows: Map composition $n\_1+n\_2+\ldots+n\_k = n$ to


\begin{align}
\sigma(n\_1) &= 1\\
\sigma(n\_1+n\_2) &= n\_1+1\\
\sigma(n\_1+n\_2+n\_3) &= n\_1+n\_2+1\\
&\ldots\\
\sigma(n\_1+n\_2+\ldots+n\_k) &= n\_1+n\_2+\ldots+n\_{k-1}+1\\
\sigma(i) &= i+1\ \text{for}\ i \not\in \{n\_1,n\_1+n\_2,\ldots,n\_1+n\_2+\ldots+n\_k\}
\end{align}


After checking this mapping is indeed a 1-1 correspondence between the compositions of $n$ and the permutations $\sigma$ with $\sigma(i) \le i+1$, we can now rewrite


\begin{align}
&\binom{n}{n\_k}\binom{n-n\_k}{n\_{k-1}}\binom{n-n\_k-n\_{k-1}}{n\_{k-2}}\ldots \binom{n-n\_k-n\_{k-1}-n\_{k-2}-\ldots-n\_2}{n\_1} = \\
&\binom{n\_1+n\_2+\ldots+n\_k}{n\_k}\binom{n\_1+n\_2+\ldots+n\_{k-1}}{n\_{k-1}}
\binom{n\_1+n\_2+\ldots+n\_{k-2}}{n\_{k-2}}\ldots \binom{n\_1}{n\_1} =\\
&\binom{n\_1+n\_2+\ldots+n\_k}{n\_1+n\_2+\ldots+n\_{k-1}}
\binom{n\_1+n\_2+\ldots+n\_{k-1}}{n\_1+n\_2+\ldots+n\_{k-2}}
\binom{n\_1+n\_2+\ldots+n\_{k-2}}{n\_1+n\_2+\ldots+n\_{k-3}}\\
&\ldots\binom{n\_1}{0}=\\
&\binom{n\_1+n\_2+\ldots+n\_k}{\sigma(n\_1+n\_2+\ldots+n\_k)-1}
\binom{n\_1+n\_2+\ldots+n\_{k-1}}{\sigma(n\_1+n\_2+\ldots+n\_{k-1})-1}\\
&\binom{n\_1+n\_2+\ldots+n\_{k-2}}{\sigma(n\_1+n\_2+\ldots+n\_{k-2})-1}
\ldots \binom{n\_1}{\sigma(n\_1)-1} = \prod\_{i=1}^n \binom{i}{\sigma(i)-1}
\end{align}


The more general formulas follow by noticing that the mapping from compositions to permutations described above is a bijection between compositions with exactly m ones and permutations with exactly m fixed points.


