Subset of the Shape of Numbers
Abstract: This article is based on the concept of Shape of numbers, introduces subset of the Shape and obtains its calculation formula. This article also makes some analysis and draws new conclusions, especially the calculation method of 1M+2M+3M+···+NM. The Shape’s concept becomes clearer and richness. 1. Introduction

Peng, J. has introduced Shape of numbers in  :

$\left({I}_{1},{I}_{2},\cdots ,{I}_{M}\right),\text{\hspace{0.17em}}{I}_{i}\in N,\text{\hspace{0.17em}}{I}_{1}<{I}_{2}<\cdots <{I}_{M}$

There are M-1 intervals between adjacent numbers.

${I}_{i+1}-{I}_{i}=1$ means continuity, ${I}_{i+1}-{I}_{i}>1$ means discontinuity.

Shape of numbers: collect $\left({I}_{1},{I}_{2},\cdots ,{I}_{M}\right)$ with the same continuity and discontinuity at the same position into a catalog, call it a Shape. A Shape has a min Item:

$\left(1,{K}_{1},{K}_{2},\cdots \right)$, Use the symbol PS = [min Item] to represent it. If ${K}_{i+1}-{K}_{i}=D>1$ then only ${I}_{i+1}-{I}_{i}\ge D$ is allowed.

The single $\left({I}_{1},{I}_{2},\cdots ,{I}_{M}\right)$ is an item, ${I}_{1}{I}_{2}\cdots {I}_{M}$ is the product. Ii is a factor.

Example:

$PS=\left[1,2\right]\to \left(1,2\right),\left(2,3\right),\left(3,4\right),\left(1000,1001\right)\in PS$

$PS=\left[1,3\right]\to \left(1,3\right),\left(1,4\right),\left(2,4\right),\left(1,5\right),\left(2,5\right),\left(3,5\right),\left(1000,2001\right)\in PS$

$PS=\left[1,4\right]\to \left(1,4\right),\left(1,5\right),\left(2,5\right),\left(1,6\right),\left(2,6\right),\left(3,6\right)\in PS,\left(3,5\right),\left(4,6\right)\notin PS$

$PS=\left[1,4,6\right]\to \left(1,4,7\right),\left(1,5,7\right),\left(2,5,7\right)\in PS,\left(3,5,7\right)\notin PS$

Define:

SET(N, PS) = set of items belonging to PS in $\left[1,N-1\right]$

PM(PS) = count of factors

PB(PS) = count of discontinuities

MIN(PS) = min product: $MIN\left(\left[1,2,3\right]\right)=1×2×3$, $MIN\left(\left[1,2,4\right]\right)=1×2×4$

IDX(PS) = (max factor)+1

PH(PS) = IDX(PS) − PB(PS) − 2

Basic Shape: intervals = 1 or 2

BASE(PS) = BS: if 1) PB(BS) = PB(PS), 2) PM(BS) = PM(PS), 3) BS is a Basic Shape 4) BS has discontinuity intervals at the same positions of PS.

Example:

$PS=\left[1,2\right]\to BASE\left(PS\right)=\left[1,2\right]$

$PS=\left[1,3\right],\left[1,4\right],\left[1,K>2\right]\to BASE\left(PS\right)=\left[1,3\right]$

$PS=\left[1,3,4\right],\left[1,4,5\right],\left[1,K>2,X=K+1\right]\to BASE\left(PS\right)=\left[1,3,4\right]$

$PS=\left[1,3,5\right],\left[1,4,9\right],\left[1,K>2,X>K+1\right]\to BASE\left(PS\right)=\left[1,3,5\right]$

|SET(N, PS)| = Count of items in SET(N, PS)

Example:

$SUM\left(6,\left[1,2,4\right]\right)=1×2×4+1×2×5+2×3×5$

$SUM\left(9,\left[1,4,7\right]\right)=1×4×7+1×4×8+1×5×8+2×5×8$

  came to the following conclusion:

1.1) $|SET\left(N,PS\right)|=\left(\begin{array}{c}N-PH\left(PS\right)-1\\ PB\left(PS\right)+1\end{array}\right)$

1.2) $SUM\left(N,PS\right)=MIN\left(PS\right)\left(\begin{array}{c}N\\ IDX\left(PS\right)\end{array}\right)$, PS is a Basic Shape

The following uses count of $X\in K$ for count of $\left\{{X}_{1},{X}_{2},\cdots ,{X}_{M}\right\}\in \left\{{K}_{1},{K}_{2},\cdots ,{K}_{M}\right\}$

1.3) $PS=\left[1,{K}_{1},\cdots ,{K}_{M}\right]$, $BS=BASE\left(PS\right)=\left[1,{G}_{1},\cdots ,{G}_{M}\right]$

Use the form $\left({G}_{1}+{K}_{1}\right)\left({G}_{2}+{K}_{2}\right)\cdots \left({G}_{M}+{K}_{M}\right)=\sum {X}_{1}{X}_{2}\cdots {X}_{M}$, Xi = Gi or Ki.

The expansion has 2M items, don’t swap the factors of ${X}_{1}{X}_{2}\cdots {X}_{M}$, then each ${X}_{1}{X}_{2}\cdots {X}_{M}$ corresponds to one expression = ${A}_{q}\left(\begin{array}{c}N-PH\left(PS\right)\\ IDX\left(BS\right)-q\end{array}\right)$, q = count of $X\in K$

$SUM\left(N,PS\right)=\sum {A}_{q}\left(\begin{array}{c}N-PH\left(PS\right)\\ IDX\left(BS\right)-q\end{array}\right)$, 2M items in total.

${A}_{q}={\prod }_{i=1}^{M}\left({X}_{i}+{D}_{i}\right)$, ${D}_{i}=\left\{\begin{array}{l}-m:{X}_{i}={G}_{i},m=\text{countof}\text{\hspace{0.17em}}\left\{{X}_{1},\cdots ,{X}_{i-1}\right\}\in K\\ +m:{X}_{i}={K}_{i},m=\text{countof}\text{\hspace{0.17em}}\left\{{X}_{1},\cdots ,{X}_{i-1}\right\}\in G\end{array}$

Example:

$PS=\left[1,{K}_{1}\ge 3,{K}_{2}\ge {K}_{1}+2,{K}_{3}\ge {K}_{2}+2\right]$, $BS=BASE\left(PS\right)=\left[1,3,5,7\right]$

$\begin{array}{c}\text{Theform}=\left(3+{K}_{1}\right)\left(5+{K}_{2}\right)\left(7+{K}_{3}\right)\\ =3×5×7+3×5×{K}_{3}+3×{K}_{2}×7+3×{K}_{2}×{K}_{3}\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}+{K}_{1}×5×7+{K}_{1}×5×{K}_{3}+{K}_{1}×{K}_{2}×7+{K}_{1}×{K}_{2}×{K}_{3}\end{array}$

$\begin{array}{c}P=N-PH\left(PS\right)=N-\left\{IDX\left(PS\right)-PB\left(PS\right)-2\right\}\\ =N-\left\{{K}_{3}+1-3-2\right\}=N-{K}_{3}+4\end{array}$

$IDX\left(BS\right)=8$

?

$\begin{array}{l}SUM\left(N,PS\right)=3×5×7\left(\begin{array}{c}P\\ 8\end{array}\right)+3×5×\left({K}_{3}+2\right)\left(\begin{array}{c}P\\ 7\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}}\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}}+3×\left({K}_{2}+1\right)×\left(7-1\right)\left(\begin{array}{c}P\\ 7\end{array}\right)+3×\left({K}_{2}+1\right)×\left({K}_{3}+1\right)\left(\begin{array}{c}P\\ 6\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}}\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}×\left(5-1\right)×\left(7-1\right)\left(\begin{array}{c}P\\ 7\end{array}\right)+{K}_{1}×\left(5-1\right)×\left({K}_{3}+1\right)\left(\begin{array}{c}P\\ 6\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}}\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}×\text{}{K}_{2}×\left(7-2\right)\left(\begin{array}{c}P\\ 6\end{array}\right)+{K}_{1}×{K}_{2}×{K}_{3}\left( P 5 \right)\end{array}$

