更短的组合数等幂和

fungarwai · 发表于 2014-5-24 10:07:06

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

https://zh.wikipedia.org/wiki/%E ... 2%E6%B1%82%E5%92%8C

$\begin{pmatrix}1\end{pmatrix}
\begin{pmatrix}1^1\end{pmatrix}=
\begin{pmatrix}1\end{pmatrix}$

$\begin{pmatrix}1 & 0\\-3 & 1\end{pmatrix}
\begin{pmatrix}1^2\\2^2\end{pmatrix}=
\begin{pmatrix}1\\1\end{pmatrix}$

$\begin{pmatrix}1 & 0 & 0\\-4 & 1 & 0\\6 & -4 & 1\end{pmatrix}
\begin{pmatrix}1^3\\2^3\\3^3\end{pmatrix}=
\begin{pmatrix}1\\4\\1\end{pmatrix}$

$\begin{pmatrix}1 & 0 & 0 & 0\\-5 & 1 & 0 & 0\\10 & -5 & 1 & 0\\-10 & 10 & -5 & 1\end{pmatrix}
\begin{pmatrix}1^4\\2^4\\3^4\\4^4\end{pmatrix}=
\begin{pmatrix}1\\11\\11\\1\end{pmatrix}$

$\begin{pmatrix}1 & 0 & 0 & 0 & 0\\-6 & 1 & 0 & 0 & 0\\15 & -6 & 1 & 0 & 0\\-20 & 15 & -6 & 1 & 0\\15 & -20 & 15 & -6 & 1\end{pmatrix}
\begin{pmatrix}1^5\\2^5\\3^5\\4^5\\5^5\end{pmatrix}=
\begin{pmatrix}1\\26\\66\\26\\1\end{pmatrix}$

$\D\sum_{i=1}^n i^1=C_{n+1}^2$

$\D\sum_{i=1}^n i^2=C_{n+2}^3+C_{n+1}^3$

$\D\sum_{i=1}^n i^3=C_{n+3}^4+4C_{n+2}^4+C_{n+1}^4$

$\D\sum_{i=1}^n i^4=C_{n+4}^5+11C_{n+3}^5+11C_{n+2}^5+C_{n+1}^5$

$\D\sum_{i=1}^n i^5=C_{n+5}^6+26C_{n+4}^6+66C_{n+3}^6+26C_{n+2}^6+C_{n+1}^6$

1 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
1 4 1 0 0 0 0 0 0 0
1 11 11 1 0 0 0 0 0 0
1 26 66 26 1 0 0 0 0 0
1 57 302 302 57 1 0 0 0 0
1 120 1191 2416 1191 120 1 0 0 0
1 247 4293 15619 15619 4293 247 1 0 0
1 502 14608 88234 156190 88234 14608 502 1 0
1 1013 47840 455192 1310354 1310354 455192 47840 1013 1

kastin · 发表于 2014-5-24 10:56:14

左边的系数矩阵怎么确定？

fungarwai · 发表于 2014-5-24 12:14:18

kastin 发表于 2014-5-24 10:56
左边的系数矩阵怎么确定？

$a_{ij}=(-1)^{i-j} C_{m+1}^j$（笔误，更正为$a_{ij}=(-1)^{i-j} C_{m+1}^{i-j}$）

A=zeros(n);
for i=1:n
for j=1:n
if(j<=i)
A(i,j)=(-1)^(i-j)*nchoosek(n+1,i-j);
end
end
end

复制代码

xbtianlang · 发表于 2014-6-12 11:05:09

哈哈，刚看了链接，原来是马后炮，好在是独立完成的！

cn8888 · 发表于 2014-6-12 14:57:29

链接很不错,
看了我很喜欢,
原来矩阵是那么地有价值!
https://zh.wikipedia.org/wiki/%E ... 2%E6%B1%82%E5%92%8C

建议把帖子精华

fungarwai · 发表于 2014-12-28 12:27:02

本帖最后由 fungarwai 于 2014-12-28 21:10 编辑

最近这堆数列还涉及到两种地方

