Subset of the Shape of Numbers

Ji Peng

doi:10.4236/oalib.1107040

Open Access Library Journal > Vol.7 No.12, December 2020

Subset of the Shape of Numbers

Ji Peng
Department of Electronic Information, Nanjing University, Nanjing, China.
DOI: 10.4236/oalib.1107040 PDF HTML XML 396 Downloads 889 Views Citations

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 1^M+2^M+3^M+···+N^M. The Shape’s concept becomes clearer and richness.

Keywords

Shape of Numbers, Calculation Formula, Sum of Powers of Integers, Combinatorics, Congruence, Stirling Number

Share and Cite:

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

1. Introduction

Peng, J. has introduced Shape of numbers in [1] [2]:

$(I_{1}, I_{2}, \dots, I_{M}), I_{i} \in N, I_{1} < I_{2} < \dots < 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 $(I_{1}, I_{2}, \dots, I_{M})$ with the same continuity and discontinuity at the same position into a catalog, call it a Shape. A Shape has a min Item:

$(1, K_{1}, K_{2}, \dots)$ , Use the symbol PS = [min Item] to represent it. If $K_{i + 1} - K_{i} = D > 1$ then only $I_{i + 1} - I_{i} \geq D$ is allowed.

The single $(I_{1}, I_{2}, \dots, I_{M})$ is an item, $I_{1} I_{2} \dots I_{M}$ is the product. I_i is a factor.

Example:

$P S = [1, 2] \to (1, 2), (2, 3), (3, 4), (1000, 1001) \in P S$

$P S = [1, 3] \to (1, 3), (1, 4), (2, 4), (1, 5), (2, 5), (3, 5), (1000, 2001) \in P S$

$P S = [1, 4] \to (1, 4), (1, 5), (2, 5), (1, 6), (2, 6), (3, 6) \in P S, (3, 5), (4, 6) \notin P S$

$P S = [1, 4, 6] \to (1, 4, 7), (1, 5, 7), (2, 5, 7) \in P S, (3, 5, 7) \notin P S$

Define:

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

PM(PS) = count of factors

PB(PS) = count of discontinuities

MIN(PS) = min product: $M I N ([1, 2, 3]) = 1 \times 2 \times 3$ , $M I N ([1, 2, 4]) = 1 \times 2 \times 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:

$P S = [1, 2] \to B A S E (P S) = [1, 2]$

$P S = [1, 3], [1, 4], [1, K > 2] \to B A S E (P S) = [1, 3]$

$P S = [1, 3, 4], [1, 4, 5], [1, K > 2, X = K + 1] \to B A S E (P S) = [1, 3, 4]$

$P S = [1, 3, 5], [1, 4, 9], [1, K > 2, X > K + 1] \to B A S E (P S) = [1, 3, 5]$

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

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

Example:

$S U M (6, [1, 2, 4]) = 1 \times 2 \times 4 + 1 \times 2 \times 5 + 2 \times 3 \times 5$

$S U M (9, [1, 4, 7]) = 1 \times 4 \times 7 + 1 \times 4 \times 8 + 1 \times 5 \times 8 + 2 \times 5 \times 8$

[1] [2] came to the following conclusion:

1.1) $| S E T (N, P S) | = (\begin{matrix} N - P H (P S) - 1 \\ P B (P S) + 1 \end{matrix})$

1.2) $S U M (N, P S) = M I N (P S) (\begin{matrix} N \\ I D X (P S) \end{matrix})$ , PS is a Basic Shape

The following uses count of $X \in K$ for count of ${X_{1}, X_{2}, \dots, X_{M}} \in {K_{1}, K_{2}, \dots, K_{M}}$

1.3) $P S = [1, K_{1}, \dots, K_{M}]$ , $B S = B A S E (P S) = [1, G_{1}, \dots, G_{M}]$

Use the form $(G_{1} + K_{1}) (G_{2} + K_{2}) \dots (G_{M} + K_{M}) = \sum X_{1} X_{2} \dots X_{M}$ , X_i = G_i or K_i.

The expansion has 2^M items, don’t swap the factors of $X_{1} X_{2} \dots X_{M}$ , then each $X_{1} X_{2} \dots X_{M}$ corresponds to one expression = $A_{q} (\begin{matrix} N - P H (P S) \\ I D X (B S) - q \end{matrix})$ , q = count of $X \in K$

$S U M (N, P S) = \sum A_{q} (\begin{matrix} N - P H (P S) \\ I D X (B S) - q \end{matrix})$ , 2^M items in total.

$A_{q} = \prod_{i = 1}^{M} (X_{i} + D_{i})$ , $D_{i} = {\begin{cases} - m : X_{i} = G_{i}, m = countof {X_{1}, \dots, X_{i - 1}} \in K \\ + m : X_{i} = K_{i}, m = countof {X_{1}, \dots, X_{i - 1}} \in G \end{cases}$

Example:

$P S = [1, K_{1} \geq 3, K_{2} \geq K_{1} + 2, K_{3} \geq K_{2} + 2]$ , $B S = B A S E (P S) = [1, 3, 5, 7]$

$\begin{matrix} Theform = (3 + K_{1}) (5 + K_{2}) (7 + K_{3}) \\ = 3 \times 5 \times 7 + 3 \times 5 \times K_{3} + 3 \times K_{2} \times 7 + 3 \times K_{2} \times K_{3} \\ + K_{1} \times 5 \times 7 + K_{1} \times 5 \times K_{3} + K_{1} \times K_{2} \times 7 + K_{1} \times K_{2} \times K_{3} \end{matrix}$

$\begin{matrix} P = N - P H (P S) = N - {I D X (P S) - P B (P S) - 2} \\ = N - {K_{3} + 1 - 3 - 2} = N - K_{3} + 4 \end{matrix}$

$I D X (B S) = 8$

$\begin{array}{l} S U M (N, P S) = 3 \times 5 \times 7 (\begin{matrix} P \\ 8 \end{matrix}) + 3 \times 5 \times (K_{3} + 2) (\begin{matrix} P \\ 7 \end{matrix}) \\ + 3 \times (K_{2} + 1) \times (7 - 1) (\begin{matrix} P \\ 7 \end{matrix}) + 3 \times (K_{2} + 1) \times (K_{3} + 1) (\begin{matrix} P \\ 6 \end{matrix}) \\ + K_{1} \times (5 - 1) \times (7 - 1) (\begin{matrix} P \\ 7 \end{matrix}) + K_{1} \times (5 - 1) \times (K_{3} + 1) (\begin{matrix} P \\ 6 \end{matrix}) \\ + K_{1} \times K_{2} \times (7 - 2) (\begin{matrix} P \\ 6 \end{matrix}) + K_{1} \times K_{2} \times K_{3} ( P 5 ) \end{array}$

$Anitem \in P S = {begin, K_{1} + E_{1}, \dots, K_{M} + E_{M}}$ , K is fixed, E is variable.

$Aproduct = begin \times (K_{1} + E_{1}) \dots (K_{M} + E_{M}) = begin \times \sum F_{1} F_{2} \dots F_{M}$ , $F_{i} = E_{i}$ or $F_{i} = K_{i}$

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

Define

$S U M_K (S E T (N, P S), P F = F_{1} F_{2} \dots F_{M})$ = Sum of one part of $S U M (N, P S)$

PF indicates the part. $P F = F_{1} F_{2} \dots F_{M}$ , $F_{i} = E_{i}$ or $F_{i} = K_{i}$

Rewrite 1.3) and add {braces}:

