Shape of Numbers and Calculation Formula of Stirling Numbers

Ji Peng

Department of Electronic Information, Nanjing University, Nanjing, China.

DOI: 10.4236/oalib.1106081                

Abstract

This article investigated the idea of Shape of numbers and introduced new operators. The idea divides all products of k distinct integers in [1, n - 1] into 2^K-1 catalogs and derives the calculation formula of every catalog. As a simple deduction, a direct formula of the Stirling numbers of the first kind S1(n, n - k) and a simple recursive formula of Stirling numbers of the second kind S2(n, n - k) are obtained. By analyzing the Shape of numbers, new congruence formulas are obtained.

Keywords

Combinatorics, Shape of Numbers, Stirling Numbers, Congruence Formula

1. Introduction

In combinatorial mathematics, Stirling numbers refer to two kinds of numbers [1] : the first and the second. The first kind of Stirling number represents the number of M circles arranged by N different elements. The second kind of Stirling number represents the number of schemes to split N different elements into M sets. Many papers have researched the general calculation formula of the first Stirling number S1(n, n − k) and the second Stirling number S2(n, n − k), but general results are not obtained.

This article originate from the solution of the sum of all products of k distinct integers in [1, n − 1] without using combination counting.

2. Shape of Numbers

$C\left(N,M\right)$ is binomial coefficient, Integral polynomial can be expressed as $f\left(n\right)={\displaystyle \sum K_i*C\left(n,m_i\right)}$ [2]. Here K_i is the coefficient, m_i is the exponent.

Definition 2.1 operator:

$L_{A}C\left(N,M\right)=M*C\left(N,M+1\right)$, $L_{B}C\left(N,M\right)=\left(M+1\right)*C\left(N,M+2\right)$

It is easy to prove that different operators do not satisfy the commutative law, and the same operator can be written in the form of power.

$L_B\left(L_{A}C\left(N,M\right)\right)=L_B\left(M*C\left(N,M+1\right)\right)=\left(M+2\right)*M*C\left(N,M+3\right)$

$\begin{array}{c}{L}_A\left(L_{B}C\left(N,M\right)\right)=L_A\left(\left(M+1\right)*C\left(N,M+2\right)\right)\\ =\left(M+2\right)*\left(M+1\right)*C\left(N,M+3\right)\end{array}$

$L_A^{2}C\left(N,M\right)=M*\left(M+1\right)*C\left(N,M+2\right)$

$L_B^{2}C\left(N,M\right)=\left(M+1\right)*\left(M+3\right)*C\left(N,M+4\right)$

$L_A\left(L_A^{2}C\left(N,M\right)\right)=M*\left(M+1\right)*\left(M+2\right)*C\left(N,M+3\right)=L_A^2\left(L_{A}C\left(N,M\right)\right)$

$\begin{array}{c}{L}_B\left(L_B^{2}C\left(N,M\right)\right)=\left(M+1\right)*\left(M+3\right)*\left(M+5\right)*C\left(N,M+6\right)\\ =L_B^2\left(L_{B}C\left(N,M\right)\right)\end{array}$

Definition 2.2: Let $f\left(n\right)={\displaystyle \sum K_i*C\left(n,m_i\right)}$, then $L_{A}f\left(n\right)={\displaystyle \sum K_i*L_{A}C\left(n,m_i\right)}$, $L_{B}f\left(n\right)={\displaystyle \sum K_i*L_{B}C\left(n,m_i\right)}$.

Easy to prove:

$C\left(N,M+1\right)={\displaystyle {\sum }_{n=0}^{N-1}C\left(n,M\right)}$ [1] (1)

${\displaystyle {\sum }_{n=0}^{N-1}M*C\left(n,M\right)}=L_{A}C\left(N,M\right)$ (2)

${\displaystyle {\sum }_{n=0}^{N-1}\left(n-M\right)*C\left(n,M\right)}=L_{B}C\left(N,M\right)$ (3)

${\displaystyle {\sum }_{n=0}^{N-1}n*C\left(n-1,M\right)}=L_{B}C\left(N,M\right)$ (4)

${\displaystyle {\sum }_{n=0}^{N-1}n*f\left(n\right)}=L_{A}f\left(n\right)+L_{B}f\left(n\right)$ (5)

Proof:

Let $f\left(n\right)={\displaystyle \sum K_i*C\left(n,m_i\right)}$