$\text{Anitem}\in PS=\left\{\text{begin},{K}_{1}+{E}_{1},\cdots ,{K}_{M}+{E}_{M}\right\}$, K is fixed, E is variable.

$\text{Aproduct}=\text{begin}×\left({K}_{1}+{E}_{1}\right)\cdots \left({K}_{M}+{E}_{M}\right)=\text{begin}×\sum {F}_{1}{F}_{2}\cdots {F}_{M}$, ${F}_{i}={E}_{i}$ or ${F}_{i}={K}_{i}$

That is, a product can be broken down into 2M parts.

Define

$SUM\text{_}K\left(SET\left(N,PS\right),PF={F}_{1}{F}_{2}\cdots {F}_{M}\right)$ = Sum of one part of $SUM\left(N,PS\right)$

PF indicates the part. $PF={F}_{1}{F}_{2}\cdots {F}_{M}$, ${F}_{i}={E}_{i}$ or ${F}_{i}={K}_{i}$

$\begin{array}{c}SUM\left(N,PS\right)=\sum \text{product}=\sum \sum \text{begin}×{F}_{1}\cdots {F}_{M}\\ =\sum {\prod }_{i=1}^{M}\left({X}_{i}+{D}_{i}\right)\left(\begin{array}{c}A\\ {M}_{q}\end{array}\right)\end{array}$

${X}_{i}+{D}_{i}=\left\{\begin{array}{l}\left\{{G}_{i}-{D}_{i}\right\}:{X}_{i}={G}_{i},{D}_{i}=\text{countof}\text{\hspace{0.17em}}\left\{{X}_{1},\cdots ,{X}_{i-1}\right\}\in K\\ \left\{{K}_{i}\right\}+\left\{{D}_{i}\right\}:{X}_{i}={K}_{i},{D}_{i}=\text{countof}\text{\hspace{0.17em}}\left\{{X}_{1},\cdots ,{X}_{i-1}\right\}\in G\end{array}$

Let $SUM1\left(N,PS\right)=SUM\left(N,PS\right)$ expand by the {braces}:

1.4) $SUM\text{_}K\left(SET\left(N,PS\right),PF\right)=\sum \text{Expansionof}SUM1\left(N,PS\right)$ with same $\left\{{K}_{i}\right\}\in PF=\sum {\prod }_{i=1}^{M}{Y}_{i}\left(\begin{array}{c}A\\ {M}_{q}\end{array}\right)$, ${Y}_{i}=\left\{\begin{array}{l}0:{F}_{i}={K}_{i},{X}_{i}={G}_{i}\\ {K}_{i}:{F}_{i}={K}_{i},{X}_{i}={K}_{i}\\ {G}_{i}-{D}_{i}:{F}_{i}={E}_{i},{X}_{i}={G}_{i},{D}_{i}=\text{countof}\left\{{X}_{1},\cdots ,{X}_{i-1}\right\}\in K\\ {D}_{i}:{F}_{i}={E}_{i},{X}_{i}={K}_{i},{D}_{i}=\text{countof}\left\{{X}_{1},\cdots ,{X}_{i-1}\right\}\in G\end{array}$

Example:

$SUM\left(N,\left[1,{K}_{1}\ge 3,{K}_{2}\ge {K}_{1}+2\right]\right)$, $\text{form}=\left(3+{K}_{1}\right)\left(5+{K}_{2}\right)$ ?

$\begin{array}{l}=15\left(\begin{array}{c}N-{K}_{2}+3\\ 6\end{array}\right)+3\left(\left\{{K}_{2}\right\}+\left\{1\right\}\right)\left(\begin{array}{c}N-{K}_{2}+3\\ 5\end{array}\right)\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{ }\text{ }+{K}_{1}\left(\left\{5-1\right\}\right)\left(\begin{array}{c}N-{K}_{2}+3\\ 5\end{array}\right)+{K}_{1}{K}_{2}\left(\begin{array}{c}N-{K}_{2}+3\\ 4\end{array}\right)\end{array}$

Expand by the {braces}:

$\begin{array}{l}=\left\{15\left(\begin{array}{c}N-{K}_{2}+3\\ 6\end{array}\right)+3\left(\begin{array}{c}N-{K}_{2}+3\\ 5\end{array}\right)\right\}+3{K}_{2}\left(\begin{array}{c}N-{K}_{2}+3\\ 5\end{array}\right)\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{ }\text{ }+4{K}_{1}\left(\begin{array}{c}N-{K}_{2}+3\\ 5\end{array}\right)+{K}_{1}{K}_{2}\left(\begin{array}{c}N-{K}_{2}+3\\ 4\end{array}\right)\\ ={\sum }_{\text{begin}=1}^{N-{K}_{2}}\sum \text{begin}×\left({K}_{1}+{E}_{1,\text{begin}}\right)\left({K}_{2}+{E}_{2,\text{begin}}\right)\end{array}$

?

$\begin{array}{l}SUM\text{_}K\left(SET\left(N,PS\right),{E}_{1}{E}_{2}\right)\\ ={\sum }_{\text{allitems}}\text{begin}\ast {E}_{1,i}{E}_{2,i}=15\left(\begin{array}{c}N-{K}_{2}+3\\ 6\end{array}\right)+3\left(\begin{array}{c}N-{K}_{2}+3\\ 5\end{array}\right)\end{array}$

$SUM\text{_}K\left(SET\left(N,PS\right),{E}_{1}{K}_{2}\right)={\sum }_{\text{allitems}}\text{begin}\ast {E}_{1,i}{K}_{2}=3{K}_{2}\left(\begin{array}{c}N-{K}_{2}+3\\ 5\end{array}\right)$

$SUM\text{_}K\left(SET\left(N,PS\right),{K}_{1}{E}_{2}\right)={\sum }_{\text{allitems}}\text{begin}\ast {K}_{1}{E}_{2,i}=4{K}_{1}\left(\begin{array}{c}N-{K}_{2}+3\\ 5\end{array}\right)$

$SUM\text{_}K\left(SET\left(N,PS\right),{K}_{1}{K}_{2}\right)={\sum }_{\text{allitems}}\text{begin}\ast {K}_{1}{K}_{2}={K}_{1}{K}_{2}\left(\begin{array}{c}N-{K}_{2}+3\\ 4\end{array}\right)$

This can explain why 1.3) has that strange form:

We can calculate every part of 1.3) by some way without 1.3). There may be complex relationships between the parts, but their sum just match a simple form.

1.5) Use the symbol of 1.3), when ${G}_{i}={K}_{i}$, ${N}_{1}=\text{Count}\text{\hspace{0.17em}}\text{of}\text{\hspace{0.17em}}X\in K$, ${N}_{1}+{N}_{2}=M$

$H\left({N}_{1},{N}_{2},K\right)=\sum {A}_{q={N}_{1}}=\sum {\prod }_{i=1}^{M}\left({X}_{i}+{D}_{i}\right)={K}_{1}{K}_{2}\cdots {K}_{M}\left(\begin{array}{c}M\\ {N}_{1},{N}_{2}\end{array}\right)$

Sum traverses all (N1, N2)-Choice of K

This ? 1.3) is compatible with 1.2)

1.6) P is a prime number, {PS1, PS2, …} are all of the Basic Shapes,

$PM\left(PS1\right)=PM\left(PS2\right)=\cdots$, $PB\left(PS1\right)=PB\left(PS2\right)=\cdots >0$, $IDX\left(PS1\right)=IDX\left(PS2\right)=\cdots =P$,