$\begin{matrix} S U M (N, P S) = \sum product = \sum \sum begin \times F_{1} \dots F_{M} \\ = \sum \prod_{i = 1}^{M} (X_{i} + D_{i}) (\begin{matrix} A \\ M_{q} \end{matrix}) \end{matrix}$

$X_{i} + D_{i} = {\begin{cases} {G_{i} - D_{i}} : X_{i} = G_{i}, D_{i} = countof {X_{1}, \dots, X_{i - 1}} \in K \\ {K_{i}} + {D_{i}} : X_{i} = K_{i}, D_{i} = countof {X_{1}, \dots, X_{i - 1}} \in G \end{cases}$

Let $S U M 1 (N, P S) = S U M (N, P S)$ expand by the {braces}:

1.4) $S U M_K (S E T (N, P S), P F) = \sum Expansionof S U M 1 (N, P S)$ with same ${K_{i}} \in P F = \sum \prod_{i = 1}^{M} Y_{i} (\begin{matrix} A \\ M_{q} \end{matrix})$ , $Y_{i} = {\begin{cases} 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} = countof {X_{1}, \dots, X_{i - 1}} \in K \\ D_{i} : F_{i} = E_{i}, X_{i} = K_{i}, D_{i} = countof {X_{1}, \dots, X_{i - 1}} \in G \end{cases}$

Example:

$S U M (N, [1, K_{1} \geq 3, K_{2} \geq K_{1} + 2])$ , $form = (3 + K_{1}) (5 + K_{2})$ ?

$\begin{array}{l} = 15 (\begin{matrix} N - K_{2} + 3 \\ 6 \end{matrix}) + 3 ({K_{2}} + {1}) (\begin{matrix} N - K_{2} + 3 \\ 5 \end{matrix}) \\ + K_{1} ({5 - 1}) (\begin{matrix} N - K_{2} + 3 \\ 5 \end{matrix}) + K_{1} K_{2} (\begin{matrix} N - K_{2} + 3 \\ 4 \end{matrix}) \end{array}$

Expand by the {braces}:

$\begin{array}{l} = {15 (\begin{matrix} N - K_{2} + 3 \\ 6 \end{matrix}) + 3 (\begin{matrix} N - K_{2} + 3 \\ 5 \end{matrix})} + 3 K_{2} (\begin{matrix} N - K_{2} + 3 \\ 5 \end{matrix}) \\ + 4 K_{1} (\begin{matrix} N - K_{2} + 3 \\ 5 \end{matrix}) + K_{1} K_{2} (\begin{matrix} N - K_{2} + 3 \\ 4 \end{matrix}) \\ = \sum_{begin = 1}^{N - K_{2}} \sum begin \times (K_{1} + E_{1, begin}) (K_{2} + E_{2, begin}) \end{array}$

$\begin{array}{l} S U M_K (S E T (N, P S), E_{1} E_{2}) \\ = \sum_{allitems} begin * E_{1, i} E_{2, i} = 15 (\begin{matrix} N - K_{2} + 3 \\ 6 \end{matrix}) + 3 (\begin{matrix} N - K_{2} + 3 \\ 5 \end{matrix}) \end{array}$

$S U M_K (S E T (N, P S), E_{1} K_{2}) = \sum_{allitems} begin * E_{1, i} K_{2} = 3 K_{2} (\begin{matrix} N - K_{2} + 3 \\ 5 \end{matrix})$

$S U M_K (S E T (N, P S), K_{1} E_{2}) = \sum_{allitems} begin * K_{1} E_{2, i} = 4 K_{1} (\begin{matrix} N - K_{2} + 3 \\ 5 \end{matrix})$

$S U M_K (S E T (N, P S), K_{1} K_{2}) = \sum_{allitems} begin * K_{1} K_{2} = K_{1} K_{2} (\begin{matrix} N - K_{2} + 3 \\ 4 \end{matrix})$

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} = Count of X \in K$ , $N_{1} + N_{2} = M$

$H (N_{1}, N_{2}, K) = \sum A_{q = N_{1}} = \sum \prod_{i = 1}^{M} (X_{i} + D_{i}) = K_{1} K_{2} \dots K_{M} (\begin{matrix} M \\ N_{1}, N_{2} \end{matrix})$

Sum traverses all (N₁, N₂)-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,

$P M (P S 1) = P M (P S 2) = \dots$ , $P B (P S 1) = P B (P S 2) = \dots > 0$ , $I D X (P S 1) = I D X (P S 2) = \dots = P$ ,

That is, them are Basic shapes, have same count of factors and same count of discontinuities > 0, and max factor = P − 1, then $M I N (P S 1) + M I N (P S 2) + \dots \equiv 0 M O D P$

Example:

$\begin{array}{l} 1 \times 2 \times 4 \times 6 + 1 \times 3 \times 4 \times 6 + 1 \times 3 \times 5 \times 6 \\ \equiv 1 \times 2 \times 3 \times 4 \times 6 + 1 \times 2 \times 3 \times 5 \times 6 + 1 \times 2 \times 4 \times 5 \times 6 + 1 \times 3 \times 4 \times 5 \times 6 \\ \equiv 0 M O D 7 \end{array}$

2. Subset of SET(N, PS)

$P S = [1, K_{1}, K_{2}, \dots, K_{M}]$ , $P T = [1, T_{1}, T_{2}, \dots, T_{M}]$ , $Item = {I_{0}, I_{1}, I_{2}, \dots, I_{M}} \in S E T (N, P S)$

