Further Study of the Shape of the Numbers and More Calculation Formulas
Abstract: The core of Shape of numbers is formal calculation, which has three forms. This paper proves the equivalence of these forms and extends the formula to the general case. Some properties of the coefficients are summarized and some new conclusions are drawn. The coefficient matrix is studied and the corresponding results are obtained. Using the formal method, the calculation formula of ∑n-0N-1Πi-1M (Ki+Diqn) is obtained. The key is to use the Gaussian coefficient, which shows its new scope of application. Using the derivation in this paper, the calculation formula of ∑n-0N-1qn(MN+M) is obtained. By introducing a new number: AqM=∑k-0Mqn(1-q)M-kqKS2(M,k)k, this paper obtains the formula of ∑n-0N-1qnnM, at the same time, find the other three expressions of AqM.

1. Introduction

Peng, J. has introduced Shape of numbers and three forms of calculation in [1] [2] [3] [4] [5]:

${K}_{i},{D}_{i}\in \text{CommutativeRing}$.

M series: $Seri{e}_{i}=\left\{{K}_{i},{K}_{i}+{D}_{i},{K}_{i}+2{D}_{i},\cdots ,{K}_{i}+\left(N-1\right){D}_{i}\right\}$, $i\in \left[1,M\right]$.

Use $PS=\left[{K}_{1}:{D}_{1},\cdots ,{K}_{M}:{D}_{M}\right]$ to represent thems.

$\left[{K}_{1}:1,\cdots ,{K}_{M}:1\right]$ is abbreviated as $\left[{K}_{1},\cdots ,{K}_{M}\right]$.

$\text{Anitem}=\left({I}_{1},{I}_{2},\cdots ,{I}_{M}\right)$, ${I}_{i}$ comes from Seriei. A product = ${\prod }_{i=1}^{M}{I}_{i}$.

Use $PT=\left[{T}_{1}=1,{T}_{2},\cdots ,{T}_{M}\right]$ to indicate the item’s range:

${I}_{i}={K}_{i}+{a}_{i}{D}_{i},\left\{\begin{array}{l}{T}_{i+1}-{T}_{i}=1,\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{means}\text{\hspace{0.17em}}{a}_{i}={a}_{i+1},\text{\hspace{0.17em}}\text{continuity}\\ {T}_{i+1}-{T}_{i}=2,\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{means}\text{\hspace{0.17em}}{a}_{i}\le {a}_{i+1},\text{\hspace{0.17em}}\text{discontinuity}.\end{array}$

PS and PT are defined as Shape of numbers, they indicate some items.

$SUM\left(N,PS,PT\right)=\underset{\text{allitems}}{\sum }\text{product}$.

PB(PT) = count of discontinuity in PT, PM(PT) = count of factors in PT.

By default, the following uses:

$PS=\left[{K}_{1}:{D}_{1},\cdots ,{K}_{M}:{D}_{M}\right]$, $PT=\left[{T}_{1},\cdots ,{T}_{M}\right]$.

H(q) is short for H(PS, PT, q), SUM(N) is short for SUM(N, PS, PT).

The Form: $\left({T}_{1}+{K}_{1}\right)\left({T}_{2}+{K}_{2}\right)\cdots \left({T}_{M}+{K}_{M}\right)=\sum {\prod }_{i=1}^{M}{X}_{M}$, ${X}_{i}={T}_{i}$ or ${K}_{i}$.

Don’t swap the factors. Each $\prod {X}_{i}$ corresponds to one expression in SUM(…).

$X\left(T\right)=\text{countof}\left\{{X}_{1},\cdots ,{X}_{M}\right\}\in \left\{{T}_{1},\cdots ,{T}_{M}\right\}$,

${X}_{K-1}=\text{countof}\left\{{X}_{1},\cdots ,{X}_{i-1}\right\}\in \left\{{K}_{1},\cdots ,{K}_{M}\right\}$.

1.1) $q=X\left(T\right)$, $PM=PM\left(PT\right)$,

$\begin{array}{l}SUM\left(N\right)=\\ \stackrel{{\text{Form}}_{1}}{\to }{\sum }_{q=0}^{PM}{H}_{1}\left(q\right)\left(\begin{array}{c}N+{T}_{M}-PM\\ N-1-q\end{array}\right),{B}_{i}=\left\{\begin{array}{l}\left({T}_{i}-{X}_{K-1}\right){D}_{i};{X}_{i}={T}_{i}\\ {K}_{i}+{X}_{T-1}{D}_{i};{X}_{i}={K}_{i}\end{array}\\ \stackrel{{\text{Form}}_{2}}{\to }{\sum }_{q=0}^{PM}{H}_{2}\left(q\right)\left(\begin{array}{c}N+{T}_{M}-PM+q\\ N-1\end{array}\right),{B}_{i}=\left\{\begin{array}{l}\left({T}_{i}-{X}_{K-1}\right){D}_{i};{X}_{i}={T}_{i}\\ {K}_{i}+\left({X}_{K-1}-{T}_{i}\right){D}_{i};{X}_{i}={K}_{i}\end{array}\\ \stackrel{{\text{Form}}_{3}}{\to }{\sum }_{q=0}^{PM}{H}_{3}\left(q\right)\left(\begin{array}{c}N+{T}_{M}-q\\ N-1-q\end{array}\right),{B}_{i}=\left\{\begin{array}{l}-{K}_{i}+\left({T}_{i}-{X}_{T-1}\right){D}_{i};{X}_{i}={T}_{i}\\ {K}_{i}+{X}_{T-1}{D}_{i};{X}_{i}={K}_{i}\end{array}\end{array}$

$H\left(q\right)=H\left(PS,PT,q\right)={\sum }_{\text{all}\text{\hspace{0.17em}}\text{of}\text{\hspace{0.17em}}\text{the}\text{\hspace{0.17em}}\prod {X}_{i}\text{\hspace{0.17em}}\text{with}\text{\hspace{0.17em}}X\left(T\right)=q}{\prod }_{i=1}^{M}{B}_{i}$.

In particular:

1.2) $SUM\left(N,\left[1,2,\cdots ,M\right],\left[1,3,\cdots ,2M-1\right]\right)={S}_{1}\left(N+M,N\right)$, unsigned Stirling number.

1.3) $SUM\left(N,\left[1,1,\cdots ,1\right],\left[1,3,\cdots ,2M-1\right]\right)={S}_{2}\left(N+M,N\right)$, Stirling number of the second kind.

1.4) $SUM\left(N,\left[1,1,\cdots ,1\right],\left[1,2,\cdots ,M\right]\right)={1}^{M}+{2}^{M}+\cdots +{N}^{M}$.

2. Equivalence of Three Forms

The following change Ti’s domain to $ℤ$ and ${T}_{i+1}-{T}_{i}$ is not restricted.

$PS1=\left[PS,{K}_{M+1}:{D}_{M+1}\right]$, $PT1=\left[PT,{T}_{M+1}\right]$, use $H\left(PS1,q\right)=H\left(PS1,PT1,q\right)$.

2.0) Recurrence relation

${H}_{1}\left(PS1,q\right)={H}_{1}\left(q-1\right)\left({T}_{M+1}-\left[M-\left(q-1\right)\right]\right){D}_{M+1}+{H}_{1}\left(q\right)\left({K}_{M+1}+q{D}_{M+1}\right)$

$\begin{array}{l}{H}_{2}\left(PS1,q\right)={H}_{2}\left(q-1\right)\left({T}_{M+1}-\left[M-\left(q-1\right)\right]\right){D}_{M+1}\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}+{H}_{2}\left(q\right)\left({K}_{M+1}+\left[-{T}_{M+1}+M-q\right]{D}_{M+1}\right)\end{array}$

$\begin{array}{c}{H}_{3}\left(PS1,q\right)={H}_{3}\left(q-1\right)\left(-{K}_{M+1}+\left[{T}_{M+1}-\left(q-1\right)\right]{D}_{M+1}\right)\\ \text{\hspace{0.17em}}\text{ }+{H}_{3}\left(q\right)\left({K}_{M+1}+q{D}_{M+1}\right)\end{array}$

2.1) ① ${H}_{1}\left(q\right)={\sum }_{x=q}^{M}{H}_{2}\left(x\right)\left(\begin{array}{c}x\\ q\end{array}\right)={\sum }_{x=0}^{q}{H}_{3}\left(x\right)\left(\begin{array}{c}M-x\\ M-q\end{array}\right)$

${H}_{2}\left(q\right)={\sum }_{x=q}^{M}{\left(-1\right)}^{x+q}{H}_{1}\left(x\right)\left(\begin{array}{c}x\\ q\end{array}\right),{H}_{3}\left(q\right)={\sum }_{x=0}^{q}{\left(-1\right)}^{x+q}{H}_{1}\left(x\right)\left(\begin{array}{c}M-x\\ M-q\end{array}\right)$

[Proof]

Suppose ${H}_{1}\left(q\right)={\sum }_{x=q}^{M}{H}_{2}\left(x\right)\left(\begin{array}{c}x\\ q\end{array}\right)={\sum }_{x=0}^{M}{H}_{2}\left(x\right)\left(\begin{array}{c}x\\ q\end{array}\right)$, $y={T}_{M+1}-M-1$ $.$

$\begin{array}{l}\text{A}:{H}_{1}\left(PS1,q\right)\\ =\left({T}_{M+1}-M-1+q\right){D}_{M+1}{H}_{1}\left(q-1\right)+\left({K}_{M+1}+q{D}_{M+1}\right){H}_{1}\left(q\right)\\ =\left(y+q\right){D}_{M+1}{\sum }_{x=0}^{M}{H}_{2}\left(x\right)\left\{\left(\begin{array}{c}x+1\\ q\end{array}\right)-\left(\begin{array}{c}x\\ q\end{array}\right)\right\}+\left({K}_{M+1}+q{D}_{M+1}\right){\sum }_{k=0}^{M}{H}_{2}\left(x\right)\left(\begin{array}{c}x\\ q\end{array}\right)\\ =\left(y+q\right){D}_{M+1}{\sum }_{x=0}^{M}{H}_{2}\left(x\right)\left(\begin{array}{c}x+1\\ q\end{array}\right)+\left({K}_{M+1}-y{D}_{M+1}\right){\sum }_{k=0}^{M}{H}_{2}\left(x\right)\left( x q \right)\end{array}$

$\begin{array}{l}\text{B}:{\sum }_{x=0}^{M+1}{H}_{2}\left(PS1,x\right)\left(\begin{array}{c}x\\ q\end{array}\right)\\ ={\sum }_{x=0}^{M+1}\left\{{H}_{2}\left(x-1\right)\left(y+x\right){D}_{M+1}\left(\begin{array}{c}x\\ q\end{array}\right)+{H}_{2}\left(x\right)\left({K}_{M+1}+\left(-y-1-x\right){D}_{M+1}\right)\left(\begin{array}{c}x\\ q\end{array}\right)\right\}\\ ={\sum }_{x=0}^{M}\left\{{H}_{2}\left(x\right)\left(y+x+1\right){D}_{M+1}\left(\begin{array}{c}x+1\\ q\end{array}\right)+{H}_{2}\left(x\right)\left({K}_{M+1}+\left(-y-1-x\right){D}_{M+1}\right)\left(\begin{array}{c}x\\ q\end{array}\right)\right\}\end{array}$

$\begin{array}{l}\left[\text{A}-\text{B}\right]\\ ={\sum }_{x=0}^{M}{H}_{2}\left(x\right)\left(q-1-x\right){D}_{M+1}\left(\begin{array}{c}x+1\\ q\end{array}\right)+{\sum }_{x=0}^{M}{H}_{2}\left(x\right)\left(1+x\right){D}_{M+1}\left(\begin{array}{c}x\\ q\end{array}\right)\\ ={D}_{M+1}{\sum }_{x=0}^{M}{H}_{2}\left(x\right)q\left(\begin{array}{c}x+1\\ q\end{array}\right)-{D}_{M+1}{\sum }_{x=0}^{M}{H}_{2}\left(x\right)\left(1+x\right)\left(\begin{array}{c}x\\ q-1\end{array}\right)=0\end{array}$

$\to {H}_{1}\left(q\right)={\sum }_{x=q}^{M}{H}_{2}\left(x\right)\left( x q \right)$

$\stackrel{\text{sameway}}{\to }{H}_{1}\left(q\right)={\sum }_{x=0}^{q}{H}_{3}\left(x\right)\left(\begin{array}{c}M-x\\ M-q\end{array}\right)\stackrel{\text{Inversion}}{\to }$

q.e.d.

In particular:

2.2) ① ${H}_{1}\left(0\right)={H}_{3}\left(0\right)={\sum }_{x=0}^{M}{H}_{2}\left(x\right)={\prod }_{i=1}^{M}{K}_{i}$ ;

${H}_{1}\left(M\right)={H}_{2}\left(M\right)={\sum }_{x=0}^{M}{H}_{3}\left(x\right)={\prod }_{i=1}^{M}{T}_{i}{D}_{i}$ ;

${H}_{2}\left(0\right)={\left(-1\right)}^{M}{H}_{3}\left(M\right)={\sum }_{x=0}^{M}{\left(-1\right)}^{x}{H}_{1}\left(x\right)$ ;

${H}_{1}\left(1\right)={\sum }_{x=1}^{M}{H}_{2}\left(x\right)x=M{H}_{3}\left(0\right)+{H}_{3}\left(1\right)$.

Calculation with 2.1):

2.3) ${\sum }_{q=0}^{M}{H}_{1}\left(q\right)={\sum }_{q=0}^{M}{H}_{2}\left(q\right){2}^{q}={\sum }_{q=0}^{M}{H}_{3}\left(q\right){2}^{M-q}$.

Use 2.1) $\to {\text{Form}}_{\text{1}}={\text{Form}}_{\text{2}}={\text{Form}}_{\text{3}}$.

2.4) ① ${\sum }_{q=0}^{M}{H}_{1}\left(q\right)\left(\begin{array}{c}A\\ B-q\end{array}\right)={\sum }_{q=0}^{M}{H}_{2}\left(q\right)\left(\begin{array}{c}A+q\\ B\end{array}\right)={\sum }_{q=0}^{M}{H}_{3}\left(q\right)\left(\begin{array}{c}A+M-q\\ B-q\end{array}\right)$

${\sum }_{q=0}^{M}{H}_{1}\left(q\right)\left(\begin{array}{c}A\\ q\end{array}\right)={\sum }_{q=0}^{M}{H}_{2}\left(q\right)\left(\begin{array}{c}A+q\\ q\end{array}\right)={\sum }_{q=0}^{M}{H}_{3}\left(q\right)\left(\begin{array}{c}A+M-q\\ M\end{array}\right)$

2.5) $\begin{array}{l}{\sum }_{q=0}^{M}{H}_{1}\left(q\right)q\left(\begin{array}{c}A+1\\ B-q\end{array}\right)={\sum }_{q=0}^{M}{H}_{2}\left(q\right)q\left(\begin{array}{c}A+q\\ B-1\end{array}\right)\\ ={\sum }_{q=0}^{M}\left\{{H}_{3}\left(q\right)q\left(\begin{array}{c}A+M-q\\ B-q\end{array}\right)+M{H}_{3}\left(q\right)\left(\begin{array}{c}A+M-q\\ B-1-q\end{array}\right)\right\}\end{array}$

[Proof]

Suppose it’s holds when M, Let $y={T}_{M+1}-M-1$.