That is, them are Basic shapes, have same count of factors and same count of discontinuities > 0, and max factor = P − 1, then $MIN\left(PS1\right)+MIN\left(PS2\right)+\cdots \equiv 0\text{\hspace{0.17em}}MOD\text{\hspace{0.17em}}P$

Example:

$\begin{array}{l}1×2×4×6+1×3×4×6+1×3×5×6\\ \equiv 1×2×3×4×6+1×2×3×5×6+1×2×4×5×6+1×3×4×5×6\\ \equiv 0\text{\hspace{0.17em}}MOD\text{\hspace{0.17em}}7\end{array}$

2. Subset of SET(N, PS)

$PS=\left[1,{K}_{1},{K}_{2},\cdots ,{K}_{M}\right]$, $PT=\left[1,{T}_{1},{T}_{2},\cdots ,{T}_{M}\right]$, $\text{Item}=\left\{{I}_{0},{I}_{1},{I}_{2},\cdots ,{I}_{M}\right\}\in SET\left(N,PS\right)$

If PB(PS) = 0, $\text{items}\in SET\left(N,PS\right)$ is very simple.

If PB(PS) > 0, some changes appear in SET(N, PS).

We can fix some discontinuities of the Shape to get subsets.

Define SET(N, PS, PT) =Subset of SET(N, PS), a valid

$\begin{array}{l}PT=\left[1,{T}_{1},\cdots ,{T}_{M}\right]\\ =\left\{\begin{array}{l}{T}_{i+1}-{T}_{i}=1:{K}_{i+1}-{K}_{i}=1,\text{\hspace{0.17em}}\text{means}\text{\hspace{0.17em}}{I}_{i+1}-{I}_{i}=1\\ {T}_{i+1}-{T}_{i}=1:{K}_{i+1}-{K}_{i}=D>1,\text{\hspace{0.17em}}\text{means}\text{\hspace{0.17em}}{I}_{i+1}-{I}_{i}=D\\ {T}_{i+1}-{T}_{i}=2:{K}_{i+1}-{K}_{i}=D>1,\text{\hspace{0.17em}}\text{means}\text{\hspace{0.17em}}{I}_{i+1}-{I}_{i}\ge D\end{array}\end{array}$ (*)

others are invalid.

Example:

$SET\left(N,\left[1,3,5\right],\left[1,3,5\right]\right)=SET\left(N,\left[1,3,5\right]\right)$

$SET\left(N,\left[1,3,5\right],\left[1,4,5\right]\right)$, $SET\left(N,\left[1,3,5\right],\left[1,3,6\right]\right)$, $SET\left(N,\left[1,2,9\right],\left[1,3,4\right]\right)$ is invalid.

$\begin{array}{l}SET\left(N,\left[1,3,5\right],\left[1,2,4\right]\right)\\ =\left\{\left(1,3,5\right),\left(1,3,6\right),\left(2,4,6\right),\left(1,3,7\right),\left(2,4,7\right),\left(3,5,7\right),\cdots \right\}\end{array}$

${I}_{2}-{I}_{1}=\left(3-1\right)=2$, ${I}_{3}-{I}_{2}\ge \left(5-3\right)=2$

$\begin{array}{l}SET\left(N,\left[1,3,5\right],\left[1,3,4\right]\right)\\ =\left\{\left(1,3,5\right),\left(1,4,6\right),\left(2,4,6\right),\left(1,5,7\right),\left(2,5,7\right),\left(3,5,7\right),\cdots \right\}\end{array}$

${I}_{3}-{I}_{2}=\left(5-3\right)=2$, ${I}_{2}-{I}_{1}\ge \left(3-1\right)=2$

$SET\left(N,\left[1,3,5\right],\left[1,2,3\right]\right)=\left\{\left(1,3,5\right),\left(2,4,6\right),\left(3,5,7\right),\cdots \right\}$

$\begin{array}{l}SET\left(N,\left[1,4,8\right],\left[1,2,4\right]\right)\\ =\left\{\left(1,4,8\right),\left(1,4,9\right),\left(2,5,9\right),\left(1,4,10\right),\left(2,5,10\right),\left(3,6,10\right),\cdots \right\}\end{array}$

${I}_{2}-{I}_{1}=\left(4-1\right)=3$, ${I}_{3}-{I}_{2}\ge \left(8-4\right)=4$

PT only has the change at (*). When a change happens, make the interval fixed.

The more changes, the fewer items:

Define PCHG(PS, PT) = count of change from BASE(PS) to PT

Example:

$PCHG\left(\left[1,3,5\right],\left[1,2,4\right]\right)=PCHG\left(\left[1,4,7\right],\left[1,2,4\right]\right)=1$, changed at T1

$PCHG\left(\left[1,3,5\right],\left[1,3,4\right]\right)=PCHG\left(\left[1,4,7\right],\left[1,3,4\right]\right)=1$, changed at T2

$PCHG\left(\left[1,3,5\right],\left[1,2,3\right]\right)=PCHG\left(\left[1,8,10\right],\left[1,2,3\right]\right)=2$, changed at T1, T2

2.1) $SET\left(N,PS\right)=SET\left(N,PS,BASE\left(PS\right)\right)$

2.2) $|SET\left(N,PS,PT\right)|=\left(\begin{array}{c}N-PH\left(PS\right)-1-PCHG\left(PS,PT\right)\\ PB\left(PT\right)+1\end{array}\right)$

If PT1 only change Ti of PT, Obvious: $PCHG\left(PS,PT1\right)=PCHG\left(PS,PT\right)+1$

2.3) If PT1 only change Ti of PT, $PT1=\left[1,{T}_{1},\cdots ,{T}_{i-1},{T}_{i}-1,{T}_{i+1}-1,\cdots ,{T}_{M}-1\right]$.

Let $PS1=\left[1,{K}_{1},\cdots ,{K}_{i-1},{K}_{i}+1,{K}_{i+1}+1,\cdots ,{K}_{M}+1\right]$, then

$SET\left(N,PS,PT\right)=SET\left(N,PS,PT1\right)\cup SET\left(N,PS1,PT\right)$

$SET\left(N,PS,PT1\right)=SET\left(N,PS,PT\right)-SET\left(N,PS1,PT\right)$

In particular: $PCHG\left(PS,PT\right)=1$ ? $SET\left(N,PS,PT\right)=SET\left(N,PS\right)-SET\left(N,PS1\right)$

[Proof]

PT1 change Ti of PT ? ${T}_{i}-{T}_{i-1}=2$ ? ${K}_{i}-{K}_{i-1}>1$ ? $PCHG\left(PS,PT\right)=PCHG\left(PS1,PT\right)$

$\begin{array}{l}|SET\left(N,PS,PT1\right)|+|SET\left(N,PS1,PT\right)|\\ =\left(\begin{array}{c}N-PH\left(PS\right)-1-PCHG\left(PS,PT1\right)\\ PB\left(PT1\right)+1\end{array}\right)\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{ }+\left(\begin{array}{c}N-PH\left(PS1\right)-1-PCHG\left(PS1,PT\right)\\ PB\left(PT\right)+1\end{array}\right)\\ =\left(\begin{array}{c}N-PH\left(PS\right)-2-PCHG\left(PS,PT\right)\\ PB\left(PT\right)\end{array}\right)\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{ }+\left(\begin{array}{c}N-PH\left(PS\right)-2-PCHG\left(PS1,PT\right)\\ PB\left(PT\right)+1\end{array}\right)\end{array}$

$\begin{array}{l}=\left(\begin{array}{c}N-PH\left(PS\right)-2-PCHG\left(PS,PT\right)\\ PB\left(PT\right)\end{array}\right)\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{ }+\left(\begin{array}{c}N-PH\left(PS\right)-2-PCHG\left(PS,PT\right)\\ PB\left(PT\right)+1\end{array}\right)\\ =\left(\begin{array}{c}N-PH\left(PS\right)-1-PCHG\left(PS,PT\right)\\ PB\left(PT\right)+1\end{array}\right)\\ =|SET\left(N,PS,PT\right)|\end{array}$