$\begin{array}{l}{\displaystyle {\sum }_{n=0}^{N-1}n*f\left(n\right)}\\ ={\displaystyle \sum K_i}*{\displaystyle {\sum }_{n=0}^{N-1}{m}_i*C\left(n,m_i\right)}+{\displaystyle \sum K_i}*{\displaystyle {\sum }_{n=0}^{N-1}\left(n-m_i\right)*C\left(n,m_i\right)}\\ =L_{A}f\left(n\right)+L_{B}f(n)\end{array}$

Definition 2.3: An unordered pair of M different positive integers ( $K_1,K_2,\cdots ,K_m$ ), sort K_i from small to large, there are M − 1 intervals between adjacent numbers. Use A for continuity and B for discontinuity, record as a string of M − 1 characters (for example: AABB...) to represents a catalog, define collection of all catalogs as Shape of numbers. Use the symobl PX represent a catelog (if M = 1 then PX = 1). The single ( $K_1,K_2,\cdots ,K_m$ ) is a Item, $K_1*K_2*\cdots *K_m$ is the product of a item, K_i is called the factor.

For example:

(1, 2, 4) have 2 intervals, the number 1 and 2 is continuous, 2 and 4 is discontinuous, then PX = AB;

(200, 213, 600, 601) have 3 intervals, 200 and 213 is discontinuous, 600 and 601 is continuous, then PX = BBA;

(1, 2, 5, 6), (2, 3, 6, 7), (20, 21, 60, 61) PX = ABA; (1, 3, 5), (1, 3, 6), (2, 4, 6), (200, 401, 678) PX = BB.

Definition 2.4:

PM = Count of numbers in PX, PA = Count of A in PX, PB = Count of B in PX

Obviously, $PM=PA+PB+1$

|PX| = Count of items belonging to PX

MIN(PX) = Minimum product of PX, for example: $MIN\left(AA\right)=1*2*3$, $MIN\left(AB\right)=1*2*4$

IDX(PX) = 2 + PA + 2 * PB = PM + PB + 1, for example: $IDX\left(AA\right)=4$, $IDX\left(AB\right)=5$

SUM(N, PX) = Sum of all the product of items belonging to PX in $\left[1,N-1\right]$, for example: $SUM\left(6,AB\right)=1*2*4+1*2*5+2*3*5$

END(N, PX) = Set of items belonging to PX with the maximum factor N − 1

For example: $END\left(6,B\right)=\left\{\left(1,5\right),\left(2,5\right),\left(3,5\right)\right\}$

Obviously:

$END\left(IDX,PX\right)=\left\{MIN\right\}$, the minimum factor of MIN(PX) is 1, the maximum factor of MIN(PX) is IDX(PX) − 1.

Easy to prove: $SUM\left(N,1\right)=C\left(N,2\right)$ ; $SUM\left(N,A\right)=1*2*C\left(N,3\right)$ ; $SUM\left(N,B\right)=1*3*C\left(N,4\right)$

Definition 2.5:

PX + A = Attach A at PX tail

PX + B = Attach B at PX tail

PX − 1 = Remove the tail of PX

PX − A = PX ends with A and remove the tail

PX − B = PX ends with B and remove the tail

For example: $AB+A=ABA$, $AB+B=ABB$, $ABA-A=ABB-B=AB$, it is meaningless to $ABA-B$, $ABB-A$.

Definition 2.6 short form:

$Idx=IDX\left(PX\right)$, $IdxA=IDX\left(PX+A\right)$, $IdxB=IDX\left(PX+B\right)$,

$Min=MIN\left(PX\right)$, $MinA=MIN\left(PX+A\right)$, $MinB=MIN\left(PX+B\right)$

From definition:

$MinA=Min*Idx$ (6)

$MinB=Min*\left(Idx+1\right)$ (7)

$\sum END\left(N,PX+A\right)=\left(N-1\right)*\sum END\left(N-1,PX\right)$ (8)

$\sum END\left(N,PX+B\right)=\left(N-1\right)*SUM\left(N-2,PX\right)$ (9)

(2.1) $SUM\left(N,PX+A\right)=L_{A}SUM\left(N,PX\right)$, $SUM\left(N,PX+B\right)=L_{B}SUM\left(N,PX\right)$

Proof:

For PX = 1, direct validation:

$SUM\left(N,A\right)=1*2*C\left(N,3\right)=L_{A}C\left(N,2\right)=L_{A}SUM\left(N,1\right)$ ;

$SUM\left(N,B\right)=1*3*C\left(N,3\right)=L_{B}C\left(N,2\right)=L_{B}SUM\left(N,1\right)$

For general PX:

$\begin{array}{c}SUM\left(N,PX+B\right)=\sum END\left(N,PX+B\right)+SUM\left(N-1,PX+B\right)\\ =\left(N-1\right)*SUM\left(N-2,PX\right)+SUM\left(N-1,PX+B\right)\\ ={\displaystyle {\sum }_{n=0}^{N-1}n*SUM\left(n-1,PX\right)}\\ =L_{B}SUM\left(N,PX\right)\end{array}$

The last step is obtained from (4).

$\begin{array}{l}SUM\left(N,PX+A\right)+SUM\left(N,PX+B\right)\\ =\left(N-1\right)*SUM\left(N-1,PX\right)+SUM\left(N-1,PX+A\right)+SUM\left(N-1,PX+B\right)\\ ={\displaystyle {\sum }_{n=0}^{N-1}n*SUM\left(n,PX\right)}\\ =L_{A}SUM\left(N,PX\right)+L_{B}SUM\left(N,PX\right)\end{array}$

$\to$ $SUM\left(N,PX+A\right)=L_{A}SUM\left(N,PX\right)$

(2.2) $SUM\left(N,PX\right)=Min*C\left(N,Idx\right)$, $\sum END\left(N,PX\right)=Min*C\left(N-1,Idx-1\right)$

Proof:

$PX=A:SUM\left(N,A\right)=1*2*C\left(N,3\right)=MIN\left(A\right)*C\left(N,IDX(A)\right)$

$PX=B:SUM\left(N,B\right)=1*3*C\left(N,4\right)=MIN\left(B\right)*C\left(N,IDX(B)\right)$

For general PX, From (2.1):

$\begin{array}{c}SUM\left(N,PX+A\right)=L_{A}SUM\left(N,PX\right)=L_A\left\{Min*C\left(N,Idx\right)\right\}\\ =Min*Idx*C\left(N,Idx+1\right)=MinA*C\left(N,IdxA\right)\end{array}$

$\begin{array}{c}SUM\left(N,PX+B\right)=L_{B}SUM\left(N,PX\right)=L_B\left\{Min*C\left(N,Idx\right)\right\}\\ =Min*\left(Idx+1\right)*C\left(N,Idx+2\right)\\ =MinB*C\left(N,IdxB\right)\end{array}$

$\begin{array}{c}\sum END\left(N,PX\right)=Min*C\left(N,Idx\right)-Min*C\left(N-1,Idx\right)\\ =Min*C\left(N-1,Idx-1\right)\end{array}$

q.e.d.

This is a series of formulas, for example:

$SUM\left(6,AA\right)=1*2*3+2*3*4+3*4*5=1*2*3*C\left(6,4\right)=90$

$SUM\left(6,AB\right)=1*2*4+1*2*5+2*3*5=1*2*4*C\left(6,5\right)=48$

$SUM\left(6,BA\right)=1*3*4+1*4*5+2*4*5=1*3*4*C\left(6,5\right)=72$

$SUM\left(7,BB\right)=1*3*5+1*3*6+1*4*6+2*4*6=1*3*5*C\left(7,6\right)=105$

$\begin{array}{c}SUM\left(8,BB\right)=SUM\left(7,BB\right)+1*\left(3+4+5\right)*7+2*\left(4+5\right)*7+3*5*7\\ =1*3*5*C\left(8,6\right)=420\end{array}$

$\begin{array}{c}SUM\left(8,BAB\right)=1*3*4*6+1*\left(3*4+4*5\right)*7+2*4*5*7\\ =576=1*3*4*6*C\left(8,7\right)\end{array}$

$\begin{array}{c}SUM\left(9,BAB\right)=SUM\left(8,BAB\right)+1*\left(3*4+4*5+5*6\right)*8\\ +2*\left(4*5+5*6\right)*8+3*5*6*8\\ =2592=Min*C\left(9,7\right)\end{array}$

3. The Direct Calculation Formula of S1(n, n − k)

Definition 3.1: $F_1\left(N,M\right)=S1\left(N,N-M\right)$, specify $F_1\left(N,0\right)=1$ ; $F_1\left(N,M\right)=0\left(N\le M\right)$

Already know $F_1\left(N,0\right)=C\left(N,0\right)$ ; $F_1\left(N,1\right)=C\left(N,2\right)$ ; $F_1\left(N,N-1\right)=\left(N-1\right)!$ [3]

$F_1\left(N,M\right)$ is actually the sum of the products of all M different numbers in $\left[\text{1},n-\text{1}\right]$, from the definition (3.1) $F_1\left(N,M\right)=\sum MIN\left(PX\right)*C\left(N,IDX\left(PX\right)\right)$, the summation traversal all PX of PM = M.

There are 2^M−1 items in the expansion, and the exponent is from M + 1 to 2M