$\begin{array}{l}\text{A}:{\sum }_{q=0}^{M+1}{H}_{1}\left(PS1,q\right)\left(\begin{array}{c}A\\ B-q\end{array}\right)\\ ={\sum }_{q=0}^{M+1}\left\{\left(y+q\right){D}_{M+1}{H}_{1}\left(q-1\right)+\left({K}_{M+1}+q{D}_{M+1}\right){H}_{1}\left(q\right)\right\}\left(\begin{array}{c}A\\ B-q\end{array}\right)\\ ={\sum }_{q=0}^{M}\left\{\left(y+q+1\right){D}_{M+1}{H}_{1}\left(q\right)\left(\begin{array}{c}A\\ B-1-q\end{array}\right)+\left({K}_{M+1}+q{D}_{M+1}\right){H}_{1}\left(q\right)\left(\begin{array}{c}A\\ B-q\end{array}\right)\right\}\\ =\left(y+1\right){D}_{M+1}{\sum }_{q=0}^{M}{H}_{1}\left(q\right)\left(\begin{array}{c}A\\ B-1-q\end{array}\right)+{K}_{M+1}{\sum }_{q=0}^{M}{H}_{1}\left(q\right)\left(\begin{array}{c}A\\ B-q\end{array}\right)\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}+{D}_{M+1}{\sum }_{q=0}^{M}{H}_{1}\left(q\right)q\left(\begin{array}{c}A+1\\ B-q\end{array}\right)\end{array}$

$\begin{array}{l}\text{B}:{\sum }_{q=0}^{M+1}{H}_{2}\left(PS1,q\right)\left(\begin{array}{c}A+q\\ B\end{array}\right)\\ ={\sum }_{q=0}^{M+1}\left\{\left(y+q\right){D}_{M+1}{H}_{2}\left(q-1\right)+\left({K}_{M+1}+\left(-y-1-q\right){D}_{M+1}\right){H}_{2}\left(q\right)\right\}\left(\begin{array}{c}A+q\\ B\end{array}\right)\\ =\left(y+1\right){D}_{M+1}{\sum }_{q=0}^{M}{H}_{2}\left(q\right)\left(\begin{array}{c}A+q\\ B-1\end{array}\right)+{K}_{M+1}{\sum }_{q=0}^{M}{H}_{2}\left(q\right)\left(\begin{array}{c}A+q\\ B\end{array}\right)\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}+{D}_{M+1}{\sum }_{q=0}^{M}{H}_{2}\left(q\right)q\left(\begin{array}{c}A+q\\ B-1\end{array}\right)\end{array}$

$\stackrel{2.4\right)}{\to }\text{A}=\text{B}$

$\begin{array}{l}\stackrel{2.4\right)}{\to }\sum {H}_{1}\left(q\right)\left(\begin{array}{c}A\\ B-1-q\end{array}\right)=\sum {H}_{2}\left(q\right)\left(\begin{array}{c}A+q\\ B-1\end{array}\right),\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{ }\sum {H}_{1}\left(q\right)\left(\begin{array}{c}A\\ B-q\end{array}\right)=\sum {H}_{2}\left(q\right)\left(\begin{array}{c}A+q\\ B\end{array}\right)\to \text{left}\end{array}$

q.e.d.

Example 2.1

M = 1:

${\text{Form}}_{1}={T}_{1}{D}_{1}\left(\begin{array}{c}A\\ B-1\end{array}\right)+{K}_{1}\left(\begin{array}{c}A\\ B\end{array}\right)$ ;

${\text{Form}}_{2}={T}_{1}{D}_{1}\left(\begin{array}{c}A+1\\ B\end{array}\right)+\left({K}_{1}-{T}_{1}{D}_{1}\right)\left(\begin{array}{c}A\\ B\end{array}\right)$ ;

${\text{Form}}_{3}=\left(-{K}_{1}+{T}_{1}{D}_{1}\right)\left(\begin{array}{c}A\\ B-1\end{array}\right)+{K}_{1}\left(\begin{array}{c}A+1\\ B\end{array}\right)$ ;

M = 2:

$\begin{array}{l}{\text{Form}}_{1}={T}_{1}{T}_{2}{D}_{1}{D}_{2}\left(\begin{array}{c}A\\ B-2\end{array}\right)+\left[{K}_{1}\left({T}_{2}-1\right){D}_{2}+{T}_{1}{D}_{1}\left({K}_{2}+{D}_{2}\right)\right]\left(\begin{array}{c}A\\ B-1\end{array}\right)\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}+{K}_{1}{K}_{2}\left(\begin{array}{c}A\\ B\end{array}\right);\end{array}$

$\begin{array}{l}{\text{Form}}_{2}={T}_{1}{T}_{2}{D}_{1}{D}_{2}\left(\begin{array}{c}A+2\\ B\end{array}\right)+\left[\left({K}_{1}-{T}_{1}{D}_{1}\right)\left({T}_{2}-1\right){D}_{2}\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}+{T}_{1}{D}_{1}\left({K}_{2}-{T}_{2}{D}_{2}\right)\right]\left(\begin{array}{c}A+1\\ B\end{array}\right)+\left({K}_{1}-{T}_{1}{D}_{1}\right)\left({K}_{2}-{T}_{2}{D}_{2}+{D}_{2}\right)\left(\begin{array}{c}A\\ B\end{array}\right);\end{array}$

$\begin{array}{c}{\text{Form}}_{3}=\left(-{K}_{1}+{T}_{1}{D}_{1}\right)\left(-{K}_{2}+{T}_{2}{D}_{2}-{D}_{2}\right)\left(\begin{array}{c}A\\ B-2\end{array}\right)+\left[{K}_{1}\left(-{K}_{2}+{T}_{2}{D}_{2}\right)\\ \text{\hspace{0.17em}}\text{ }+\left(-{K}_{1}+{T}_{1}{D}_{1}\right)\left({K}_{2}+{D}_{2}\right)\right]\left(\begin{array}{c}A+1\\ B-1\end{array}\right)+{K}_{1}{K}_{2}\left(\begin{array}{c}A+2\\ B\end{array}\right).\end{array}$

3. Generalization of Calculation Formula

If $f\left(n\right)=\sum {A}_{i}\left(\begin{array}{c}{N}_{i}\\ {m}_{i}\end{array}\right)$, ${m}_{i}$ is not changed with n, then define

${\nabla }^{p}f\left(n\right)=\sum {A}_{i}\left(\begin{array}{c}{N}_{i}-p\\ {m}_{i}-p\end{array}\right),P\in ℤ$

$\nabla f\left(n\right)=f\left(n\right)-f\left(n-1\right)$, this is a little different from the difference

${\nabla }^{0}f\left(n\right)=f\left(n\right),{\nabla }^{-1}f\left(N\right)={\sum }_{n=0}^{N-1}f\left( n \right)$

Eg: $\nabla \left(\begin{array}{c}n+1\\ n-1\end{array}\right)=\nabla \left(\begin{array}{c}n+1\\ 2\end{array}\right)=\left(\begin{array}{c}n\\ 1\end{array}\right)\ne \left(\begin{array}{c}n\\ n-2\end{array}\right)$.

In [1], 1.1) is proved by

(*) ${\sum }_{n=0}^{N-1}n\left(\begin{array}{c}n+K\\ M\end{array}\right)=\left(M+1\right)\left(\begin{array}{c}N+K\\ M+2\end{array}\right)+\left(M-K\right)\left(\begin{array}{c}N+K\\ M+1\end{array}\right)$

$SUM\left(N,PS1,\left[PT,{T}_{M}+1\right]\right)={\sum }_{n=0}^{N-1}\left({K}_{M+1}+n×{D}_{M+1}\right)×\nabla SUM\left(n+1\right)$

$SUM\left(N,PS1,\left[PT,{T}_{M}+2\right]\right)={\sum }_{n=0}^{N-1}\left({K}_{M+1}+n×{D}_{M+1}\right)×{\nabla }^{0}SUM\left(n+1\right)$

$PS1=\left[PS,{K}_{M+1}:{D}_{M+1}\right],PT1=\left[PT,{T}_{M+1}={T}_{M}+2-p\right]$.

Define: $SUM\left(N,PS1,PT1\right)={\sum }_{n=0}^{N-1}\left({K}_{M+1}+n×{D}_{M+1}\right)×{\nabla }^{p}SUM\left(n+1\right)$

$SUM\left(N,PS1,PT1\right)$ can be calculated using the same method of 1.1).

The Form: $\left({T}_{1}+{K}_{1}\right)\left({T}_{2}+{K}_{2}\right)\cdots \left({T}_{M}+{K}_{M}\right)=\sum {\prod }_{i=1}^{M}{X}_{M}$, ${X}_{i}={T}_{i}$ or ${K}_{i}$.

3.1) $q=X\left(T\right)$, $PM=PM\left(PT\right)$,

$\begin{array}{l}SUM\left(N\right)=\\ \stackrel{{\text{Form}}_{1}}{\to }{\sum }_{q=0}^{PM}{H}_{1}\left(q\right)\left(\begin{array}{c}N+{T}_{M}-PM\\ N-1-q\end{array}\right),{B}_{i}=\left\{\begin{array}{l}\left({T}_{i}-{X}_{K-1}\right){D}_{i};{X}_{i}={T}_{i}\\ {K}_{i}+{X}_{T-1}{D}_{i};{X}_{i}={K}_{i}\end{array}\\ \stackrel{{\text{Form}}_{2}}{\to }{\sum }_{q=0}^{PM}{H}_{2}\left(q\right)\left(\begin{array}{c}N+{T}_{M}-PM+q\\ N-1\end{array}\right),{B}_{i}=\left\{\begin{array}{l}\left({T}_{i}-{X}_{K-1}\right){D}_{i};{X}_{i}={T}_{i}\\ {K}_{i}+\left({X}_{K-1}-{T}_{i}\right){D}_{i};{X}_{i}={K}_{i}\end{array}\\ \stackrel{{\text{Form}}_{3}}{\to }{\sum }_{q=0}^{PM}{H}_{3}\left(q\right)\left(\begin{array}{c}N+{T}_{M}-q\\ N-1-q\end{array}\right),{B}_{i}=\left\{\begin{array}{l}-{K}_{i}+\left({T}_{i}-{X}_{T-1}\right){D}_{i};{X}_{i}={T}_{i}\\ {K}_{i}+{X}_{T-1}{D}_{i};{X}_{i}={K}_{i}\end{array}\end{array}$

$H\left(q\right)=H\left(PS,PT,q\right)={\sum }_{\text{all}\text{\hspace{0.17em}}\text{of}\text{\hspace{0.17em}}\text{the}\text{\hspace{0.17em}}\prod {X}_{i}\text{\hspace{0.17em}}\text{with}\text{\hspace{0.17em}}X\left(T\right)=q}{\prod }_{i=1}^{M}{B}_{i}$.

[Proof]

$SUM\left(N\right)\stackrel{{\text{Form}}_{1}}{\to }{\sum }_{q=0}^{M}{H}_{1}\left(q\right)\left(\begin{array}{c}N+{T}_{M}-M\\ N-1-q\end{array}\right)={\sum }_{q=0}^{M}{H}_{1}\left(q\right)\left(\begin{array}{c}N+{T}_{M}-M\\ {T}_{M}-M+1+q\end{array}\right)$

$\begin{array}{l}{\sum }_{n=0}^{N-1}\left({K}_{M+1}+n×{D}_{M+1}\right)×{\nabla }^{p}SUM\left(n+1\right)\\ ={\sum }_{n=0}^{N-1}\left({K}_{M+1}+n×{D}_{M+1}\right)×{\sum }_{q=0}^{M}{H}_{1}\left(q\right)\left(\begin{array}{c}n+1+{T}_{M}-M-p\\ {T}_{M}-M+1+q-p\end{array}\right)\stackrel{\left(\ast \right)}{\to }\\ ={\sum }_{q=0}^{M}\left({T}_{M}-M+2+q-p\right){D}_{M+1}×{H}_{1}\left(q\right)\left(\begin{array}{c}N+1+{T}_{M}-M-p\\ {T}_{M}-M+3+q-p\end{array}\right)\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}+{\sum }_{q=0}^{M}\left({K}_{M+1}+q{D}_{M+1}\right)×{H}_{1}\left(q\right)\left(\begin{array}{c}N+1+{T}_{M}-M-p\\ {T}_{M}-M+2+q-p\end{array}\right)\end{array}$

$\begin{array}{l}={\sum }_{q=0}^{M}\left({T}_{M+1}-\left[M-q\right]\right){D}_{M+1}×{H}_{1}\left(q\right)\left(\begin{array}{c}N+{T}_{M+1}-\left(M+1\right)\\ N-1-\left(q+1\right)\end{array}\right)\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}+{\sum }_{q=0}^{M}\left({K}_{M+1}+q{D}_{M+1}\right)×{H}_{1}\left(q\right)\left(\begin{array}{c}N+{T}_{M+1}-\left(M+1\right)\\ N-1-q\end{array}\right)\\ ={\sum }_{q=0}^{M+1}{H}_{1}\left(PS1,PT1,q\right)\left(\begin{array}{c}N+{T}_{M+1}-\left(M+1\right)\\ N-1-q\end{array}\right)\stackrel{2.4\right)}{\to }\text{threeforms}\end{array}$

q.e.d.

3.2) $PS1=\left[D×A:D,PS\right]$, $PT1=\left[A,PT\right]$

${H}_{1}\left(PS1,q\right)=D×A×\left[{H}_{1}\left(q\right)+{H}_{1}\left(q-1\right)\right]$ ;

${H}_{2}\left(PS1,0\right)=0,{H}_{2}\left(PS1,q\right)=D×A×{H}_{2}\left(q-1\right)$ ;

${H}_{3}\left(PS1,M+1\right)=0,{H}_{3}\left(PS1,q\right)=\text{}D×A×{H}_{3}\left(q\right)$ ;

${H}_{1}\left(\left[D×{T}_{1}:D,\cdots ,D×{T}_{M}:D\right],\left[{T}_{1},\cdots ,{T}_{M}\right],q\right)={D}^{M}\left(\begin{array}{c}M\\ q\end{array}\right){\prod }_{i=1}^{M}{T}_{i}$ ;

$SUM\left(N,PT,PT\right)={\prod }_{i=1}^{M}{T}_{i}\left(\begin{array}{c}N+{T}_{M}\\ {T}_{M}+1\end{array}\right)$ ;

$SUM\left(N,\left[{L}_{1},\cdots ,{L}_{P},PS\right],\left[{L}_{1},\cdots ,{L}_{P},PT\right]\right)={\prod }_{i=1}^{P}{L}_{i}SUM\left(N\right)$.

These are conclusions of [1] and can be extended to the new PT.

3.3) $PS1=\left[1,1,\cdots ,1,PS\right]$, $PT1=\left[1,1,\cdots ,1,PT\right]$, $SUM\left(N,PS1,PT1\right)=SUM\left(N\right)$.

P = Count of 1 added

$\to$ expands ${\sum }_{q=0}^{M}{H}_{1}\left(q\right)\left(\begin{array}{c}A+P\\ B-q\end{array}\right)$ to ${\sum }_{q=0}^{M+P}{H}_{1}\left(PS1,q\right)\left(\begin{array}{c}A\\ B-q\end{array}\right)$.

Now PT’s domain is extended to $ℕ$ and ${T}_{i+1}-{T}_{i}$ is not restricted.

If ${T}_{M}\le 0$, $SUM\left(N\right)={\sum }_{q=0}^{M}{H}_{1}\left(q\right)\left(\begin{array}{c}A\\ B\end{array}\right)$, $B<0$, the formula has no meaning

when regardless of the actual meaning, ${\text{Form}}_{\text{1}}={\text{Form}}_{\text{2}}={\text{Form}}_{\text{3}}$ still established.