Count of the Items is equal.

Every item in SET(N, PS1, PT) is in SET(N, PS, PT), and not in SET(N, PS, PT1).

q.e.d.

if $PCHG\left(PS,PT\right)=2$, PT changes at Ti and Tj, then

$PT=\left[1,{G}_{1},\cdots ,{G}_{i-1},{G}_{i}-1,\cdots ,{G}_{j-1}-1,{G}_{j}-2,{G}_{j+1}-2,\cdots ,{G}_{M}-2\right]$

Let

$PTA=\left[1,{G}_{1},\cdots ,{G}_{i-1},{G}_{i}-1,\cdots ,{G}_{M}-1\right]$,

$PTB=\left[1,{G}_{1},\cdots ,{G}_{j-1},{G}_{j}-1,\cdots ,{G}_{M}-1\right]$

$PSA=\left[1,{K}_{1},\cdots ,{K}_{i-1},{K}_{i}+1,\cdots ,{K}_{M}+1\right]$,

$PSB=\left[1,{K}_{1},\cdots ,{K}_{j-1},{K}_{j}+1,\cdots ,{K}_{M}+1\right]$

$PS2=\left[1,{K}_{1},\cdots ,{K}_{i-1},{K}_{i}+1,\cdots ,{K}_{j-1}+1,{K}_{j}+2,{K}_{j+1}+2,\cdots ,{K}_{M}+2\right]$

?

$\begin{array}{l}SET\left(N,PS,PT\right)=SET\left(N,PS,PTA\right)-SET\left(N,PSA,PTA\right)\\ =\left\{SET\left(N,PS,BS\right)-SET\left(N,PSB,BS\right)\right\}\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{ }–\left\{SET\left(N,PSA,BS\right)-SET\left(N,PS2,BS\right)\right\}\\ =SET\left(N,PS,BS\right)-\left[SET\left(N,PSA,BS\right)\cup SET\left(N,PSB,BS\right)\right]\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{ }+SET\left(N,PS2,BS\right)\\ =SET\left(N,PS\right)-\left[SET\left(N,PSA\right)\cup SET\left(N,PSB\right)\right]+SET\left(N,PS2\right)\end{array}$

General:

2.4) The relationship between SET(N, PS, PT) and SET(N, PSX) is similar to the Inclusion Exclusion Principle.

3. Calculation formula of SET(N, PS, PT)

Define:

SUM_SUBSET(N, PS, PT) = Sum of all products in SET(N, PS, PT)

When PT is invalid, SUM_SUBSET(N, PS, PT) = 0

Only valid PT is discussed below.

$PS=\left[1,{K}_{1},{K}_{2},\cdots ,{K}_{M}\right]$, $BS=BASE\left(PS\right)=\left[1,{G}_{1},{G}_{2},\cdots ,{G}_{M}\right]$, $PT=\left[1,{T}_{1},{T}_{2},\cdots ,{T}_{M}\right]$

3.1) Use the form $\left({T}_{1}+{K}_{1}\right)\left({T}_{2}+{K}_{2}\right)\cdots \left({T}_{M}+{K}_{M}\right)=\sum {X}_{1}{X}_{2}\cdots {X}_{M}$, then

$SUM\text{_}SUBSET\left(N,PS,PT\right)=\sum {A}_{q}\left(\begin{array}{c}N-PH\left(PS\right)-PCHG\left(PS,PT\right)\\ IDX\left(PT\right)-q\end{array}\right)$

${A}_{q}={\prod }_{i=1}^{M}\left({X}_{i}+{D}_{i}\right)$, ${D}_{i}=\left\{\begin{array}{l}-m:{X}_{i}={T}_{i},m=\text{countof}\left\{{X}_{1},\cdots ,{X}_{i-1}\right\}\in K\\ +m:{X}_{i}={K}_{i},m=\text{countof}\left\{{X}_{1},\cdots ,{X}_{i-1}\right\}\in T\end{array}$

$q=\text{count}\text{\hspace{0.17em}}\text{of}\text{\hspace{0.17em}}X\in K$

[Proof]

1) If PT = BS, then $SUM\text{_}SUBSET\left(N,PS,BS\right)=SUM\left(N,PS\right)$ ? the formula holds.

2) If M = 1 and PT has 1 change, then $PS=\left[1,{K}_{1}>2\right]$, $PT=\left[1,{T}_{1}\right]=\left[1,2\right]$, $BS=\left[1,{G}_{1}\right]=\left[1,3\right]$,

Let $PS1=\left[1,{K}_{1}+1\right]$, 2.3) →

$\begin{array}{l}SUM\text{_}SUBSET\left(N,PS,PT\right)\\ =SUM\left(N,PS\right)-SUM\left(N,PS1\right)\\ =\left\{{G}_{1}\left(\begin{array}{c}N-PH\left(PS\right)\\ IDX\left(BS\right)\end{array}\right)+{K}_{1}\left(\begin{array}{c}N-PH\left(PS\right)\\ IDX\left(BS\right)-1\end{array}\right)\right\}\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{ }\text{ }-\left\{{G}_{1}\left(\begin{array}{c}N-PH\left(PS1\right)\\ IDX\left(BS\right)\end{array}\right)+\left({K}_{1}+1\right)\left(\begin{array}{c}N-PH\left(PS1\right)\\ IDX\left(BS\right)-1\end{array}\right)\right\}\end{array}$

$\begin{array}{l}=\left\{{G}_{1}\left(\begin{array}{c}N-PH\left(PS1\right)\\ IDX\left(BS\right)\end{array}\right)+{K}_{1}\left(\begin{array}{c}N-PH\left(PS1\right)\\ IDX\left(BS\right)-1\end{array}\right)\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{ }\text{ }+{G}_{1}\left(\begin{array}{c}N-PH\left(PS1\right)\\ IDX\left(BS\right)-1\end{array}\right)+{K}_{1}\left(\begin{array}{c}N-PH\left(PS1\right)\\ IDX\left(BS\right)-2\end{array}\right)\right\}\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{ }\text{ }-\left\{{G}_{1}\left(\begin{array}{c}N-PH\left(PS1\right)\\ IDX\left(BS\right)\end{array}\right)+\left({K}_{1}+1\right)\left(\begin{array}{c}N-PH\left(PS1\right)\\ IDX\left(BS\right)-1\end{array}\right)\right\}\\ =\left({G}_{1}-1\right)\left(\begin{array}{c}N-PH\left(PS1\right)\\ IDX\left(BS\right)-1\end{array}\right)+{K}_{1}\left(\begin{array}{c}N-PH\left(PS1\right)\\ IDX\left(BS\right)-2\end{array}\right)\end{array}$

$\begin{array}{l}={T}_{1}\left(\begin{array}{c}N-PH\left(PS1\right)\\ IDX\left(BS\right)-1\end{array}\right)+{K}_{1}\left(\begin{array}{c}N-PH\left(PS1\right)\\ IDX\left(BS\right)-2\end{array}\right)\\ ={T}_{1}\left(\begin{array}{c}N-PH\left(PS\right)-1\\ IDX\left(PT\right)\end{array}\right)+{K}_{1}\left(\begin{array}{c}N-PH\left(PS\right)-1\\ IDX\left(PT\right)-1\end{array}\right)\\ ={T}_{1}\left(\begin{array}{c}N-PH\left(PS\right)-PCHG\left(PS,PT\right)\\ IDX\left(PT\right)\end{array}\right)\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{ }\text{ }+{K}_{1}\left(\begin{array}{c}N-PH\left(PS\right)-PCHG\left(PS,PT\right)\\ IDX\left(PT\right)-1\end{array}\right)\end{array}$

