Expansion of the Shape of Numbers

doi:10.4236/oalib.1107120

Open Access Library Journal
Vol.08 No.01(2021), Article ID:106774,18 pages
10.4236/oalib.1107120

Ji Peng

●How to Cite this Article

Department of Electronic Information, Nanjing University, Nanjing, China

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

Received: December 28, 2020; Accepted: January 23, 2021; Published: January 26, 2021

ABSTRACT

This article extends the concept of the shape of numbers. Originally, a shape was defined as $[1, K_{1}, K_{2}, \dots]$ , $1 < K_{1} < K_{2} < \dots$ , $K_{i} \in N$ . In this paper, the domain of a shape is extended from N to Z, the low bound is extended from 1 to Z, and $K_{i} < K_{i + 1}$ , $K_{i} = K_{i + 1}$ , $K_{i} > K_{i + 1}$ are allowed, which prove that they can be calculated with the similar form $(T_{0} + K_{0}) (T_{1} + K_{1}) (T_{2} + K_{2}) \dots$ . In this way, a lot of calculation formulas can be obtained. At the end, the form is obtained to calculate $\begin{array}{l} K_{1} \times \dots \times K_{M} + (L + K_{1}) \times \dots \times (L + K_{M}) + (2 L + K_{1}) \times \dots \times (2 L + K_{M}) \\ + (3 L + K_{1}) \times \dots \times (3 L + K_{M}) + \dots \end{array}$ .

Subject Areas:

Discrete Mathematics

Keywords:

Shape of Numbers, Calculation Formula, Combinatorics, Congruence, Stirling Number

1. Introduction

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

$(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)$ that use the symbol PS = [min Item] to represent it.

If $K_{i + 1} - K_{i} = D > 1$ , only $I_{i + 1} - I_{i} \geq D$ is allowed. If $K_{i + 1} - K_{i} = 1$ , only $I_{i + 1} - I_{i} = 1$ is allowed.

The single $(I_{1}, I_{2}, \dots, I_{M})$ is an item, $I_{1} \times I_{2} \times \dots \times 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]$

End(N, PS) = set of items belonging to PS with the max factor = N − 1;

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

[3] introduced the subset:

If PB(PS) = 0, SET(N, PS) is simple.

If PB(PS) > 0, then can fix some interval of discontinuities to get subsets.

SET(N, PS, PT) = subset of SET(N, PS), a valid

$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}$ (*)

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

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

Example:

$P C H G ([1, 3, 5], [1, 3, 5]) = 0$

$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₂

SUM_SUBSET(N, PS, PT) is defined in [3] = sum of all products in SET(N, PS, PT)

Now, SUM() and SUM_SUBSET() are uniformly defined as SUM(N, PS, PT), SUM(N, PS, BASE(PS)) is abbreviated as SUM(N, PS)

Only valid PT is discussed below.

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

(1.1) $| S E T (N, P S, P T) | = (\begin{matrix} N - P H (P S) - P C H G (P S, P T) - 1 \\ P B (P T) + 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}]$ , $P T = [1, T_{1}, T_{2}, \dots, T_{M}]$

Use the form $(T_{1} + K_{1}) (T_{2} + K_{2}) \dots (T_{M} + K_{M}) = \sum X_{1} X_{2} \dots X_{M}$ , X_i = T_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) - P C H G (P S, P T) \\ I D X (P T) - q \end{matrix})$

$q = countof X \in K$ .

$S U M (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}$

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]$ ,

$I D X (B S) = 8$

$\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) - P C H G (P S, P T) \\ = N - {I D X (P S) - P B (P S) - 2} - 0 \\ = N - {K_{3} + 1 - 3 - 2} = N - K_{3} + 4 \end{matrix}$

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

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

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

PF indicates the part. F_i = E_i or K_i

Rewrite 1.3), add {braces}:

$\begin{matrix} S U M (N, P S, P T) = \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} {T_{i} - D_{i}} : X_{i} = T_{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 T \end{cases}$

Expand SUM(N, PS, PT) by {braces}:

(1.4) SUM_K(N, PS, PT, PF) = ∑Expansion of SUM() 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} = T_{i} \\ K_{i} : F_{i} = K_{i}, X_{i} = K_{i} \\ T_{i} - D_{i} : F_{i} = E_{i}, X_{i} = T_{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 T \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 (N, P S, B 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 (N, P S, B 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 (N, P S, B 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 (N, P S, B 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})$

In this paper, we extend the definition of Shape of Numbers and generalize the corresponding results.

2. The Extension of Shape

Redefine:

$P S = [minItem] = [K_{0}, \dots, K_{M}, \dots]$ , $Item = (I_{0}, \dots, I_{M}, \dots)$ ,

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

1) change factor’s domain of definition from N to Z, change K₀ from 1 to Z.

2) allow $K_{0} \leq K_{1} \leq \dots \leq K_{M}$ , If $K_{i + 1} = K_{i}$ , only $I_{i + 1} = I_{i}$ is allowed. $G_{i + 1} - G_{i} = 1$

3) allow $K_{i} > K_{i + 1}$ , only $I_{i + 1} = I_{i}$ is allowed. $G_{i + 1} - G_{i} = 1$ .

Example:

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

$\begin{array}{l} S E T (8, [3, 5]) = {(3, 5), (3, 6), (4, 6), (3, 7), (4, 7), (5, 7)} \\ \neq S E T (8, [1, 3]) - S E T (5, [1, 3]) \end{array}$

$P S = [3, 5, 4, 6] \to B A S E (P S) = [1, 3, 4, 6]$

$S E T (8, P S) = {(3, 5, 4, 6), (3, 6, 5, 7), (4, 6, 5, 7), (3, 5, 4, 7)}$

Redefine:

Basic Shape: K₀ = 1 and intervals = 1 or 2

SET(N, PS) = set of items belonging to PS in [K₀, N − 1], Max Factor of item ≤ N − 1

PB(PS) = Count of discontinuities in BS

PH(PS) = (Max Factor) − 1 − PB(BS)

IDX(PS) = IDX of $B S = {\max factor of B S} + 1 = P M (B S) + P B (B S) + 1$

D¹f(n): if $f (n) = \sum A_{i} (\begin{matrix} N - n_{i} \\ m_{i} \end{matrix})$ , then $D^{1} f (n) = \sum A_{i} (\begin{matrix} N - n_{i} - 1 \\ m_{i} - 1 \end{matrix})$

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

