找回密码
 欢迎注册
查看: 26577|回复: 15

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

[复制链接]
发表于 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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-5-24 10:56:14 | 显示全部楼层
左边的系数矩阵怎么确定?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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}$)

  1. A=zeros(n);
  2. for i=1:n
  3.     for j=1:n
  4.         if(j<=i)
  5.             A(i,j)=(-1)^(i-j)*nchoosek(n+1,i-j);
  6.         end
  7.     end
  8. end
复制代码

点评

nchoosek(n+1,i-j)这里是i-j?你给的公式不符合啊  发表于 2014-5-24 13:40
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-6-12 11:05:09 | 显示全部楼层
哈哈,刚看了链接,原来是马后炮,好在是独立完成的!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-6-12 14:57:29 | 显示全部楼层
链接很不错,
看了我很喜欢,
原来矩阵是那么地有价值!
https://zh.wikipedia.org/wiki/%E ... 2%E6%B1%82%E5%92%8C

建议把帖子精华
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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} \]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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\)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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\)直接证明
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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!\)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 00:07 , Processed in 0.050993 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表