If PB(PS) = 0, $items \in S E T (N, P S)$ 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} P T = [1, T_{1}, \dots, T_{M}] \\ = {\begin{cases} T_{i + 1} - T_{i} = 1 : K_{i + 1} - K_{i} = 1, means I_{i + 1} - I_{i} = 1 \\ T_{i + 1} - T_{i} = 1 : K_{i + 1} - K_{i} = D > 1, means I_{i + 1} - I_{i} = D \\ T_{i + 1} - T_{i} = 2 : K_{i + 1} - K_{i} = D > 1, means I_{i + 1} - I_{i} \geq D \end{cases} \end{array}$ (*)

others are invalid.

Example:

$S E T (N, [1, 3, 5], [1, 3, 5]) = S E T (N, [1, 3, 5])$

$S E T (N, [1, 3, 5], [1, 4, 5])$ , $S E T (N, [1, 3, 5], [1, 3, 6])$ , $S E T (N, [1, 2, 9], [1, 3, 4])$ is invalid.

$\begin{array}{l} S E T (N, [1, 3, 5], [1, 2, 4]) \\ = {(1, 3, 5), (1, 3, 6), (2, 4, 6), (1, 3, 7), (2, 4, 7), (3, 5, 7), \dots} \end{array}$

$I_{2} - I_{1} = (3 - 1) = 2$ , $I_{3} - I_{2} \geq (5 - 3) = 2$

$\begin{array}{l} S E T (N, [1, 3, 5], [1, 3, 4]) \\ = {(1, 3, 5), (1, 4, 6), (2, 4, 6), (1, 5, 7), (2, 5, 7), (3, 5, 7), \dots} \end{array}$

$I_{3} - I_{2} = (5 - 3) = 2$ , $I_{2} - I_{1} \geq (3 - 1) = 2$

$S E T (N, [1, 3, 5], [1, 2, 3]) = {(1, 3, 5), (2, 4, 6), (3, 5, 7), \dots}$

$\begin{array}{l} S E T (N, [1, 4, 8], [1, 2, 4]) \\ = {(1, 4, 8), (1, 4, 9), (2, 5, 9), (1, 4, 10), (2, 5, 10), (3, 6, 10), \dots} \end{array}$

$I_{2} - I_{1} = (4 - 1) = 3$ , $I_{3} - I_{2} \geq (8 - 4) = 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:

$P C H G ([1, 3, 5], [1, 2, 4]) = P C H G ([1, 4, 7], [1, 2, 4]) = 1$ , changed at T₁

$P C H G ([1, 3, 5], [1, 3, 4]) = P C H G ([1, 4, 7], [1, 3, 4]) = 1$ , changed at T₂

$P C H G ([1, 3, 5], [1, 2, 3]) = P C H G ([1, 8, 10], [1, 2, 3]) = 2$ , changed at T₁, T₂

2.1) $S E T (N, P S) = S E T (N, P S, B A S E (P S))$

2.2) $| S E T (N, P S, P T) | = (\begin{matrix} N - P H (P S) - 1 - P C H G (P S, P T) \\ P B (P T) + 1 \end{matrix})$

If PT1 only change T_i of PT, Obvious: $P C H G (P S, P T 1) = P C H G (P S, P T) + 1$

2.3) If PT1 only change T_i of PT, $P T 1 = [1, T_{1}, \dots, T_{i - 1}, T_{i} - 1, T_{i + 1} - 1, \dots, T_{M} - 1]$ .

Let $P S 1 = [1, K_{1}, \dots, K_{i - 1}, K_{i} + 1, K_{i + 1} + 1, \dots, K_{M} + 1]$ , then

$S E T (N, P S, P T) = S E T (N, P S, P T 1) \cup S E T (N, P S 1, P T)$

$S E T (N, P S, P T 1) = S E T (N, P S, P T) - S E T (N, P S 1, P T)$

In particular: $P C H G (P S, P T) = 1$ ? $S E T (N, P S, P T) = S E T (N, P S) - S E T (N, P S 1)$

[Proof]

PT1 change T_i of PT ? $T_{i} - T_{i - 1} = 2$ ? $K_{i} - K_{i - 1} > 1$ ? $P C H G (P S, P T) = P C H G (P S 1, P T)$

$\begin{array}{l} | S E T (N, P S, P T 1) | + | S E T (N, P S 1, P T) | \\ = (\begin{matrix} N - P H (P S) - 1 - P C H G (P S, P T 1) \\ P B (P T 1) + 1 \end{matrix}) \\ + (\begin{matrix} N - P H (P S 1) - 1 - P C H G (P S 1, P T) \\ P B (P T) + 1 \end{matrix}) \\ = (\begin{matrix} N - P H (P S) - 2 - P C H G (P S, P T) \\ P B (P T) \end{matrix}) \\ + (\begin{matrix} N - P H (P S) - 2 - P C H G (P S 1, P T) \\ P B (P T) + 1 \end{matrix}) \end{array}$

$\begin{array}{l} = (\begin{matrix} N - P H (P S) - 2 - P C H G (P S, P T) \\ P B (P T) \end{matrix}) \\ + (\begin{matrix} N - P H (P S) - 2 - P C H G (P S, P T) \\ P B (P T) + 1 \end{matrix}) \\ = (\begin{matrix} N - P H (P S) - 1 - P C H G (P S, P T) \\ P B (P T) + 1 \end{matrix}) \\ = | S E T (N, P S, P T) | \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 $P C H G (P S, P T) = 2$ , PT changes at T_i and T_j, then

$P T = [1, G_{1}, \dots, G_{i - 1}, G_{i} - 1, \dots, G_{j - 1} - 1, G_{j} - 2, G_{j + 1} - 2, \dots, G_{M} - 2]$

Let

$P T A = [1, G_{1}, \dots, G_{i - 1}, G_{i} - 1, \dots, G_{M} - 1]$ ,

$P T B = [1, G_{1}, \dots, G_{j - 1}, G_{j} - 1, \dots, G_{M} - 1]$

$P S A = [1, K_{1}, \dots, K_{i - 1}, K_{i} + 1, \dots, K_{M} + 1]$ ,

$P S B = [1, K_{1}, \dots, K_{j - 1}, K_{j} + 1, \dots, K_{M} + 1]$

$P S 2 = [1, K_{1}, \dots, K_{i - 1}, K_{i} + 1, \dots, K_{j - 1} + 1, K_{j} + 2, K_{j + 1} + 2, \dots, K_{M} + 2]$

$\begin{array}{l} S E T (N, P S, P T) = S E T (N, P S, P T A) - S E T (N, P S A, P T A) \\ = {S E T (N, P S, B S) - S E T (N, P S B, B S)} \\ - {S E T (N, P S A, B S) - S E T (N, P S 2, B S)} \\ = S E T (N, P S, B S) - [S E T (N, P S A, B S) \cup S E T (N, P S B, B S)] \\ + S E T (N, P S 2, B S) \\ = S E T (N, P S) - [S E T (N, P S A) \cup S E T (N, P S B)] + S E T (N, P S 2) \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.