2.2) Specify $(\begin{matrix} N < M \\ M \end{matrix}) = 0$ , $\sum_{n = 0}^{N - 1} n (\begin{matrix} n - K \\ M \end{matrix}) = (M + 1) (\begin{matrix} N - K \\ M + 2 \end{matrix}) + (M + K) (\begin{matrix} N - K \\ M + 1 \end{matrix})$

2.3) $P S = [K_{0}, K_{1}, \dots, K_{M}]$ , $P T = [1, T_{1}, T_{2}, \dots, T_{M}]$ , can use the form $(T_{0} + K_{0}) \dots (T_{M} + K_{M})$

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

$A_{q} = \prod_{i = 0}^{M} (X_{i} + D_{i})$ ,

$D_{i} = {\begin{cases} - m : X_{i} = T_{i}, m = countof {X_{0}, \dots, X_{i - 1}} \in K \\ + m : X_{i} = K_{i}, m = countof {X_{0}, \dots, X_{i - 1}} \in T \end{cases}$

$q = countof X \in K$

[Proof]

Here only prove SUM(N, PS), SUM(N, PS, PT) can use the same method.

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

Use the similar way of [2], by definition:

(1*) $S U M (N, P S) = \sum_{n = - \infty}^{N} \sum E N D (n, P S)$

(2*) $\sum E N D (N, P S) = D^{1} S U M (N, P S)$

(3*) $S U M (N, [P S, K_{M + 1} = 1 + K_{M}]) = \sum_{n = - \infty}^{N - 1} n \times \sum E N D (n, P S)$

(4*) $S U M (N, [P S, K_{M + 1} = K_{M}]) = \sum_{n = - \infty}^{N - 1} n \times \sum E N D (n + 1, P S)$

(5*) $S U M (N, [P S, K_{M + 1} > 1 + K_{M}]) = \sum_{n = - \infty}^{N - 1} n \times S U M (n - (K_{M + 1} - K_{M}) + 1, P S)$

Suppose $S U M (N, P S) = \sum X_{0} X_{1} \dots X_{M} (\begin{matrix} N - P H (P S) - 1 \\ M_{i} \end{matrix})$ , Max factor of PS = K_M

$P = n - P H (P S) - 1 = n - [K_{M} - 1 - P B (B S)] - 1 = n - [K_{M} - P B (B S)]$

$Q = N - P H (P S) - 1$

$C = Countof {X_{0}, \dots, X_{M}} \in K$ ,

$M_{i} = I D X (B S) - C$

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

$\begin{array}{l} S U M (N, P S 1) = \sum_{n = - \infty}^{N - 1} n \times \sum E N D (n, P S) = \sum_{n = - \infty}^{N - 1} n \times D^{1} S U M (n, P S) \\ = \sum_{n = - \infty}^{N - 1} n \times \sum X_{0} \dots X_{M} (\begin{matrix} P - 1 \\ M_{i} - 1 \end{matrix}) \\ = \sum_{n = - \infty}^{N - 1} n \times \sum X_{0} \dots X_{M} (\begin{matrix} n - [K_{M} - P B (B S) + 1] \\ M_{i} - 1 \end{matrix}) \overset{(2.2)}{\to} \\ = \sum^{} (X_{0} \dots X_{M} M_{i} (\begin{matrix} Q - 1 \\ M_{i} + 1 \end{matrix}) + X_{0} \dots X_{M} (M_{i} - 1 + K_{M} - P B (B S) + 1) (\begin{matrix} Q - 1 \\ M_{i} \end{matrix})) \end{array}$

$M_{i} = I D X (B S) - C = 1 + G_{M} - C = G_{M + 1} - C$

$\begin{array}{l} M_{i} - 1 + K_{M} - P B (B S) + 1 \\ = M_{i} + K_{M} - P B (B S) = I D X (B S) - C + K_{M} - P B (B S) \\ = (P M (B S) + P B (B S) + 1) - C + K_{M} - P B (B S) \\ = K_{M} + 1 + P M (B S) - C = K_{M + 1} + (M + 1) - C \end{array}$

$\begin{array}{l} S U M (N, P S 1) \\ = \sum X_{0} \dots X_{M} (G_{M + 1} - C) (\begin{matrix} Q - 1 \\ I D X (B S) - C + 1 \end{matrix}) \\ + \sum X_{0} \dots X_{M} (K_{M + 1} + M + 1 - C) (\begin{matrix} Q - 1 \\ I D X (B S) - C \end{matrix}) \\ = \sum X_{0} \dots X_{M} (G_{M + 1} - C) (\begin{matrix} N - P H (P S 1) - 1 \\ I D X (B S 1) - C \end{matrix}) \\ + \sum X_{0} \dots X_{M} (K_{M + 1} + M + 1 - C) (\begin{matrix} N - P H (P S 1) - 1 \\ I D X (B S 1) - (C + 1) \end{matrix}) \end{array}$

à Match the form $(G_{0} + K_{0}) (G_{1} + K_{1}) \dots (G_{M} + K_{M}) {G_{M + 1} + K_{M + 1}}$ .

2) $P S 1 = [P S, K_{M + 1} = K_{M}]$ , $B S 1 = B A S E (P S 1) = [B S, G_{M + 1} = 1 + G_{M}]$

$\begin{array}{l} S U M (N, P S 1) = \sum_{n = - \infty}^{N - 1} n \times \sum^{} E N D (n + 1, P S) \\ = \sum_{n = - \infty}^{N - 1} n \times D^{1} S U M (n + 1, P S) \\ = \sum_{n = - \infty}^{N - 1} n \times \sum X_{0} \dots X_{M} (\begin{matrix} P \\ M_{i} - 1 \end{matrix}) \\ = \sum_{n = - \infty}^{N - 1} n \times \sum X_{0} \dots X_{M} (\begin{matrix} n - [K_{M} - P B (B S)] \\ M_{i} - 1 \end{matrix}) \overset{( 2.2 )}{\to} \end{array}$

$\begin{array}{l} = \sum^{} (X_{0} \dots X_{M} M_{i} (\begin{matrix} Q \\ M_{i} + 1 \end{matrix}) + X_{0} \dots X_{M} (M_{i} - 1 + K_{M} - P B (B S)) (\begin{matrix} Q \\ M_{i} \end{matrix})) \\ = \sum X_{0} \dots X_{M} (G_{M + 1} - C) (\begin{matrix} N - P H (P S 1) - 1 \\ I D X (B S 1) - C \end{matrix}) \\ + \sum X_{0} \dots X_{M} (K_{M} + M + 1 - C) (\begin{matrix} N - P H (P S 1) - 1 \\ I D X (B S 1) - (C + 1) \end{matrix}) \end{array}$