The form = (T1 + K1) ? The formula holds.

3) If M > 1 and PT only has 1 change at TM, then $PT=\left[1,{G}_{1},\cdots ,{G}_{M-1},{G}_{M}-1\right]$

Let $PS1=\left[1,{K}_{1},\cdots ,{K}_{M-1},{K}_{M}+1\right]$, 2.3) → $PH\left(PS1\right)=PH\left(PS\right)+1$ :

$\begin{array}{l}SUM\left(N,PS,PT\right)=SUM\left(N,PS\right)-SUM\left(N,PS1\right)\\ ={\sum }_{i=IDX\left(BS\right)-M}^{IDX\left(BS\right)}\sum {A}_{i}\left(\begin{array}{c}N-PH\left(PS\right)\\ i\end{array}\right)-{\sum }_{i=IDX\left(BS\right)-M}^{IDX\left(BS\right)}\sum {B}_{i}\left(\begin{array}{c}N-PH\left(PS1\right)\\ i\end{array}\right)\\ ={\sum }_{i=IDX\left(BS\right)-M}^{IDX\left(BS\right)}\sum {A}_{i}\left\{\left(\begin{array}{c}N-PH\left(PS1\right)\\ i\end{array}\right)+\left(\begin{array}{c}N-PH\left(PS1\right)\\ i-1\end{array}\right)\right\}\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{ }\text{ }-{\sum }_{i=IDX\left(BS\right)-M}^{IDX\left(BS\right)}\sum {B}_{i}\left(\begin{array}{c}N-PH\left(PS1\right)\\ i\end{array}\right)\end{array}$

$\begin{array}{l}={\sum }_{i=IDX\left(BS\right)-M}^{IDX\left(BS\right)}\left(\sum {A}_{i}-\sum {B}_{i}\right)\left(\begin{array}{c}N-PH\left(PS1\right)\\ i\end{array}\right)+\sum {A}_{i}\left(\begin{array}{c}N-PH\left(PS1\right)\\ i-1\end{array}\right)\\ ={\sum }_{i=IDX\left(BS\right)-M}^{IDX\left(BS\right)}\left(\sum {A}_{i}-\sum {B}_{i}\right)\left(\begin{array}{c}N-PH\left(PS\right)-1\\ i\end{array}\right)+\sum {A}_{i}\left(\begin{array}{c}N-PH\left(PS\right)-1\\ i-1\end{array}\right)\\ ={\sum }_{i=IDX\left(BS\right)-M-1}^{IDX\left(BS\right)}\sum {C}_{J}\left(\begin{array}{c}N-PH\left(PS\right)-1\\ J\end{array}\right),J=i-1,\sum {C}_{J-1}=\sum {A}_{i+1}+\sum {A}_{i}-\sum {B}_{i}\\ ={\sum }_{J=IDX\left(PT\right)-M}^{IDX\left(PT\right)+1}\sum {C}_{J}\left(\begin{array}{c}N-PH\left(PS\right)-1\\ J\end{array}\right)\end{array}$

When $i=IDS\left(BS\right)$, $\sum {C}_{i}=MIN\left(BS\right)-MIN\left(BS\right)=0$

$={\sum }_{J=IDX\left(PT\right)-M}^{IDX\left(PT\right)}\sum {C}_{J}\left(\begin{array}{c}N-PH\left(PS\right)-1\\ J\end{array}\right)$

Use the symbol of (1.3)

$i=IDX\left(BS\right)-CNT$, $CNT=\text{Count}\text{\hspace{0.17em}}\text{of}\text{\hspace{0.17em}}X\in K$

Let $R\left(E\right)=\sum {\prod }_{L=1}^{M-1}\left({X}_{L}+{D}_{L}\right)$, $E=\text{Count}\text{\hspace{0.17em}}\text{of}\text{\hspace{0.17em}}\left\{{X}_{1},\cdots ,{X}_{M-1}\right\}\in K$

$\begin{array}{l}\sum {A}_{i+1}=R\left(CNT-1\right)\left({G}_{M}-\left(CNT-1\right)\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}}+R\left(CNT-2\right)\left({K}_{M}+\left(M-1\right)-\left(CNT-2\right)\right)\end{array}$

$\sum {A}_{i}=R\left(CNT\right)\left({G}_{M}-CNT\right)+R\left(CNT-1\right)\left({K}_{M}+\left(M-1\right)-\left(CNT-1\right)\right)$

$\sum {B}_{i}=R\left(CNT\right)\left({G}_{M}-CNT\right)+R\left(CNT-1\right)\left(\left({K}_{M}+1\right)+\left(M-1\right)-\left(CNT-1\right)\right)$

$\begin{array}{l}\sum {C}_{J-1}=\sum {A}_{i+1}+\sum {A}_{i}-\sum {B}_{i}\\ =R\left(CNT-1\right)\left({G}_{M}-CNT\right)+R\left(CNT-2\right)\left({K}_{M}+M-CNT+1\right)\\ =R\left(CNT-1\right)\left({T}_{M}-\left\{CNT\text{}-1\right\}\right)+R\left(CNT-2\right)\left({K}_{M}+\left\{\left(M-1\right)-\left(CNT-2\right)\right\}\right)\end{array}$

? Match of the form $\left({T}_{1}+{K}_{1}\right)\left({T}_{2}+{K}_{2}\right)\cdots \left({T}_{M}+{K}_{M}\right)$

4) If M > 1 and PT only has 1 change at ${T}_{i}{}_{, Let $R\left(E\right)=\sum {\prod }_{L=1,l\ne i}^{M}\left({X}_{L}+{D}_{L}\right)$, use the same method of (3).

5) if $PCHG\left(PS,PT\right)>1$, Use 2.3) → divide the Items into subset ? deducing by induction.

q.e.d.

Example:

$N-PH\left(\left[1,3,5,7\right]\right)-PCHG\left(\left[1,3,5,7\right],\left[1,2,3,4\right]\right)=N-\left(8-3-2\right)-3=N-6$

$SUM\text{_}SUBSET\left(N,\left[1,3,5,7\right],\left[1,2,3,4\right]\right)$

?

$\begin{array}{c}\text{form}=\left(2+3\right)\left(3+5\right)\left(4+7\right)\\ =24\left(\begin{array}{c}N-6\\ 5\end{array}\right)+108\left(\begin{array}{c}N-6\\ 4\end{array}\right)+174\left(\begin{array}{c}N-6\\ 3\end{array}\right)+105\left(\begin{array}{c}N-6\\ 2\end{array}\right)\\ =1×3×5×7+2×4×6×8+3×5×7×9+\cdots \end{array}$

Among:

$24=2×3×4$ ; $105=3×5×7$

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

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

Use the same method of 3.1)

3.2) Calculation formula of SUM_K(SET(N, PS, PT), PF) is similar to 1.4).

Example:

$\begin{array}{l}SUM\text{_}SUBSET\left(N,\left[1,3,7\right],\left[1,2,3\right]\right)\\ =6\left(\begin{array}{c}N-6\\ 4\end{array}\right)+2×\left(\left\{7\right\}+\left\{1\right\}\right)\left(\begin{array}{c}N-6\\ 3\end{array}\right)+3×\left(\left\{3-1\right\}\right)\left(\begin{array}{c}N-6\\ 3\end{array}\right)+3×7\left(\begin{array}{c}N-6\\ 2\end{array}\right)\end{array}$

$\begin{array}{l}SUM\text{_}SUBSET\left(10,\left[1,3,7\right],\left[1,2,3\right]\right)\\ =1×3×7+2×4×8+3×5×9\\ =1×3×7+2×\left(3+1\right)×\left(7+1\right)+3×\left(3+2\right)×\left(7+2\right)\\ =\left\{1×3×7+2×3×7+3×3×7\right\}+\left\{2×3×1+3×3×2\right\}\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{ }\text{ }+\left\{2×1×7+3×2×7\right\}+\left\{2×1×1+3×2×2\right\}\end{array}$