PT’s domain can be extended to $ℂ$.

4. Properties of Coefficients

Define

${F}_{M}^{N+M-1}={\sum }_{1\le {I}_{i}\le {I}_{i+1}\le N+M-1}{\prod }_{i=1}^{M}{I}_{i}={S}_{1}\left(N+M,N\right)$

${E}_{M}^{N}=\underset{{\lambda }_{1}+{\lambda }_{2}+\cdots +{\lambda }_{N}=M}{\sum }{1}^{{\lambda }_{1}}{2}^{{\lambda }_{2}}\cdots {N}^{{\lambda }_{N}}={S}_{2}\left(N+M,N\right)$

$\begin{array}{l}{E}_{p}^{q+1}\odot \left(PT,K\right)=\underset{{\lambda }_{1}+{\lambda }_{2}+\cdots +{\lambda }_{q+1}=p}{\sum }{1}^{{\lambda }_{1}}{2}^{{\lambda }_{2}}\cdots {\left(q+1\right)}^{{\lambda }_{q+1}}\\ \text{ }×\left({T}_{1}+{\lambda }_{1}K\right)\left({T}_{2}+{\lambda }_{1}K+{\lambda }_{2}K\right)\cdots \left({T}_{q}+{\lambda }_{1}K+{\lambda }_{2}K+\cdots +{\lambda }_{q}K\right),{\lambda }_{i}\ge 0\end{array}$

PT in section 1: ${T}_{1}=1$, $\left\{\begin{array}{l}{T}_{i+1}-{T}_{i}=1:\text{meanscontinuity}\\ {T}_{i+1}-{T}_{i}=2,\text{meansdiscontinuity}.\end{array}$

[1] call them Basic Shapes and define:

$PB\left(PT\right)=\text{countofdiscontinuity},\text{\hspace{0.17em}}MIN\left(PT\right)={\prod }_{i=1}^{M}{T}_{i}{D}_{i}$.

Expand the definition:

$PS=\left[{K}_{1}:{D}_{1},{K}_{2}:{D}_{2},\cdots \right],\text{Item}=\left\{{K}_{1}+{\lambda }_{1}{D}_{1},{K}_{2}+{\lambda }_{2}{D}_{2},\cdots \right\}$

Specify ${\lambda }_{1}=0$, $\left\{\begin{array}{l}{\lambda }_{i}={\lambda }_{i+1}:\text{meanscontinuity}\\ {\lambda }_{i}+1={\lambda }_{i+1},\text{meansdiscontinuity}\end{array}$

PB (item of PS) = count of discontinuity in an item, $\text{value}\in \left[0,M-1\right]$.

$MIN\left(\text{item}\text{\hspace{0.17em}}\text{of}\text{\hspace{0.17em}}PS\right)={\prod }_{i=1}^{M}\left({K}_{i}+{\lambda }_{i}{D}_{i}\right)$

$MI{N}_{q}\left(PS\right)=\underset{PB\left(\text{ }\right)=q}{\sum }MIN\left(\text{item}\text{\hspace{0.17em}}\text{of}\text{\hspace{0.17em}}PS\right),\text{\hspace{0.17em}}MI{N}_{q}\text{\hspace{0.17em}}\text{is}\text{\hspace{0.17em}}\text{short}\text{\hspace{0.17em}}\text{for}\text{\hspace{0.17em}}MI{N}_{q}\left(\left[1,\cdots ,M\right]\right)$.

By definition →

4.1) ① $\begin{array}{c}{H}_{1}\left(q\right)={\left(-1\right)}^{M-q}{H}_{2}\left(\left[-{K}_{i}+{T}_{i}{D}_{i}-\left(i-1\right){D}_{i}\right],PT\right)\\ ={\left(-1\right)}^{q}{H}_{3}\left(PS,\left[\frac{{K}_{i}}{{D}_{i}}-{T}_{i}+\left(i-1\right)\right]\right);\end{array}$

${H}_{2}\left(q\right)={\left(-1\right)}^{M-q}{H}_{1}\left(\left[-{K}_{i}+{T}_{i}{D}_{i}-\left(i-1\right){D}_{i}\right],PT\right);$

${H}_{3}\left(q\right)={\left(-1\right)}^{q}{H}_{1}\left(PS,\left[\frac{{K}_{i}}{{D}_{i}}-{T}_{i}+\left(i-1\right)\right]\right).$

4.2) $PS=\left[1,1,\cdots \right],PT=\left[{T}_{i}={T}_{1}+\left(i-1\right)\left(K+1\right)\right]$

${H}_{1}\left(q\right)={E}_{M-q}^{q+1}\odot \left(PT,K\right)$ ;

${H}_{3}\left(q\right)={E}_{M-q}^{q+1}\odot \left(\left[{T}_{i}=\left({T}_{1}-1\right)+\left(i-1\right)K\right],K+1\right)$ ;

${E}_{M-q}^{q+1}\odot \left(PT,K\right)={E}_{M-1-q}^{q+1}\odot \left(\left[K+{T}_{i}\right],K\right)+{T}_{1}{E}_{M-1-q}^{q+1}\odot \left(\left[K+{T}_{i}\right],K\right)$.

[Proof]

${H}_{1}\left(q\right)=\sum \prod \left(X\in T\right)\prod \left(X\in K\right)\stackrel{\text{def}}{\to }\sum \prod \left(X\in K\right)={E}_{M-q}^{q+1}$

$\prod X={1}^{{\lambda }_{1}}\left\{{\prod }_{x=1}^{A-1}{X}_{{\lambda }_{1}+x}\right\}{A}^{{\lambda }_{A}}\left\{{\prod }_{x=1}^{B-A}{X}_{{\lambda }_{1}+A-1+{\lambda }_{A}+x}\right\}{B}^{{\lambda }_{B}}\cdots$

$\begin{array}{l}{\prod }_{x=1}^{A-1}{X}_{{\lambda }_{1}+x}={\prod }_{x=1}^{A-1}\left({T}_{1}+\left[{\lambda }_{1}+x-1\right]\left[K+1\right]-{\lambda }_{1}\right)\\ ={\prod }_{x=1}^{A-1}\left({T}_{X}+{\lambda }_{1}K\right)\stackrel{{\lambda }_{2},{\lambda }_{3},\cdots =0}{\to }=\left({T}_{1}+{\lambda }_{1}K\right)\cdots \left({T}_{A-1}+\cdots +{\lambda }_{A-1}K\right)\end{array}$

$\stackrel{\text{sameway}}{\to }{\prod }_{x=1}^{B-A}{X}_{{\lambda }_{1}+A-1+{\lambda }_{A}+x}=\left({T}_{A}+{\lambda }_{1}K+\cdots \right)\cdots \left({T}_{B-1}+\cdots \right)\to ①$

q.e.d.

4.3) $\left\{\begin{array}{l}①\text{\hspace{0.17em}}PS1=\left[{K}_{2}:{D}_{2},\cdots ,{K}_{M}:{D}_{M}\right],PT1=\left[\frac{{K}_{2}}{{D}_{2}}+1,\cdots ,\frac{{K}_{M}}{{D}_{M}}+M-1\right]\\ ②\text{\hspace{0.17em}}PS1=\left[{D}_{2}:{D}_{2},\cdots ,{D}_{M}:{D}_{M}\right],PT1=\left[\frac{{K}_{2}}{{D}_{2}}+1,\cdots ,\frac{{K}_{M}}{{D}_{M}}+M-1\right]\to \\ ③\text{\hspace{0.17em}}PS1=\left[{K}_{2}:{D}_{2},\cdots ,{K}_{M}:{D}_{M}\right],PT1=\left[-1,\cdots ,-1\right]\end{array}$

$\left\{\begin{array}{l}{K}_{1}×{H}_{1}\left(PS1,q\right)=MI{N}_{q}\left(PS\right),{H}_{1}\left(PS,\left[\frac{{K}_{1}}{{D}_{1}},PT1\right],q\right)=MI{N}_{q}+MI{N}_{q-1}\\ {K}_{1}×{H}_{2}\left(PS1,q\right)={\left(-1\right)}^{M-1-q}MI{N}_{q}\left(PS\right)\\ {K}_{1}×{H}_{3}\left(PS1,q\right)={\left(-1\right)}^{q}MI{N}_{q}\left( P S \right)\end{array}$

Example 4.1: ${H}_{1}\left(q\right),{H}_{2}\left(q\right),{H}_{3}\left(q\right)$ are equal to:

$PS=\left[1,1,\cdots \right],PT=\left[1,1,\cdots \right]$ $\left\{\begin{array}{l}\left(\begin{array}{c}M\\ q\end{array}\right)={E}_{M-q}^{q+1}\odot \left(PT,-1\right)\\ {H}_{2}\left(M\right)=1,{H}_{2}\left(q0\right)=0\end{array}$

$PS=\left[1,2,\cdots ,M\right],PT=\left[1,2,\cdots ,M\right]=\left\{\begin{array}{l}M!\left(\begin{array}{c}M\\ q\end{array}\right)\\ {H}_{2}\left(M\right)=M!,{H}_{2}\left(q0\right)=0\end{array}$

$PS=\left[1,1,\cdots \right]$, $PT=\left[1,2,\cdots ,M\right]$,

$〈\begin{array}{c}M\\ q\end{array}〉=\text{Euleriannumber}:{N}^{M}={\sum }_{q=0}^{M-1}〈\begin{array}{c}M\\ q\end{array}〉\left(\begin{array}{c}N+q\\ M\end{array}\right)$

$\left\{\begin{array}{l}q!{E}_{M-q}^{q+1}=q!{S}_{2}\left(M+1,q+1\right)\\ \stackrel{\text{def}}{\to }{\left(-1\right)}^{M-q}q!{E}_{M-q}^{q}={\left(-1\right)}^{M-q}q!{S}_{2}\left(M,q\right)\\ 〈\begin{array}{c}M\\ M-1-q\end{array}〉=〈\begin{array}{c}M\\ q\end{array}〉={E}_{M-q}^{q+1}\odot \left(\left[0,0,\cdots \right],1\right)={E}_{M-1-q}^{q+1}\odot \left(\left[1,1,\cdots \right],1\right)\end{array}$

$\stackrel{2.2\right)}{\to }{H}_{1}\left(M\right)={\sum }_{q=0}^{M}{H}_{3}\left(q\right)\to {\sum }_{q=0}^{M}〈\begin{array}{c}M\\ q\end{array}〉=M!$

$\stackrel{2.2\right)}{\to }{H}_{1}\left(1\right)={\sum }_{q=0}^{M}{H}_{2}\left(q\right)q\to {\sum }_{q=0}^{M}{\left(-1\right)}^{M-q}q×q!{S}_{2}\left(M,q\right)={2}^{M}-1$

$PS=\left[1,1,\cdots \right],PT=\left[2,3,\cdots ,M\right]$

$\left\{\begin{array}{l}\left(q+1\right)!{E}_{M-1-q}^{q+1}=\left(q+1\right)!{S}_{2}\left(M,q+1\right)\\ {\left(-1\right)}^{M-1-q}\left(q+1\right)!{E}_{M-1-q}^{q+1}={\left(-1\right)}^{M-1-q}\left(q+1\right)!{S}_{2}\left(M,q+1\right)\\ 〈\begin{array}{c}M\\ M-1-q\end{array}〉=〈\begin{array}{c}M\\ q\end{array}〉={E}_{M-1-q}^{q+1}\odot \left(\left[1,1,\cdots \right],1\right)\end{array}$

$PS=\left[1,1,\cdots \right],PT=\left[1,3,\cdots ,2M-1\right]=\left\{\begin{array}{l}{E}_{M-q}^{q+1}\odot \left(PT,1\right)\\ {\left(-1\right)}^{M-q}MI{N}_{q-1}\\ {E}_{M-q}^{q+1}\odot \left(\left[0,1,2,\cdots \right],2\right)\end{array}$

$PS=\left[1,1,\cdots \right],PT=\left[3,5,\cdots ,2M-1\right]=\left\{\begin{array}{l}{E}_{M-1-q}^{q+1}\odot \left(PT,1\right)\\ {\left(-1\right)}^{M-1-q}MI{N}_{q}\\ {E}_{M-1-q}^{q+1}\odot \left(\left[2,3,4,\cdots \right],2\right)\end{array}$

$PS=\left[1,2,\cdots ,M\right]$,

$PT=\left[1,3,\cdots ,2M-1\right]=\left\{\begin{array}{l}MI{N}_{q}+MI{N}_{q-1}\\ \stackrel{\text{def}}{\to }1×{\left(-1\right)}^{M-q}{E}_{M-q}^{q}\odot \left(\left[3,5,\cdots \right],1\right)\\ \stackrel{\text{def}}{\to }1×{E}_{q}^{M-q}\odot \left(\left[2,3,4,\cdots \right],2\right)\end{array}$

$PS=\left[2,3,\cdots ,M\right]$,

$PT=\left[3,5,\cdots ,2M-1\right]=\left\{\begin{array}{l}MI{N}_{q}\\ \stackrel{\text{def}}{\to }{\left(-1\right)}^{M-1-q}{E}_{M-1-q}^{q+1}\odot \left(\left[3,5,\cdots \right],1\right)\\ \stackrel{\text{def}}{\to }{E}_{q}^{M-q}\odot \left(\left[2,3,4,\cdots \right],2\right)\end{array}$

③ ④, ⑤ ⑥, ⑦ ⑧ are in pairs, they can verify 3.2).

5. Continuity and Discontinuity

MINq appears in $SUM\left(N,\left[1,1,\cdots \right],\left[3,5,\cdots \right]\right)$ and $SUM\left(N,\left[2,3,\cdots \right],\left[3,5,\cdots \right]\right)$. It’s easy to write out their items directly by continuity and discontinuity.

[1] has proved: ${\sum }_{q=0}^{M-1}{\left(-1\right)}^{M-1-q}MI{N}_{q}=1$. Extand it:

$\stackrel{2.2\right)}{\to }{K}_{1}×{H}_{1}\left(0\right)={K}_{1}{\sum }_{q=0}^{M-1}{H}_{2}\left(q\right)\stackrel{4.3\right)}{\to }={\sum }_{q=0}^{M-1}{\left(-1\right)}^{M-1-q}MI{N}_{q}\left(PS\right)\to$

5.1) ${\sum }_{q=0}^{M-1}{\left(-1\right)}^{M-1-q}MI{N}_{q}\left(PS\right)={K}_{1}{\prod }_{i=2}^{M}{D}_{i}$

Example 5.1:

Basic Shape, M = 3:

$1×3×5-\left(1×3×4+1×2×4\right)+1×2×3=1$.

Basic Shape, M = 4:

$\begin{array}{l}1×3×5×7-\left(1×3×5+1×3×4+1×2×4\right)×6\\ \text{ }+\left(1×2×3+1×3×4+1×2×4\right)×5-1×2×3×4=1.\end{array}$

$PS=\left[5,10:10,2:3,3:10\right]$ :

$\begin{array}{l}5×20×8×33-\left(5×10×5+5×20×5+5×20×8\right)×23\\ +\left(5×10×2+5×10×5+5×20×5\right)×13-5×10×2×3\\ =1500=5×10×3×10\end{array}$

$PS=\left[1,1,\cdots \right],PT=\left[2,\cdots ,M\right]\to {\sum }_{q=1}^{M}{\left(-1\right)}^{M-q}q!{S}_{2}\left(M,q\right)=1$.

5.2) ① $MI{N}_{M-2}=\frac{2\left(M-1\right)}{3}\left(2M-1\right)!!$

$2×MI{N}_{M-1}+MI{N}_{M-2}\equiv 0\text{\hspace{0.17em}}MOD\text{\hspace{0.17em}}{\left(M+2\right)}^{2}$, $M>3$, M is odd

[Proof]

$PS=\left[2,3,\cdots ,M\right],PT=\left[3,5,\cdots ,2M-1\right]$

${H}_{1}\left(M-2\right)=MI{N}_{M-2}={\sum }_{i=1}^{M-1}\left(\prod X\in T\right)×2i$

${H}_{2}\left(M-2\right)=-{\sum }_{i=1}^{M-1}\left(\prod X\in T\right)×i=-\frac{1}{2}{H}_{1}\left(M-2\right)$

$\stackrel{2.1\right)}{\to }{H}_{2}\left(M-2\right)=-\left(M-1\right){H}_{1}\left(M-1\right)+{H}_{1}\left(M-2\right)\to ①$

$2×MI{N}_{M-1}+MI{N}_{M-2}=\frac{2\left(M+2\right)}{3}×\left(2M-1\right)!!\to ②$

q.e.d.

Example 5.2:

$2×\left(1×3×5\right)+\left(1×2×4+1×3×4\right)=50\equiv 0\text{\hspace{0.17em}}MOD\text{\hspace{0.17em}}25$

$\begin{array}{l}2×\left(1×3×5×7×9\right)+\left(1×3×5×7+1×3×5×6+1×3×4×6+1×2×4×6\right)×8\\ =4410\equiv 0\text{\hspace{0.17em}}MOD\text{\hspace{0.17em}}49\end{array}$

when PT is Basic Shape, items in SUM can be classified by continuity and discontinuity.

Eg: use A for continuity, B for discontinuity

$\left[1,2,3\right]=\text{AA},\text{\hspace{0.17em}}\left[1,2,4\right]=\text{AB},\text{\hspace{0.17em}}\left[1,3,4\right]=\text{BA},\text{\hspace{0.17em}}\left[1,3,5\right]=\text{BB}$.

Products of ${F}_{M}^{N+M-1}$ can be divided into ${2}^{M-1}$ categories.

It’s easy to write them intuitively. Eg: $\text{1}×\text{2}×\text{4}$, $\text{2}×\text{3}×\text{5}$, $\text{1}×\text{2}×\text{5}$, $\cdots$, ${I}_{1}+1={I}_{2}$, ${I}_{2}+1<{I}_{3}\in \left[1,2,4\right]$.

Each category has a simple formula $\stackrel{3.2\right)-⑤}{\to }$

$SUM\left(N-PB\left(PT\right),PT,PT\right)=MIN\left(PT\right)\left(\begin{array}{c}N+M\\ {T}_{M}+1\end{array}\right)$.

This is the promotion of ${\sum }_{n=0}^{N-1}\left(\begin{array}{c}n\\ M\end{array}\right)=\left(\begin{array}{c}N\\ M+1\end{array}\right)$

$\stackrel{\text{Traverse}}{\to }{F}_{M}^{N+M-1}=SUM\left(N,\left[2,3,\cdots \right],\left[3,5,\cdots \right]\right)={\sum }_{q=0}^{M-1}MI{N}_{q}\left(\begin{array}{c}N+M\\ M+1+q\end{array}\right)$.

Similarly: for Basic PT, arbitrarily PS can use the classification.

Example 5.3:

$\begin{array}{l}SUM\left(N,\left[1,1,1\right],\left[1,3,5\right]\right)\\ =SUM\left(N,\left[1,1,1\right],\left[1,2,3\right]\right)+SUM\left(N-1,\left[1,1,2\right],\left[1,2,4\right]\right)\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{ }+SUM\left(N-1,\left[1,2,2\right],\left[1,3,4\right]\right)+SUM\left(N-2,\left[1,2,3\right],\left[1,3,5\right]\right)\end{array}$

$\begin{array}{l}SUM\left(N,\left[1,1,1\right],\left[1,3,4\right]\right)\\ =SUM\left(N,\left[1,1,1\right],\left[1,2,3\right]\right)+SUM\left(N-1,\left[1,2,2\right],\left[1,3,4\right]\right)\end{array}$

The pairs of PSx and PTx compare with PS and $\left[1,2,\cdots ,M\right]$, $PB\left(PSx\right)=PB\left(PTx\right)$, and the discontinuity at the same position. They are called having the same shape.

5.3) For Basic PT, $PS1=\left[1,1,\cdots ,PS\right]$, $PT1=\left[1,1,\cdots ,PT\right]$, count of 1 added = PB(PT)