à Match the form $(G_{0} + K_{0}) (G_{1} + K_{1}) \dots (G_{M} + K_{M}) {G_{M + 1} + K_{M + 1}}$ .

3) $P S 1 = [P S, K_{M + 1} > K_{M} + 1]$ , $B S 1 = B A S E (P S 1) = [B S, 2 + G_{M}]$

$\begin{array}{l} S U M (N, P S 1) = \sum_{n = - \infty}^{N - 1} n \times S U M (n - (K_{M + 1} - K_{M} - 1), P S) \\ = \sum_{n = - \infty}^{N - 1} n \times \sum X_{0} \dots X_{M} (\begin{matrix} n - (K_{M + 1} - K_{M} - 1) - P H (P S) - 1 \\ M_{i} \end{matrix}) \\ = \sum_{n = - \infty}^{N - 1} n \times \sum X_{0} \dots X_{M} (\begin{matrix} n - [K_{M + 1} - K_{M} + P H (P S)] \\ M_{i} \end{matrix}) \end{array}$

$\begin{matrix} Q 1 = N - [K_{M + 1} - K_{M} + P H (P S)] \\ = N - [K_{M + 1} - K_{M} + K_{M} - 1 - P B (B S)] \\ = N - [K_{M + 1} - 1 - P B (B S)] \\ = N - [K_{M + 1} - 1 - P B (B S 1)] - 1 \\ = N - P H (P S 1) - 1 \end{matrix}$

$\begin{array}{l} S U M (N, P S 1) \overset{(2.2)}{\to} \\ = \sum X_{0} \dots X_{M} (M_{i} + 1) (\begin{matrix} Q 1 \\ M_{i} + 2 \end{matrix}) \\ + \sum X_{0} \dots X_{M} (K_{M + 1} - K_{M} + P H (P S) + M_{i}) (\begin{matrix} Q 1 \\ M_{i} + 1 \end{matrix}) \end{array}$

$M_{i} + 1 = I D X (B S) - C + 1 = 1 + G_{M} - C + 1 = G_{M + 1} - C$

$\begin{array}{l} K_{M + 1} - K_{M} + P H (P S) + M_{i} = K_{M + 1} - K_{M} + P H (P S) + I D X (B S) - C \\ = K_{M + 1} - K_{M} + (K_{M} - 1 - P B (B S)) + (P M (B S) + P B (B S) + 1) - C \\ = K_{M + 1} + P M (B S) - C = K_{M + 1} + M + 1 - C \end{array}$

$\begin{array}{l} S U M (N, P S 1) \\ = \sum X_{0} \dots X_{M} (G_{M + 1} - C) (\begin{matrix} Q 1 \\ M_{i} + 2 \end{matrix}) \\ + \sum X_{0} \dots X_{M} (K_{M + 1} + M + 1 - C) (\begin{matrix} Q 1 \\ M_{i} + 1 \end{matrix}) \\ = \sum X_{0} \dots X_{M} (G_{M + 1} - C) (\begin{matrix} Q 1 \\ I D X (B S) - C + 2 \end{matrix}) \\ + \sum X_{0} \dots X_{M} (K_{M + 1} + M + 1 - C) (\begin{matrix} Q 1 \\ I D X (B S) - C + 1 \end{matrix}) \end{array}$

$\begin{array}{l} = \sum X_{0} \dots X_{M} (G_{M + 1} - C) (\begin{matrix} N - P H (P S 1) - 1 \\ I D X (B S 1) - C \end{matrix}) \\ + \sum X_{0} \dots X_{M} (K_{M + 1} + M + 1 - C) (\begin{matrix} N - P H (P S 1) - 1 \\ I D X (B S 1) - (C + 1) \end{matrix}) \end{array}$

à Match the form $(G_{0} + K_{0}) (G_{1} + K_{1}) \dots (G_{M} + K_{M}) {G_{M + 1} + K_{M + 1}}$ .

4) $P S 1 = [P S, K_{M + 1} < K_{M}]$ , $B S 1 = B A S E (P S 1) = [B S, 1 + G_{M}]$

By definition:

$\begin{array}{l} S U M (N, [P S, K_{M + 1}]) = \sum_{n = - \infty}^{N - 1} (n + K_{M + 1} - K_{M}) \sum E N D (n + 1, P S) \\ = \sum_{n = - \infty}^{N - 1} (n + K_{M + 1} - K_{M}) \times D^{1} S U M (n + 1, P S) \\ = \sum_{n = - \infty}^{N - 1} (n + K_{M + 1} - K_{M}) \times \sum X_{0} \dots X_{M} (\begin{matrix} p \\ M_{i} - 1 \end{matrix}) \\ = \sum_{n = - \infty}^{N - 1} n \times \sum X_{0} \dots X_{M} (\begin{matrix} P \\ M_{i} - 1 \end{matrix}) + \sum_{n = - \infty}^{N - 1} (K_{M + 1} - K_{M}) \\ \times \sum X_{0} \dots X_{M} (\begin{matrix} P \\ M_{i} - 1 \end{matrix}) \end{array}$

$\begin{array}{l} = \sum X_{0} \dots X_{M} {M_{i} (\begin{matrix} Q \\ M_{i} + 1 \end{matrix}) + (M_{i} - 1 + K_{M} - P B (B S)) (\begin{matrix} Q \\ M_{i} \end{matrix}) \\ + (K_{M + 1} - K_{M}) (\begin{matrix} Q \\ M_{i} \end{matrix})} \\ = \sum X_{0} \dots X_{M} {(I D X (B S) - C) (\begin{matrix} Q \\ M_{i} + 1 \end{matrix}) + (M_{i} + K_{M + 1} - P B (B S) - 1) (\begin{matrix} Q \\ M_{i} \end{matrix})} \end{array}$

$\begin{array}{l} M_{i} + K_{M + 1} - P B (P S) - 1 = I D X (B S) - C + K_{M + 1} - P B (B S) - 1 \\ = (P M (B S) + P B (B S) + 1) - C + K_{M + 1} - P B (B S) - 1 \\ = K_{M + 1} + (M + 1) - C \end{array}$

$\begin{array}{l} S U M (N, P S 1) \\ = \sum X_{0} \dots X_{M} (G_{M + 1} - C) (\begin{matrix} N - P H (P S 1) - 1 \\ I D X (B S 1) - C \end{matrix}) \\ + \sum X_{0} \dots X_{M} (K_{M + 1} + M + 1 - C) (\begin{matrix} N - P H (P S 1) - 1 \\ I D X (B S 1) - (C + 1) \end{matrix}) \end{array}$

à Match the form $(G_{0} + K_{0}) \dots (G_{M} + K_{M}) {G_{M + 1} + K_{M + 1}}$ .

