更短的组合数等幂和

fungarwai

交错组合求和

3.$Ftn(n,n)=0$

\(\displaystyle \sum_{k=0}^{n+1} (-1)^{n-k} C_{n+1}^k C_k^x =\sum_{k=x}^{n+1} (-1)^{n-k} C_{n+1}^k C_k^x =C_{n+1}^x \sum_{k=x}^{n+1} (-1)^{n-k} C_{n+1-x}^{k-x}\)
\(\displaystyle =C_{n+1}^x \sum_{k=0}^{n+1-x} (-1)^{n-x-k} C_{n+1-x}^k =0(x\le n)\)
\(\displaystyle (k-n-1)^n =\sum_{x=0}^n c_x C_k^x\)
\(\displaystyle Ftn(n,n)=\sum_{k=0}^n (-1)^k C_{n+1}^k (n+1-k)^n =\sum_{k=0}^{n+1} (-1)^{n-k} (k-n-1)^n =\sum_{k=0}^{n+1} (-1)^{n-k} C_{n+1}^k \sum_{x=0}^n c_x C_k^x=0\)

fungarwai

排列1,2,...,n，记N(P)为中间n-1个序的逆序总数，Pn(n,m)为这些逆序总数为m的排列总数
P=1
N(P)=0
Pn(1,0)=1
P=12,21
N(P)=0,1
Pn(2,0)=1,Pn(2,1)=1
P=123,132,213,231,312,321
N(P)=0,1,1,1,1,2
Pn(3,0)=1,Pn(3,1)=4,Pn(3,2)=1

fungarwai

逆序总数为m，把n+1放在逆序中，这个逆序变成顺序然后逆序，逆序总数不变：a>b→a<n+1>b
把n+1放在最后，逆序总数不变：ab...z<n+1
逆序总数为m-1，把n+1放在顺序中（n-1-(m-1)个），这个顺序变成顺序然后逆序，多了一个逆序：a<b→a<n+1>b
把n+1放在最前，多了一个逆序：n+1>ab...z
$a(n+1,m)=(m+1)a(n,m)+(n-m+1)a(n,m-1)$
然后就是这个数列

fungarwai

从这个模型来看，这些性质就能看出来了
\(Pn(n,m)=Pn(n,n-1-m)\)：
把\(Pn(n,m)\)个逆序总数为m的排列反转，得到\(Pn(n,m)\)个顺序总数为m的排列
顺序总数为m的排列有\(Pn(n,n-1-m)\)个
\(Pn(n,n)=0\)：
逆序总数与顺序总数的总和为n-1，不存在逆序总数为n的排列
\(\displaystyle \sum_{m=0}^{n-1} Pn(n,m)=n!\)：
逆序总数为0到n-1的值，取遍所有值的排列总数为\(n!\)

fungarwai

https://en.wikipedia.org/wiki/Eulerian_number

裏面的Worpitzky's identity跟我做的一摸一樣

$\sum_{k=1}^{N}k^n=\sum_{m=0}^{n-1}A(n,m) C_{N+1+m}^{n+1}$