$F_1\left(N,0\right)=C\left(N,0\right)$

$F_1\left(N,1\right)=1!*C\left(N,2\right)$

$F_1\left(N,2\right)=2!*C\left(N,3\right)+1*3*C\left(N,4\right)$

$\begin{array}{c}{F}_1\left(N,3\right)=3!*C\left(N,4\right)+1*3*4*C\left(N,5\right)+1*2*4*C\left(N,5\right)\\ +1*3*5*C\left(N,6\right)\end{array}$

$\begin{array}{c}{F}_1\left(N,4\right)=4!*C\left(N,5\right)+1*3*4*5*C\left(N,6\right)+1*2*4*5*C\left(N,6\right)\\ +1*3*5*6*C\left(N,7\right)+1*2*3*5*C\left(N,6\right)\\ +1*3*4*6*C\left(N,7\right)+1*2*4*6*C\left(N,7\right)\\ +1*3*5*7*C\left(N,8\right)\end{array}$

$\begin{array}{c}{F}_1\left(N,5\right)=5!*C\left(N,6\right)+1*3*4*5*6*C\left(N,7\right)+1*2*4*5*6*C\left(N,7\right)\\ +1*3*5*6*7*C\left(N,8\right)+1*2*3*5*6*C\left(N,7\right)\\ +1*3*4*6*7*C\left(N,8\right)+1*2*4*6*7*C\left(N,8\right)\\ +1*3*5*7*8*C\left(N,9\right)+4!*6*C\left(N,7\right)\end{array}$

$\begin{array}{c}+1*3*4*5*7*C\left(N,8\right)+1*2*4*5*7*C\left(N,8\right)\\ +1*3*5*6*8*C\left(N,9\right)+1*2*3*5*7*C\left(N,8\right)\\ +1*3*4*6*8*C\left(N,9\right)+1*2*4*6*8*C\left(N,9\right)\\ +1*3*5*7*9*C\left(N,10\right)\end{array}$

$\begin{array}{c}{F}_1\left(N,6\right)=6!*C\left(N,7\right)+1*3*4*5*6*7*C\left(N,8\right)\\ +1*2*4*5*6*7*C\left(N,8\right)+1*3*5*6*7*8*C\left(N,9\right)\\ +1*2*3*5*6*7*C\left(N,8\right)+1*3*4*6*7*8*C\left(N,9\right)\\ +1*2*4*6*7*8*C\left(N,9\right)+1*3*5*7*8*9*C\left(N,10\right)\\ +4!*6*7*C\left(N,8\right)+1*3*4*5*7*8*C\left(N,9\right)\end{array}$

$\begin{array}{l}+1*2*4*5*7*8*C\left(N,9\right)+1*3*5*6*8*9*C\left(N,10\right)\\ +1*2*3*5*7*8*C\left(N,9\right)+1*3*4*6*8*9*C\left(N,10\right)\\ +1*2*4*6*8*9*C\left(N,10\right)+1*3*5*7*9*10*C\left(N,11\right)\\ +5!*7*C\left(N,8\right)+1*3*4*5*6*8*C\left(N,9\right)\\ +1*2*4*5*6*8*C\left(N,9\right)+1*3*5*6*7*9*C\left(N,10\right)\end{array}$

$\begin{array}{l}+1*2*3*5*6*8*C\left(N,9\right)+1*3*4*6*7*9*C\left(N,10\right)\\ +1*2*4*6*7*9*C\left(N,10\right)+1*3*5*7*8*10*C\left(N,11\right)\\ +4!*6*8*C\left(N,9\right)+1*3*4*5*7*9*C\left(N,10\right)\end{array}$

$\begin{array}{l}+1*2*4*5*7*9*C\left(N,10\right)+1*3*5*6*8*10*C\left(N,11\right)\\ +1*2*3*5*7*9*C\left(N,10\right)+1*3*4*6*8*10*C\left(N,11\right)\\ +1*2*4*6*8*10*C\left(N,11\right)+1*3*5*7*9*11*C\left(N,12\right)\end{array}$

It can be verified by reference [4].

(3.2) $F_1\left(N,M\right)=L_A{F}_1\left(N,M-1\right)+L_B{F}_1\left(N,M-1\right)={\left(L_A+L_B\right)}^{M-1}{F}_1\left(n,1\right)$

Proof:

From the property of $S1\left(n,k\right)$ [5]

$\to$ $F_1\left(N,M\right)=\left(N-1\right)*F_1\left(N-1,M-1\right)+F_1\left(N-1,M\right)$

$\to$ $F_1\left(N,M\right)={\displaystyle {\sum }_{n=0}^{N-1}n*F_1\left(N-1,M\right)}$