?

$\left\{1×3×7+2×3×7+3×3×7\right\}=3×7\left(\begin{array}{c}10-6\\ 2\end{array}\right)$

$\left\{2×3×1+3×3×2\right\}=3×\left(\left\{3-1\right\}\right)\left(\begin{array}{c}N-6\\ 3\end{array}\right)=6\left(\begin{array}{c}10-6\\ 3\end{array}\right)$

$\left\{2×1×7+3×2×7\right\}=2×7\left(\begin{array}{c}N-6\\ 3\end{array}\right)=14\left(\begin{array}{c}N-6\\ 3\end{array}\right)$

$\left\{2×1×1+3×2×2\right\}=6\left(\begin{array}{c}10-6\\ 4\end{array}\right)+2×\left\{1\right\}\left(\begin{array}{c}10-6\\ 3\end{array}\right)$

3.3) Use the form $\left({T}_{1}+{K}_{1}\right)\left({T}_{2}+{K}_{2}\right)\cdots \left({T}_{M}+{K}_{M}\right)=\sum {X}_{1}{X}_{2}\cdots {X}_{M}$

$\begin{array}{l}SUM\text{_}K\left(SET\left(N,PS,PT\right),{E}_{1}{E}_{2}\cdots {E}_{M}\right)\\ =\sum {A}_{q}\left(\begin{array}{c}N-PH\left(PS\right)-PCHG\left(PS,PT\right)\\ IDX\left(PT\right)-q\end{array}\right)\end{array}$

${A}_{q}={\prod }_{i=1}^{M}{D}_{i}$, ${D}_{i}=\left\{\begin{array}{l}{T}_{i}-m:{X}_{i}={T}_{i},m=\text{countof}\text{\hspace{0.17em}}\left\{{X}_{2},\cdots ,{X}_{i-1}\right\}\in K\\ +m:{X}_{i}={K}_{i},m=\text{countof}\text{\hspace{0.17em}}\left\{{X}_{2},\cdots ,{X}_{i-1}\right\}\in T\end{array}$

$q=\text{count}\text{\hspace{0.17em}}\text{of}\text{\hspace{0.17em}}X\in K$, ${X}_{1}={T}_{1}$, 2M-1 Items in total.

In particular:

If $PT1=\left[1,{T}_{1},\cdots ,{T}_{M}\right]=\left[1,2,\cdots ,M+1\right]$, then $PB\left(PS\right)=PCHG\left(PS,PT1\right)$

$\begin{array}{l}N-PH\left(PS\right)-PCHG\left(PS,PT1\right)\\ =N-\left[IDX\left(PS\right)-2-PB\left(PS\right)\right]-PB\left(PS\right)\\ =N-\left({K}_{M}-1\right)\end{array}$

$IDX\left(PT1\right)=M+2$

$\begin{array}{l}SUM\left(SET\left(N,PS,PT1\right),{E}_{1}\cdots {E}_{M}\right)\\ =2×{1}^{M}+3×{2}^{M}+\cdots +\left(N-{K}_{M}\right)×{\left(N-{K}_{M}-1\right)}^{M}\end{array}$

?

$\begin{array}{l}SUM\left(SET\left(N+{K}_{M}+1,PS,PT1\right),{E}_{1}\cdots {E}_{M}\right)\\ =2×{1}^{M}+3×{2}^{M}+\cdots +\left(N+1\right)×{N}^{M}\end{array}$

3.4) ${\sum }_{n=1}^{N}\left(n+1\right){n}^{M}=SUM\text{_}K\left(SET\left(N+{K}_{M}+1,PS,PT1\right),{E}_{1}\cdots {E}_{M}\right)$

4. Analysis of SUM_SUBSET(N, PS, [1, 2, ∙∙∙, M + 1])

$PS=\left[1,{K}_{1},{K}_{2},\cdots ,{K}_{M}\right]$, $PT1=\left[1,2,3,\cdots ,M+1\right]$. The simplest subset of PS is SET(N, PS, PT1).

$\begin{array}{l}SUM\text{_}SUBSET\left(N,PS,PT1\right)\\ ={\sum }_{q=0}^{M}{C}_{q}\left(\begin{array}{c}N-\left({K}_{M}-1\right)\\ M+2-q\end{array}\right)={\sum }_{n=1}^{N-{K}_{M}}{\sum }_{q=0}^{M}{C}_{q}\left(\begin{array}{c}n\\ M+1-q\end{array}\right)\\ =1×{K}_{1}×\cdots ×{K}_{M}+2×\left(1+{K}_{1}\right)×\cdots ×\left(1+{K}_{M}\right)+\cdots \\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{ }\text{ }+\left(N-{K}_{M}\right)×\left(\left[N-{K}_{M}-1\right]+{K}_{1}\right)×\cdots ×\left(N-1\right)\\ ={\sum }_{n=1}^{N-{K}_{M}}n\left(n+{K}_{1}-1\right)\left(n+{K}_{2}-1\right)\cdots \left(n+{K}_{M}-1\right)\end{array}$ (1*)

Solve (1*) in a normal way:

Decompose $n\left(n+{K}_{1}-1\right)\cdots \left(n+{K}_{M}-1\right)$ to ${\sum }_{j=1}^{M+1}{D}_{j}\left(\begin{array}{c}n\\ j\end{array}\right)$ ? ${D}_{j}={C}_{q}$, $q=M+1-j$

4.1) $1<{K}_{1}<\cdots <{K}_{M}$, 3.1) can decompose $n\left(n+{K}_{1}-1\right)\cdots \left(n+{K}_{M}-1\right)$ to ${\sum }_{j=1}^{M+1}{D}_{j}\left( n j \right)$

In particular, 1.5) ? ${C}_{q}=\left(M+1\right)!\left(\begin{array}{c}M\\ M-q\end{array}\right)$ ? ${D}_{j}=\left(M+1\right)!\left(\begin{array}{c}M\\ j-1\end{array}\right)$ ?

4.2) ${\left[x\right]}^{M}=\frac{M!}{M!}\left(\begin{array}{c}M-1\\ M-1\end{array}\right){\left[x\right]}_{M}+\frac{M!}{\left(M-1\right)!}\left(\begin{array}{c}M-1\\ M-2\end{array}\right){\left[x\right]}_{M-1}+\cdots +\frac{M!}{1!}\left(\begin{array}{c}M-1\\ 0\end{array}\right){\left[x\right]}_{1}$

4.3) P is a prime number, $N-\left({K}_{M}-1\right)=P$

1) $|SET\left(N,PS,PT1\right)|=P-1$,

2) $\begin{array}{l}SET\left(N,PS,PT1\right)\\ =\left\{\left(1,{K}_{1},\cdots ,{K}_{M}\right),\left(2,1+{K}_{1},\cdots ,1+{K}_{M}\right)\cdots \left(P-1,\cdots ,N-1\right)\right\}\end{array}$

3) if ${K}_{M}\le P-1$ and $PS\ne \left[1,2,\cdots ,P-1\right]$, then $SUM\text{_}SUBSET\left(N,PS,PT1\right)\equiv 0\text{\hspace{0.17em}}MOD\text{\hspace{0.17em}}P$

[Proof]

$\begin{array}{l}|SET\left(N,PS,PT1\right)|=\left(\begin{array}{c}N-PH\left(PS\right)-1-PCHG\left(PS,PT1\right)\\ PB\left(PT1\right)+1\end{array}\right)\\ =\left(\begin{array}{c}\left(P+{K}_{M}-1\right)-\left({K}_{M}+1-PB\left(PS\right)-2\right)-1-PCHG\left(PS,PT1\right)\\ 1\end{array}\right)\\ \stackrel{PB\left(PS\right)=PCHG\left(PS,PT1\right)}{\to }P-1\to \left(1\right)\left( 2 \right)\end{array}$

