更短的组合数等幂和

tommywong

$\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}$

看似胡乱乘出来的东西是

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

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

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

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

$\displaystyle \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$

等幂和组合公式的系数！

那么，这个系数有通项吗？

tommywong

用matlab算了前10个
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

tommywong

公式可以从$xC_{x+k}^m=(k+1)C_{x+k}^{m+1}+(m-k)C_{x+k+1}^{m+1}$递推出来

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

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

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

但这样又变慢了

isee

主要是看不懂呀。

路过一下。

tommywong

未证阶段，没有东西可以懂。

之前的公式是：$\displaystyle\sum_{i=1}^n (a+(i-1)d)^m=[C_n^j]_{1 \times (m+1)}[(-1)^{i-j}C_{i-1}^{j-1}]_{(m+1) \times (m+1)}[(a+(i-1)d)^m]_{(m+1) \times 1}$

现在是：$\displaystyle \sum_{i=1}^n i^m=[C_{n+j}^{m+1}]_{1\times m}[(-1)^{i-j}C_{m+1}^{i-j}]_{m \times m}[i^m]_{m \times 1}$

$\begin{pmatrix}1 & 0 & 0 & 0 & 0 & 0\\-7 & 1 & 0 & 0 & 0 & 0\\21 & -7 & 1 & 0 & 0 & 0\\-35 & 21 & -7 & 1 & 0 & 0\\35 & -35 & 21 & -7 & 1 & 0\\-21 & 35 & -35 & 21 & -7 & 1\end{pmatrix}
\begin{pmatrix}1^6\\2^6\\3^6\\4^6\\5^6\\6^6\end{pmatrix}=
\begin{pmatrix}1\\57\\302\\302\\57\\1\end{pmatrix}$

由对称性还可使计算量减半

$\begin{pmatrix}1 & 0 & 0\\-7 & 1 & 0\\21 & -7 & 1\\21 & -7 & 1\\-7 & 1 & 0\\1 & 0 & 0\end{pmatrix}
\begin{pmatrix}1^6\\2^6\\3^6\end{pmatrix}=
\begin{pmatrix}1\\57\\302\\302\\57\\1\end{pmatrix}$

$\displaystyle \sum_{i=1}^n i^6=C_{n+1}^7+57C_{n+2}^7+302C_{n+3}^7+302C_{n+4}^7+57C_{n+5}^7+C_{n+6}^7$