Then it can be proved by (5).

q.e.d.

It can be understood as: Each product of $F_1\left(N,M\right)$ = (Product of the first M-1 factors) × (Factor M).

Assuming the catalog of first M-1 factors is PX, then

L_A means PX + A, no new discontinuity is generated;

L_B means PX + B, new discontinuity is generated.

From (3.2), even if there is no concept of Shape of numbers, we can get the expansion.

Method 1: recursive method

1: list $F_1\left(N,M-1\right)$, change

new exponent = (Original exponent) + 1, new coefficient = (Original coefficient) × (Original exponent)

that is $L_A{F}_1\left(N,M-1\right)$.

2: list $F_1\left(N,M-1\right)$ again, change

new exponent = (Original exponent) +2, new coefficient = (Original coefficient) × (Original exponent + 1)

that is $L_B{F}_1\left(N,M-1\right)$.

Method 2: direct method

The expansion of ${\left(L_A+L_B\right)}^{M-1}$ is similar to ${\left(A+B\right)}^{M-1}$ without commutative. Coefficient changes according to the arrangement of A and B, begin from 1 and from left to right:

in case of A, the coefficient has a factor + 1,

in case of B, the coefficient has a factor + 2.

Items, coefficient and exponent are all clear.

For example:

${\left(A+B\right)}^3=AAA+\left(AAB+ABA+BAA\right)+\left(ABB+BAB+BBA\right)+BBB$

$\to$ $\begin{array}{c}{F}_1\left(N,4\right)=1*2*3*4*C\left(N,5\right)\\ +\left(1*2*3*5+1*2*4*5+1*3*4*5\right)*C\left(N,6\right)\\ +\left(1*2*4*6+1*3*4*6+1*3*5*6\right)*C\left(N,7\right)\\ +1*3*5*7*C\left(N,8\right)\end{array}$

4. The Recursive Calculation Formula of S2(n, n − k)

Definition 4.1. $F_2\left(N,M\right)=S2\left(N,N-M\right)$, specify $F_2\left(N,M\right)=0\left(N<M\right)$

Already know $F_2\left(N,0\right)=S2\left(N,N\right)=1$ ; $F_2\left(N,1\right)=S2\left(N,N-1\right)=C\left(N,2\right)$ [6].

When M > 5, it’s difficult to solve it with combination method.

(4.1) $F_2\left(N,M\right)={\displaystyle \underset{n=0}{\overset{N-1}{\sum }}\left(n-M\right)*F_2\left(n-1,M-1\right)}$

Proof:

Already know $S2\left(N,M\right)=S2\left(N-1,M-1\right)+M\ast S2\left(N-1,M\right)$ [7]

$\begin{array}{c}{F}_2\left(N,M\right)=S2\left(N,N-M\right)\\ =\left(N-M\right)*S2\left(N-1,N-M\right)+S2\left(N-1,N-M-1\right)\\ =\left(N-M\right)*S2\left(N-1,\left(N-1\right)-\left(M-1\right)\right)+S2\left(N-1,\left(N-1\right)-M\right)\\ =\left(N-M\right)*F_2\left(N-1,M-1\right)+F_2\left(N-1,M\right)\end{array}$

(4.2) $F_2\left(N,M\right)=L_A{F}_2\left(N,M-1\right)+L_B{F}_2\left(N,M-1\right)-M*\sum F_2\left(N,M-1\right)$

The proof process is the same as similar to (5).

This is the recursive method:

Exponent is from M + 1 to 2M,

$\begin{array}{l}\text{Coefficientofexponent}K\text{in}{F}_2\left(N,M\right)\\ =\left\{\text{Coefficientofexponent}K-\text{1in}{F}_2\left(N,M-1\right)\right\}*\left(K-M\right)\\ +\left\{\text{Coefficientofexponent}K-\text{2in}{F}_2\left(N,M-1\right)\right\}*\left(K-1\right)\end{array}$

$F_2\left(N,0\right)=C\left(N,0\right)$

$F_2\left(N,1\right)=C\left(N,2\right)$

$F_2\left(N,2\right)=C\left(N,3\right)+3*C\left(N,4\right)$

$F_2\left(N,3\right)=C\left(N,4\right)+10*C\left(N,5\right)+15*C\left(N,6\right)$

$F_2\left(N,4\right)=C\left(N,5\right)+25*C\left(N,6\right)+105*C\left(N,7\right)+105*C\left(N,8\right)$

$\begin{array}{c}{F}_2\left(N,5\right)=C\left(N,6\right)+56*C\left(N,7\right)+490*C\left(N,8\right)\\ +1260*C\left(N,9\right)+945*C\left(N,10\right)\end{array}$