$P S = [1, K_{1}, K_{2}, \dots, K_{M}]$ , $B S = B A S E (P S) = [1, G_{1}, G_{2}, \dots, G_{M}]$ , $P T = [1, T_{1}, T_{2}, \dots, T_{M}]$

3.1) Use the form $(T_{1} + K_{1}) (T_{2} + K_{2}) \dots (T_{M} + K_{M}) = \sum X_{1} X_{2} \dots X_{M}$ , then

$S U M_S U B S E T (N, P S, P T) = \sum A_{q} (\begin{matrix} N - P H (P S) - P C H G (P S, P T) \\ I D X (P T) - q \end{matrix})$

$A_{q} = \prod_{i = 1}^{M} (X_{i} + D_{i})$ , $D_{i} = {\begin{cases} - m : X_{i} = T_{i}, m = countof {X_{1}, \dots, X_{i - 1}} \in K \\ + m : X_{i} = K_{i}, m = countof {X_{1}, \dots, X_{i - 1}} \in T \end{cases}$

$q = count of X \in K$

[Proof]

1) If PT = BS, then $S U M_S U B S E T (N, P S, B S) = S U M (N, P S)$ ? the formula holds.

2) If M = 1 and PT has 1 change, then $P S = [1, K_{1} > 2]$ , $P T = [1, T_{1}] = [1, 2]$ , $B S = [1, G_{1}] = [1, 3]$ ,

Let $P S 1 = [1, K_{1} + 1]$ , 2.3) →

$\begin{array}{l} S U M_S U B S E T (N, P S, P T) \\ = S U M (N, P S) - S U M (N, P S 1) \\ = {G_{1} (\begin{matrix} N - P H (P S) \\ I D X (B S) \end{matrix}) + K_{1} (\begin{matrix} N - P H (P S) \\ I D X (B S) - 1 \end{matrix})} \\ - {G_{1} (\begin{matrix} N - P H (P S 1) \\ I D X (B S) \end{matrix}) + (K_{1} + 1) (\begin{matrix} N - P H (P S 1) \\ I D X (B S) - 1 \end{matrix})} \end{array}$

$\begin{array}{l} = {G_{1} (\begin{matrix} N - P H (P S 1) \\ I D X (B S) \end{matrix}) + K_{1} (\begin{matrix} N - P H (P S 1) \\ I D X (B S) - 1 \end{matrix}) \\ + G_{1} (\begin{matrix} N - P H (P S 1) \\ I D X (B S) - 1 \end{matrix}) + K_{1} (\begin{matrix} N - P H (P S 1) \\ I D X (B S) - 2 \end{matrix})} \\ - {G_{1} (\begin{matrix} N - P H (P S 1) \\ I D X (B S) \end{matrix}) + (K_{1} + 1) (\begin{matrix} N - P H (P S 1) \\ I D X (B S) - 1 \end{matrix})} \\ = (G_{1} - 1) (\begin{matrix} N - P H (P S 1) \\ I D X (B S) - 1 \end{matrix}) + K_{1} (\begin{matrix} N - P H (P S 1) \\ I D X (B S) - 2 \end{matrix}) \end{array}$

$\begin{array}{l} = T_{1} (\begin{matrix} N - P H (P S 1) \\ I D X (B S) - 1 \end{matrix}) + K_{1} (\begin{matrix} N - P H (P S 1) \\ I D X (B S) - 2 \end{matrix}) \\ = T_{1} (\begin{matrix} N - P H (P S) - 1 \\ I D X (P T) \end{matrix}) + K_{1} (\begin{matrix} N - P H (P S) - 1 \\ I D X (P T) - 1 \end{matrix}) \\ = T_{1} (\begin{matrix} N - P H (P S) - P C H G (P S, P T) \\ I D X (P T) \end{matrix}) \\ + K_{1} (\begin{matrix} N - P H (P S) - P C H G (P S, P T) \\ I D X (P T) - 1 \end{matrix}) \end{array}$

The form = (T₁ + K₁) ? The formula holds.

3) If M > 1 and PT only has 1 change at T_M, then $P T = [1, G_{1}, \dots, G_{M - 1}, G_{M} - 1]$

Let $P S 1 = [1, K_{1}, \dots, K_{M - 1}, K_{M} + 1]$ , 2.3) → $P H (P S 1) = P H (P S) + 1$ :

$\begin{array}{l} S U M (N, P S, P T) = S U M (N, P S) - S U M (N, P S 1) \\ = \sum_{i = I D X (B S) - M}^{I D X (B S)} \sum A_{i} (\begin{matrix} N - P H (P S) \\ i \end{matrix}) - \sum_{i = I D X (B S) - M}^{I D X (B S)} \sum B_{i} (\begin{matrix} N - P H (P S 1) \\ i \end{matrix}) \\ = \sum_{i = I D X (B S) - M}^{I D X (B S)} \sum A_{i} {(\begin{matrix} N - P H (P S 1) \\ i \end{matrix}) + (\begin{matrix} N - P H (P S 1) \\ i - 1 \end{matrix})} \\ - \sum_{i = I D X (B S) - M}^{I D X (B S)} \sum B_{i} (\begin{matrix} N - P H (P S 1) \\ i \end{matrix}) \end{array}$

$\begin{array}{l} = \sum_{i = I D X (B S) - M}^{I D X (B S)} (\sum A_{i} - \sum B_{i}) (\begin{matrix} N - P H (P S 1) \\ i \end{matrix}) + \sum A_{i} (\begin{matrix} N - P H (P S 1) \\ i - 1 \end{matrix}) \\ = \sum_{i = I D X (B S) - M}^{I D X (B S)} (\sum A_{i} - \sum B_{i}) (\begin{matrix} N - P H (P S) - 1 \\ i \end{matrix}) + \sum A_{i} (\begin{matrix} N - P H (P S) - 1 \\ i - 1 \end{matrix}) \\ = \sum_{i = I D X (B S) - M - 1}^{I D X (B S)} \sum C_{J} (\begin{matrix} N - P H (P S) - 1 \\ J \end{matrix}), J = i - 1, \sum C_{J - 1} = \sum A_{i + 1} + \sum A_{i} - \sum B_{i} \\ = \sum_{J = I D X (P T) - M}^{I D X (P T) + 1} \sum C_{J} (\begin{matrix} N - P H (P S) - 1 \\ J \end{matrix}) \end{array}$

