$n!$ as a sum of $n$ positive integers

116 Views Asked by At

We partition $(n-1)!$ into $n-1$ parts in the following way. Consider a permutation $(a_1,a_2,\ldots,a_n)$ of $(1,2,\ldots,n)$. We say that $a_k$ dominates its predecessors if $a_j<a_k$ for $j<k$. Of course, the leftmost number, $a_1$, is trivially dominant. Note that there are exactly $(n-1)!$ ways in which $a_n$ can be dominant, which happens precisely when $a_n=n$.

Observe that, since the first (leftmost) dominant number is always $a_1$, there is no way that $a_n$ can be the first dominant number. Also observe that $a_n$ can be the $n$-th (rightmost) dominant number in exactly one way, namely iff $(a_1,a_2,\ldots,a_n)=(1,2,\ldots,n)$. We define $f_n(j),\ j=1,2,\ldots, n,$ to be the number of ways in which $a_n$ can be the $j$-th dominant number. I find

$f_n(1)=0,\\ f_n(2)=(n-2)!,\\ f_n(3)=\sum_{k=1}^{n-2}\frac{(n-2)!}{k},\\ f_n(n-1)=\frac{(n-1)(n-2)}{2},\\ f_n(n)=1.$

We have $$\sum_{j=2}^{n}f_n(j)=(n-1)!,$$ which expresses $(n-1)!$ as a sum of $n-1$ terms, as promised. Is there a formula for $f_n$?

1

There are 1 best solutions below

0
On BEST ANSWER

To find $f_n(j)$, let $a_1, a_{k_2},\ldots, a_{k_{j-1}},a_n$ be the $j$ dominant numbers, where $1<k_2<\cdots <k_{j-1}<n$. It must be $a_n=n$ and $a_{k_{j-1}}=n-1.$ Now choose the predecessors of $a_{k_{j-1}}$ (i.e., the numbers in positions $1,2,\ldots, k_{j-1}-1$) and put the largest one at position $k_{j-2}$; this can be done in ${n-2 \choose k_{j-1}-1}$ ways. Next choose the predecessors of $a_{k_{j-2}}$ (out of the remaining predecessors of $a_{k_{j-1}}$) and place the largest one at position $k_{j-3}$; this can be done in ${k_{j-1}-2 \choose k_{j-2}-1}$ ways. Continue in this way until the predecessors of $a_{k_2}$ have been chosen and the largest one of them has been placed at position $1$. Then arrange the $k_2-2$ remaining predecessors of $a_{k_2}$, then the $k_3-k_2-1$ remaining predecessors of $a_{k_3}$, and so on, until, finally, the remaining $n-k_{j-1}-1$ predecessors of $a_n$ have been arranged. This gives $$\begin{split} f_n(j)&=\sum_{1<k_2<\cdots<k_{j-1}<n}{n-2 \choose k_{j-1}-1}{k_{j-1}-2 \choose k_{j-2}-1}\cdots {k_3-2 \choose k_2-1}\\ & \qquad \qquad(k_2-2)!(k_3-k_2-1)!\cdots (k_{j-1}-k_{j-2}-1)!(n-k_{j-1}-1)! \\ &=\sum_{1<k_2<\cdots<k_{j-1}<n}\frac{(n-2)!}{(k_2-1)(k_3-1)\cdots (k_{j-1}-1)}. \end{split}$$ Hence $$\begin{split} (n-1)!&=\sum_{j=2}^nf(j)=\sum_{j=1}^{n-1}f(j+1)\\ &=\sum_{j=1}^{n-1}\sum_{1<k_2<\cdots<k_{j}<n}\frac{(n-2)!}{(k_2-1)(k_3-1)\cdots (k_j-1)}. \end{split}$$