$\begin{array}{c}{F}_2\left(N,6\right)=C\left(N,7\right)+119*C\left(N,8\right)+1918*C\left(N,9\right)+9450*C\left(N,10\right)\\ +17325*C\left(N,11\right)+10395*C\left(N,12\right)\end{array}$

Among: $\text{119}=\text{56}*\left(\text{8}-\text{6}\right)+\text{1}*\text{7}$, $1918=490*\left(9-6\right)+56*8$, $17325=945*\left(10-5\right)+1260*10$, $10395=0+945*11$

$\begin{array}{c}{F}_2\left(N,7\right)=C\left(N,8\right)+246*C\left(N,9\right)+6825*C\left(N,10\right)+56980*C\left(N,11\right)\\ +190575*C\left(N,12\right)+270270*C\left(N,13\right)+135135*C\left(N,14\right)\end{array}$

Among: $190575=17325*\left(12-7\right)+9450*11$, $270270=10395*\left(13-7\right)+17325*12$, $135135=10395*13$

$\begin{array}{c}{F}_2\left(N,8\right)=C\left(N,9\right)+501*C\left(N,10\right)+22935*C\left(N,11\right)+302995*C\left(N,12\right)\\ +1636635*C\left(N,13\right)+4099095*C\left(N,14\right)\\ +4729725*C\left(N,15\right)+2027025*C\left(N,16\right)\end{array}$

Among: $302995=56980*\left(12-8\right)+6825*11$, $4729725=135135*\left(15-8\right)+270270*14$, $2027025=135135*15$

It can be verified by reference [7] [8].

5. Simple Analysis of the Shape of Numbers

(5.1) Items of $F_1\left(N,M\right)$ are divided into $2^{M-1}$ categories according to PX, and according to PB (from 0 to M = 1), they can be divided into PB families.

Count of per family |{PX:PB is same}| = $C\left(M-1,PB\right)$, $\left|PX\right|=C\left(N-M,PB+1\right)$, $\left|END\left(N,PX\right)\right|=C\left(N-M-1,PB\right)$

Proof:

If PB = 0, find M consecutive numbers from 1 to N − 1 is equivalent to finding 1 number from 1 to N − M.

$\left|PX\right|=N-M=C\left(N-M,1\right)$

If PB = 1, {PX} with the same PB has the same |PX|, we can only calculate $\left|B{A}^M{}^{-\text{2}}\right|$.

Items begin with Number 1: 1 × 3 …, 1 × 4 …, equivalent to finding M − 1 consecutive numbers from 3 to n − 1,

$\left|\text{ItemsbeginwithNumber1}\right|=\left(N-2\right)-\left(M-1\right)=N-M-1$

Items begin with Number 2: 2 × 4 …, 2 × 5 …, equivalent to finding M − 1 consecutive numbers from 4 to n − 1,

$\left|\text{ItemsbeginwithNumber2}\right|=\left(N-3\right)-\left(M-1\right)=N-M-2$

So $\left|PX\right|={\displaystyle {\sum }_{i=1}^{N-M-1}C\left(N-M-i,1\right)}=C\left(N-M,2\right)$.

It can be proved by mathematical induction $\left|PX\right|={\displaystyle {\sum }_{i=1}^{N-M-PB}C\left(N-M-i,PB\right)}=C\left(N-M,PB+1\right)$

Verification:

$C\left(M-1,0\right)+C\left(M-1,1\right)+\cdots +C\left(M-1,M-1\right)=2^{M-1}$ (10)

$\begin{array}{l}{\displaystyle {\sum }_{PB=0}^{M-1}C\left(M-1,PB\right)*C\left(N-M,PB+1\right)}\\ ={\displaystyle {\sum }_{PB=0}^{M-1}C\left(M-1,PB\right)*C\left(N-M,\left(N-M\right)-\left(PB+1\right)\right)}\\ ={\displaystyle {\sum }_{PB=0}^{M-1}C\left(M-1,PB\right)*C\left(N-M,N-PA\right)}\\ ={\displaystyle {\sum }_{PB=0}^{M-1}C\left(M-1,PA\right)*C\left(N-M,N-PA\right)}\\ =C\left(N-1,M\right)\end{array}$ (11)

Among: $C\left(M-1,PB\right)$ = Count of PX with the same PB, $C\left(N-M,PB+1\right)=\left|PX\right|$, $C\left(N-1,M\right)$ = Count of items of $F_1\left(N,M\right)$.