${H}_{1}\left(PS1,PT1,q\right)={\sum }_{A+B=q,PB\left(PSx\right)=PB\left(PTx\right)=A,\text{sameshape}}{H}_{1}\left(PSx,PTx,B\right)$.

P is Prime, P > 2, [1] has proved:

5.4) $MI{N}_{q}\equiv 0\text{\hspace{0.17em}}MOD\text{\hspace{0.17em}}P$, $q>0$, $q+M=P-1$

5.5) $MI{N}_{q}\equiv 0\text{\hspace{0.17em}}MOD\text{\hspace{0.17em}}P$, $\left\{\begin{array}{l}①\text{\hspace{0.17em}}M=P,q\ge 0\\ ②\text{\hspace{0.17em}}M=P-1,q>0\\ ③\text{\hspace{0.17em}}M

[Proof]

For ③: $q+M=P-1\to$ proved by 5.4)

$q+M=P:P=\text{Max}\text{\hspace{0.17em}}\text{factor}\text{\hspace{0.17em}}\text{of}\text{\hspace{0.17em}}MI{N}_{q}\to \text{holds}$

$q+M>P:MI{N}_{q}=\left(\text{Items}\text{\hspace{0.17em}}\text{has}\text{\hspace{0.17em}}P\right)+\left(\text{Items}\text{\hspace{0.17em}}\text{has}\text{\hspace{0.17em}}\text{no}\text{\hspace{0.17em}}P\right)$

$\left(\text{Items}\text{\hspace{0.17em}}\text{has}\text{\hspace{0.17em}}\text{no}\text{\hspace{0.17em}}P\right)=\sum \prod \left(\text{factors}\ge P+1\right)×\left\{\sum \prod \left(\text{factors}\le P-1\right)\right\}$

$\left\{\sum \prod \left(\text{factors}\le P-1\right)\right\}$ is a MIN that match the conditions of 5.4)

q.e.d.

5.6) $P=M+2$, ① ${E}_{M}^{N}\equiv$${F}_{M}^{M+N-1}\equiv \left\{\begin{array}{l}1,N\equiv 1\text{\hspace{0.17em}}MOD\text{\hspace{0.17em}}P\\ 0,N\overline{)\equiv }1\text{\hspace{0.17em}}MOD\text{\hspace{0.17em}}P\end{array}\text{\hspace{0.17em}}MOD\text{\hspace{0.17em}}P$

[Proof]

$\stackrel{\text{Example}\text{\hspace{0.17em}}4.1-⑥}{\to }{E}_{M}^{N}={\sum }_{q=0}^{M-1}{\left(-1\right)}^{M-1-q}MI{N}_{q}\left(\begin{array}{c}N+M+q\\ N-1\end{array}\right)\stackrel{5.5\right)-③}{\to }$

$\equiv MI{N}_{0}\left(\begin{array}{c}N+M\\ N-1\end{array}\right)\equiv \left(P-2\right)!\left(\begin{array}{c}N+P-2\\ N-1\end{array}\right)\equiv \left(\begin{array}{c}P+N-2\\ N-1\end{array}\right)MOD\text{\hspace{0.17em}}P\to ①$

$\begin{array}{l}\stackrel{\text{Example}\text{\hspace{0.17em}}4.1-⑧}{\to }{F}_{M}^{M+N-1}={\sum }_{q=0}^{M-1}MI{N}_{q}\left(\begin{array}{c}N+M\\ N-1-q\end{array}\right)\\ \equiv MI{N}_{0}\left(\begin{array}{c}N+P-2\\ P-1\end{array}\right)MOD\text{\hspace{0.17em}}P\to ②\end{array}$

q.e.d.

5.7) $P=M+N$, ① ${F}_{M}^{M+N-1}\equiv$${E}_{M}^{N}\equiv 0\text{\hspace{0.17em}}MOD\text{\hspace{0.17em}}P$, $0

[Proof]

${F}_{M}^{M+N-1}={\sum }_{q=0}^{M-1}MI{N}_{q}\left(\begin{array}{c}P\\ M+1+q\end{array}\right)$

$\left\{\begin{array}{l}2MP,M+q\ge P-1\stackrel{5.5\right)}{\to }MI{N}_{q}\equiv 0\text{\hspace{0.17em}}MOD\text{\hspace{0.17em}}P\\ 2M>P,M+q

q.e.d.

$N+M=P\stackrel{\text{def}}{\to }{F}_{M}^{P-1}=\left(P-1\right){F}_{M-1}^{P-2}+{F}_{M}^{P-2};{E}_{M}^{N}=N{E}_{M-1}^{N}+{E}_{M}^{N-1}\to$

(1) ${S}_{1}\left(P,N\right)=\left(P-1\right){S}_{1}\left(P-1,N\right)+{S}_{1}\left(P-1,N-1\right)$

(2) ${S}_{2}\left(P,N\right)=N{S}_{2}\left(P-1,N\right)+{S}_{2}\left(P-1,N-1\right)$

5.8) ① ${S}_{1}\left(P-1,q\right)\equiv 1\text{\hspace{0.17em}}MOD\text{\hspace{0.17em}}P,\text{\hspace{0.17em}}1\le q\le P-1$

$q!{S}_{2}\left(P-1,q\right)\equiv {\left(-1\right)}^{q+1}\text{\hspace{0.17em}}MOD\text{\hspace{0.17em}}P,\text{\hspace{0.17em}}1\le q\le P-1$

[Proof]

For ①: $q=1$, ${S}_{1}\left(P-1,q\right)=1$, holds.

If q holds, ${S}_{1}\left(P,q+1\right)\equiv 0\text{\hspace{0.17em}}MOD\text{\hspace{0.17em}}P$

$\begin{array}{c}{S}_{1}\left(P,q+1\right)=\left(P-1\right){S}_{1}\left(P-1,q+1\right)+{S}_{1}\left(P-1,q\right)\\ \equiv -{S}_{1}\left(P-1,q+1\right)+1\equiv 0\text{\hspace{0.17em}}MOD\text{\hspace{0.17em}}P\to ①\end{array}$

For ②: $q=1$, $q!{S}_{2}\left(P-1,q\right)=1$, holds.

If q holds, ${S}_{2}\left(P,q+1\right)\equiv 0\text{\hspace{0.17em}}MOD\text{\hspace{0.17em}}P$, $q!{S}_{2}\left(P,q+1\right)\equiv 0\text{\hspace{0.17em}}MOD\text{\hspace{0.17em}}P$

$q!{S}_{2}\left(P,q+1\right)=\left(q+1\right)!{S}_{2}\left(P-1,q+1\right)+q!{S}_{2}\left(P-1,q\right)\equiv 0\text{\hspace{0.17em}}MOD\text{\hspace{0.17em}}P\to ②$

q.e.d.

Chart of 5.6), ${F}_{M}^{M+N-1}={S}_{1}\left(N+M,N\right)$, ${E}_{M}^{N}={S}_{2}\left(N+M,N\right)$

5.9) ${\sum }_{n=1}^{P-1}{n}^{P-2}\equiv 0\text{\hspace{0.17em}}MOD\text{\hspace{0.17em}}{P}^{2},P>3$

[Proof]

[1] has obtained this, but its proof is incorrect.

$\begin{array}{l}{P}^{P-2}+{\sum }_{n=1}^{P-1}{n}^{P-2}={\sum }_{n=1}^{P-1}{n}^{P-2}=SUM\left(P,\left[1,\cdots ,1\right],\left[1,\cdots ,P-2\right]\right)\\ ={\sum }_{q=0}^{P-2}q!{S}_{2}\left(P-1,q+1\right)\left(\begin{array}{c}P\\ q+1\end{array}\right)={\sum }_{q=1}^{P-1}\left(q-1\right)!{S}_{2}\left(P-1,q\right)\left(\begin{array}{c}P\\ q\end{array}\right)\\ ={\sum }_{q=1}^{\frac{P-1}{2}}\left\{\left(q-1\right)!{S}_{2}\left(P-1,q\right)\left(\begin{array}{c}P\\ q\end{array}\right)+\left(p-q-1\right)!{S}_{2}\left(P-1,p-q\right)\left(\begin{array}{c}P\\ p-q\end{array}\right)\right\}\end{array}$

$\stackrel{5.8\right)-②}{\to }\equiv {\sum }_{q=1}^{\frac{P-1}{2}}\left[{\left(-1\right)}^{q+1}+{\left(-1\right)}^{P-q+1}\right]\left(\begin{array}{c}P\\ q\end{array}\right)$, this step of [1] is wrong

$\begin{array}{l}{\sum }_{n=1}^{P}{n}^{P-2}={\sum }_{q=1}^{P-1}\left(q-1\right)!{S}_{2}\left(P-1,q\right)\left(\begin{array}{c}P\\ q\end{array}\right)\\ =p{\sum }_{q=1}^{P-1}\frac{q!{S}_{2}\left(P-1,q\right)}{{q}^{2}}\left(\begin{array}{c}P-1\\ q-1\end{array}\right)\stackrel{5.8\right)-②}{\to }\end{array}$

$\left(q-1\right)!{S}_{2}\left(P-1,q\right)\left(\begin{array}{c}P\\ q\end{array}\right)\in ℕ\to \frac{q!{S}_{2}\left(P-1,q\right)}{{q}^{2}}\left(\begin{array}{c}P-1\\ q-1\end{array}\right)\in ℕ$

$\begin{array}{l}\frac{{\sum }_{n=1}^{P}{n}^{P-2}}{p}\equiv {\sum }_{q=1}^{P-1}\frac{{\left(-1\right)}^{q+1}}{{q}^{2}}\left(\begin{array}{c}P-1\\ q-1\end{array}\right)\stackrel{\left(\begin{array}{c}P-1\\ q-1\end{array}\right)\equiv {\left(-1\right)}^{q-1}}{\to }\\ \equiv {\sum }_{q=1}^{P-1}\frac{1}{{q}^{2}}\equiv {\sum }_{q=1}^{P-1}{q}^{2}\equiv 0\text{\hspace{0.17em}}MOD\text{\hspace{0.17em}}P\end{array}$

q.e.d.

6. Coefficient Matrix

$SUM\left(N,PS,PT\right)={\sum }_{q=0}^{M}{H}_{1}\left(q\right)\left(\begin{array}{c}N+{T}_{M}-M\\ N-1-q\end{array}\right)={\sum }_{q=0}^{M}{H}_{1}\left(q\right)\left(\begin{array}{c}N+{T}_{M}-M\\ {T}_{M}-M+1+q\end{array}\right)$

N starts from x to x + M, taking H1(q) as variables, then get a linear equations.

Let $P=x+{T}_{M}-M,Q=x-1$, each row from left to right, Q is from small to large

$\stackrel{{\text{Form}}_{\text{1}}}{\to }{A}_{1}\left(P,Q,M\right)=\left[\begin{array}{ccc}\left(\begin{array}{c}P\\ Q\end{array}\right)& \cdots & \left(\begin{array}{c}P\\ Q-M\end{array}\right)\\ ⋮& \ddots & ⋮\\ \left(\begin{array}{c}P+M\\ Q+M\end{array}\right)& \cdots & \left(\begin{array}{c}P+M\\ Q\end{array}\right)\end{array}\right]$