When $i = I D S (B S)$ , $\sum C_{i} = M I N (B S) - M I N (B S) = 0$

$= \sum_{J = I D X (P T) - M}^{I D X (P T)} \sum C_{J} (\begin{matrix} N - P H (P S) - 1 \\ J \end{matrix})$

Use the symbol of (1.3)

$i = I D X (B S) - C N T$ , $C N T = Count of X \in K$

Let $R (E) = \sum \prod_{L = 1}^{M - 1} (X_{L} + D_{L})$ , $E = Count of {X_{1}, \dots, X_{M - 1}} \in K$

$\begin{array}{l} \sum A_{i + 1} = R (C N T - 1) (G_{M} - (C N T - 1)) \\ + R (C N T - 2) (K_{M} + (M - 1) - (C N T - 2)) \end{array}$

$\sum A_{i} = R (C N T) (G_{M} - C N T) + R (C N T - 1) (K_{M} + (M - 1) - (C N T - 1))$

$\sum B_{i} = R (C N T) (G_{M} - C N T) + R (C N T - 1) ((K_{M} + 1) + (M - 1) - (C N T - 1))$

$\begin{array}{l} \sum C_{J - 1} = \sum A_{i + 1} + \sum A_{i} - \sum B_{i} \\ = R (C N T - 1) (G_{M} - C N T) + R (C N T - 2) (K_{M} + M - C N T + 1) \\ = R (C N T - 1) (T_{M} - {C N T - 1}) + R (C N T - 2) (K_{M} + {(M - 1) - (C N T - 2)}) \end{array}$

? Match of the form $(T_{1} + K_{1}) (T_{2} + K_{2}) \dots (T_{M} + K_{M})$

4) If M > 1 and PT only has 1 change at $T_{i}_{< M}$ , Let $R (E) = \sum \prod_{L = 1, l \neq i}^{M} (X_{L} + D_{L})$ , use the same method of (3).

5) if $P C H G (P S, P T) > 1$ , Use 2.3) → divide the Items into subset ? deducing by induction.

q.e.d.

Example:

$N - P H ([1, 3, 5, 7]) - P C H G ([1, 3, 5, 7], [1, 2, 3, 4]) = N - (8 - 3 - 2) - 3 = N - 6$

$S U M_S U B S E T (N, [1, 3, 5, 7], [1, 2, 3, 4])$

$\begin{matrix} form = (2 + 3) (3 + 5) (4 + 7) \\ = 24 (\begin{matrix} N - 6 \\ 5 \end{matrix}) + 108 (\begin{matrix} N - 6 \\ 4 \end{matrix}) + 174 (\begin{matrix} N - 6 \\ 3 \end{matrix}) + 105 (\begin{matrix} N - 6 \\ 2 \end{matrix}) \\ = 1 \times 3 \times 5 \times 7 + 2 \times 4 \times 6 \times 8 + 3 \times 5 \times 7 \times 9 + \dots \end{matrix}$

Among:

$24 = 2 \times 3 \times 4$ ; $105 = 3 \times 5 \times 7$

$108 = 2 \times 3 \times (7 + 2) + 2 \times (5 + 1) \times (4 - 1) + 3 \times (3 - 1) \times (4 - 1)$

$174 = 2 \times (5 + 1) \times (7 + 1) + 3 \times (3 - 1) \times (7 + 1) + 3 \times 5 \times (4 - 2)$

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} S U M_S U B S E T (N, [1, 3, 7], [1, 2, 3]) \\ = 6 (\begin{matrix} N - 6 \\ 4 \end{matrix}) + 2 \times ({7} + {1}) (\begin{matrix} N - 6 \\ 3 \end{matrix}) + 3 \times ({3 - 1}) (\begin{matrix} N - 6 \\ 3 \end{matrix}) + 3 \times 7 (\begin{matrix} N - 6 \\ 2 \end{matrix}) \end{array}$

$\begin{array}{l} S U M_S U B S E T (10, [1, 3, 7], [1, 2, 3]) \\ = 1 \times 3 \times 7 + 2 \times 4 \times 8 + 3 \times 5 \times 9 \\ = 1 \times 3 \times 7 + 2 \times (3 + 1) \times (7 + 1) + 3 \times (3 + 2) \times (7 + 2) \\ = {1 \times 3 \times 7 + 2 \times 3 \times 7 + 3 \times 3 \times 7} + {2 \times 3 \times 1 + 3 \times 3 \times 2} \\ + {2 \times 1 \times 7 + 3 \times 2 \times 7} + {2 \times 1 \times 1 + 3 \times 2 \times 2} \end{array}$

${1 \times 3 \times 7 + 2 \times 3 \times 7 + 3 \times 3 \times 7} = 3 \times 7 (\begin{matrix} 10 - 6 \\ 2 \end{matrix})$

${2 \times 3 \times 1 + 3 \times 3 \times 2} = 3 \times ({3 - 1}) (\begin{matrix} N - 6 \\ 3 \end{matrix}) = 6 (\begin{matrix} 10 - 6 \\ 3 \end{matrix})$

${2 \times 1 \times 7 + 3 \times 2 \times 7} = 2 \times 7 (\begin{matrix} N - 6 \\ 3 \end{matrix}) = 14 (\begin{matrix} N - 6 \\ 3 \end{matrix})$

${2 \times 1 \times 1 + 3 \times 2 \times 2} = 6 (\begin{matrix} 10 - 6 \\ 4 \end{matrix}) + 2 \times {1} (\begin{matrix} 10 - 6 \\ 3 \end{matrix})$

3.3) Use the form $(T_{1} + K_{1}) (T_{2} + K_{2}) \dots (T_{M} + K_{M}) = \sum X_{1} X_{2} \dots X_{M}$

$\begin{array}{l} S U M_K (S E T (N, P S, P T), E_{1} E_{2} \dots E_{M}) \\ = \sum A_{q} (\begin{matrix} N - P H (P S) - P C H G (P S, P T) \\ I D X (P T) - q \end{matrix}) \end{array}$