田忌赛马
n=1时只能输掉，记分布为{1}
n=2时可打平、可输掉，记分布为{1,1}
n=3时
f(x,y,z)=(x>1)+(y>2)+(z>3)
f(1,2,3)=0
f(1,3,2)=1
f(2,1,3)=1
f(2,3,1)=2
f(3,1,2)=1
f(3,2,1)=1
记分布为{1,4,1}
递推公式：$a(n+1,m)=(m+1)a(n,m)+(n-m+1)a(n,m-1)$
考虑第n+1匹马
若前n匹马能取胜m次，第n+1匹马放在能取胜的m匹马上，或第n+1匹马放在原位：$(m+1)a(n,m)$
若前n匹马能取胜m-1次，第n+1匹马放在不能取胜的m-1匹马上：$(n-m+1)a(n,m-1)$

将n个箱子编号为1,2,3,...,n，n个球编号为1,2,3,...,n
编号i的球只能放入编号1,2,3,...,i
求恰有m个空箱子的放球方法数$a(n,m)$
多项式模拟：a(a+b)(a+b+c)...
$a=a,{1}$，$a(1,0)=1$
$a(a+b)=a^2+ab,{1,1}$，$a(2,0)=1,a(2,1)=1$
$a(a+b)(a+b+c)=a^3+2a^2b+a^2c+ab^2+abc,{1,2+1+1,1}$,$a(3,0)=1,a(3,1)=4,a(3,2)=1$
递推公式：$a(n+1,m)=(m+1)a(n,m)+(n-m+1)a(n,m-1)$
n个箱子恰有m个空箱子时，第n+1个球放进m个空箱子的其中1个或者第n+1个箱子：$(m+1)a(n,m)$
n个箱子恰有m-1个空箱子时，第n+1个球放进n-(m-1)个非空箱子：$(n-m+1)a(n,m-1)$

看来可以弄一个“阶乘分布”了
\[ Ftn(n,m)=n!Ft(n,m)=\sum_{k=0}^m (-1)^k C_{n+1}^k (m+1-k)^n \]
\[\sum_{i=1}^N i^n = \sum_{m=0}^{n-1} Ftn(n,m)C_{N+1+m}^{n+1} \]

fungarwai · 发表于 2014-12-28 19:07:32

证明$\displaystyle a(n+1,m)=(m+1)a(n,m)+(n-m+1)a(n,m-1)\Rightarrow a(n,m)=\sum_{k=0}^m (-1)^k C_{n+1}^k (m+1-k)^n$
$\displaystyle a(n,m)=\sum_{k=0}^m (-1)^k C_{n+1}^k (m+1-k)^n$
$\displaystyle \Leftrightarrow a(n,m)-\sum_{k=1}^m (-1)^k C_{n+1}^k (m+1-k)^n=(m+1)^n$
$\displaystyle \Leftarrow a(n+1,m)-\sum_{k=1}^m (-1)^k C_{n+2}^k (m+1-k)^{n+1}=(m+1)[a(n,m)-\sum_{k=1}^m (-1)^k C_{n+1}^k (m+1-k)^n]$
$\displaystyle \Leftrightarrow a(n+1,m)=(m+1)a(n,m)+\sum_{k=1}^m (-1)^k C_{n+2}^k (m+1-k)^{n+1}-(m+1)\sum_{k=1}^m (-1)^k C_{n+1}^k (m+1-k)^n$
$\displaystyle \Leftarrow (n-m+1)\sum_{k=0}^{m-1} (-1)^k C_{n+1}^k (m-k)^n=\sum_{k=1}^m (-1)^k C_{n+2}^k (m+1-k)^{n+1}-(m+1)\sum_{k=1}^m (-1)^k C_{n+1}^k (m+1-k)^n$
$\displaystyle \Leftrightarrow \sum_{k=1}^m (-1)^k (m+1-k)^n [(m+1-k)C_{n+2}^k -(m+1)C_{n+1}^k+(n-m+1)C_{n+1}^{k-1}]=0$
$\displaystyle \Leftarrow (m+1-k)C_{n+2}^k-(m+1)C_{n+1}^k+(n-m+1)C_{n+1}^{k-1}=0$
$\displaystyle \Leftrightarrow (m+1)C_{n+1}^{k-1}-(n+2)C_{n+1}^{k-1}+(n-m+1)C_{n+1}^{k-1}=0$