(5.2) $\sum END\left(Idx+1,PX\right)=Min*Idx$, $SUM\left(Idx+1,PX\right)=Min*\left(Idx+1\right)$

This can be directly calculated by (2.2), and can be proved by mathematical induction.

Proof:

$PX=A$, $\sum END\left(IDX\left(A\right)+1,A\right)=2*3=\left(1*2\right)*3=MIN\left(A\right)*IDX(A)$

$PX=B$, $\sum END\left(IDX\left(B\right)+1,B\right)=1*4+2*4=\left(1*3\right)*4=MIN\left(B\right)*IDX(B)$

$\sum END\left(Idx+1,PX\right)=Min*Idx$. Note that end items have the same maximum factor, form (8) (9)

$\begin{array}{l}\sum END\left(IdxA+1,PX+A\right)\\ =\sum END\left(IdxA,PX\right)*IdxA=Min*Idx*IdxA=MinA*IdxA\end{array}$

$\begin{array}{l}\sum END\left(IdxB+1,PX+B\right)\\ =SUM\left(Idx+1,PX\right)*IdxB=Min*\left(Idx+1\right)*IdxB=MinB*IdxB\end{array}$

q.e.d.

Direct calculation:

(5.3) Average of $SUM\left(N,PX\right)=Min*C\left(N,PM\right)/C\left(Idx,PM\right)$ ; Average of $\sum END\left(N,PX\right)=Min*C\left(N-1,PM\right)/C\left(Idx-1,PM\right)$

(5.4) $MinA=SUM\left(Idx+1,PX\right)-Min$, $MinB=SUM\left(Idx+1,PX\right)$

(5.5) $SUM\left(H*Idx-1,PX\right)=\left(H-1\right)*\sum END\left(H*Idx,PX\right)$

Gauss computing $1+2+\cdots +\left(N-1\right)$ use the method of adding the first and last two terms:

$\left(1+N-1\right)+\left(2+N-2\right)+\cdots =N*\left(N-1\right)/2$, where N is the sum of each group, $\left(N-1\right)/2$ is the count of groups.

This is a similar way: Take $\sum END\left(N,PX\right)$ as a whole, select H × Idx items, sum from small to large, where (H − 1) is similar to count of groups, $\sum END\left(H*Idx,PX\right)$ is similar to the sum of a group.

For example:

$\begin{array}{l}\text{1}+\text{2}+\text{3}+\text{4}+\text{5}+\text{6}+\cdots \\ =\left(\text{1}+\text{2}\right)+\text{3}+\text{4}+\text{5}+\text{6}+\cdots =\text{3}*\text{1}+\left(\text{3}+\text{4}+\text{5}+\text{6}+\dots \right)\\ =\left(\text{1}+\text{2}+\text{3}+\text{4}\right)+\left(\text{5}+\text{6}+\cdots \right)=\text{5}*\text{2}+\left(\text{5}+\text{6}+\cdots \right)\end{array}$

$\begin{array}{l}\text{1}*\text{2}+\text{2}*\text{3}+\text{3}*\text{4}+\text{4}*\text{5}+\text{5}*\text{6}+\cdots \\ =\left(\text{1}*\text{2}+\text{2}*\text{3}+\text{3}*\text{4}\right)+\text{4}*\text{5}+\text{5}*\text{6}+\cdots \\ =\text{4}*\text{5}+\left(\text{4}*\text{5}+\text{5}*\text{6}+\cdots \right)\end{array}$

(5.6) $SUM\left(N,PX\right)\equiv \sum END\left(N,PX\right)\equiv 0\text{MOD}Min$

(5.7) When N increases, $Sum\left(N,PX\right)$ with the same PM and PB increases proportionally, regardless of N

For example:

$\begin{array}{l}SUM\left(N,AAB\right):SUM\left(N,ABA\right):SUM\left(N,BAA\right)\\ =MIN\left(AAB\right):MIN\left(ABA\right):MIN\left(BAA\right)\end{array}$

(5.8) For prime number P, $SUM\left(P,PX\right)\equiv 0\text{MOD}P*Min$, ( $Idx<P$ )

From number theory we know $F_1\left(P,M\right)\equiv 0\text{MOD}P$, ( $M<P-1$ ) [9] [10], this is its promotion.

For example:

$F_1\left(5,2\right)=1*\text{2}+\text{2}*\text{3}+\text{3}*\text{4}+\text{1}*\text{3}+\text{1}*\text{4}+\text{2}*\text{4}\equiv 0\text{MOD5}$