$\stackrel{{\text{Form}}_{\text{2}}}{\to }{A}_{2}\left(P,Q,M\right)=\left[\begin{array}{ccc}\left(\begin{array}{c}P\\ Q\end{array}\right)& \cdots & \left(\begin{array}{c}P+M\\ Q\end{array}\right)\\ ⋮& \ddots & ⋮\\ \left(\begin{array}{c}P+M\\ Q+M\end{array}\right)& \cdots & \left(\begin{array}{c}P+2M\\ Q+M\end{array}\right)\end{array}\right]$

$\stackrel{{\text{Form}}_{\text{3}}}{\to }{A}_{3}\left(P,Q,M\right)=\left[\begin{array}{ccc}\left(\begin{array}{c}P+M\\ Q\end{array}\right)& \cdots & \left(\begin{array}{c}P\\ Q-M\end{array}\right)\\ ⋮& \ddots & ⋮\\ \left(\begin{array}{c}P+2M\\ Q+M\end{array}\right)& \cdots & \left(\begin{array}{c}P+M\\ Q\end{array}\right)\end{array}\right]$

They are $\left(M+1\right)×\left(M+1\right)$ matrices

6.1) ① $‖{A}_{2}\left(P,Q,M\right)‖=\frac{\left(\begin{array}{c}P\\ Q\end{array}\right)}{\left(\begin{array}{c}P\\ 0\end{array}\right)}\frac{\left(\begin{array}{c}P+2\\ Q+1\end{array}\right)}{\left(\begin{array}{c}P+2\\ 1\end{array}\right)}\frac{\left(\begin{array}{c}P+4\\ Q+2\end{array}\right)}{\left(\begin{array}{c}P+4\\ 2\end{array}\right)}\cdots \frac{\left(\begin{array}{c}P+2M\\ Q+M\end{array}\right)}{\left(\begin{array}{c}P+2M\\ M\end{array}\right)}=‖{A}_{2}\left(P,P-Q,M\right)‖$

② Upper triangle: colq of ${A}_{2}\left(1,0,M\right)={\left[\left(\begin{array}{c}q\\ 0\end{array}\right),\left(\begin{array}{c}q\\ 1\end{array}\right),\left(\begin{array}{c}q\\ 2\end{array}\right),\cdots ,\left(\begin{array}{c}q\\ q\end{array}\right),\cdots \right]}^{\text{T}}$

[Proof]

$\begin{array}{l}{\text{Row}}_{M+1}:={\text{Row}}_{M+1}-{\text{Row}}_{M}\frac{P+M}{Q+M}\\ =\left[0\text{\hspace{0.17em}}\text{ }\frac{\left(\begin{array}{c}P+M+1\\ Q+M\end{array}\right)}{P+M+1}\frac{2\left(\begin{array}{c}P+M+2\\ Q+M\end{array}\right)}{P+M+2}\cdots \frac{M\left(\begin{array}{c}P+2M\\ Q+M\end{array}\right)}{P+2M}\right]\end{array}$

$\begin{array}{l}{\text{Row}}_{M}:={\text{Row}}_{M}-{\text{Row}}_{M-1}\frac{P+M-1}{Q+M-1}\\ =\left[0\text{\hspace{0.17em}}\text{ }\frac{\left(\begin{array}{c}P+M\\ Q+M-1\end{array}\right)}{P+M}\frac{2\left(\begin{array}{c}P+M+1\\ Q+M-1\end{array}\right)}{P+M+1}\cdots \frac{M\left(\begin{array}{c}P+2M-1\\ Q+M-1\end{array}\right)}{P+2M-1}\right]\end{array}$

$\cdots$

${\text{Row}}_{2}:={\text{Row}}_{2}-{\text{Row}}_{1}\frac{P+1}{Q+1}=\left[0\text{\hspace{0.17em}}\text{ }\frac{\left(\begin{array}{c}P+2\\ Q+1\end{array}\right)}{P+2}\frac{2\left(\begin{array}{c}P+3\\ Q+1\end{array}\right)}{P+3}\cdots \frac{M\left(\begin{array}{c}P+M+1\\ Q+1\end{array}\right)}{P+M+1}\right]$

Repeat the above process and change it into upper triangle.

$\frac{\left(\begin{array}{c}P\\ Q\end{array}\right)}{\left(\begin{array}{c}P\\ 0\end{array}\right)}\frac{\left(\begin{array}{c}P+1\\ Q\end{array}\right)}{\left(\begin{array}{c}P+1\\ 0\end{array}\right)}\frac{\left(\begin{array}{c}P+2\\ Q\end{array}\right)}{\left(\begin{array}{c}P+2\\ 0\end{array}\right)}\frac{\left(\begin{array}{c}P+3\\ Q\end{array}\right)}{\left(\begin{array}{c}P+3\\ 0\end{array}\right)}\cdots \frac{\left(\begin{array}{c}P+M\\ Q\end{array}\right)}{\left(\begin{array}{c}P+M\\ 0\end{array}\right)}$

$\frac{\left(\begin{array}{c}P+2\\ Q+1\end{array}\right)}{\frac{p+2}{1}}\frac{\left(\begin{array}{c}P+3\\ Q+1\end{array}\right)}{\frac{p+3}{2}}\frac{\left(\begin{array}{c}P+4\\ Q+1\end{array}\right)}{\frac{p+4}{3}}\cdots \frac{\left(\begin{array}{c}P+M+1\\ Q+1\end{array}\right)}{\frac{p+M+1}{M}}$

$\frac{\left(\begin{array}{c}P+4\\ Q+2\end{array}\right)}{\frac{\left(p+4\right)\left(p+3\right)}{2!}}\frac{\left(\begin{array}{c}P+5\\ Q+2\end{array}\right)}{\frac{\left(p+5\right)\left(p+4\right)}{3×2}}\cdots \frac{\left(\begin{array}{c}P+M+2\\ Q+2\end{array}\right)}{\frac{\left(p+M+2\right)\left(p+M+1\right)}{M\left(M-1\right)}}$

$\cdots$

when the original matrix is transformed into an upper triangular matrix,

${\text{Row}}_{K+1}:={\text{Row}}_{K+1}-{\text{Row}}_{K}\frac{P+K}{Q+K}$, repeat the operation K times.

q.e.d.

6.2) $‖{A}_{1}\left(P,Q,M\right)‖=‖{A}_{2}\left(P,Q,M\right)‖=‖{A}_{3}\left(P,Q,M\right)‖$

[Proof]

${A}_{2}\stackrel{{\text{Row}}_{i+1}:={\text{Row}}_{i+1}-{\text{Row}}_{i}\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}\text{repeat}}{\to }\text{change}\text{\hspace{0.17em}}\left({\text{row}}_{1},{\text{col}}_{1}\right)\text{\hspace{0.17em}}\text{to}\text{\hspace{0.17em}}\left( P Q \right)$

$\begin{array}{l}\left[\begin{array}{ccc}\left(\begin{array}{c}P\\ Q\end{array}\right)& \cdots & \left(\begin{array}{c}P+M\\ Q\end{array}\right)\\ ⋮& \ddots & ⋮\\ \left(\begin{array}{c}P\\ Q+M\end{array}\right)& \cdots & \left(\begin{array}{c}P+M\\ Q+M\end{array}\right)\end{array}\right]\stackrel{\text{transpose}}{\to }\\ \left[\begin{array}{ccc}\left(\begin{array}{c}P\\ Q\end{array}\right)& \cdots & \left(\begin{array}{c}P\\ Q+M\end{array}\right)\\ ⋮& \ddots & ⋮\\ \left(\begin{array}{c}P+M\\ Q\end{array}\right)& \cdots & \left(\begin{array}{c}P+M\\ Q+M\end{array}\right)\end{array}\right]={A}_{1}\left(P,P-Q,M\right)\end{array}$

${A}_{1}\stackrel{{\text{col}}_{i}:={\text{col}}_{i}+{\text{col}}_{i+1}\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}\text{repeat}\to }{\to }\text{change}\text{\hspace{0.17em}}\left({\text{row}}_{1},{\text{col}}_{1}\right)\text{\hspace{0.17em}}\text{to}\text{\hspace{0.17em}}\left(\begin{array}{c}P+M\\ Q\end{array}\right)={A}_{3}$

q.e.d.

Use $‖A‖$ for $‖{A}_{1,2,3}‖$.

6.3) $‖A\left(P,0,M\right)‖=1$,

$‖A\left(P,1,M\right)‖=\left(\begin{array}{c}P+M\\ 1+M\end{array}\right)$, $‖A\left(P,Q>0,M\right)‖={\prod }_{q=0}^{Q-1}\frac{\left(\begin{array}{c}P+M-q\\ 1+M\end{array}\right)}{\left(\begin{array}{c}1+M+q\\ 1+M\end{array}\right)}$

[Proof]

$\stackrel{6.1\right)}{\to }‖A\left(P,1,M\right)‖=\frac{P}{1}\frac{P+1}{2}\frac{P+2}{3}\cdots \frac{P+M}{M+1}=\left(\begin{array}{c}P+M\\ 1+M\end{array}\right)$

q.e.d.

${T}_{M}\ge M$, $N\in \left[1,M+1\right]$, then

Matrix of $SUM\left(N\right)=A\left(1+{T}_{M}-M,0,M\right)$, Matrix of $\nabla SUM\left(N\right)=A\left({T}_{M}-M,0,M\right)$

Use Cramer’s law, let $y\left(n\right)=SUM\left(N\right)$ or $\nabla SUM\left( N \right)$

${H}_{1}\left(q\right)=‖{A}_{1}\left(P,0,M\right)\stackrel{\text{replace}\text{\hspace{0.17em}}{\text{col}}_{q+1}}{\to }{\left[y\left(1\right),\cdots ,y\left(M+1\right)\right]}^{\text{T}}‖$

${A}_{1}\left(P,0,M\right)=\left[\begin{array}{ccc}\left(\begin{array}{c}P\\ 0\end{array}\right)& \cdots & 0\\ ⋮& \ddots & ⋮\\ \left(\begin{array}{c}P+M\\ M\end{array}\right)& \cdots & \left(\begin{array}{c}P+M\\ 0\end{array}\right)\end{array}\right]=\left[\begin{array}{ccc}1& \cdots & 0\\ ⋮& \ddots & ⋮\\ \left(\begin{array}{c}P+M\\ M\end{array}\right)& \cdots & 1\end{array}\right]$

when colq+1 replace with ${\left[y\left(1\right),\cdots \right]}^{\text{T}}$, calculate from colq+1, only $\left\{y\left(1\right),\cdots ,y\left(q+1\right)\right\}$ work.

From algebraic cofactor, y(k) corresponds to ${1}^{K-1}×‖{A}_{Tmp}‖×{1}^{M-q}$ count of rows of ${A}_{Tmp}=\left(M+1\right)-\left(K-1\right)-\left(M-q\right)-1=q-K+1$

$\left({\text{row}}_{k},{\text{col}}_{q+1}\right)=\left(\begin{array}{c}P+K-1\\ K-1-q\end{array}\right),\left(q+1\right)-\left(q-k+1\right)-1=k-1$

$\left({\text{row}}_{0},{\text{col}}_{0}\right)\text{\hspace{0.17em}}\text{of}\text{\hspace{0.17em}}{A}_{Tmp}=\left({\text{row}}_{k+1},{\text{col}}_{k-1}\right)=\left(\begin{array}{c}P+K\\ 1\end{array}\right)$

$‖{A}_{Tmp}‖=‖{A}_{1}\left(P+k,1,q-k\right)‖=\left(\begin{array}{c}P+q\\ q+1-k\end{array}\right)\to$

6.4) ${T}_{M}\ge M$, ${H}_{1}\left(q\right)=\left\{\begin{array}{l}{\sum }_{k=1}^{q+1}{\left(-1\right)}^{q+1+k}\left(\begin{array}{c}1+{T}_{M}-M+q\\ q+1-k\end{array}\right)SUM\left(k\right)\\ {\sum }_{k=1}^{q+1}{\left(-1\right)}^{q+1+k}\left(\begin{array}{c}{T}_{M}-M+q\\ q+1-k\end{array}\right)\nabla SUM\left( k \right)\end{array}$

$\nabla SUM\left(N,\left[1,\cdots ,1\right],\left[2,\cdots ,M\right]\right)={N}^{M}\to {A}_{1}\left(1,0,M-1\right)$

$\left(q+1\right)!{S}_{2}\left(M,q+1\right)={\sum }_{k=1}^{q+1}{\left(-1\right)}^{q+1+k}\left(\begin{array}{c}q+1\\ q+1-k\end{array}\right){k}^{M}$

$\to q!{S}_{2}\left(M,q\right)={\sum }_{k=0}^{q}{\left(-1\right)}^{q+k}\left(\begin{array}{c}q\\ q-k\end{array}\right){k}^{M}$

$x=q-k\to q!{S}_{2}\left(M,q\right)={\sum }_{x=0}^{q}{\left(-1\right)}^{x}\left(\begin{array}{c}q\\ x\end{array}\right){\left(q-x\right)}^{M}$,

this is a known formula.

$\begin{array}{l}SUM\left(N,\left[1,\cdots ,M\right],\left[1,\cdots ,M\right]\right)=\left(\begin{array}{c}M+N\\ M+1\end{array}\right)\\ \to \left(\begin{array}{c}M\\ q\end{array}\right)={\sum }_{k=0}^{q}{\left(-1\right)}^{k+q}\left(\begin{array}{c}q\\ k\end{array}\right)\left(\begin{array}{c}M+k\\ M+1\end{array}\right)\end{array}$

$\begin{array}{l}SUM\left(N,\left[2,3,\cdots ,M\right],\left[3,5,\cdots ,2M-1\right]\right)\\ \to MI{N}_{q-1}={\sum }_{k=0}^{q}{\left(-1\right)}^{k+q}\left(\begin{array}{c}M+q\\ q-k\end{array}\right){S}_{1}\left(k+M,k\right)\end{array}$

Similarly,

${A}_{3}\left(P,0,M\right)=\left[\begin{array}{ccc}\left(\begin{array}{c}P+M\\ 0\end{array}\right)& \cdots & 0\\ ⋮& \ddots & ⋮\\ \left(\begin{array}{c}P+2M\\ M\end{array}\right)& \cdots & \left(\begin{array}{c}P+M\\ 0\end{array}\right)\end{array}\right]=\left[\begin{array}{ccc}1& \cdots & 0\\ ⋮& \ddots & ⋮\\ \left(\begin{array}{c}P+2M\\ M\end{array}\right)& \cdots & 1\end{array}\right]\to$

y(k) corresponds to ${1}^{K-1}×‖{A}_{Tmp}‖×{1}^{M-q}$, count of rows of ${A}_{Tmp}=q-k+1$

$\left({\text{row}}_{k},{\text{col}}_{q+1}\right)=\left(\begin{array}{c}P+M+K-1-q\\ K-1-q\end{array}\right)$

$\left({\text{row}}_{0},{\text{col}}_{0}\right)\text{\hspace{0.17em}}\text{of}\text{\hspace{0.17em}}{A}_{Tmp}=\left({\text{row}}_{k+1},{\text{col}}_{k-1}\right)=\left(\begin{array}{c}P+M+1\\ 1\end{array}\right)$

$P+M+1-\left(q-k\right)=P+M+1-q+k$

$‖{A}_{Tmp}‖=‖{A}_{3}\left(P+M+1-q+K,1,q-k\right)‖=\left(\begin{array}{c}P+M+1\\ q+1-k\end{array}\right)\to$

6.5) ${T}_{M}\ge M$, ${H}_{3}\left(q\right)=\left\{\begin{array}{l}{\sum }_{k=1}^{q+1}{\left(-1\right)}^{q+1+k}\left(\begin{array}{c}2+{T}_{M}\\ q+1-k\end{array}\right)SUM\left(k\right)\\ {\sum }_{k=1}^{q+1}{\left(-1\right)}^{q+1+k}\left(\begin{array}{c}1+{T}_{M}\\ q+1-k\end{array}\right)\nabla SUM\left( k \right)\end{array}$

$\nabla SUM\left(N,\left[1,\cdots ,1\right],\left[2,\cdots ,M\right]\right)={N}^{M}\to {A}_{3}\left(1,0,M-1\right)\to$

$\begin{array}{l}〈\begin{array}{c}M\\ q\end{array}〉={\sum }_{k=1}^{q+1}{\left(-1\right)}^{q+k-1}\left(\begin{array}{c}M+1\\ q+1-k\end{array}\right){k}^{M}\\ \stackrel{x=q+1-k}{\to }{\sum }_{x=0}^{q}{\left(-1\right)}^{x}\left(\begin{array}{c}M+1\\ x\end{array}\right){\left(q+1-x\right)}^{M}\end{array}$

This is a known formula too.

$\stackrel{6.1\right)}{\to }{A}_{2}\left(1,0,M\right)=\left[\begin{array}{ccc}\left(\begin{array}{c}0\\ 0\end{array}\right)& \cdots & \left(\begin{array}{c}M\\ 0\end{array}\right)\\ ⋮& \ddots & ⋮\\ 0& \cdots & \left(\begin{array}{c}M\\ M\end{array}\right)\end{array}\right]$