fungarwai · 发表于 2014-12-29 09:15:26

$\displaystyle \sum_{i=1}^n i^2=\begin{pmatrix} C_n^1 & C_n^2 & C_n^3 \end{pmatrix}\begin{pmatrix} 1 & 0 & 0\\-1 & 1 & 0\\1 & -2 & 1\end{pmatrix}\begin{pmatrix} 1^2 \\ 2^2 \\ 3^2 \end{pmatrix}=\begin{pmatrix} C_n^1 & C_n^2 & C_n^3 \end{pmatrix}\begin{pmatrix} 1 \\ 3 \\ 2 \end{pmatrix}$

$\begin{pmatrix} C_n^1 & C_n^2 & C_n^3 \end{pmatrix}\begin{pmatrix} 1 & 0 & 0\\2 & 1 & 0\\1 & 1 & 1\end{pmatrix}=\begin{pmatrix} C_{n+2}^3 & C_{n+1}^3 & C_n^3 \end{pmatrix}$

$\begin{pmatrix} 1 & 0 & 0\\-2 & 1 & 0\\1 & -1 & 1\end{pmatrix}\begin{pmatrix} 1 & 0 & 0\\-1 & 1 & 0\\1 & -2 & 1\end{pmatrix}=\begin{pmatrix} 1 & 0 & 0\\-3 & 1 & 0\\3 & -3 & 1\end{pmatrix}$

$\displaystyle \sum_{i=1}^n i^2=\begin{pmatrix} C_{n+2}^3 & C_{n+1}^3 & C_n^3 \end{pmatrix}\begin{pmatrix} 1 & 0 & 0\\-3 & 1 & 0\\3 & -3 & 1\end{pmatrix}\begin{pmatrix} 1^2 \\ 2^2 \\ 3^2 \end{pmatrix}=\begin{pmatrix} C_{n+2}^3 & C_{n+1}^3 & C_n^3 \end{pmatrix}\begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix}$

从$\displaystyle \sum_{i=1}^n i^2$可看出这些矩阵的规律性，所以$\displaystyle \sum_{i=1}^N i^n = \sum_{m=0}^{n-1} Ftn(n,m)C_{N+1+m}^{n+1}$可以用$\displaystyle Ftn(n,m)=\sum_{k=0}^m (-1)^k C_{n+1}^k (m+1-k)^n$直接证明

fungarwai · 发表于 2014-12-29 09:39:16

本帖最后由 fungarwai 于 2014-12-29 10:09 编辑

总结一下，现在证明了：
#6 田忌赛马问题的递推关系
#6 箱子放球问题的递推关系
#7 从递推关系得出通解
#8 组合数等幂和的通解
还可以去证明
1.从通解得出递推关系
2.$Ftn(n,m)=Ftn(n,n-1-m)$
3.$Ftn(n,n)=0$
4.$\displaystyle \sum_{m=0}^{n-1}Ftn(n,m)=n!$

fungarwai · 发表于 2014-12-29 10:07:32

1.从通解得出递推关系
$\displaystyle Ftn(n+1,m)=(m+1)Ftn(n,m)+(n-m+1)Ftn(n,m-1)$
$\displaystyle \iff \sum_{k=0}^m (-1)^k C_{n+2}^k (m+1-k)^{n+1}=(m+1)\sum_{k=0}^m (-1)^k C_{n+1}^k (m+1-k)^n +(n-m+1)\sum_{k=0}^{m-1} (-1)^k C_{n+1}^k (m-k)^n$
$\displaystyle \iff \sum_{k=1}^m (-1)^k (m+1-k)^n [(m+1-k)C_{n+2}^k -(m+1)C_{n+1}^k+(n-m+1)C_{n+1}^{k-1}]=0$
同#7

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 更短的组合数等幂和

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

点评