q.e.d.

Example:

$N - P H ([- 11, - 7, - 4]) - 1 = N - (- 4 - 2 - 1) - 1 = N + 6$ ,

$B A S E ([- 11, - 7, - 4]) = [1, 3, 5]$

$S U M (N, [- 11, - 7, - 4])$ à $form = (1 - 11) (3 - 7) (5 - 4)$ à

$= 15 (\begin{matrix} N + 6 \\ 6 \end{matrix}) - 118 (\begin{matrix} N + 6 \\ 5 \end{matrix}) + 315 (\begin{matrix} N + 6 \\ 4 \end{matrix}) - 308 (\begin{matrix} N + 6 \\ 3 \end{matrix})$

$15 = 1 \times 3 \times 5$ ;

$- 308 = (- 11) \times (- 7) \times ( - 4 )$

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

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

$\begin{array}{l} S U M (- 2, [- 11, - 7, - 4]) \\ = (- 11) \times (- 7) \times (- 4) + (- 11) \times (- 7) \times (- 3) \\ + (- 11) \times (- 6) \times (- 3) + (- 10) \times (- 6) \times (- 3) \\ = 315 - 308 \times 4 = - 917 \end{array}$

$\begin{array}{l} S U M (- 1, [- 11, - 7, - 4]) \\ = S U M (- 2, [- 11, - 7, - 4]) + (- 11) \times (- 7) \times (- 2) + (- 11) \times (- 6) \times (- 2) \\ + (- 11) \times (- 5) \times (- 2) + (- 11) \times (- 7) \times (- 2) \\ + (- 11) \times (- 6) \times (- 2) + (- 11) \times (- 5) \times (- 2) \\ = - 118 + 315 \times 5 - 308 \times 10 = - 1623 \end{array}$

$S U M (N, [4, 7, 11], [1, 2, 4])$ à $form = (1 + 4) (2 + 7) (4 + 11)$ à

$= 8 (\begin{matrix} N - 10 \\ 5 \end{matrix}) + 62 (\begin{matrix} N - 10 \\ 4 \end{matrix}) + 200 (\begin{matrix} N - 10 \\ 3 \end{matrix}) + 308 (\begin{matrix} N - 10 \\ 2 \end{matrix})$

$62 = 1 \times 2 \times (11 + 2) + 1 \times (7 + 1) \times (4 - 1) + 4 \times (2 - 1) \times (4 - 1)$

$200 = 1 \times (7 + 1) \times (11 + 1) + 4 \times (2 - 1) \times (11 + 1) + 4 \times 7 \times (4 - 2)$

[1, 2, 4] means $I_{1} - I_{0} = K_{1} - K_{0} = 7 - 4 = 3$ , $I_{2} - I_{1} = K_{2} - K_{1} \geq 11 - 7 = 4$

$\begin{array}{l} S U M (15, [4, 7, 11], [1, 2, 4]) \\ = 4 \times 7 \times 11 + 4 \times 7 \times 12 + 5 \times 8 \times 12 + 4 \times 7 \times 13 + 5 \times 8 \times 13 \\ + 6 \times 9 \times 13 + 4 \times 7 \times 14 + 5 \times 8 \times 14 + 6 \times 9 \times 14 + 7 \times 10 \times 14 \\ = 8 + 62 \times 5 + 200 \times 10 + 308 \times 10 = 5398 \end{array}$

$N - P H ([4, 7, 1, 8]) - 1 = N - (8 - 1 - 2) - 1 = N - 6$ , $B A S E ([4, 7, 1, 8]) = [1, 3, 4, 6]$

$S U M (N, [4, 7, 1, 8])$ à $form = (1 + 4) (3 + 7) (4 + 1) (6 + 8)$ à

$= 72 (\begin{matrix} N - 6 \\ 7 \end{matrix}) + 417 (\begin{matrix} N - 6 \\ 6 \end{matrix}) + 922 (\begin{matrix} N - 6 \\ 5 \end{matrix}) + 876 (\begin{matrix} N - 6 \\ 4 \end{matrix}) + 224 (\begin{matrix} N - 6 \\ 3 \end{matrix})$

$\begin{array}{l} 417 = 1 \times 3 \times 4 \times (8 + 3) + 1 \times 3 \times (1 + 2) \times (6 - 1) \\ + 1 \times (7 + 1) \times (4 - 1) \times (6 - 1) + 4 \times (3 - 1) \times (4 - 1) \times (6 - 1) \end{array}$

$\begin{array}{l} 922 = 1 \times 3 \times (1 + 2) \times (8 + 2) + 1 \times (7 + 1) \times (4 - 1) \times (8 + 2) \\ + 4 \times (3 - 1) \times (4 - 1) \times (8 + 2) + 1 \times (7 + 1) \times (1 + 1) \times (6 - 2) \\ + 4 \times (3 - 1) \times (1 + 1) \times (6 - 2) + 4 \times 7 \times (4 - 2) \times (6 - 2) \end{array}$

$\begin{array}{l} 876 = 4 \times 7 \times 1 \times (6 - 3) + 4 \times 7 \times (4 - 2) \times (8 + 1) \\ + 4 \times (3 - 1) \times (1 + 1) \times (8 + 1) + 1 \times (7 + 1) \times (1 + 1) \times (8 + 1) \end{array}$

$\begin{array}{l} S U M (13, [4, 7, 1, 8]) \\ = 4 \times 7 \times 1 \times 8 + 4 \times 7 \times 1 \times 9 + (4 + 5) \times 8 \times 2 \times 9 + 4 \times 7 \times 1 \times 10 \\ + (4 + 5) \times 8 \times 2 \times 10 + (4 + 5 + 6) \times 9 \times 3 \times 10 + 4 \times 7 \times 1 \times 11 \\ + (4 + 5) \times 8 \times 2 \times 11 + (4 + 5 + 6) \times 9 \times 3 \times 11 + (4 + 5 + 6 + 7) \end{array}$

$\begin{array}{l} \times 10 \times 4 \times 11 + 4 \times 7 \times 1 \times 12 + (4 + 5) \times 8 \times 2 \times 12 + (4 + 5 + 6) \times 9 \times 3 \times 12 \\ + (4 + 5 + 6 + 7) \times 10 \times 4 \times 12 + (4 + 5 + 6 + 7 + 8) \times 11 \times 5 \times 12 \\ = 72 + 417 \times 7 + 922 \times 21 + 876 \times 35 + 224 \times 35 = 60853 \end{array}$

2.2. SUM_K(N, PS, PT, PF)

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