In the algebraic cofactor, $\left({\text{row}}_{q+1},{\text{row}}_{q+2},\cdots ,{\text{row}}_{M+1}\right)$ will work.

RowK corresponds to ${1}^{q}×‖{A}_{Tmp}‖×{1}^{M+1-K}$ count of rows of ${A}_{Tmp}=\left(M+1\right)-q-\left(M+1-k\right)-1=k-q-1$

$\left({\text{row}}_{k},{\text{col}}_{q+1}\right)=\left(\begin{array}{c}q\\ k-1\end{array}\right),k-\left(k-q-1\right)=q+1$

$\left({\text{row}}_{0},{\text{col}}_{0}\right)\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{of}\text{\hspace{0.17em}}{A}_{Tmp}=\left({\text{row}}_{q+1},{\text{col}}_{q+2}\right)=\left(\begin{array}{c}q+1\\ q\end{array}\right)$

$‖{A}_{Tmp}‖=‖{A}_{2}\left(q+1,q,k-q-2\right)‖=‖{A}_{2}\left(q+1,1,k-q-2\right)‖=\left(\begin{array}{c}k-1\\ q\end{array}\right)$

It can be concluded by induction:

$\stackrel{6.1\right)}{\to }y\left(k\right)\text{\hspace{0.17em}}\text{willchangeto}\text{\hspace{0.17em}}z\left(k\right)={\sum }_{x=1}^{k}{\left(-1\right)}^{k-x}y\left(x\right)\left( K x \right)$

${H}_{2}\left(q\right)={\sum }_{k=q+1}^{M+1}{\left(-1\right)}^{q+k-1}\left(\begin{array}{c}k-1\\ q\end{array}\right)z\left( k \right)$

$\nabla SUM\left(N,\left[1,\cdots ,1\right],\left[2,\cdots ,M\right]\right)={N}^{M}\to Z\left(k\right)=k!{S}_{2}\left(M,k\right)\to$

$q!{S}_{2}\left(M,q\right)={\sum }_{k=q}^{M}{\left(-1\right)}^{M+k}\left(\begin{array}{c}k-1\\ q-1\end{array}\right)k!{S}_{2}\left(M,k\right)$, this matches 2.1)-②

7. ${\sum }_{n=0}^{N-1}{\prod }_{i=1}^{M}\left({K}_{i}+{D}_{i}{q}^{n}\right)$

We need an expression similar to $\left(\begin{array}{c}N\\ M\end{array}\right)$, which is Gaussian coefficient ${\left[\begin{array}{c}N\\ M\end{array}\right]}_{q}$

${\left[\begin{array}{c}N\\ M\end{array}\right]}_{q}=\frac{\left({q}^{N}-1\right)\left({q}^{N-1}-1\right)\cdots \left({q}^{N-\left(M-1\right)}-1\right)}{\left({q}^{M}-1\right)\left({q}^{M-1}-1\right)\cdots \left(q-1\right)},\text{\hspace{0.17em}}q\ne 1,\text{\hspace{0.17em}}{\left[\begin{array}{c}N\\ 0\end{array}\right]}_{q}=1,\text{\hspace{0.17em}}\text{Abbreviated}\text{\hspace{0.17em}}\text{as}\text{\hspace{0.17em}}\left[\begin{array}{c}N\\ M\end{array}\right]$

1) $\left[\begin{array}{c}N\\ M\end{array}\right]=\left[\begin{array}{c}N\\ M-q\end{array}\right]$

2) $\left[\begin{array}{c}N\\ M\end{array}\right]=\left[\begin{array}{c}N-1\\ M-1\end{array}\right]+{q}^{M}\left[\begin{array}{c}N-1\\ M\end{array}\right]$

7.1) ① ${\sum }_{n=0}^{N-1}{q}^{n}\left[\begin{array}{c}n+M\\ M\end{array}\right]=\left[\begin{array}{c}N+M\\ M+1\end{array}\right]$

${\sum }_{n=0}^{N-1}{q}^{n}\left[\begin{array}{c}n+K\\ M\end{array}\right]={q}^{M-K}\left[\begin{array}{c}N+K\\ M+1\end{array}\right];{\sum }_{n=0}^{N-1}{q}^{n}\left[\begin{array}{c}n\\ M\end{array}\right]={q}^{M}\left[\begin{array}{c}N\\ M+1\end{array}\right]$

[Proof]

When n = 0, ① is obviously true. Suppose it holds when N − 1,

$\begin{array}{l}{\sum }_{n=0}^{N}{q}^{n}\left[\begin{array}{c}n+M\\ M\end{array}\right]=\left[\begin{array}{c}N+M\\ M+1\end{array}\right]+{q}^{N}\left[\begin{array}{c}N+M\\ M\end{array}\right]\\ =\frac{\left({q}^{N+M}-1\right)\left({q}^{N+M-1}-1\right)\cdots \left({q}^{N}-1\right)}{\left({q}^{M+1}-1\right)\left({q}^{M}-1\right)\left({q}^{M-1}-1\right)\cdots \left(q-1\right)}+{q}^{N}\frac{\left({q}^{N+M}-1\right)\left({q}^{N+M-1}-1\right)\cdots \left({q}^{N+1}-1\right)}{\left({q}^{M}-1\right)\left({q}^{M-1}-1\right)\cdots \left(q-1\right)}\\ =\left[\begin{array}{c}N+M+1\\ M+1\end{array}\right]\end{array}$

${\sum }_{n=0}^{N-1}{q}^{n}\left[\begin{array}{c}n+K\\ M\end{array}\right]\stackrel{x=n+K-M}{\to }{q}^{M-K}{\sum }_{x=0}^{N-1+K-M}{q}^{x}\left[\begin{array}{c}x+M\\ M\end{array}\right]={q}^{M-K}\left[\begin{array}{c}N+K\\ M+1\end{array}\right]$

q.e.d.

${\sum }_{n=0}^{N-1}{q}^{n}=\frac{{q}^{N}-1}{q-1}=\left[\begin{array}{c}N\\ 1\end{array}\right]$

$\begin{array}{l}{\sum }_{n=0}^{N-1}{q}^{n}\left({K}_{1}+{D}_{1}{q}^{n}\right)={\sum }_{n=0}^{N-1}\left({q}^{n}\left({q}^{n}-1\right){D}_{1}+\left({K}_{1}+{D}_{1}\right){q}^{n}\right)\\ ={\sum }_{n=0}^{N-1}\left(q-1\right){q}^{n}\left[\begin{array}{c}N\\ 1\end{array}\right]{D}_{1}+\left({K}_{1}+{D}_{1}\right){q}^{n}\left[\begin{array}{c}N\\ 0\end{array}\right]\\ =q\left(q-1\right){D}_{1}\left[\begin{array}{c}N\\ 2\end{array}\right]+\left({K}_{1}+{D}_{1}\right)\left[\begin{array}{c}N\\ 1\end{array}\right]\end{array}$

$\begin{array}{l}{\sum }_{n=0}^{N-1}{q}^{n}\left({K}_{1}+{D}_{1}{q}^{n}\right)\left({K}_{2}+{D}_{2}{q}^{n}\right)\\ ={\sum }_{n=0}^{N-1}\left({D}_{1}{D}_{2}{q}^{3n}+\left({K}_{1}{D}_{2}+{K}_{2}{D}_{1}\right){q}^{2n}+{K}_{1}{K}_{2}{q}^{n}\right)\\ ={\sum }_{n=0}^{N-1}\left({D}_{1}{D}_{2}{q}^{2n}\left({q}^{n}-1\right)+\left({K}_{1}{D}_{2}+{K}_{2}{D}_{1}+{D}_{1}{D}_{2}\right){q}^{2n}+{K}_{1}{K}_{2}{q}^{n}\right)\\ ={\sum }_{n=0}^{N-1}\left[{D}_{1}{D}_{2}{q}^{n+1}\left({q}^{n}-1\right)\left({q}^{n-1}-1\right)+\left({K}_{1}{D}_{2}+{K}_{2}{D}_{1}+{D}_{1}{D}_{2}\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}+q{D}_{1}{D}_{2}\right){q}^{n}\left({q}^{n}-1\right)+\left({K}_{1}{K}_{2}+{K}_{1}{D}_{2}+{K}_{2}{D}_{1}+{D}_{1}{D}_{2}\right){q}^{n}\right]\end{array}$

$\begin{array}{l}={D}_{1}{D}_{2}{q}^{3}\left({q}^{2}-1\right)\left(q-1\right)\left[\begin{array}{c}N\\ 3\end{array}\right]+\left({K}_{1}{D}_{2}+{K}_{2}{D}_{1}+{D}_{1}{D}_{2}\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}+q{D}_{1}{D}_{2}\right)q\left(q-1\right)\left[\begin{array}{c}N\\ 2\end{array}\right]+\left({K}_{1}{K}_{2}+{K}_{1}{D}_{2}+{K}_{2}{D}_{1}+{D}_{1}{D}_{2}\right)\left[\begin{array}{c}N\\ 1\end{array}\right]\\ =q\left(q-1\right){D}_{1}×{q}^{2}\left({q}^{2}-1\right){D}_{2}\left[\begin{array}{c}N\\ 3\end{array}\right]+q\left(q-1\right)\left\{\left({K}_{1}+{D}_{1}\right){D}_{2}\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}+{D}_{1}\left({K}_{2}+q{D}_{2}\right)\right\}\left[\begin{array}{c}N\\ 2\end{array}\right]+\left({K}_{1}+{D}_{1}\right)\left({K}_{2}+{D}_{2}\right)\left[\begin{array}{c}N\\ 1\end{array}\right]\end{array}$

${T}_{i}$ is arbitrary, use the Form ${\prod }_{i=1}^{M}\left({K}_{i}+{T}_{i}\right)$, ${X}_{T}=\text{count}\text{\hspace{0.17em}}\text{of}\text{\hspace{0.17em}}\left\{{X}_{1},\cdots ,{X}_{i}\right\}\in T$

7.2) ${\sum }_{n=0}^{N-1}{q}^{n}{\prod }_{i=1}^{M}\left({K}_{i}+{D}_{i}{q}^{n}\right)={\sum }_{g=0}^{M}G\left(M,g\right)\left[\begin{array}{c}N\\ g+1\end{array}\right]$

$G\left(M,g\right)={\sum }_{\prod {X}_{i}\text{\hspace{0.17em}}\text{with}\text{\hspace{0.17em}}X\left(T\right)=g}{\prod }_{i=1}^{M}f\left( X i \right)$

$f\left({X}_{i}\right)=\left\{\begin{array}{l}{q}^{{X}_{T}}\left({q}^{{X}_{T}}-1\right){D}_{i};X\in T\\ {K}_{i}+{q}^{{X}_{T-1}}{D}_{i};X\in K\end{array}$

[Proof]

When M = 1, 2, it’s true. Let $G\left(q\right)=G\left(M,q\right)$

Suppose $F\left(N\right)={\sum }_{n=0}^{N-1}{q}^{n}{\prod }_{i=1}^{M}\left({K}_{i}+{D}_{i}{q}^{n}\right)={\sum }_{g=0}^{M}G\left(g\right)\left[\begin{array}{c}N\\ g+1\end{array}\right]\to$

$\begin{array}{c}{q}^{n}{\prod }_{i=1}^{M}\left({K}_{i}+{D}_{i}{q}^{n}\right)=F\left(n+1\right)-F\left(n\right)\\ ={\sum }_{g=0}^{M}G\left(g\right)\left\{\left[\begin{array}{c}n+1\\ g+1\end{array}\right]-\left[\begin{array}{c}n\\ g+1\end{array}\right]\right\}\\ ={\sum }_{g=0}^{M}G\left(g\right)\left\{\left({q}^{g+1}-1\right)\left[\begin{array}{c}n\\ g+1\end{array}\right]+\left[\begin{array}{c}n\\ g\end{array}\right]\right\}\end{array}$

$\begin{array}{l}{\sum }_{n=0}^{N-1}{q}^{n}{\prod }_{i=1}^{M+1}\left({K}_{i}+{D}_{i}{q}^{n}\right)\\ ={K}_{M+1}{\sum }_{n=0}^{N-1}{q}^{n}{\prod }_{i=1}^{M}\left({K}_{i}+{D}_{i}{q}^{n}\right)+{D}_{M+1}{\sum }_{n=0}^{N-1}{q}^{n}{\prod }_{i=1}^{M+1}\left({K}_{i}+{D}_{i}{q}^{n}\right){q}^{n}\\ ={K}_{M+1}{\sum }_{g=0}^{M}G\left(g\right)\left[\begin{array}{c}N\\ g+1\end{array}\right]+{D}_{M+1}{\sum }_{g=0}^{M}G\left(g\right){\sum }_{n=0}^{N-1}{q}^{n}\left\{\left({q}^{g+1}-1\right)\left[\begin{array}{c}n\\ g+1\end{array}\right]+\left[\begin{array}{c}n\\ g\end{array}\right]\right\}\end{array}$

$\begin{array}{l}\stackrel{7.1\right)}{\to }{\sum }_{g=0}^{M}G\left(g\right)\left({K}_{M+1}+{q}^{g}{D}_{M+1}\right)\left[\begin{array}{c}N\\ g+1\end{array}\right]\\ \text{ }+{\sum }_{g=0}^{M}G\left(g\right){q}^{g+1}\left({q}^{g+1}-1\right){D}_{M+1}\left[\begin{array}{c}N\\ g+2\end{array}\right]\\ ={\sum }_{g=0}^{M+1}G\left(M+1,g\right)\left[\begin{array}{c}N\\ g+1\end{array}\right]\end{array}$

q.e.d.

In the same way, use the Form = $\left({T}_{1}+{K}_{1}\right)\cdots \left({T}_{M}+{K}_{M}\right)$ :

7.3) ${\sum }_{n=0}^{N-1}{\prod }_{i=1}^{M}\left({K}_{i}+{D}_{i}{q}^{n}\right)={\sum }_{g=1}^{M}G\left(M,g\right)\left[\begin{array}{c}N\\ g\end{array}\right]+N{\prod }_{i=1}^{M}{K}_{i}$