$A_{q} = \prod_{i = 1}^{M} D_{i}$ , $D_{i} = {\begin{cases} T_{i} - m : X_{i} = T_{i}, m = countof {X_{2}, \dots, X_{i - 1}} \in K \\ + m : X_{i} = K_{i}, m = countof {X_{2}, \dots, X_{i - 1}} \in T \end{cases}$

$q = count of X \in K$ , $X_{1} = T_{1}$ , 2^M^-1 Items in total.

In particular:

If $P T 1 = [1, T_{1}, \dots, T_{M}] = [1, 2, \dots, M + 1]$ , then $P B (P S) = P C H G (P S, P T 1)$

$\begin{array}{l} N - P H (P S) - P C H G (P S, P T 1) \\ = N - [I D X (P S) - 2 - P B (P S)] - P B (P S) \\ = N - (K_{M} - 1) \end{array}$

$I D X (P T 1) = M + 2$

$\begin{array}{l} S U M (S E T (N, P S, P T 1), E_{1} \dots E_{M}) \\ = 2 \times 1^{M} + 3 \times 2^{M} + \dots + (N - K_{M}) \times {(N - K_{M} - 1)}^{M} \end{array}$

$\begin{array}{l} S U M (S E T (N + K_{M} + 1, P S, P T 1), E_{1} \dots E_{M}) \\ = 2 \times 1^{M} + 3 \times 2^{M} + \dots + (N + 1) \times N^{M} \end{array}$

3.4) $\sum_{n = 1}^{N} (n + 1) n^{M} = S U M_K (S E T (N + K_{M} + 1, P S, P T 1), E_{1} \dots E_{M})$

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

$P S = [1, K_{1}, K_{2}, \dots, K_{M}]$ , $P T 1 = [1, 2, 3, \dots, M + 1]$ . The simplest subset of PS is SET(N, PS, PT1).

$\begin{array}{l} S U M_S U B S E T (N, P S, P T 1) \\ = \sum_{q = 0}^{M} C_{q} (\begin{matrix} N - (K_{M} - 1) \\ M + 2 - q \end{matrix}) = \sum_{n = 1}^{N - K_{M}} \sum_{q = 0}^{M} C_{q} (\begin{matrix} n \\ M + 1 - q \end{matrix}) \\ = 1 \times K_{1} \times \dots \times K_{M} + 2 \times (1 + K_{1}) \times \dots \times (1 + K_{M}) + \dots \\ + (N - K_{M}) \times ([N - K_{M} - 1] + K_{1}) \times \dots \times (N - 1) \\ = \sum_{n = 1}^{N - K_{M}} n (n + K_{1} - 1) (n + K_{2} - 1) \dots (n + K_{M} - 1) \end{array}$ (1*)

Solve (1*) in a normal way:

Decompose $n (n + K_{1} - 1) \dots (n + K_{M} - 1)$ to $\sum_{j = 1}^{M + 1} D_{j} (\begin{matrix} n \\ j \end{matrix})$ ? $D_{j} = C_{q}$ , $q = M + 1 - j$

4.1) $1 < K_{1} < \dots < K_{M}$ , 3.1) can decompose $n (n + K_{1} - 1) \dots (n + K_{M} - 1)$ to $\sum_{j = 1}^{M + 1} D_{j} ( n j )$

In particular, 1.5) ? $C_{q} = (M + 1)! (\begin{matrix} M \\ M - q \end{matrix})$ ? $D_{j} = (M + 1)! (\begin{matrix} M \\ j - 1 \end{matrix})$ ?

4.2) ${[x]}^{M} = \frac{M!}{M!} (\begin{matrix} M - 1 \\ M - 1 \end{matrix}) {[x]}_{M} + \frac{M!}{(M - 1)!} (\begin{matrix} M - 1 \\ M - 2 \end{matrix}) {[x]}_{M - 1} + \dots + \frac{M!}{1!} (\begin{matrix} M - 1 \\ 0 \end{matrix}) {[x]}_{1}$

4.3) P is a prime number, $N - (K_{M} - 1) = P$

1) $| S E T (N, P S, P T 1) | = P - 1$ ,

2) $\begin{array}{l} S E T (N, P S, P T 1) \\ = {(1, K_{1}, \dots, K_{M}), (2, 1 + K_{1}, \dots, 1 + K_{M}) \dots (P - 1, \dots, N - 1)} \end{array}$

3) if $K_{M} \leq P - 1$ and $P S \neq [1, 2, \dots, P - 1]$ , then $S U M_S U B S E T (N, P S, P T 1) \equiv 0 M O D P$

[Proof]

$\begin{array}{l} | S E T (N, P S, P T 1) | = (\begin{matrix} N - P H (P S) - 1 - P C H G (P S, P T 1) \\ P B (P T 1) + 1 \end{matrix}) \\ = (\begin{matrix} (P + K_{M} - 1) - (K_{M} + 1 - P B (P S) - 2) - 1 - P C H G (P S, P T 1) \\ 1 \end{matrix}) \\ \overset{P B (P S) = P C H G (P S, P T 1)}{\to} P - 1 \to (1) ( 2 ) \end{array}$

$S U M_S U B S E T (N, P S, P T 1) = \sum_{q = 0}^{M} C_{q} (\begin{matrix} P \\ I D X (P T 1) - q \end{matrix})$

$K_{M} \leq P - 1$ and $P S \neq [1, 2, \dots, P - 1] \to I D X (P T 1) < P \to ( 3 )$

q.e.d.

When $K_{M} = P - 1$ and $P S \neq [1, 2, \dots, P - 1]$

$\begin{array}{l} S U M_S U B S E T (N, P S, P T 1) \\ = 1 \times K_{1} \times \dots \times K_{M} + 2 \times (1 + K_{1}) \times \dots \times P \\ + 3 \times (2 + K_{1}) \dots (2 + K_{M - 1}) (2 + K_{M}) \\ + 4 \times (3 + K_{1}) \dots (3 + K_{M - 1}) (3 + K_{M}) + \dots \\ + (P - 1) \times (P - 2 + K_{1}) \times \dots \times (P - 2 + K_{M}) \end{array}$

$3 \times (2 + K_{1}) \dots (2 + K_{M - 1}) (2 + K_{M}) \equiv 1 \times 3 \times (2 + K_{1}) \dots (2 + K_{M - 1})$

$\begin{array}{l} 4 \times (3 + K_{1}) \dots (3 + K_{M - 1}) (3 + K_{M}) \\ \equiv 2 \times (1 + [3]) \times (1 + [2 + K_{1}]) \dots (1 + [2 + K_{M - 1}]) \end{array}$

$\dots$

$\begin{array}{l} (P - 1) \times (P - 2 + K_{1}) \dots (P - 2 + K_{M}) \\ \equiv (P - 1) \times (P - 2 + K_{1}) \dots (P - 2 + K_{M - 1}) (2 P - 3) \\ \equiv (P - 4 + [1]) (P - 4 + [3]) (P - 4 + [2 + K_{1}]) \dots (P - 4 + [2 + K_{M - 1}]) \end{array}$

