12
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 10
    $\begingroup$ The $2^{n-1}$ nonzero terms in the sum corresponds to subsets of $[n-1]$ (choosing the $i$ with $\sigma(i)=i+1$, there is a unique way to fill in the other $\sigma(j)\leq j$), and in turn these subsets of $[n-1]$ correspond to the compositions of $n$ in the usual way. I would guess that for a given permutation, that product of binomial weights you have corresponds to the number of ordered set partitions with that composition as its block sizes (this should be a multinomial coefficient). $\endgroup$
    – Sam Hopkins
    Jan 30 '21 at 1:52
  • 5
    $\begingroup$ Adding to that, there is a unique element with $\sigma(j) \le j$ in each cycle of $\sigma$, and the parts of the composition corresponding to the set of such elements are just the cycle lengths in some order. So the second formula (and further generalizations) follow the same way. $\endgroup$
    – lambda
    Jan 30 '21 at 6:03
  • 3
    $\begingroup$ The formula can be stated as matrix permanent: $$\sum_{\sigma \in S_n}\prod_{i=1}^n \binom{i}{\sigma(i)-1} = \mathrm{per} \left[ \binom{i}{j-1}\right]_{i,j=1}^n.$$ $\endgroup$
    – Max Alekseyev
    Jan 30 '21 at 16:45
4
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • 2
    $\begingroup$ By the way, it would be interesting to extend this formula to "other types" somehow. The ordered Bell numbers count all the faces of all dimensions of the Type A Coxeter arrangement (a.k.a. braid arrangement), so this has a natural analog in other types. Not clear what the special set of $2^{n-1}$ elements of $S_n$, and those weights, correspond to in other types, however. $\endgroup$
    – Sam Hopkins
    Jan 30 '21 at 15:31
  • 1
    $\begingroup$ $a_n = \sum_{\sigma \in S_n^{even}}\prod_{i=1}^n \binom{i}{\sigma(i)-1}$ where the sum is restricted to the even permutations seems to yield OEIS sequence A032109, which is the Stirling transform of A001710, the sequence |A_n|, where A_n = alternating group of $n$ letters. $\endgroup$
    – Jose A Rodriguez
    Jan 31 '21 at 13:33
  • 1
    $\begingroup$ @JoseARodriguez: And the sum restricted to odd permutations gives A032109 decreased by 1. So, $$a_n = 2\cdot \texttt{A032109}(n) - 1.$$ $\endgroup$
    – Max Alekseyev
    Jan 31 '21 at 16:53
  • 1
    $\begingroup$ @JoseARodriguez: The connection between A000670 and A032109 trivially follows from their exponential generating functions. $\endgroup$
    – Max Alekseyev
    Jan 31 '21 at 18:11
  • 1
    $\begingroup$ @JoseARodriguez: See math.stackexchange.com/q/2509795 for $k=0$ and $x=1$. $\endgroup$
    – Max Alekseyev
    Jan 31 '21 at 19:25

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.