$Aproduct = (K_{0} + E_{0}) \times (K_{1} + E_{1}) \dots (K_{M} + E_{M}) = \sum F_{0} 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.

Use the same method of [2]

2.4) SUM_K(N, PS, PT, PF) is similar to (1.4), except the form = $(T_{0} + K_{0}) \dots$

Example:

$B A S E ([4, 7, 11]) = B S = [1, 3, 5]$

$\begin{array}{l} S U M (13, [4, 7, 11]) \\ = 4 \times 7 \times 11 + 4 \times 7 \times (11 + 1) + 4 \times (7 + 1) \times (11 + 1) + (4 + 1) \times (7 + 1) \times (11 + 1) \\ = {4 \times 7 \times 11 + 4 \times 7 \times 11 + 4 \times 7 \times 11 + 4 \times 7 \times 11} \\ + {4 \times 7 \times 1 + 4 \times 7 \times 1 + 4 \times 7 \times 1} + {4 \times 1 \times 11 + 4 \times 1 \times 11} + {1 \times 7 \times 11} \\ + {4 \times 1 \times 1 + 4 \times 1 \times 1} + {1 \times 7 \times 1} + {1 \times 1 \times 11} + {1 \times 1 \times 1} \end{array}$

$4 \times 7 \times 11 \to 308$

$\begin{array}{l} S U M_K (13, P S, B S, K_{0} K_{1} K_{2}) \\ = {4 \times 7 \times 11 + 4 \times 7 \times 11 + 4 \times 7 \times 11 + 4 \times 7 \times 11} = 308 (\begin{matrix} N - 9 \\ 3 \end{matrix}) \end{array}$

$4 \times 7 \times (5 - 2) \to 4 \times 7 \times 3$

$\begin{array}{l} S U M_K (13, P S, B S, K_{0} K_{1} E_{2}) \\ = {4 \times 7 \times 1 + 4 \times 7 \times 1 + 4 \times 7 \times 1} = 4 \times 7 \times 3 (\begin{matrix} N - 9 \\ 4 \end{matrix}) \end{array}$

$4 \times (3 - 1) \times (11 + 1) \to 4 \times 2 \times 11$

$S U M_K (13, P S, B S, K_{0} E_{1} K_{2}) = {4 \times 1 \times 11 + 4 \times 1 \times 11} = 4 \times 2 \times 11 (\begin{matrix} N - 9 \\ 4 \end{matrix})$

$1 \times (7 + 1) \times (11 + 1) \to 1 \times 7 \times 11$

$S U M_K (13, P S, B S, E_{0} K_{1} K_{2}) = {1 \times 7 \times 11} = 1 \times 7 \times 11 (\begin{matrix} N - 9 \\ 4 \end{matrix})$

$4 \times (3 - 1) \times (5 - 1) + 4 \times (3 - 1) \times (11 + 1) \to 4 \times 3 \times 4 + 4 \times 2 \times 1$

$\begin{array}{l} S U M_K (13, P S, B S, K_{0} E_{1} E_{2}) \\ = {4 \times 1 \times 1 + 4 \times 1 \times 1} = 4 \times 3 \times 4 (\begin{matrix} N - 9 \\ 5 \end{matrix}) + 4 \times 2 \times 1 (\begin{matrix} N - 9 \\ 4 \end{matrix}) \end{array}$

$1 \times (7 + 1) \times (5 - 1) + 1 \times (7 + 1) \times (11 + 1) \to 1 \times 7 \times 4 + 1 \times 7 \times 1$

$\begin{array}{l} S U M_K (13, P S, B S, E_{0} K_{1} E_{2}) \\ = {1 \times 7 \times 1} = 1 \times 7 \times 4 (\begin{matrix} N - 9 \\ 5 \end{matrix}) + 1 \times 7 \times 1 (\begin{matrix} N - 9 \\ 4 \end{matrix}) \end{array}$

$1 \times 3 \times (11 + 2) + 1 \times (7 + 1) \times (11 + 1) \to 1 \times 3 \times 11 + 1 \times 1 \times 11$

$\begin{array}{l} S U M_K (13, P S, B S, E_{0} E_{1} K_{2}) \\ = {1 \times 1 \times 11} = 1 \times 3 \times 11 (\begin{matrix} N - 9 \\ 5 \end{matrix}) + 1 \times 1 \times 11 (\begin{matrix} N - 9 \\ 4 \end{matrix}) \end{array}$

$\begin{array}{l} 1 \times 3 \times 5 + [1 \times 3 \times (11 + 2) + 1 \times (7 + 1) \times (5 - 1) + 4 \times (3 - 1) \times (5 - 1)] \\ + [1 \times (7 + 1) \times (11 + 1) + 4 \times (3 - 1) \times (11 + 1) + 4 \times 7 \times (5 - 2)] \\ \to 1 \times 3 \times 5 + [1 \times 3 \times 2 + 1 \times 1 \times 4 + 0] + [1 \times 1 \times 1 + 0 + 0] = 15 + [10] + [1] \end{array}$

$\begin{array}{l} S U M_K (13, P S, B S, E_{0} E_{1} E_{2}) \\ = {1 \times 1 \times 1} = 15 (\begin{matrix} N - 9 \\ 6 \end{matrix}) + 10 (\begin{matrix} N - 9 \\ 5 \end{matrix}) + (\begin{matrix} N - 9 \\ 4 \end{matrix}) \end{array}$

3. Coefficient Analysis

$K = [K_{1}, \dots, K_{M}]$ ,

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

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

Define $H (K, T, N, S) = \sum B_{N}$ , $0 \leq N \leq M$ , $N = countof X \in T$

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

H(K, T, N, 1) is abbreviated as H(K, T, N)

3.1) $H (K, T, M) = T_{1} \times T_{2} \times \dots \times T_{M}$ , $H (K, T, 0) = K_{1} \times K_{2} \times \dots \times K_{M}$

[3] has proved:

$S U M (N + 1, [1, 1, \dots, 1], [1, 2, \dots, M]) = \sum_{n = 1}^{N} n^{M} = \sum_{K = 1}^{M} K! S_{2} (M, K) (\begin{matrix} N + 1 \\ K + 1 \end{matrix})$

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

3.2) $H ([1, 1, \dots, 1], [2, 3, \dots, M], N) = (M - N)! \times S_{2} (M, M - N)$

$S U M (N, [K_{0} = 1, K_{1}, \dots, K_{M}], [T_{0} = 1, T_{1}, \dots, T_{M}])$

can use the form = $(T_{1} + K_{1}) \dots (T_{M} + K_{M})$ or $(T_{0} + K_{0}) (T_{1} + K_{1}) \dots (T_{M} + K_{M})$