$\begin{array}{l} 1 \times K_{1} \times \dots \times K_{M} \equiv 1 \times K_{1} \times \dots \times (P - 1) \equiv (P + 1) (P + K_{1}) \dots (P + P - 1) \\ \equiv (P - 1) (P - 2 + 3) ([P - 2] + [2 + K_{1}]) \dots ([P - 2] + [2 + K_{M - 1}]) \end{array}$

$\begin{array}{l} S U M_S U B S E T (N, P S, P T 1) \\ \equiv S U M_S U B S E T (N, [1, 3, 2 + K_{1}, ϵ, 2 + K_{M - 1}], P T 1) M O D P \end{array}$

$P S = [1, K_{1} \dots K_{M}]$ can be slided to $[1, 3, 2 + K_{1}, \dots, 2 + K_{M - 1}]$ by MOD P

If $K_{M} = P - 1$ and exists $K_{i + 1} - K_{i} > 2$ , PS can be slided to $[1, \dots, X < P - 1]$

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 $[1, \dots, X = P - 1]$

Define:

A Basic Shape $P S = [1, K_{1} \dots K_{M}] = 〚 L_{1} L_{2} \dots L_{Q} 〛$ , among:

L_i = count of continuity. (L_i, L_i₊₁) means a discontinuity, there are Q-1 discontinuities.

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

Obvious: $〚 L_{1} L_{2} \dots L_{Q} 〛$ can been slided to $[L_{Q}, L_{1}, L_{2}, \dots]$ , $[L_{Q - 1}, L_{Q}, L_{1}, L_{2}, \dots]$ , $\dots$

4.4) PS is a Basic Shape, $I D X (P S) = P$ , $P S \neq [1, 2, \dots, P - 1]$ , ${P S 1, P S 2, \dots}$ are all shapes that PS can scroll to, then $M I N (P S 1) + M I N (P S 2) + \dots \equiv 0 M O D P$ . This is a promotion of 1.6)

[Proof]

$3 \times (2 + K_{1}) \dots (2 + K_{M - 1}) (2 + K_{M}) \equiv 1 \times 3 \times (2 + K_{1}) \dots (2 + K_{M - 1}) M O D P$

If $2 + K_{M - 1} \neq P$ , $[1, 3, (2 + K_{1}), \dots, (2 + K_{M - 1})] \in {P S 1, P S 2, \dots}$

…

$S U M_S U B S E T (N, P S 1, P T 1) \equiv M I N (P S 1) + M I N (P S 2) + \dots \equiv 0 M O D P$

q.e.d.

Example:

$\begin{array}{l} 1 \times (3 \times 4 \times 5) \times (7 \times 8) \times 10 + 1 \times 3 \times (5 \times 6 \times 7) \times (9 \times 10) \\ + (1 \times 2) \times 4 \times 6 \times (8 \times 9 \times 10) + (1 \times 2 \times 3) \times (5 \times 6) \times 8 \times 10 \\ = 139260 \equiv 0 M O D 11 \end{array}$

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

Use the form $(T_{1} + K_{1}) (T_{2} + K_{2}) \dots (T_{M} + K_{M})$ .

In general, K_i and K_j cannot be exchanged, but when $P T = P T 1 = [1, 2, \dots, M + 1]$ ,

$S U M_S U B S E T (N, P S, P T 1) = \sum_{q = 0}^{M} C_{q} (\begin{matrix} N - P H (P S) - P C H G (P S, P T 1) \\ I D X (P T 1) - q \end{matrix})$

$C_{q} = \sum \prod_{i = 1}^{M} (X_{i} + D_{i}) = \sum \prod_{choice M - q from T} (T - D) \prod_{choice q from K} (K + D)$

Easy to see: $\prod_{choice M - q from T} (T - D) = (M + 1 - q)!$

Can prove: $(K_{1}, K_{2}, \dots, K_{M})$ is permutable in $\sum \prod_{choice q from K} (K + D)$

? $(K_{1}, K_{2}, \dots, K_{M})$ is permutable in the form.

$\begin{array}{l} S U M_S U B S E T (N, P S, P T 1) \\ = \sum_{q = 0}^{M} A_{q} (\begin{matrix} N - K_{M} + 1 \\ M + 2 - q \end{matrix}) = \sum_{n = K_{M} + 1}^{N} \sum_{q = 0}^{M} A_{q} (\begin{matrix} n - K_{M} \\ M + 1 - q \end{matrix}) \\ = 1 \times K_{1} \times \dots \times K_{M} + 2 \times (1 + K_{1}) \times \dots \times (2 + K_{M}) + \dots \end{array}$

Add one more factor K_i to the end:

$\begin{array}{l} 1 \times K_{1} \times \dots \times K_{M} \times K_{i} + 2 \times (1 + K_{1}) \times \dots \times (1 + K_{M}) \times (1 + K_{i}) + \dots \\ = \sum_{n = K_{M} + 1}^{N} \sum_{q = 0}^{M} A_{q} (\begin{matrix} n - K_{M} \\ M + 1 - q \end{matrix}) (n - 1 - K_{M} + K_{i}) \\ = \sum_{n = K_{M} + 1}^{N} \sum_{q = 0}^{M} A_{q} (\begin{matrix} n - K_{M} \\ M + 1 - q \end{matrix}) ([n - K_{M} + 1] + [K_{i} - 2]) \\ = \sum_{n = K_{M} + 1}^{N} \sum_{q = 0}^{M} {A_{q} (M + 2 - q) (\begin{matrix} n - K_{M} + 1 \\ M + 2 - q \end{matrix}) + A_{q} (K_{i} - 2) (\begin{matrix} n - K_{M} \\ M + 1 - q \end{matrix})} \\ = \sum_{q = 0}^{M} A_{q} (M + 2 - q) (\begin{matrix} N - K_{M} + 2 \\ M + 3 - q \end{matrix}) + \sum_{q = 0}^{M} A_{q} (K_{i} - 2) (\begin{matrix} N - K_{M} + 1 \\ M + 2 - q \end{matrix}) \end{array}$

$\begin{array}{l} = \sum_{q = 0}^{M} A_{q} (M + 2 - q) (\begin{matrix} N - K_{M} + 1 \\ M + 3 - q \end{matrix}) \\ + \sum_{q = 0}^{M} {A_{q} (M + 2 - q) + A_{q} (K_{i} - 2)} (\begin{matrix} N - K_{M} + 1 \\ M + 2 - q \end{matrix}) \\ = \sum_{q = 0}^{M} A_{q} (M + 2 - q) (\begin{matrix} N - K_{M} + 1 \\ M + 3 - q \end{matrix}) \\ + \sum_{q = 0}^{M} A_{q} (K_{i} + (M - q)) (\begin{matrix} N - K_{M} + 1 \\ M + 3 - (q + 1) \end{matrix}) \end{array}$