$G\left(M,g\right)={\sum }_{\prod {X}_{i}\text{\hspace{0.17em}}\text{with}\text{\hspace{0.17em}}X\left(T\right)=g}{\prod }_{i=1}^{M}f\left( X i \right)$

$f\left({X}_{i}\right)=\left\{\begin{array}{l}1;X\in T,{X}_{T-1}=0\\ {q}^{{X}_{T-1}}\left({q}^{{X}_{T-1}}-1\right){D}_{i};X\in T,{X}_{T-1}>0\\ {K}_{i};X\in K,{X}_{T-1}=0\\ {K}_{i}+{q}^{{X}_{T-1}-1}{D}_{i};X\in K,{X}_{T-1}>0\end{array}$

7.4) $\frac{{q}^{MN}-1}{{q}^{M}-1}={\sum }_{g=1}^{M}\left({\prod }_{i=1}^{g-1}{q}^{i}\left({q}^{i}-1\right)\right)\left[\begin{array}{c}N\\ g\end{array}\right]\left[\begin{array}{c}M-1\\ M-g\end{array}\right]$

[Proof]

${\sum }_{n=0}^{N-1}{\prod }_{i=1}^{M}\left(0+{q}^{n}\right)={\sum }_{n=0}^{N-1}{q}^{Mn}=\frac{{q}^{MN}-1}{{q}^{M}-1}={\sum }_{g=1}^{M}G\left(M,g\right)\left[\begin{array}{c}N\\ g\end{array}\right]$

In $G\left(M,g\right)$, $\prod \left(X\in T\right)={\prod }_{i=1}^{g-1}{q}^{i}\left({q}^{i}-1\right)$, ${X}_{1}$ must be ${T}_{1}$, count of $\left(X\in K\right)=M-g$, $M-1$ positions can be placed.

In 1916 MacMahon [6] observed that $\left[\begin{array}{c}N\\ K\end{array}\right]={\sum }_{w\in \Omega \left(N,K\right)}{q}^{inv\left(w\right)}$, $\Omega \left(N,K\right)$ denotes all permutations of the multiset $\left\{{0}^{N-K},{1}^{K}\right\}$, that is, all words $w={w}_{1},\cdots ,{w}_{n}$

with n - k zeroes and k ones, and inv(・) denotes the inversion statistic defined by $inv\left({w}_{1},\cdots ,{w}_{n}\right)=|\left\{\left(i,j\right):1\le i{w}_{j}\right\}|$.

So in $G\left(M,g\right)$, $\sum \prod \left(X\in K\right)=\left[\begin{array}{c}M-1\\ M-g\end{array}\right]$

q.e.d.

7.5) ① ${\left(K+D\right)}^{M}={K}^{M}+D{\sum }_{g=0}^{M-1}{k}^{g}{\left(K+D\right)}^{M-g}$

$\begin{array}{c}{\left(K+q\right)}^{M}={K}^{M}+q{\sum }_{g=0}^{M-1}{k}^{g}{\left(K+1\right)}^{M-1-g}\\ \text{\hspace{0.17em}}\text{ }+q\left(q-1\right){\sum }_{a+b+c=M-2,a,b,c\ge 0}{k}^{a}{\left(K+1\right)}^{b}{\left(K+q\right)}^{c}\end{array}$

[Proof]

${\sum }_{n=0}^{0}{\prod }_{i=1}^{M}\left(K+D{q}^{n}\right)={K}^{M}+G\left(M,1\right)\left[\begin{array}{c}1\\ 1\end{array}\right]\to ①$

$\begin{array}{l}{\sum }_{n=0}^{1}{\prod }_{i=1}^{M}\left(K+{q}^{n}\right)-{\sum }_{n=0}^{0}{\prod }_{i=1}^{M}\left(K+{q}^{n}\right)\\ =2{K}^{M}+G\left(M,1\right)\left[\begin{array}{c}2\\ 1\end{array}\right]+G\left(M,2\right)\left[\begin{array}{c}2\\ 2\end{array}\right]-\left({K}^{M}+G\left(M,1\right)\left[\begin{array}{c}1\\ 1\end{array}\right]\right)\\ ={K}^{M}+G\left(M,1\right)\frac{\left({q}^{2}-1\right)}{\left(q-1\right)}+G\left(M,2\right)-\left({K}^{M}+G\left(M,1\right)\right)\to ②\end{array}$

q.e.d.

7.2) can be understood as use the Form = $\left({T}_{1}+{K}_{1}\right)\cdots \left({T}_{M}+{K}_{M}\right)$, $PT=\left[1,2,\cdots ,M\right]$

$f\left({X}_{i}\right)=\left\{\begin{array}{l}{q}^{{T}_{i}-{X}_{K-1}}\left({q}^{{T}_{i}-{X}_{K-1}}-1\right){D}_{i};{X}_{i}={T}_{i}\\ {K}_{i}+{q}^{{X}_{T-1}}{D}_{i};{X}_{i}={K}_{i}\end{array}$

But it can not be simply extended to something like 3.1).

8. ${\sum }_{n=0}^{N-1}{q}^{n}\left(\begin{array}{c}n+M\\ M\end{array}\right)$

8.1) ${\sum }_{n=0}^{N-1}{q}^{n}\left(\begin{array}{c}n+M\\ M\end{array}\right)={q}^{N}{\sum }_{g=0}^{M}{\left(-1\right)}^{g}\frac{\left(\begin{array}{c}N+M-1-g\\ M-g\end{array}\right)}{{\left(q-1\right)}^{g+1}}+\frac{{\left(-1\right)}^{M+1}}{{\left(q-1\right)}^{M+1}}$

[Proof]

$M=0,\text{\hspace{0.17em}}{\sum }_{n=0}^{N-1}{q}^{n}\left(\begin{array}{c}n\\ 0\end{array}\right)=\frac{{q}^{N}-1}{q-1}=\frac{{q}^{N}\left(\begin{array}{c}N-1\\ 0\end{array}\right)}{q-1}-\frac{1}{q-1},\text{\hspace{0.17em}}\text{holds}$

$\begin{array}{l}M=1,{\sum }_{n=0}^{N-1}{q}^{n}\left(\begin{array}{c}n+1\\ 1\end{array}\right)={\sum }_{n=0}^{N-1}{q}^{n}\left(n+1\right)\\ ={\sum }_{n=0}^{N-1}{q}^{n}+{\sum }_{n=1}^{N-1}{q}^{n}+\cdots +{\sum }_{n=N-1}^{N-1}{q}^{n}\\ =N{\sum }_{n=0}^{N-1}{q}^{n}-\left({\sum }_{n=0}^{0}{q}^{n}+{\sum }_{n=0}^{1}{q}^{n}+\cdots +{\sum }_{n=0}^{N-2}{q}^{n}\right)\\ =N\frac{{q}^{N}-1}{q-1}-\left(\frac{q-1}{q-1}+\frac{{q}^{2}-1}{q-1}+\cdots +\frac{{q}^{N-1}-1}{q-1}\right)\\ =N\frac{{q}^{N}-1}{q-1}-\frac{\left(1+q+{q}^{2}+\cdots +{q}^{N-1}\right)-N}{q-1}\\ =\frac{{q}^{N}N}{q-1}-\frac{{q}^{N}-1}{{\left(q-1\right)}^{2}}=\frac{{q}^{N}\left(\begin{array}{c}N\\ 1\end{array}\right)}{q-1}-\frac{{q}^{N}\left(\begin{array}{c}N\\ 0\end{array}\right)}{{\left(q-1\right)}^{2}}+\frac{1}{{\left(q-1\right)}^{2}},\text{\hspace{0.17em}}\text{holds}\end{array}$

Suppose it holds at M − 1; When M and N = 1, ${\sum }_{n=0}^{N-1}{q}^{n}\left(\begin{array}{c}n+M\\ M\end{array}\right)=1$

$\begin{array}{c}A={\sum }_{g=0}^{M}{\left(-1\right)}^{g}\frac{{q}^{N}\left(\begin{array}{c}N+M-1-g\\ M-g\end{array}\right)}{{\left(q-1\right)}^{g+1}}+\frac{{\left(-1\right)}^{M+1}}{{\left(q-1\right)}^{M+1}}\\ =\frac{q}{{\left(q-1\right)}^{1}}+\cdots +{\left(-1\right)}^{M}\frac{q}{{\left(q-1\right)}^{M+1}}+\frac{{\left(-1\right)}^{M+1}}{{\left(q-1\right)}^{M+1}}\end{array}$

${\left(q-1\right)}^{M+1}A=q\left\{{\left(q-1\right)}^{M}-{\left(q-1\right)}^{M-1}+\cdots +{\left(-1\right)}^{M-1}\right\}+{\left(-1\right)}^{M+1}$

$\stackrel{7.5\right)-②,K=-1}{\to }={\left(q-1\right)}^{M+1}\to A=1$ ; It holds when M and N = 1.

Suppose it holds at M and N

$\begin{array}{l}{\sum }_{n=0}^{N}{q}^{n}\left(\begin{array}{c}n+M\\ M\end{array}\right)={\sum }_{n=0}^{N}{q}^{n}\left\{\left(\begin{array}{c}n+M-1\\ M\end{array}\right)+\left(\begin{array}{c}n+M-1\\ M-1\end{array}\right)\right\}\\ =q{\sum }_{n=0}^{N-1}{q}^{n}\left(\begin{array}{c}n+M\\ M\end{array}\right)+{\sum }_{n=0}^{N}{q}^{n}\left(\begin{array}{c}n+M-1\\ M-1\end{array}\right)\\ ={\sum }_{g=0}^{M}{\left(-1\right)}^{g}\frac{{q}^{N+1}\left(\begin{array}{c}N+M-1-g\\ M-g\end{array}\right)}{{\left(q-1\right)}^{g+1}}+\frac{q{\left(-1\right)}^{M+1}}{{\left(q-1\right)}^{M+1}}\end{array}$

$\begin{array}{l}\text{\hspace{0.17em}}\text{\hspace{0.17em}}+{\sum }_{g=0}^{M-1}{\left(-1\right)}^{g}\frac{{q}^{N+1}\left(\begin{array}{c}N+M-1-g\\ M-1-g\end{array}\right)}{{\left(q-1\right)}^{g+1}}+\frac{{\left(-1\right)}^{M}}{{\left(q-1\right)}^{M}}\\ ={\sum }_{g=0}^{M}{\left(-1\right)}^{g}\frac{{q}^{N+1}\left(\begin{array}{c}\left(N+1\right)+M-1-g\\ M-g\end{array}\right)}{{\left(q-1\right)}^{g+1}}+\frac{{\left(-1\right)}^{M+1}}{{\left(q-1\right)}^{M+1}}\end{array}$

It holds when M and N + 1.

q.e.d.

Example 8.1

${\sum }_{n=0}^{N-1}{q}^{n}\left(\begin{array}{c}n\\ 0\end{array}\right)=\frac{{q}^{N}}{q-1}-\frac{1}{q-1}$

${\sum }_{n=0}^{N-1}{q}^{n}\left(\begin{array}{c}n+1\\ 1\end{array}\right)=\frac{{q}^{N}\left(\begin{array}{c}N\\ 1\end{array}\right)}{q-1}-\frac{{q}^{N}}{{\left(q-1\right)}^{2}}+\frac{1}{{\left(q-1\right)}^{2}}$

${\sum }_{n=0}^{N-1}{q}^{n}\left(\begin{array}{c}n+2\\ 2\end{array}\right)=\frac{{q}^{N}\left(\begin{array}{c}N+1\\ 2\end{array}\right)}{q-1}-\frac{{q}^{N}\left(\begin{array}{c}N\\ 1\end{array}\right)}{{\left(q-1\right)}^{2}}+\frac{{q}^{N}}{{\left(q-1\right)}^{3}}-\frac{1}{{\left(q-1\right)}^{3}}$

8.2) ${\sum }_{n=0}^{N-1}{q}^{n}\left(\begin{array}{c}n+M-K\\ M\end{array}\right)={q}^{N}{\sum }_{g=0}^{M}{\left(-1\right)}^{g}\frac{\left(\begin{array}{c}N-K+M-1-g\\ M-g\end{array}\right)}{{\left(q-1\right)}^{g+1}}+\frac{{\left(-1\right)}^{M+1}{q}^{K}}{{\left(q-1\right)}^{M+1}}$, $N\ge 1+K$

[Proof]

$\begin{array}{l}{\sum }_{n=0}^{N-1}{q}^{n}\left(\begin{array}{c}n+M-K\\ M\end{array}\right)={\sum }_{n=k}^{N-1}{q}^{n}\left(\begin{array}{c}n+M-K\\ M\end{array}\right)={q}^{K}{\sum }_{n=0}^{N-1-K}{q}^{n}\left(\begin{array}{c}n+M\\ M\end{array}\right)\\ ={q}^{K}\left\{{q}^{N-K}{\sum }_{g=0}^{M}{\left(-1\right)}^{g}\frac{\left(\begin{array}{c}N-K+M-1-g\\ M-g\end{array}\right)}{{\left(q-1\right)}^{g+1}}+\frac{{\left(-1\right)}^{M+1}}{{\left(q-1\right)}^{M+1}}\right\}\end{array}$

q.e.d.

$\to {\sum }_{n=0}^{N-1}{q}^{n}\left(\begin{array}{c}n\\ M\end{array}\right)={q}^{N}{\sum }_{g=0}^{M}{\left(-1\right)}^{g}\frac{\left(\begin{array}{c}N-1-g\\ M-g\end{array}\right)}{{\left(q-1\right)}^{g+1}}+\frac{{\left(-1\right)}^{M+1}{q}^{M}}{{\left(q-1\right)}^{M+1}},N\ge 1+M$

$\to {\sum }_{n=0}^{N-1}{q}^{n}\left(\begin{array}{c}n+M-1\\ M\end{array}\right)={q}^{N}{\sum }_{g=0}^{M}{\left(-1\right)}^{g}\frac{\left(\begin{array}{c}N+M-2-g\\ M-g\end{array}\right)}{{\left(q-1\right)}^{g+1}}+\frac{{\left(-1\right)}^{M+1}q}{{\left(q-1\right)}^{M+1}},N\ge 2$

$\to {\sum }_{n=0}^{N-1}{q}^{n}\left(\begin{array}{c}n-1\\ M\end{array}\right)={q}^{N}{\sum }_{g=0}^{M}{\left(-1\right)}^{g}\frac{\left(\begin{array}{c}N-2-g\\ M-g\end{array}\right)}{{\left(q-1\right)}^{g+1}}+\frac{{\left(-1\right)}^{M+1}{q}^{M+1}}{{\left(q-1\right)}^{M+1}},N\ge 2+M$

9. ${\sum }_{n=0}^{N-1}{q}^{n}{n}^{M}$

Define ${A}_{q}^{M}={\sum }_{k=0}^{M}{\left(1-q\right)}^{M-k}{q}^{K}{S}_{2}\left(M,k\right)k!,\text{\hspace{0.17em}}q\ne 0,1,\text{\hspace{0.17em}}M\ge 0$

${A}_{2}^{M}=1,2,6,26,150,1082,9366,\cdots$ http://oeis.org/A000629

${A}_{3}^{M}=1,3,12,66,480,4368,47712,\cdots$ http://oeis.org/A123227

${A}_{4}^{M}=1,4,20,132,1140,12324,160020,\cdots$ http://oeis.org/A201355

${A}_{q}^{0}=1,{A}_{q}^{1}=q$