For arbitrary K, T:

3.3) $H ([P, K], [P, T], N, S) = P \times H (K, T, N, S) + P \times H (K, T, N - 1, S)$

[Proof]

$\begin{array}{l} H ([P, K, K_{M + 1}], [P, T, T_{M + 1}], N + 1, S) \\ = (X_{M + 1} = K_{M + 1}) + (X_{M + 1} = T_{M + 1}) \\ = H ([P, K], [P, T], N + 1, S) (K_{M + 1} + [N + 1] \times S) \\ + H ([P, K], [P, T], N, S) (T_{M + 1} - [M + 1 - N] \times S) \\ = {P \times H (K, T, N + 1, S) + P \times H (K, T, N, S)} (K_{M + 1} + [N + 1] \times S) \\ + {P \times H (K, T, N, S) + P \times H (K, T, N - 1, S)} (T_{M + 1} - [M + 1 - N] \times S) \end{array}$

$\begin{array}{l} = P \times {H (K, T, N + 1, S) (K_{M + 1} + [N + 1] \times S) \\ + H (K, T, N, S) (T_{M + 1} - [M - N] \times S)} \\ + P \times {H (K, T, N, S) {(K_{M + 1} + N \times S)}_{}^{} \\ + H (K, T, N - 1, S) (T_{M + 1} - [M - (N - 1)] \times S)} \\ = P \times H ([K, K_{M + 1}], [T, T_{M + 1}], N + 1, S) + P \times H ([K, K_{M + 1}], [T, T_{M + 1}], N, S) \end{array}$

q.e.d.

this à

3.4) $S U M (N, [1, 2, \dots, n, K_{1}, \dots, K_{M}], [1, 2, \dots, n, T_{1}, \dots, T_{M}])$

can use the form: $(T_{1} + K_{1}) \dots (T_{M} + K_{M}) = n! \sum A_{q} (\begin{matrix} N - P H (P S) - P C H G (P S, P T) + n - 1 \\ I D X (P T) - q \end{matrix})$

[2] has proved:

3.5) $H (K, K, N, S) = (\begin{matrix} M \\ N \end{matrix}) K_{1} \times K_{2} \times \dots \times K_{M}$

1.3) can derive 1.2) from this.

3.6) if $K_{i} + S = K_{i + 1}$ , $T_{i} + S = T_{i + 1}$ , then $H (K, T, N, S) = (\begin{matrix} M \\ N \end{matrix}) T_{1} \dots T_{N} \times K_{N + 1} \dots K_{M}$

[Proof]

Suppose $H (K, T, N, S) = (\begin{matrix} M \\ N \end{matrix}) T_{1} \dots T_{N} K_{N + 1} K_{N + 2} \dots K_{M}$

$\begin{array}{l} H ([K, K_{M + 1} = S + K_{M}], [T, T_{M + 1} = S + T_{M}], N + 1, S) \\ = (X_{M + 1} = K_{M + 1}) + (X_{M + 1} = T_{M + 1}) \\ = H (K, T, N + 1, S) (K_{M + 1} + [N + 1] \times S) \\ + H (K, T, N, S) (T_{M + 1} - [M - N] \times S) \end{array}$

$\begin{array}{l} = (\begin{matrix} M \\ N + 1 \end{matrix}) T_{1} \dots T_{N + 1} K_{N + 2} \dots K_{M} (K_{M + 1} + [N + 1] \times S) \\ + (\begin{matrix} M \\ N \end{matrix}) T_{1} \dots T_{N} K_{N + 1} \dots K_{M} (T_{M + 1} - [M - N] \times S) \\ = T_{1} \dots T_{N} K_{N + 2} \dots K_{M} (\begin{matrix} M \\ N + 1 \end{matrix}) T_{N + 1} (K_{M + 1} + [N + 1] \times S) \\ + T_{1} \dots T_{N} K_{N + 2} \dots K_{M} (\begin{matrix} M \\ N \end{matrix}) K_{N + 1} (T_{M + 1} - [M - N] \times S) \end{array}$

$\begin{array}{l} = T_{1} \dots T_{N} K_{N + 2} \dots K_{M} (\begin{matrix} M \\ N + 1 \end{matrix}) [T_{N + 1} K_{M + 1} + T_{N + 1} (N + 1) \times S] \\ + T_{1} \dots T_{N} K_{N + 2} \dots K_{M} (\begin{matrix} M \\ N \end{matrix}) [K_{M + 1} - [M - N] \times S] \\ \times ([T_{N + 1} + [M - N] \times S] - [M - N] \times S) \end{array}$

$\begin{array}{l} = T_{1} \dots T_{N} K_{N + 2} \dots K_{M} [(\begin{matrix} M \\ N + 1 \end{matrix}) T_{N + 1} K_{M + 1} + (\begin{matrix} M \\ N \end{matrix}) T_{N + 1} K_{M + 1}] \\ + T_{1} \dots T_{N} K_{N + 2} \dots K_{M} [(\begin{matrix} M \\ N + 1 \end{matrix}) T_{N + 1} (N + 1) - (\begin{matrix} M \\ N \end{matrix}) T_{N + 1} (M - N)] \times S \\ = T_{1} \dots T_{N} K_{N + 2} \dots K_{M} [(\begin{matrix} M \\ N + 1 \end{matrix}) T_{N + 1} K_{M + 1} + (\begin{matrix} M \\ N \end{matrix}) T_{N + 1} K_{M + 1}] \\ = (\begin{matrix} M + 1 \\ N + 1 \end{matrix}) T_{1} \dots T_{N + 1} K_{N + 2} \dots K_{M + 1} \end{array}$

à $H ([K, K_{M + 1}], [T, T_{M + 1}], N + 1, S)$ holds

q.e.d.

Define

$F_{Q}^{K} = \sum Q - productwithdifferentfactors \in K$ , the sum traverse all combinations.

$E_{Q}^{K} = \sum Q - product with factors \in K$ , the sum traverse all combinations.

$F_{Q}^{{1, 2, \dots, N}}$ is abbreviated as $F_{Q}^{N}$ , $E_{Q}^{{1, 2, \dots, N}}$ is abbreviated as $E_{Q}^{N}$ ;

$F_{0}^{K} = E_{0}^{K} = 1$ ; $F_{Q > | K |}^{K} = 0$ ;

By definition:

$E_{Q}^{N + 1} = (N + 1) E_{Q - 1}^{N + 1} + E_{Q}^{N}; F_{Q}^{[K, K_{M + 1}]} = K_{M + 1} F_{Q - 1}^{K} + F_{Q}^{K}$ .