Let $P S 2 = [1, K_{1}, \dots, K_{M}, K_{M + 1} = K_{i}]$ ,

$P T 2 = [1, T_{1}, \dots, T_{M}, T_{M + 1}] = [1, 2, \dots, M + 1, M + 2]$

$I D X (P T 2) = M + 3$ , $N - P H (P S 2) - P C H G (P S 2, P T 2) = N - K_{M} + 1$

$q = count of {X_{1}, \dots, X_{M}} \in K$

$A_{q} (M + 2 - q) = A_{q} (T_{M + 1} - q)$ means $X_{M + 1} = T_{M + 1}$ , $A_{q} (K_{i} + (M - q))$ means $X_{M + 1} = K_{M + 1}$

It’s match the form $(T_{1} + K_{1}) (T_{2} + K_{2}) \dots (T_{M} + K_{M}) (T_{M}_{+ 1} + K_{i})$

Recursion ?

5.1) $K_{i} < K_{j}$ , $K_{i} = K_{j}$ , $K_{i} > K_{j}$ are allowed, $S U M_S U B S E T (N, P S, P T 1)$ can use the form $(T_{1} + K_{1}) (T_{2} + K_{2}) \dots (T_{M} + K_{M})$

Example:

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

$\begin{array}{l} S U M_S U B S E T (N, [1, 3, 5, 3], [1, 2, 3, 4]) \\ = 24 (\begin{matrix} N - 4 \\ 5 \end{matrix}) + 84 (\begin{matrix} N - 4 \\ 4 \end{matrix}) + 102 (\begin{matrix} N - 4 \\ 3 \end{matrix}) + 45 (\begin{matrix} N - 4 \\ 2 \end{matrix}) \end{array}$

Among:

$45 = 3 \times 5 \times 3$

$102 = 3 \times 5 \times (4 - 2) + 3 \times (3 - 1) \times (3 + 1) + 2 \times (5 + 1) \times (3 + 1)$

$84 = 2 \times 3 \times (3 + 2) + 2 \times (5 + 1) \times (4 - 1) + 3 \times (3 - 1) \times (4 - 1)$

$\begin{array}{l} S U M_S U B S E T (9, [1, 3, 5, 3], [1, 2, 3, 4]) \\ = 1 \times 3 \times 3 \times 5 + 2 \times 4 \times 4 \times 6 + 3 \times 5 \times 5 \times 7 + 4 \times 6 \times 6 \times 8 = 1914 \\ = 24 (\begin{matrix} 5 \\ 5 \end{matrix}) + 84 (\begin{matrix} 5 \\ 4 \end{matrix}) + 102 (\begin{matrix} 5 \\ 3 \end{matrix}) + 45 ( 5 2 ) \end{array}$

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

$\begin{array}{l} S U M_S U B S E T (N, [1, 4, 7, 7], [1, 2, 3, 4]) \\ = 24 (\begin{matrix} N - 6 \\ 5 \end{matrix}) + 126 (\begin{matrix} N - 6 \\ 4 \end{matrix}) + 248 (\begin{matrix} N - 6 \\ 3 \end{matrix}) + 196 (\begin{matrix} N - 6 \\ 2 \end{matrix}) \end{array}$

Among:

$196 = 4 \times 7 \times 7$

$248 = 4 \times 7 \times (4 - 2) + 4 \times (3 - 1) \times (7 + 1) + 2 \times (7 + 1) \times (7 + 1)$

$126 = 2 \times 3 \times (7 + 2) + 2 \times (7 + 1) \times (4 - 1) + 4 \times (3 - 1) \times (4 - 1)$

$\begin{array}{l} S U M_S U B S E T (12, [1, 4, 7, 7], [1, 2, 3, 4]) \\ = 1 \times 4 \times 7 \times 7 + 2 \times 5 \times 8 \times 8 + 3 \times 6 \times 9 \times 9 + 4 \times 7 \times 10 \times 10 + 5 \times 8 \times 11 \times 11 \\ = 9934 = 24 (\begin{matrix} 6 \\ 5 \end{matrix}) + 126 (\begin{matrix} 6 \\ 4 \end{matrix}) + 248 (\begin{matrix} 6 \\ 3 \end{matrix}) + 196 ( 6 2 ) \end{array}$

In particular:

5.2) $\sum_{n = 1}^{M} n^{M} = S U M_S U B S E T (N + 1, [1, 1, \dots, 1], [1, 2, \dots, M])$

Example:

$(N + 1) - P H (P S) - P C H G (P S, P T 1) = (N + 1) - 0 - 0 = N + 1$

The form = $(2 + 1)$

? $1^{2} + 2^{2} + \dots + N^{2} = 2 (\begin{matrix} N + 1 \\ 3 \end{matrix}) + (\begin{matrix} N + 1 \\ 2 \end{matrix}) = \frac{N (N + 1) (2 N + 1)}{6}$

The form = $(2 + 1) (3 + 1)$

? $1^{3} + 2^{3} + \dots + N^{3} = 6 (\begin{matrix} N + 1 \\ 4 \end{matrix}) + 6 (\begin{matrix} N + 1 \\ 3 \end{matrix}) + (\begin{matrix} N + 1 \\ 2 \end{matrix}) = \frac{N^{2} {(N + 1)}^{2}}{4}$

The form = $(2 + 1) (3 + 1) (4 + 1)$

? $1^{4} + 2^{4} + \dots + N^{4} = 24 (\begin{matrix} N + 1 \\ 5 \end{matrix}) + 36 (\begin{matrix} N + 1 \\ 4 \end{matrix}) + 14 (\begin{matrix} N + 1 \\ 3 \end{matrix}) + (\begin{matrix} N + 1 \\ 2 \end{matrix})$

Among:

$14 = 2 \times (1 + 1) \times (1 + 1) + 1 \times 1 \times (4 - 2) + 1 \times (3 - 1) \times (1 + 1)$

$36 = 2 \times 3 \times (1 + 2) + 2 \times (1 + 1) \times (4 - 1) + 1 \times (3 - 1) \times (4 - 1)$

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 (M, K) (\begin{matrix} N + 1 \\ K + 1 \end{matrix})$

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} (n + 1) n^{M} = S U M_S U B S E T (N + 1, [1, 0, \dots, 0], [1, 2, \dots, M + 1])$

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	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
[2]	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

Journals Menu

Follow SCIRP

	customer@scirp.org
	+86 18163351462(WhatsApp)
	1655362766

	Paper Publishing WeChat

Journals Menu

Home

About SCIRP

Service

Policies