${n}^{M}=\nabla SUM\left(n,\left[1,\cdots ,1\right]\left[2,\cdots ,M\right]\right)\stackrel{{\text{Form}}_{\text{1}}}{\to }{\sum }_{K=0}^{M}k!{S}_{2}\left(M,k\right)\left( n K \right)$

${\nabla }^{g}{\left(N-1\right)}^{M}={\sum }_{K=g}^{M}k!{S}_{2}\left(M,k\right)\left(\begin{array}{c}N-1-g\\ K-g\end{array}\right)$.

9.1) ${\sum }_{n=0}^{N-1}{q}^{n}{n}^{M}=\frac{{q}^{N}}{{\left(q-1\right)}^{M+1}}{\sum }_{g=0}^{M}{\left(q-1\right)}^{M-g}{\left(-1\right)}^{g}{▽}^{g}{\left(N-1\right)}^{M}+\frac{{\left(-1\right)}^{M+1}{A}_{q}^{M}}{{\left(q-1\right)}^{M+1}}$

[Proof]

${\sum }_{n=0}^{N-1}{q}^{n}{n}^{0}=\frac{{q}^{N}}{q-1}-\frac{1}{q-1},\text{\hspace{0.17em}}\text{holds}$

$\begin{array}{c}{\sum }_{n=0}^{N-1}{q}^{n}{n}^{1}={\sum }_{n=0}^{N-1}{q}^{n}\left(\begin{array}{c}n\\ 1\end{array}\right)={q}^{N}{\sum }_{g=0}^{1}{\left(-1\right)}^{g}\frac{\left(\begin{array}{c}N-1-g\\ 1-g\end{array}\right)}{{\left(q-1\right)}^{g+1}}+\frac{q}{{\left(q-1\right)}^{2}}\\ =\frac{{q}^{N}\left(N-1\right)}{{\left(q-1\right)}^{1}}-\frac{{q}^{N}}{{\left(q-1\right)}^{2}}+\frac{q}{{\left(q-1\right)}^{2}}\\ =\frac{{q}^{N}}{{\left(q-1\right)}^{2}}\left(\left(q-1\right){\left(N-1\right)}^{1}-1\right)+\frac{{A}_{q}^{1}}{{\left(q-1\right)}^{2}},\text{\hspace{0.17em}}\text{holds}\end{array}$

$\begin{array}{l}{\sum }_{n=0}^{N-1}{q}^{n}{n}^{M}={\sum }_{n=0}^{N-1}{q}^{n}{\sum }_{K=0}^{M}k!{S}_{2}\left(M,k\right)\left(\begin{array}{c}n\\ K\end{array}\right)\\ ={\sum }_{K=0}^{M}K!{S}_{2}\left(M,K\right)\left\{{q}^{N}{\sum }_{g=0}^{k}{\left(-1\right)}^{g}\frac{\left(\begin{array}{c}N-1-g\\ k-g\end{array}\right)}{{\left(q-1\right)}^{g+1}}+\frac{{\left(-1\right)}^{k+1}{q}^{k}}{{\left(q-1\right)}^{k+1}}\right\}\end{array}$

$\begin{array}{l}{\sum }_{K=0}^{M}K!{S}_{2}\left(M,K\right){q}^{k}\frac{{\left(-1\right)}^{K+1}}{{\left(q-1\right)}^{K+1}}\\ =\frac{{\left(-1\right)}^{M+1}}{{\left(q-1\right)}^{M+1}}{\sum }_{K=0}^{M}K!{S}_{2}\left(M,K\right){q}^{k}{\left(q-1\right)}^{M-K}{\left(-1\right)}^{-\left(M-K\right)}=\frac{{\left(-1\right)}^{M+1}{A}_{q}^{M}}{{\left(q-1\right)}^{M+1}}\end{array}$

$\begin{array}{l}{\sum }_{K=0}^{M}K!{S}_{2}\left(M,K\right){q}^{N}{\sum }_{g=0}^{k}{\left(-1\right)}^{g}\frac{\left(\begin{array}{c}N-1-g\\ k-g\end{array}\right)}{{\left(q-1\right)}^{g+1}}=\frac{{q}^{N}\left(...\right)}{{\left(q-1\right)}^{M+1}}\\ =\frac{{q}^{N}}{{\left(q-1\right)}^{M+1}}{\sum }_{K=0}^{M}k!{S}_{2}\left(M,k\right){\sum }_{g=0}^{k}{\left(-1\right)}^{g}\left(\begin{array}{c}N-1-g\\ K-g\end{array}\right){\left(q-1\right)}^{M-g}\end{array}$

$\begin{array}{c}\left(...\right)=K!{S}_{2}\left(M,M\right)\left\{\left(\begin{array}{c}N-1\\ M\end{array}\right){\left(q-1\right)}^{M}-\left(\begin{array}{c}N-2\\ M-1\end{array}\right){\left(q-1\right)}^{M-1}+\cdots +{\left(-1\right)}^{M}\left(\begin{array}{c}N-1-M\\ 0\end{array}\right)\right\}\\ \text{\hspace{0.17em}}+K!{S}_{2}\left(M,M-1\right)\left\{\left(\begin{array}{c}N-1\\ M-1\end{array}\right){\left(q-1\right)}^{M}-\left(\begin{array}{c}N-2\\ M-2\end{array}\right){\left(q-1\right)}^{M-1}+\cdots \right\}+\cdots \\ \text{\hspace{0.17em}}+K!{S}_{2}\left(M,0\right)\left\{\left(\begin{array}{c}N-1\\ 0\end{array}\right){\left(q-1\right)}^{M}\right\}\end{array}$

$\text{Verticalcalculation}={\left(q-1\right)}^{M}{\nabla }^{0}{\left(N-1\right)}^{M}-{\left(q-1\right)}^{M-1}{\nabla }^{1}{\left(N-1\right)}^{M}\cdots$

q.e.d.

9.2) ${A}_{q}^{M}=q{\sum }_{k=0}^{M}{\left(q-1\right)}^{M-k}{S}_{2}\left(M,k\right)k!,M>0$

[Proof]

$\begin{array}{l}{n}^{M}=\nabla SUM\left(n,\left[1,\cdots ,1\right]\left[1,\cdots ,M\right]\right)\\ \stackrel{{\text{Form}}_{\text{2}}}{\to }{\sum }_{K=0}^{M}{\left(-1\right)}^{M-K}K!{S}_{2}\left(M,K\right)\left(\begin{array}{c}n+K-1\\ K\end{array}\right)\end{array}$

$\begin{array}{l}{\sum }_{n=0}^{N-1}{q}^{n}{n}^{M}={\sum }_{n=0}^{N-1}{q}^{n}{\sum }_{K=0}^{M}{\left(-1\right)}^{M-K}K!{S}_{2}\left(M,K\right)\left(\begin{array}{c}n+K-1\\ K\end{array}\right)\\ ={\sum }_{K=0}^{M}{\left(-1\right)}^{M-K}K!{S}_{2}\left(M,K\right)\left\{{q}^{N}{\sum }_{g=0}^{K}{\left(-1\right)}^{g}\frac{\left(\begin{array}{c}N+K-2-g\\ K-g\end{array}\right)}{{\left(q-1\right)}^{g+1}}+\frac{{\left(-1\right)}^{K+1}q}{{\left(q-1\right)}^{K+1}}\right\}\end{array}$

$\begin{array}{l}{\sum }_{K=0}^{M}{\left(-1\right)}^{M-K}K!{S}_{2}\left(M,K\right){\sum }_{g=0}^{K}{\left(-1\right)}^{g}\frac{{q}^{N}\left(\begin{array}{c}N+K-2-g\\ K-g\end{array}\right)}{{\left(q-1\right)}^{g+1}}\stackrel{\text{Samewayas}\text{\hspace{0.17em}}9.1\right)}{\to }\\ =\frac{{q}^{N}}{{\left(q-1\right)}^{M+1}}{\sum }_{g=0}^{M}{\left(q-1\right)}^{M-g}{\left(-1\right)}^{g}{\nabla }^{g}{\left(N-1\right)}^{M}\end{array}$

Compare with 9.1) $\to {\sum }_{K=0}^{M}{\left(-1\right)}^{M-K}K!{S}_{2}\left(M,K\right)\frac{{\left(-1\right)}^{K+1}q}{{\left(q-1\right)}^{K+1}}=\frac{{\left(-1\right)}^{M+1}{A}_{q}^{M}}{{\left(q-1\right)}^{M+1}}$

q.e.d.

${n}^{M}=\nabla SUM\left(n,\left[1,\cdots ,1\right]\left[1,\cdots ,M\right]\right)\stackrel{{\text{Form}}_{\text{1}}}{\to }{\sum }_{K=0}^{M}k!{S}_{2}\left(M+1,k+1\right)\left(\begin{array}{c}n-1\\ K\end{array}\right)\to$

9.3) ${A}_{q}^{M}={\sum }_{k=0}^{M}{\left(1-q\right)}^{M-k}{q}^{K+1}{S}_{2}\left(M+1,k+1\right)k!,\text{\hspace{0.17em}}M>0$

9.4) ${\nabla }^{g}{\left(N-1\right)}^{M}={\sum }_{k=0}^{M-g}{\left(-1\right)}^{M-g-k}\left(\begin{array}{c}M\\ k\end{array}\right){N}^{K}{S}_{2}\left(M-K+1,g+1\right)g!$

[Proof]

$\begin{array}{l}{S}_{2}\left(M,g\right)=\frac{1}{g!}{\sum }_{k=0}^{g}{\left(-1\right)}^{k}\left(\begin{array}{c}g\\ k\end{array}\right){\left(g-k\right)}^{M}\\ \stackrel{j=g-k}{\to }=\frac{1}{g!}{\sum }_{j=0}^{g}{\left(-1\right)}^{g-j}\left(\begin{array}{c}g\\ j\end{array}\right){j}^{M}=\frac{1}{\left(g-1\right)!}{\sum }_{j=1}^{g}{\left(-1\right)}^{g-j}\left(\begin{array}{c}g-1\\ j-1\end{array}\right){j}^{M-1}\\ =\frac{1}{\left(g-1\right)!}{\sum }_{j=0}^{g-1}{\left(-1\right)}^{g-1-j}\left(\begin{array}{c}g-1\\ j\end{array}\right){\left(j+1\right)}^{M-1}\end{array}$

$\begin{array}{l}{\nabla }^{g}{\left(N-1\right)}^{M}\stackrel{\text{Bydefinition}}{\to }{\sum }_{j=0}^{g}{\left(-1\right)}^{j}\left(\begin{array}{c}g\\ j\end{array}\right){\left(N-j-1\right)}^{M}\\ ={\sum }_{j=0}^{g}{\left(-1\right)}^{j}\left(\begin{array}{c}g\\ j\end{array}\right){\sum }_{K=0}^{M}\left(\begin{array}{c}M\\ k\end{array}\right){N}^{k}{\left(j+1\right)}^{M-k}{\left(-1\right)}^{M-K}\\ ={\sum }_{k=0}^{M}{\left(-1\right)}^{M-k}\left(\begin{array}{c}M\\ k\end{array}\right){N}^{k}\left({\sum }_{j=0}^{g}{\left(-1\right)}^{j}\left(\begin{array}{c}g\\ j\end{array}\right){\left(j+1\right)}^{M-K}\right)\\ ={\sum }_{k=0}^{M}{\left(-1\right)}^{M-k-g}\left(\begin{array}{c}M\\ k\end{array}\right){N}^{k}\left({\sum }_{j=0}^{g}{\left(-1\right)}^{g+j}\left(\begin{array}{c}g\\ j\end{array}\right){\left(j+1\right)}^{M-K}\right)\\ ={\sum }_{k=0}^{M}{\left(-1\right)}^{M-k-g}\left(\begin{array}{c}M\\ k\end{array}\right){N}^{K}{S}_{2}\left(M-K+1,g+1\right)g!\end{array}$

q.e.d.

9.5) ① ${A}_{q}^{M}={\sum }_{k=0}^{M}{\left(q-1\right)}^{M-k}{S}_{2}\left(M+1,k+1\right)k!$

${\sum }_{n=0}^{N-1}{q}^{n}{n}^{M}=\frac{{q}^{N}}{{\left(q-1\right)}^{M+1}}{\sum }_{g=0}^{M}{\left(-1\right)}^{M-g}{A}_{q}^{M-g}\left(\begin{array}{c}M\\ g\end{array}\right){\left(q-1\right)}^{g}{N}^{g}+\frac{{\left(-1\right)}^{M+1}{A}_{q}^{M}}{{\left(q-1\right)}^{M+1}}$

[Proof]

$\begin{array}{c}f\left(N\right)={\sum }_{n=0}^{N-1}{q}^{n}{n}^{M}=\frac{{q}^{N}}{{\left(q-1\right)}^{M+1}}\left\{\dots \right\}+\frac{{\left(-1\right)}^{M+1}{A}_{q}^{M}}{{\left(q-1\right)}^{M+1}}\\ =\frac{{q}^{N}}{{\left(q-1\right)}^{M+1}}\left\{{\sum }_{g=0}^{M}{\left(q-1\right)}^{M-g}{\left(-1\right)}^{g}{\nabla }^{g}{\left(N-1\right)}^{M}\right\}+\frac{{\left(-1\right)}^{M+1}{A}_{q}^{M}}{{\left(q-1\right)}^{M+1}}\end{array}$

$\begin{array}{l}\left\{\dots \right\}\stackrel{9.4\right)}{\to }\\ ={\sum }_{g=0}^{M}{\left(q-1\right)}^{M-g}{\left(-1\right)}^{g}{\sum }_{k=0}^{M-g}{\left(-1\right)}^{M-g-k}\left(\begin{array}{c}M\\ k\end{array}\right){N}^{K}{S}_{2}\left(M-K+1,g+1\right)g!\\ ={\sum }_{g=0}^{M}{\left(q-1\right)}^{M-g}{\sum }_{k=0}^{M-g}{\left(-1\right)}^{M-k}\left(\begin{array}{c}M\\ k\end{array}\right){N}^{K}{S}_{2}\left(M-K+1,g+1\right)g!\\ ={\left(q-1\right)}^{M}\left\{{\left(-1\right)}^{M}\left(\begin{array}{c}M\\ 0\end{array}\right){N}^{0}{S}_{2}\left(M+1,1\right)0!\text{\hspace{0.17em}}+{\left(-1\right)}^{M-1}\left(\begin{array}{c}M\\ 1\end{array}\right){N}^{1}{S}_{2}\left(M,1\right)0!\text{\hspace{0.17em}}+\cdots \right\}\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}+{\left(q-1\right)}^{M-1}\left\{{\left(-1\right)}^{M}\left(\begin{array}{c}M\\ 0\end{array}\right){N}^{0}{S}_{2}\left(M+1,2\right)1!\text{\hspace{0.17em}}+{\left(-1\right)}^{M-1}\left(\begin{array}{c}M\\ 1\end{array}\right){N}^{1}{S}_{2}\left(M,2\right)1!\text{\hspace{0.17em}}+\cdots \right\}\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}+\cdots +{\left(q-1\right)}^{0}\left\{{\left(-1\right)}^{M}\left(\begin{array}{c}M\\ 0\end{array}\right){N}^{0}{S}_{2}\left(M+1,M+1\right)M!\right\}\end{array}$

Arrange by Ng

$={\sum }_{g=0}^{M}{\left(q-1\right)}^{g}{N}^{g}\left(\begin{array}{c}M\\ g\end{array}\right){\left(-1\right)}^{M-g}{\sum }_{k=0}^{M-g}{\left(q-1\right)}^{M-g-k}{S}_{2}\left(M-g+1,k+1\right)k!$

take