Ordered Bell numbers 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?
 A: 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.
