2

I have empirical evidence to support the following conjectured identity between the derangement numbers and incomplete Bell polynomials,

$!n = \sum_{i=1}^n B_{n,i}(0,1!,2!,\dots, (n-i)!)$,

in that it holds for the first 8 or so derangement numbers. I can find several related results online, such as

$n! = \sum_{i=1}^n B_{n,i}(0!,1!,2!,\dots, (n-i)!)$

(where the factorial is used on the first element also) from Wikipedia, and

$!n = \sum_{i=1}^n i! B_{n,i}(0,1,2,\dots,(n-i))$

from a paper of Qi and Guo.

I wonder if anyone has any ideas as to whether the result I think I have is either surprising or intuitive, whether it actually holds, and if so whether there exists already a proof of it somewhere.

james.a.g
  • 73

1 Answers1

1

$$\sum_{i=1}^n B_{n,i}(0,1!,2!,\dots, (n-i)!) =B_n(0,1!,\ldots,(n-1)!)$$ where $B_n$ is the complete Bell polynomial. Also $$B_n(x_1,x_2,x_3,\ldots,x_n) =\sum_{j_1,\ldots,j_n\atop j_1+2j_2+\cdots+nj_n=n} \frac{n!}{j_1!j_2\cdots j_n!}\left(\frac{x_1}{1!}\right)^{j_1} \left(\frac{x_2}{2!}\right)^{j_2}\cdots\left(\frac{x_n}{n!}\right)^{j_n}.$$ So $$B_n(0,x_2,x_3,\ldots,x_n) =\sum_{j_2,\ldots,j_n\atop 2j_2+\cdots+nj_n=n} \frac{n!}{j_2!\cdots j_n!}\left(\frac{x_2}{2!}\right)^{j_2}\cdots\left(\frac{x_n}{n!}\right)^{j_n}$$ and so $$B_n(0,1!,2!,\ldots,(n-1)!) =\sum_{j_2,\ldots,j_n\atop 2j_2+\cdots+nj_n=n} \frac{n!}{j_2!\cdots j_n!}\left(\frac1{2}\right)^{j_2}\cdots\left(\frac1{n}\right)^{j_n}.$$ In this last sum, the summand is the number of permutations in $S_n$ with cycle structure $2^{j_2}3^{j_3}\cdots n^{j_n}$. Adding them all up gives the number of derangements.

Angina Seng
  • 158,341