$SUM\text{_}SUBSET\left(N,PS,PT1\right)={\sum }_{q=0}^{M}{C}_{q}\left(\begin{array}{c}P\\ IDX\left(PT1\right)-q\end{array}\right)$

${K}_{M}\le P-1$ and $PS\ne \left[1,2,\cdots ,P-1\right]\to IDX\left(PT1\right)

q.e.d.

When ${K}_{M}=P-1$ and $PS\ne \left[1,2,\cdots ,P-1\right]$

$\begin{array}{l}SUM\text{_}SUBSET\left(N,PS,\text{}PT1\right)\\ =1×{K}_{1}×\cdots ×{K}_{M}+2×\left(1+{K}_{1}\right)×\cdots ×P\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}+3×\left(2+{K}_{1}\right)\cdots \left(2+{K}_{M-1}\right)\left(2+{K}_{M}\right)\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}+4×\left(3+{K}_{1}\right)\cdots \left(3+{K}_{M-1}\right)\left(3+{K}_{M}\right)+\cdots \\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}+\left(P-1\right)×\left(P-2+{K}_{1}\right)×\cdots ×\left(P-2+{K}_{M}\right)\end{array}$

$3×\left(2+{K}_{1}\right)\cdots \left(2+{K}_{M-1}\right)\left(2+{K}_{M}\right)\equiv 1×3×\left(2+{K}_{1}\right)\cdots \left(2+{K}_{M-1}\right)$

$\begin{array}{l}4×\left(3+{K}_{1}\right)\cdots \left(3+{K}_{M-1}\right)\left(3+{K}_{M}\right)\\ \equiv 2×\left(1+\left[3\right]\right)×\left(1+\left[2+{K}_{1}\right]\right)\cdots \left(1+\left[2+{K}_{M-1}\right]\right)\end{array}$

$\cdots$

$\begin{array}{l}\left(P-1\right)×\left(P-2+{K}_{1}\right)\cdots \left(P-2+{K}_{M}\right)\\ \equiv \left(P-1\right)×\left(P-2+{K}_{1}\right)\cdots \left(P-2+{K}_{M-1}\right)\left(2P-3\right)\\ \equiv \left(P-4+\left[1\right]\right)\left(P-4+\left[3\right]\right)\left(P-4+\left[2+{K}_{1}\right]\right)\cdots \left(P-4+\left[2+{K}_{M-1}\right]\right)\end{array}$

$\begin{array}{l}1×{K}_{1}×\cdots ×{K}_{M}\equiv 1×{K}_{1}×\cdots ×\left(P-1\right)\equiv \left(P+1\right)\left(P+{K}_{1}\right)\cdots \left(P+P-1\right)\\ \equiv \left(P-1\right)\left(P-2+3\right)\left(\left[P-2\right]+\left[2+{K}_{1}\right]\right)\cdots \left(\left[P-2\right]+\left[2+{K}_{M-1}\right]\right)\end{array}$

?

$\begin{array}{l}SUM\text{_}SUBSET\left(N,PS,PT1\right)\\ \equiv SUM\text{_}SUBSET\left(N,\left[1,3,2+{K}_{1},ϵ,2+{K}_{M-1}\right],PT1\right)\text{\hspace{0.17em}}MOD\text{\hspace{0.17em}}P\end{array}$

$PS=\left[1,{K}_{1}\cdots {K}_{M}\right]$ can be slided to $\left[1,3,2+{K}_{1},\cdots ,2+{K}_{M-1}\right]$ by MOD P

If ${K}_{M}=P-1$ and exists ${K}_{i+1}-{K}_{i}>2$, PS can be slided to $\left[1,\cdots ,X

If ${K}_{M}=P-1$ and not exists ${K}_{i+1}-{K}_{i}>2$, PS must be a Basic Shape, can only be slided to $\left[1,\cdots ,X=P-1\right]$

Define:

A Basic Shape $PS=\left[1,{K}_{1}\cdots {K}_{M}\right]=〚{L}_{1}{L}_{2}\cdots {L}_{Q}〛$, among:

Li = count of continuity. (Li, Li+1) means a discontinuity, there are Q-1 discontinuities.

Example: $\left[1,3,5\right]=〚1,1,1〛$, $\left[1,2,3,5\right]=〚3,1〛$, $\left[1,2,4,5\right]=〚2,2〛$

Obvious: $〚{L}_{1}{L}_{2}\cdots {L}_{Q}〛$ can been slided to $\left[{L}_{Q},{L}_{1},{L}_{2},\cdots \right]$, $\left[{L}_{Q-1},{L}_{Q},{L}_{1},{L}_{2},\cdots \right]$, $\cdots$

4.4) PS is a Basic Shape, $IDX\left(PS\right)\text{\hspace{0.17em}}=\text{\hspace{0.17em}}P$, $PS\text{\hspace{0.17em}}\ne \text{\hspace{0.17em}}\left[1,2,\cdots ,P-1\right]$, $\left\{PS1,PS2,\cdots \right\}$ are all shapes that PS can scroll to, then $MIN\left(PS1\right)+MIN\left(PS2\right)+\cdots \equiv 0\text{\hspace{0.17em}}MOD\text{\hspace{0.17em}}P$. This is a promotion of 1.6)

[Proof]

$3×\left(2+{K}_{1}\right)\cdots \left(2+{K}_{M-1}\right)\left(2+{K}_{M}\right)\equiv 1×3×\left(2+{K}_{1}\right)\cdots \left(2+{K}_{M-1}\right)MOD\text{\hspace{0.17em}}P$

If $2+{K}_{M-1}\ne P$, $\left[1,3,\left(2+{K}_{1}\right),\cdots ,\left(2+{K}_{M-1}\right)\right]\in \left\{PS1,PS2,\cdots \right\}$

$SUM\text{_}SUBSET\left(N,PS1,PT1\right)\equiv MIN\left(PS1\right)+MIN\left(PS2\right)+\cdots \equiv 0\text{\hspace{0.17em}}MOD\text{\hspace{0.17em}}P$

q.e.d.

Example:

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

5. Calculation Formula of ${1}^{M}+{2}^{M}+{3}^{M}+\cdots +{N}^{M}$

Use the form $\left({T}_{1}+{K}_{1}\right)\left({T}_{2}+{K}_{2}\right)\cdots \left({T}_{M}+{K}_{M}\right)$.

In general, Ki and Kj cannot be exchanged, but when $PT=PT1=\left[1,2,\cdots ,M+1\right]$,

$SUM\text{_}SUBSET\left(N,PS,PT1\right)={\sum }_{q=0}^{M}{C}_{q}\left(\begin{array}{c}N-PH\left(PS\right)-PCHG\left(PS,PT1\right)\\ IDX\left(PT1\right)-q\end{array}\right)$

${C}_{q}=\sum {\prod }_{i=1}^{M}\left({X}_{i}+{D}_{i}\right)=\sum {\prod }_{\text{choice}\text{\hspace{0.17em}}M-q\text{\hspace{0.17em}}\text{from}\text{\hspace{0.17em}}T}\left(T-D\right){\prod }_{\text{choice}\text{\hspace{0.17em}}q\text{\hspace{0.17em}}\text{from}\text{\hspace{0.17em}}K}\left(K+D\right)$

Easy to see: ${\prod }_{\text{choice}\text{\hspace{0.17em}}M-q\text{\hspace{0.17em}}\text{from}\text{\hspace{0.17em}}T}\left(T-D\right)=\left(M+1-q\right)!$

Can prove: $\left({K}_{1},{K}_{2},\cdots ,{K}_{M}\right)$ is permutable in $\sum {\prod }_{\text{choice}\text{\hspace{0.17em}}q\text{\hspace{0.17em}}\text{from}\text{\hspace{0.17em}}K}\left(K+D\right)$