$\text{1}*\text{2}+\text{2}*\text{3}+\text{3}*\text{4}\equiv 0\text{MOD5}*\text{1}*\text{2}$, $\text{1}*\text{3}+\text{1}*\text{4}+\text{2}*\text{4}\equiv 0\text{MOD5}*\text{1}*\text{3}$

(5.9) {PX} with the same PM and PB, PB > 0, IDX(PX) = P, P > 3, then $\sum MIN\left(PX\right)\equiv 0\text{MOD}P*\left(P-1\right)$

Proof:

$F_1\left(P,M\right)\equiv 0\text{MOD}P$, all items of the expansion have the factor $C\left(P,Idx\right)$.

If Idx > P then $\text{Sum}\left(P,PX\right)=0$, if Idx < P then $P|Sum\left(P,PX\right)\to P|\sum Sum\left(P,PX\right)$, Idx = P.

For example:

$\begin{array}{l}ABB,BAB,BBA\\ \to \text{1}*\text{2}*\text{4}*\text{6}+\text{1}*\text{3}*\text{4}*\text{6}+\text{1}*\text{3}*\text{5}*\text{6}=\text{5}*\text{6}*\text{7}\equiv 0\text{MOD7}*\text{6}\end{array}$

$\begin{array}{l}AAAB,AABA,ABAA,BAAA\\ \to \text{1}*\text{2}*\text{3}*\text{4}*\text{6}+\text{1}*\text{2}*\text{3}*\text{5}*\text{6}+\text{1}*\text{2}*\text{4}*\text{5}*\text{6}+\text{1}*\text{3}*\text{4}*\text{5}*\text{6}\\ \equiv 0\text{MOD7}*\text{6}\end{array}$

(5.10) For prime number P, $F_1\left(P-1,M\right)\equiv 1\text{MOD}P$ ( $0\le M<P-2$ )

Proof:

$F_1\left(P-1,0\right)=1\equiv 1\text{MOD}P$, $F_1\left(P-1,1\right)=\left(P-1\right)\left(P-2\right)/2\equiv \left(-1\right)*\left(-2\right)/2\equiv 1\text{MOD}P$

From mathematical induction, if $F_1\left(P-1,M-1\right)\equiv \text{1MODP}$, ( $0\le M<P-2$ )

$\begin{array}{c}{F}_1\left(P,M\right)=\left(P-1\right)F_1\left(P-1,M-1\right)+F_1\left(P-1,M\right)\equiv \left(P-1\right)+F_1\left(P-1,M\right)\\ \equiv -1+F_1\left(P-1,M\right)\equiv 0\text{MOD}P\end{array}$

$\to$ $F_1\left(P-1,M\right)\equiv 1\text{MOD}P$ ( $0\le M<P-2$ )

6. Conclusions

In this paper, the concept of Shape of numbers and two new operators were introduced, and through simple way, mainly mathematical induction, the calculation formulas of Shape of numbers were obtained. Just as a simple corollary, calculation formulas of $S1\left(N,N-K\right),S2\left(N-K\right)$ are obtained. And we get some properties of Shape of numbers, especially the new congruence relation from Equations (5.8) and (5.9).

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Liu, Y. and Liu, X.S. (2006) Combinatorial Mathematics. Peking University Press, Beijing.
[2]	Hua, L.G. (1957) Number Theory Guidance. Science Press, Beijing.
[3]	Tuo, N., Gao, L. and Cai, J.X. (2010) Two Formulas of Stirling Number of the First Kind. Journal of Yan’an University (Natural Science Edition), 3, 4-6.
[4]	Xu, C.N. (2013) Operator Proof of Recurrence Formula of Stirling Number of the First Kind. Journal of Inner Mongolia University for the Nationalities (Natural Sciences), 4, 384-385.
[5]	Bruald, R.A. (2004) Combinatorial Mathematics. 3rd Edition, China Machine Press, Beijing. (S. X. Feng et al., translation)
[6]	Zhang, F.L. (2011) A Property of Stirling Number of the Second Kind. Journal of Weinan Teachers College, 12, 14-16.
[7]	Wu, Y.S. (2008) A Formula for the Second Kind of Stirling Number S2(n, n - 6). Journal of East China Jiaotong University, No. 4, 97-99.
[8]	Li, M.S. (2009) A Formula of Stirling Number S(n, n - 7). Journal of Guangdong Polytechnic Normal University, 3, 16-18.
[9]	Hardy, G.H. (2010) An Introduction to the Theory of Numbers. 6th Edition, People’s Post and Telecommunications Press, Beijing. (F. Zhang, translation)
[10]	Pan, C.D. and Pan, C.B. (2013) Elementary Number Theory. 3rd Edition, Peking University Press, Beijing.