3.7) if $T_{i} + 1 = T_{i + 1}$ , then $H (K, T, N) = T_{1} \dots T_{N} [F_{M - N}^{K} E_{0}^{N} + F_{M - N - 1}^{K} E_{1}^{N} + \dots + + F_{0}^{K} E_{M - N}^{N}]$

[Proof]

Suppose H(K, T, N) holds

$\begin{array}{l} H ([K, K_{M + 1}], [T, T_{M + 1} = 1 + T_{M}], N + 1) \\ = H (K, T, N + 1) (K_{M + 1} + N + 1) + H (K, T, N) (T_{M + 1} - [M - N]) \\ = T_{1} \dots T_{N + 1} [F_{M - N - 1}^{K} E_{0}^{N + 1} + F_{M - N - 2}^{K} E_{1}^{N + 1} + \dots + F_{0}^{K} E_{M - N - 1}^{N + 1}] (K_{M + 1} + N + 1) \\ + T_{1} \dots T_{N} [F_{M - N}^{K} E_{0}^{N} + F_{M - N - 1}^{K} E_{1}^{N} + \dots + F_{0}^{K} E_{M - N}^{N}] (T_{M + 1} - [M - N]) \\ = T_{1} \dots T_{N + 1} [F_{M - N - 1}^{K} E_{0}^{N + 1} + F_{M - N - 2}^{K} E_{1}^{N + 1} + \dots + F_{0}^{K} E_{M - N - 1}^{N + 1}] (K_{M + 1} + N + 1) \\ + T_{1} \dots T_{N + 1} [F_{M - N}^{K} E_{0}^{N} + F_{M - N - 1}^{K} E_{1}^{N} + \dots + F_{0}^{K} E_{M - N}^{N}] \end{array}$

$\begin{array}{l} H ([K, K_{M + 1}], [T, T_{M + 1} = 1 + T_{M}], N + 1) / T_{1} \dots T_{N + 1} \\ = [F_{M - N - 1}^{K} E_{0}^{N + 1} + F_{M - N - 2}^{K} E_{1}^{N + 1} + \dots + F_{0}^{K} E_{M - N - 1}^{N + 1}] (K_{M + 1} + N + 1) \\ + [F_{M - N}^{K} E_{0}^{N} + F_{M - N - 1}^{K} E_{1}^{N} + \dots + F_{0}^{K} E_{M - N}^{N}] \end{array}$

$\begin{array}{l} Sumofallitemswithcountoffactors \in K = M - N - Q \\ = F_{M - [N + 1] - Q}^{K} E_{Q}^{N + 1} K_{M + 1} + F_{M - [N + 1] - (Q - 1)}^{K} E_{Q - 1}^{N + 1} (N + 1) + F_{M - N - Q}^{K} E_{Q}^{N} \\ = F_{M - [N + 1] - Q}^{K} E_{Q}^{N + 1} K_{M + 1} + F_{M - N - Q}^{K} [(N + 1) E_{Q - 1}^{N + 1} + E_{Q}^{N}] \\ = F_{M - [N + 1] - Q}^{K} E_{Q}^{N + 1} K_{M + 1} + F_{M - N - Q}^{K} E_{Q}^{N + 1} \\ = F_{M - N - Q}^{[K, K_{M + 1}]} E_{Q}^{N + 1} = F_{[M + 1] - [N + 1] - Q}^{[K, K_{M + 1}]} E_{Q}^{N + 1} \end{array}$

à $H ([K, K_{M + 1}], [T, T_{M + 1}], N + 1)$ holds

q.e.d.

Example:

$\begin{array}{l} H ([A, B, C, D], [1, 2, 3, 4], 2) \\ = 1 \times 2 \times (C + 2) (D + 2) + 1 \times (B + 1) \times (3 - 1) (D + 2) \\ + A \times (2 - 1) \times (3 - 1) (D + 2) + 1 \times (B + 1) (C + 1) (4 - 2) \\ + A \times (2 - 1) \times (C + 1) (4 - 2) + A B (3 - 1) (4 - 2) \end{array}$

$\begin{array}{l} = 1 \times 2 [(C + 2) (D + 2) + (B + 1) (D + 2) + A (D + 2) \\ + (B + 1) (C + 1) + A (C + 1) + A B] \\ = 1 \times 2 [(C D + B D + A D + B C + A C + A B) \\ + (C + D + B + A) (1 + 2) + (1 \times 2 + 1 \times 1 + 2 \times 2)] \end{array}$

3.8) In $S U M (N, [K_{1}, \dots, K_{M}], [1, 2, \dots, M])$ , K_i can switch the order.

3.9) if $T_{i} + S = T_{i + 1}$ , then

$\begin{array}{l} H (K, T, N, S) \\ = T_{1} \dots T_{N} [F_{M - N}^{K} E_{0}^{{S, 2 S, \dots, N S}} + F_{M - N - 1}^{K} E_{1}^{{S, 2 S, \dots, N S}} + \dots + F_{0}^{K} E_{M - N}^{N {S, 2 S, \dots, N S}}] \end{array}$

$F_{M - N}^{M} = S_{1} (M + 1, N + 1)$ , S₁ is the first kind of unsigned Stirling number.

From 3.5) and 3.7)à

$\begin{array}{l} H ([1, \dots, M - 1], [1, \dots, M - 1], N) = (M - 1)! (\begin{matrix} M - 1 \\ N \end{matrix}) \\ = N! [F_{M - 1 - N}^{M - 1} E_{0}^{N} + F_{M - 1 - N - 1}^{M - 1} E_{1}^{N} + \dots + F_{0}^{M - 1} E_{M - 1 - N}^{N}] \\ = N! [S_{1} (M, N + 1) E_{0}^{N} + S_{1} (M, N + 2) E_{1}^{N} + \dots + S_{1} (M, M) E_{M - 1 - N}^{N}] \end{array}$ à

3.10) $\begin{array}{l} S_{1} (M, N + 1) E_{0}^{N} + S_{1} (M, N + 2) E_{1}^{N} + \dots + S_{1} (M, M) E_{M - 1 - N}^{N} \\ = (\begin{matrix} M - 1 \\ N \end{matrix}) \frac{(M - 1)!}{N!} \end{array}$

4. $\begin{array}{l} K_{1} \times \dots \times K_{M} + (L + K_{1}) \times \dots \times (L + K_{M}) \\ + (2 L + K_{1}) \times \dots \times (2 L + K_{M}) + \dots \end{array}$