? $\left({K}_{1},{K}_{2},\cdots ,{K}_{M}\right)$ is permutable in the form.

$\begin{array}{l}SUM\text{_}SUBSET\left(N,PS,PT1\right)\\ ={\sum }_{q=0}^{M}{A}_{q}\left(\begin{array}{c}N-{K}_{M}+1\\ M+2-q\end{array}\right)={\sum }_{n={K}_{M}+1}^{N}{\sum }_{q=0}^{M}{A}_{q}\left(\begin{array}{c}n-{K}_{M}\\ M+1-q\end{array}\right)\\ =1×{K}_{1}×\cdots ×{K}_{M}+2×\left(1+{K}_{1}\right)×\cdots ×\left(2+{K}_{M}\right)+\cdots \end{array}$

Add one more factor Ki to the end:

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

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

Let $PS2=\left[1,{K}_{1},\cdots ,{K}_{M},{K}_{M+1}={K}_{i}\right]$,

$PT2=\left[1,{T}_{1},\cdots ,{T}_{M},{T}_{M+1}\right]=\left[1,2,\cdots ,M+1,M+2\right]$

$IDX\left(PT2\right)=M+3$, $N-PH\left(PS2\right)-PCHG\left(PS2,PT2\right)=N-{K}_{M}+1$

$q=\text{count}\text{\hspace{0.17em}}\text{of}\text{\hspace{0.17em}}\left\{{X}_{1},\cdots ,{X}_{M}\right\}\in K$

${A}_{q}\left(M+2-q\right)={A}_{q}\left({T}_{M+1}-q\right)$ means ${X}_{M+1}={T}_{M+1}$, ${A}_{q}\left({K}_{i}+\left(M-q\right)\right)$ means ${X}_{M+1}={K}_{M+1}$

It’s match the form $\left({T}_{1}+{K}_{1}\right)\left({T}_{2}+{K}_{2}\right)\cdots \left({T}_{M}+{K}_{M}\right)\left({T}_{M}{}_{+1}+{K}_{i}\right)$

Recursion ?

5.1) ${K}_{i}<{K}_{j}$, ${K}_{i}={K}_{j}$, ${K}_{i}>{K}_{j}$ are allowed, $SUM\text{_}SUBSET\left(N,PS,PT1\right)$ can use the form $\left({T}_{1}+{K}_{1}\right)\left({T}_{2}+{K}_{2}\right)\cdots \left({T}_{M}+{K}_{M}\right)$

Example:

The form = $\left(2+3\right)\left(3+5\right)\left(4+3\right)$ ?

$\begin{array}{l}SUM\text{_}SUBSET\left(N,\left[1,3,5,3\right],\left[1,2,3,4\right]\right)\\ =24\left(\begin{array}{c}N-4\\ 5\end{array}\right)+84\left(\begin{array}{c}N-4\\ 4\end{array}\right)+102\left(\begin{array}{c}N-4\\ 3\end{array}\right)+45\left(\begin{array}{c}N-4\\ 2\end{array}\right)\end{array}$

Among:

$45=3×5×3$

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

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

$\begin{array}{l}SUM\text{_}SUBSET\left(9,\left[1,3,5,3\right],\left[1,2,3,4\right]\right)\\ =1×3×3×5+2×4×4×6+3×5×5×7+4×6×6×8=1914\\ =24\left(\begin{array}{c}5\\ 5\end{array}\right)+84\left(\begin{array}{c}5\\ 4\end{array}\right)+102\left(\begin{array}{c}5\\ 3\end{array}\right)+45\left( 5 2 \right)\end{array}$

The form = $\left(2+4\right)\left(3+7\right)\left(4+7\right)$ ?

$\begin{array}{l}SUM\text{_}SUBSET\left(N,\left[1,4,7,7\right],\left[1,2,3,4\right]\right)\\ =24\left(\begin{array}{c}N-6\\ 5\end{array}\right)+126\left(\begin{array}{c}N-6\\ 4\end{array}\right)+248\left(\begin{array}{c}N-6\\ 3\end{array}\right)+196\left(\begin{array}{c}N-6\\ 2\end{array}\right)\end{array}$

Among:

$196=4×7×7$

$248=4×7×\left(4-2\right)+4×\left(3-1\right)×\left(7+1\right)+2×\left(7+1\right)×\left(7+1\right)$

$126=2×3×\left(7+2\right)+2×\left(7+1\right)×\left(4-1\right)+4×\left(3-1\right)×\left(4-1\right)$

$\begin{array}{l}SUM\text{_}SUBSET\left(12,\left[1,4,7,7\right],\left[1,2,3,4\right]\right)\\ =1×4×7×7+2×5×8×8+3×6×9×9+4×7×10×10+5×8×11×11\\ =9934=24\left(\begin{array}{c}6\\ 5\end{array}\right)+126\left(\begin{array}{c}6\\ 4\end{array}\right)+248\left(\begin{array}{c}6\\ 3\end{array}\right)+196\left( 6 2 \right)\end{array}$

In particular:

5.2) ${\sum }_{n=1}^{M}{n}^{M}=SUM\text{_}SUBSET\left(N+1,\left[1,1,\cdots ,1\right],\left[1,2,\cdots ,M\right]\right)$

Example:

$\left(N+1\right)-PH\left(PS\right)-PCHG\left(PS,PT1\right)=\left(N+1\right)-0-0=N+1$

The form = $\left(2+1\right)$

? ${1}^{2}+{2}^{2}+\cdots +{N}^{2}=2\left(\begin{array}{c}N+1\\ 3\end{array}\right)+\left(\begin{array}{c}N+1\\ 2\end{array}\right)=\frac{N\left(N+1\right)\left(2N+1\right)}{6}$

The form = $\left(2+1\right)\left(3+1\right)$

? ${1}^{3}+{2}^{3}+\cdots +{N}^{3}=6\left(\begin{array}{c}N+1\\ 4\end{array}\right)+6\left(\begin{array}{c}N+1\\ 3\end{array}\right)+\left(\begin{array}{c}N+1\\ 2\end{array}\right)=\frac{{N}^{2}{\left(N+1\right)}^{2}}{4}$

The form = $\left(2+1\right)\left(3+1\right)\left(4+1\right)$

? ${1}^{4}+{2}^{4}+\cdots +{N}^{4}=24\left(\begin{array}{c}N+1\\ 5\end{array}\right)+36\left(\begin{array}{c}N+1\\ 4\end{array}\right)+14\left(\begin{array}{c}N+1\\ 3\end{array}\right)+\left(\begin{array}{c}N+1\\ 2\end{array}\right)$

Among:

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

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

S(M, K) is Stirling number of the second kind,

Definition of S(M, K) ? ${\sum }_{n=1}^{N}{n}^{M}={\sum }_{K=1}^{M}K!S\left(M,K\right)\left(\begin{array}{c}N+1\\ K+1\end{array}\right)$

It’s equal to 5.2), so we have a way to calculate S(M, K).

3.4) can be seen as ${\sum }_{n=1}^{N}\left(n+1\right){n}^{M}=SUM\text{_}SUBSET\left(N+1,\left[1,0,\cdots ,0\right],\left[1,2,\cdots ,M+1\right]\right)$

Cite this paper: Peng, J. (2020) Subset of the Shape of Numbers. Open Access Library Journal, 7, 1-15. doi: 10.4236/oalib.1107040.
References

   Peng, J. (2020) Shape of Numbers and Calculation Formula of Stirling Numbers. Open Access Library Journal, 7, 1-11. https://doi.org/10.4236/oalib.1106081

   Peng, J. (2020) Subdivide the Shape of Numbers and a Theorem of Ring. Open Access Library Journal, 7, 1-14. https://doi.org/10.4236/oalib.1106719

Top