$K = [K_{1}, \dots, K_{M}]$ , $T = [T_{1}, \dots, T_{M}]$ , Max Factor = K_M

$\begin{matrix} S U M (N, P S, P T) = \sum_{n = - \infty}^{N} \sum E N D (n, P S, P T) \\ = \sum_{n = K_{M} + 1}^{N} \sum E N D (n, P S, P T) \\ = \sum A_{q} (\begin{matrix} N - P H (P S) - P C H G (P S, P T) - 1 \\ I D X (P T) - q \end{matrix}) \end{matrix}$

When $N = K_{M} + 1$

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

à $S U M (N, P S, P T) = A_{M}$

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

SUM(N, PS, PT) can be broken down into 2^M parts.

SUM_K(N, PS, PT, PF) can explain why SUM(N, PS, PT) has that strange form:

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

SUM_K(N, PS, PT, PF) use the form =

$(T_{1} + K_{1}) \dots (T_{M} + K_{M}) = \sum \prod_{i = 1}^{M} Y_{i} (\begin{matrix} A \\ M_{q} \end{matrix})$

When T_i and D_i all increase L times. If $P T = [1, 2, \dots, M]$ , when N increase,

$| E n d (N, P S, P T) | = 1$ , match the corresponding SUM_K().

Define

$S U M L (N, P S, 1) = S U M (N + K_{M}, P S, [1, 2, \dots, M])$

$\begin{matrix} S U M L (N, P S, L) = K_{1} \times \dots \times K_{M} + (L + K_{1}) \times \dots \times (L + K_{M}) + \dots \\ + ((N - 1) L + K_{1}) \times \dots \times ((N - 1) L + K_{M}) \end{matrix}$

SUML_K(N, PS, PF, L) = corresponding part of SUML(N, PS, L)

Above à

4.1) SUML(N, PS, L), SUML_K(N, PS, PF, L),

$P T = [T_{1}, \dots, T_{M}] = [1 \times L, 2 \times L, \dots, M \times L]$ , can use the from $(T_{1} + K_{1}) \dots (T_{M} + K_{M})$

$S U M L (N, P S, L) = \sum A_{q} (\begin{matrix} N \\ M + 1 - q \end{matrix})$ , $q = countof X \in K$ , 2^M items in total.

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

Example:

$S U M L (N, [3, 5, 8], 4)$ à

$form = (1 \times 4 + 3) (2 \times 4 + 5) (3 \times 4 + 8) = (4 + 3) (8 + 5) (12 + 8)$ à

$= 384 (\begin{matrix} N \\ 4 \end{matrix}) + 896 (\begin{matrix} N \\ 3 \end{matrix}) + 636 (\begin{matrix} N \\ 2 \end{matrix}) + 120 ( N 1 )$

$384 = 4 \times 8 \times 12$ ; $120 = 3 \times 5 \times 8$

$\begin{array}{l} 896 = 4 \times 8 \times (8 + 2 \times 4) + 4 \times (5 + 1 \times 4) \times (12 - 1 \times 4) \\ + 3 \times (8 - 1 \times 4) \times (12 - 1 \times 4) \end{array}$

$\begin{array}{l} 636 = 3 \times 5 \times (12 - 2 \times 4) + 3 \times (8 - 1 \times 4) \times (8 + 1 \times 4) \\ + 4 \times (5 + 1 \times 4) \times (8 + 1 \times 4) \end{array}$

$\begin{array}{l} S U M L (6, [3, 5, 8], 4) \\ = 3 \times 5 \times 8 + 7 \times 9 \times 12 + 11 \times 13 \times 16 + 15 \times 17 \times 20 \\ + 19 \times 21 \times 24 + 23 \times 25 \times 28 \\ = 384 \times 15 + 896 \times 20 + 636 \times 15 + 120 \times 6 = 33940 \end{array}$

$S U M L (N, [1], 2) = 1 + 3 + \dots + (2 N - 1) = 2 (\begin{matrix} N \\ 2 \end{matrix}) + (\begin{matrix} N \\ 1 \end{matrix}) = N^{2}$

4.2) P is a prime number, For arbitrary $K_{1}, K_{2}, \dots, K_{M}$ :

If $M < P - 1$ , then

$\begin{array}{l} K_{1} \times K_{2} \times \dots \times K_{M} + (L + K_{1}) \times \dots \times (L + K_{M}) + \dots \\ + ((P - 1) L + K_{1}) \times \dots \times ((P - 1) L + K_{M}) \equiv 0 M O D P \end{array}$

If $M = P - 1$ and $(L, P) = 1$ then

[Proof]

$Theexpression = S U M L (P, P S, L) = \sum A_{q} (\begin{matrix} P \\ M + 1 - q \end{matrix})$

If $M < P - 1$ , then $M + 1 < P$

If $M = P - 1$ and $(L, P) = 1$ , then

$\begin{matrix} S U M L (N, P S, L) = L^{P - 1} (P - 1)! (\begin{matrix} P \\ P \end{matrix}) + \sum A_{q} (\begin{matrix} P \\ M + 1 - q \end{matrix}), q > 0 \\ \equiv L^{P - 1} (P - 1)! \equiv - 1 M O D P \end{matrix}$

q.e.d.

5. Conclusions

The whole process of [1-3] is reviewed and this paper:

[1] tries to calculate all products of k distinct integers in [1, N − 1], introduces the concept of Shape of numbers. The idea divides all products of k distinct integers in [1, N − 1] into 2^K⁻¹ catalogs and derives the calculation formula of every catalog, that is 1.2).

[1] only introduces the basic shape. The conclusion is obtained through the derivation process.

[2] introduces the shape $P S = [1, K_{1}, \dots, K_{M}]$ , tries to calculate SUM(N, PS), the form $(G_{1} + K_{1}) (G_{2} + K_{2}) \dots (G_{M} + K_{M})$ is guessed by observation and proved by induction.

At the same time, SUM_K() is introduced.

[3] introduces the subset, and shows the way to calculate $1^{M} + 2^{M} + 3^{M} + \dots + N^{M}$ .

In this paper, the Shape and the form are further extended. So a lot of numbers’s series can be calculated.

Some new congruences are also obtained in [1] [2] [3] and this article.

The whole foundation is just $(\begin{matrix} N \\ M \end{matrix}) + (\begin{matrix} N \\ M + 1 \end{matrix}) = (\begin{matrix} N + 1 \\ M + 1 \end{matrix})$ .

Conflicts of Interest

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

Cite this paper

Peng, J. (2021) Expansion of the Shape of Numbers. Open Access Library Journal, 8: e7120. https://doi.org/10.4236/oalib.1107120

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

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

Journal Menu >>