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

1. Introduction

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

K i , D i CommutativeRing .

M series: S e r i e i = { K i , K i + D i , K i + 2 D i , , K i + ( N 1 ) D i } , i [ 1 , M ] .

Use P S = [ K 1 : D 1 , , K M : D M ] to represent thems.

[ K 1 : 1 , , K M : 1 ] is abbreviated as [ K 1 , , K M ] .

Anitem = ( I 1 , I 2 , , I M ) , I i comes from Seriei. A product = i = 1 M I i .

Use P T = [ T 1 = 1 , T 2 , , T M ] to indicate the item’s range:

I i = K i + a i D i , { T i + 1 T i = 1 , means a i = a i + 1 , continuity T i + 1 T i = 2 , means a i a i + 1 , discontinuity .

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

S U M ( N , P S , P T ) = allitems product .

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

By default, the following uses:

P S = [ K 1 : D 1 , , K M : D M ] , P T = [ T 1 , , T M ] .

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

The Form: ( T 1 + K 1 ) ( T 2 + K 2 ) ( T M + K M ) = i = 1 M X M , X i = T i or K i .

Don’t swap the factors. Each X i corresponds to one expression in SUM(…).

X ( T ) = countof { X 1 , , X M } { T 1 , , T M } ,

X K 1 = countof { X 1 , , X i 1 } { K 1 , , K M } .

1.1) q = X ( T ) , P M = P M ( P T ) ,

S U M ( N ) = Form 1 q = 0 P M H 1 ( q ) ( N + T M P M N 1 q ) , B i = { ( T i X K 1 ) D i ; X i = T i K i + X T 1 D i ; X i = K i Form 2 q = 0 P M H 2 ( q ) ( N + T M P M + q N 1 ) , B i = { ( T i X K 1 ) D i ; X i = T i K i + ( X K 1 T i ) D i ; X i = K i Form 3 q = 0 P M H 3 ( q ) ( N + T M q N 1 q ) , B i = { K i + ( T i X T 1 ) D i ; X i = T i K i + X T 1 D i ; X i = K i

H ( q ) = H ( P S , P T , q ) = all of the X i with X ( T ) = q i = 1 M B i .

In particular:

1.2) S U M ( N , [ 1 , 2 , , M ] , [ 1 , 3 , , 2 M 1 ] ) = S 1 ( N + M , N ) , unsigned Stirling number.

1.3) S U M ( N , [ 1 , 1 , , 1 ] , [ 1 , 3 , , 2 M 1 ] ) = S 2 ( N + M , N ) , Stirling number of the second kind.

1.4) S U M ( N , [ 1 , 1 , , 1 ] , [ 1 , 2 , , M ] ) = 1 M + 2 M + + N M .

2. Equivalence of Three Forms

The following change Ti’s domain to and T i + 1 T i is not restricted.

P S 1 = [ P S , K M + 1 : D M + 1 ] , P T 1 = [ P T , T M + 1 ] , use H ( P S 1 , q ) = H ( P S 1 , P T 1 , q ) .

2.0) Recurrence relation

H 1 ( P S 1 , q ) = H 1 ( q 1 ) ( T M + 1 [ M ( q 1 ) ] ) D M + 1 + H 1 ( q ) ( K M + 1 + q D M + 1 )

H 2 ( P S 1 , q ) = H 2 ( q 1 ) ( T M + 1 [ M ( q 1 ) ] ) D M + 1 + H 2 ( q ) ( K M + 1 + [ T M + 1 + M q ] D M + 1 )

H 3 ( P S 1 , q ) = H 3 ( q 1 ) ( K M + 1 + [ T M + 1 ( q 1 ) ] D M + 1 ) + H 3 ( q ) ( K M + 1 + q D M + 1 )

2.1) ① H 1 ( q ) = x = q M H 2 ( x ) ( x q ) = x = 0 q H 3 ( x ) ( M x M q )

H 2 ( q ) = x = q M ( 1 ) x + q H 1 ( x ) ( x q ) , H 3 ( q ) = x = 0 q ( 1 ) x + q H 1 ( x ) ( M x M q )

[Proof]

Suppose H 1 ( q ) = x = q M H 2 ( x ) ( x q ) = x = 0 M H 2 ( x ) ( x q ) , y = T M + 1 M 1 .

A : H 1 ( P S 1 , q ) = ( T M + 1 M 1 + q ) D M + 1 H 1 ( q 1 ) + ( K M + 1 + q D M + 1 ) H 1 ( q ) = ( y + q ) D M + 1 x = 0 M H 2 ( x ) { ( x + 1 q ) ( x q ) } + ( K M + 1 + q D M + 1 ) k = 0 M H 2 ( x ) ( x q ) = ( y + q ) D M + 1 x = 0 M H 2 ( x ) ( x + 1 q ) + ( K M + 1 y D M + 1 ) k = 0 M H 2 ( x ) ( x q )

B : x = 0 M + 1 H 2 ( P S 1 , x ) ( x q ) = x = 0 M + 1 { H 2 ( x 1 ) ( y + x ) D M + 1 ( x q ) + H 2 ( x ) ( K M + 1 + ( y 1 x ) D M + 1 ) ( x q ) } = x = 0 M { H 2 ( x ) ( y + x + 1 ) D M + 1 ( x + 1 q ) + H 2 ( x ) ( K M + 1 + ( y 1 x ) D M + 1 ) ( x q ) }

[ A B ] = x = 0 M H 2 ( x ) ( q 1 x ) D M + 1 ( x + 1 q ) + x = 0 M H 2 ( x ) ( 1 + x ) D M + 1 ( x q ) = D M + 1 x = 0 M H 2 ( x ) q ( x + 1 q ) D M + 1 x = 0 M H 2 ( x ) ( 1 + x ) ( x q 1 ) = 0

H 1 ( q ) = x = q M H 2 ( x ) ( x q )

sameway H 1 ( q ) = x = 0 q H 3 ( x ) ( M x M q ) Inversion

q.e.d.

In particular:

2.2) ① H 1 ( 0 ) = H 3 ( 0 ) = x = 0 M H 2 ( x ) = i = 1 M K i ;

H 1 ( M ) = H 2 ( M ) = x = 0 M H 3 ( x ) = i = 1 M T i D i ;

H 2 ( 0 ) = ( 1 ) M H 3 ( M ) = x = 0 M ( 1 ) x H 1 ( x ) ;

H 1 ( 1 ) = x = 1 M H 2 ( x ) x = M H 3 ( 0 ) + H 3 ( 1 ) .

Calculation with 2.1):

2.3) q = 0 M H 1 ( q ) = q = 0 M H 2 ( q ) 2 q = q = 0 M H 3 ( q ) 2 M q .

Use 2.1) Form 1 = Form 2 = Form 3 .

2.4) ① q = 0 M H 1 ( q ) ( A B q ) = q = 0 M H 2 ( q ) ( A + q B ) = q = 0 M H 3 ( q ) ( A + M q B q )

q = 0 M H 1 ( q ) ( A q ) = q = 0 M H 2 ( q ) ( A + q q ) = q = 0 M H 3 ( q ) ( A + M q M )

2.5) q = 0 M H 1 ( q ) q ( A + 1 B q ) = q = 0 M H 2 ( q ) q ( A + q B 1 ) = q = 0 M { H 3 ( q ) q ( A + M q B q ) + M H 3 ( q ) ( A + M q B 1 q ) }

[Proof]

Suppose it’s holds when M, Let y = T M + 1 M 1 .

A : q = 0 M + 1 H 1 ( P S 1 , q ) ( A B q ) = q = 0 M + 1 { ( y + q ) D M + 1 H 1 ( q 1 ) + ( K M + 1 + q D M + 1 ) H 1 ( q ) } ( A B q ) = q = 0 M { ( y + q + 1 ) D M + 1 H 1 ( q ) ( A B 1 q ) + ( K M + 1 + q D M + 1 ) H 1 ( q ) ( A B q ) } = ( y + 1 ) D M + 1 q = 0 M H 1 ( q ) ( A B 1 q ) + K M + 1 q = 0 M H 1 ( q ) ( A B q ) + D M + 1 q = 0 M H 1 ( q ) q ( A + 1 B q )

B : q = 0 M + 1 H 2 ( P S 1 , q ) ( A + q B ) = q = 0 M + 1 { ( y + q ) D M + 1 H 2 ( q 1 ) + ( K M + 1 + ( y 1 q ) D M + 1 ) H 2 ( q ) } ( A + q B ) = ( y + 1 ) D M + 1 q = 0 M H 2 ( q ) ( A + q B 1 ) + K M + 1 q = 0 M H 2 ( q ) ( A + q B ) + D M + 1 q = 0 M H 2 ( q ) q ( A + q B 1 )

2.4 ) A = B

2.4 ) H 1 ( q ) ( A B 1 q ) = H 2 ( q ) ( A + q B 1 ) , H 1 ( q ) ( A B q ) = H 2 ( q ) ( A + q B ) left

q.e.d.

Example 2.1

M = 1:

Form 1 = T 1 D 1 ( A B 1 ) + K 1 ( A B ) ;

Form 2 = T 1 D 1 ( A + 1 B ) + ( K 1 T 1 D 1 ) ( A B ) ;

Form 3 = ( K 1 + T 1 D 1 ) ( A B 1 ) + K 1 ( A + 1 B ) ;

M = 2:

Form 1 = T 1 T 2 D 1 D 2 ( A B 2 ) + [ K 1 ( T 2 1 ) D 2 + T 1 D 1 ( K 2 + D 2 ) ] ( A B 1 ) + K 1 K 2 ( A B ) ;

Form 2 = T 1 T 2 D 1 D 2 ( A + 2 B ) + [ ( K 1 T 1 D 1 ) ( T 2 1 ) D 2 + T 1 D 1 ( K 2 T 2 D 2 ) ] ( A + 1 B ) + ( K 1 T 1 D 1 ) ( K 2 T 2 D 2 + D 2 ) ( A B ) ;

Form 3 = ( K 1 + T 1 D 1 ) ( K 2 + T 2 D 2 D 2 ) ( A B 2 ) + [ K 1 ( K 2 + T 2 D 2 ) + ( K 1 + T 1 D 1 ) ( K 2 + D 2 ) ] ( A + 1 B 1 ) + K 1 K 2 ( A + 2 B ) .

3. Generalization of Calculation Formula

If f ( n ) = A i ( N i m i ) , m i is not changed with n, then define

p f ( n ) = A i ( N i p m i p ) , P

f ( n ) = f ( n ) f ( n 1 ) , this is a little different from the difference

0 f ( n ) = f ( n ) , 1 f ( N ) = n = 0 N 1 f ( n )

Eg: ( n + 1 n 1 ) = ( n + 1 2 ) = ( n 1 ) ( n n 2 ) .

In [1], 1.1) is proved by

(*) n = 0 N 1 n ( n + K M ) = ( M + 1 ) ( N + K M + 2 ) + ( M K ) ( N + K M + 1 )

S U M ( N , P S 1 , [ P T , T M + 1 ] ) = n = 0 N 1 ( K M + 1 + n × D M + 1 ) × S U M ( n + 1 )

S U M ( N , P S 1 , [ P T , T M + 2 ] ) = n = 0 N 1 ( K M + 1 + n × D M + 1 ) × 0 S U M ( n + 1 )

P S 1 = [ P S , K M + 1 : D M + 1 ] , P T 1 = [ P T , T M + 1 = T M + 2 p ] .

Define: S U M ( N , P S 1 , P T 1 ) = n = 0 N 1 ( K M + 1 + n × D M + 1 ) × p S U M ( n + 1 )

S U M ( N , P S 1 , P T 1 ) can be calculated using the same method of 1.1).

The Form: ( T 1 + K 1 ) ( T 2 + K 2 ) ( T M + K M ) = i = 1 M X M , X i = T i or K i .

3.1) q = X ( T ) , P M = P M ( P T ) ,

S U M ( N ) = Form 1 q = 0 P M H 1 ( q ) ( N + T M P M N 1 q ) , B i = { ( T i X K 1 ) D i ; X i = T i K i + X T 1 D i ; X i = K i Form 2 q = 0 P M H 2 ( q ) ( N + T M P M + q N 1 ) , B i = { ( T i X K 1 ) D i ; X i = T i K i + ( X K 1 T i ) D i ; X i = K i Form 3 q = 0 P M H 3 ( q ) ( N + T M q N 1 q ) , B i = { K i + ( T i X T 1 ) D i ; X i = T i K i + X T 1 D i ; X i = K i

H ( q ) = H ( P S , P T , q ) = all of the X i with X ( T ) = q i = 1 M B i .

[Proof]

S U M ( N ) Form 1 q = 0 M H 1 ( q ) ( N + T M M N 1 q ) = q = 0 M H 1 ( q ) ( N + T M M T M M + 1 + q )

n = 0 N 1 ( K M + 1 + n × D M + 1 ) × p S U M ( n + 1 ) = n = 0 N 1 ( K M + 1 + n × D M + 1 ) × q = 0 M H 1 ( q ) ( n + 1 + T M M p T M M + 1 + q p ) ( ) = q = 0 M ( T M M + 2 + q p ) D M + 1 × H 1 ( q ) ( N + 1 + T M M p T M M + 3 + q p ) + q = 0 M ( K M + 1 + q D M + 1 ) × H 1 ( q ) ( N + 1 + T M M p T M M + 2 + q p )

= q = 0 M ( T M + 1 [ M q ] ) D M + 1 × H 1 ( q ) ( N + T M + 1 ( M + 1 ) N 1 ( q + 1 ) ) + q = 0 M ( K M + 1 + q D M + 1 ) × H 1 ( q ) ( N + T M + 1 ( M + 1 ) N 1 q ) = q = 0 M + 1 H 1 ( P S 1 , P T 1 , q ) ( N + T M + 1 ( M + 1 ) N 1 q ) 2.4 ) threeforms

q.e.d.

3.2) P S 1 = [ D × A : D , P S ] , P T 1 = [ A , P T ]

H 1 ( P S 1 , q ) = D × A × [ H 1 ( q ) + H 1 ( q 1 ) ] ;

H 2 ( P S 1 , 0 ) = 0 , H 2 ( P S 1 , q ) = D × A × H 2 ( q 1 ) ;

H 3 ( P S 1 , M + 1 ) = 0 , H 3 ( P S 1 , q ) = D × A × H 3 ( q ) ;

H 1 ( [ D × T 1 : D , , D × T M : D ] , [ T 1 , , T M ] , q ) = D M ( M q ) i = 1 M T i ;

S U M ( N , P T , P T ) = i = 1 M T i ( N + T M T M + 1 ) ;

S U M ( N , [ L 1 , , L P , P S ] , [ L 1 , , L P , P T ] ) = i = 1 P L i S U M ( N ) .

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

3.3) P S 1 = [ 1 , 1 , , 1 , P S ] , P T 1 = [ 1 , 1 , , 1 , P T ] , S U M ( N , P S 1 , P T 1 ) = S U M ( N ) .

P = Count of 1 added

expands q = 0 M H 1 ( q ) ( A + P B q ) to q = 0 M + P H 1 ( P S 1 , q ) ( A B q ) .

Now PT’s domain is extended to and T i + 1 T i is not restricted.

If T M 0 , S U M ( N ) = q = 0 M H 1 ( q ) ( A B ) , B < 0 , the formula has no meaning

when regardless of the actual meaning, Form 1 = Form 2 = Form 3 still established.

PT’s domain can be extended to .

4. Properties of Coefficients

Define

F M N + M 1 = 1 I i I i + 1 N + M 1 i = 1 M I i = S 1 ( N + M , N )

E M N = λ 1 + λ 2 + + λ N = M 1 λ 1 2 λ 2 N λ N = S 2 ( N + M , N )

E p q + 1 ( P T , K ) = λ 1 + λ 2 + + λ q + 1 = p 1 λ 1 2 λ 2 ( q + 1 ) λ q + 1 × ( T 1 + λ 1 K ) ( T 2 + λ 1 K + λ 2 K ) ( T q + λ 1 K + λ 2 K + + λ q K ) , λ i 0

PT in section 1: T 1 = 1 , { T i + 1 T i = 1 : meanscontinuity T i + 1 T i = 2 , meansdiscontinuity .

[1] call them Basic Shapes and define:

P B ( P T ) = countofdiscontinuity , M I N ( P T ) = i = 1 M T i D i .

Expand the definition:

P S = [ K 1 : D 1 , K 2 : D 2 , ] , Item = { K 1 + λ 1 D 1 , K 2 + λ 2 D 2 , }

Specify λ 1 = 0 , { λ i = λ i + 1 : meanscontinuity λ i + 1 = λ i + 1 , meansdiscontinuity

PB (item of PS) = count of discontinuity in an item, value [ 0 , M 1 ] .

M I N ( item of P S ) = i = 1 M ( K i + λ i D i )

M I N q ( P S ) = P B ( ) = q M I N ( item of P S ) , M I N q is short for M I N q ( [ 1 , , M ] ) .

By definition →

4.1) ① H 1 ( q ) = ( 1 ) M q H 2 ( [ K i + T i D i ( i 1 ) D i ] , P T ) = ( 1 ) q H 3 ( P S , [ K i D i T i + ( i 1 ) ] ) ;

H 2 ( q ) = ( 1 ) M q H 1 ( [ K i + T i D i ( i 1 ) D i ] , P T ) ;

H 3 ( q ) = ( 1 ) q H 1 ( P S , [ K i D i T i + ( i 1 ) ] ) .

4.2) P S = [ 1 , 1 , ] , P T = [ T i = T 1 + ( i 1 ) ( K + 1 ) ]

H 1 ( q ) = E M q q + 1 ( P T , K ) ;

H 3 ( q ) = E M q q + 1 ( [ T i = ( T 1 1 ) + ( i 1 ) K ] , K + 1 ) ;

E M q q + 1 ( P T , K ) = E M 1 q q + 1 ( [ K + T i ] , K ) + T 1 E M 1 q q + 1 ( [ K + T i ] , K ) .

[Proof]

H 1 ( q ) = ( X T ) ( X K ) def ( X K ) = E M q q + 1

X = 1 λ 1 { x = 1 A 1 X λ 1 + x } A λ A { x = 1 B A X λ 1 + A 1 + λ A + x } B λ B

x = 1 A 1 X λ 1 + x = x = 1 A 1 ( T 1 + [ λ 1 + x 1 ] [ K + 1 ] λ 1 ) = x = 1 A 1 ( T X + λ 1 K ) λ 2 , λ 3 , = 0 = ( T 1 + λ 1 K ) ( T A 1 + + λ A 1 K )

sameway x = 1 B A X λ 1 + A 1 + λ A + x = ( T A + λ 1 K + ) ( T B 1 + )

q.e.d.

4.3) { P S 1 = [ K 2 : D 2 , , K M : D M ] , P T 1 = [ K 2 D 2 + 1 , , K M D M + M 1 ] P S 1 = [ D 2 : D 2 , , D M : D M ] , P T 1 = [ K 2 D 2 + 1 , , K M D M + M 1 ] P S 1 = [ K 2 : D 2 , , K M : D M ] , P T 1 = [ 1 , , 1 ]

{ K 1 × H 1 ( P S 1 , q ) = M I N q ( P S ) , H 1 ( P S , [ K 1 D 1 , P T 1 ] , q ) = M I N q + M I N q 1 K 1 × H 2 ( P S 1 , q ) = ( 1 ) M 1 q M I N q ( P S ) K 1 × H 3 ( P S 1 , q ) = ( 1 ) q M I N q ( P S )

Example 4.1: H 1 ( q ) , H 2 ( q ) , H 3 ( q ) are equal to:

P S = [ 1 , 1 , ] , P T = [ 1 , 1 , ] { ( M q ) = E M q q + 1 ( P T , 1 ) H 2 ( M ) = 1 , H 2 ( q < M ) = 0 H 3 ( 0 ) = 1 , H 3 ( q > 0 ) = 0

P S = [ 1 , 2 , , M ] , P T = [ 1 , 2 , , M ] = { M ! ( M q ) H 2 ( M ) = M ! , H 2 ( q < M ) = 0 H 3 ( 0 ) = M ! , H 3 ( q > 0 ) = 0

P S = [ 1 , 1 , ] , P T = [ 1 , 2 , , M ] ,

M q = Euleriannumber : N M = q = 0 M 1 M q ( N + q M )

{ q ! E M q q + 1 = q ! S 2 ( M + 1 , q + 1 ) def ( 1 ) M q q ! E M q q = ( 1 ) M q q ! S 2 ( M , q ) M M 1 q = M q = E M q q + 1 ( [ 0 , 0 , ] , 1 ) = E M 1 q q + 1 ( [ 1 , 1 , ] , 1 )

2.2 ) H 1 ( M ) = q = 0 M H 3 ( q ) q = 0 M M q = M !

2.2 ) H 1 ( 1 ) = q = 0 M H 2 ( q ) q q = 0 M ( 1 ) M q q × q ! S 2 ( M , q ) = 2 M 1

P S = [ 1 , 1 , ] , P T = [ 2 , 3 , , M ]

{ ( q + 1 ) ! E M 1 q q + 1 = ( q + 1 ) ! S 2 ( M , q + 1 ) ( 1 ) M 1 q ( q + 1 ) ! E M 1 q q + 1 = ( 1 ) M 1 q ( q + 1 ) ! S 2 ( M , q + 1 ) M M 1 q = M q = E M 1 q q + 1 ( [ 1 , 1 , ] , 1 )

P S = [ 1 , 1 , ] , P T = [ 1 , 3 , , 2 M 1 ] = { E M q q + 1 ( P T , 1 ) ( 1 ) M q M I N q 1 E M q q + 1 ( [ 0 , 1 , 2 , ] , 2 )

P S = [ 1 , 1 , ] , P T = [ 3 , 5 , , 2 M 1 ] = { E M 1 q q + 1 ( P T , 1 ) ( 1 ) M 1 q M I N q E M 1 q q + 1 ( [ 2 , 3 , 4 , ] , 2 )

P S = [ 1 , 2 , , M ] ,

P T = [ 1 , 3 , , 2 M 1 ] = { M I N q + M I N q 1 def 1 × ( 1 ) M q E M q q ( [ 3 , 5 , ] , 1 ) def 1 × E q M q ( [ 2 , 3 , 4 , ] , 2 )

P S = [ 2 , 3 , , M ] ,

P T = [ 3 , 5 , , 2 M 1 ] = { M I N q def ( 1 ) M 1 q E M 1 q q + 1 ( [ 3 , 5 , ] , 1 ) def E q M q ( [ 2 , 3 , 4 , ] , 2 )

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

5. Continuity and Discontinuity

MINq appears in S U M ( N , [ 1 , 1 , ] , [ 3 , 5 , ] ) and S U M ( N , [ 2 , 3 , ] , [ 3 , 5 , ] ) . It’s easy to write out their items directly by continuity and discontinuity.

[1] has proved: q = 0 M 1 ( 1 ) M 1 q M I N q = 1 . Extand it:

2.2 ) K 1 × H 1 ( 0 ) = K 1 q = 0 M 1 H 2 ( q ) 4.3 ) = q = 0 M 1 ( 1 ) M 1 q M I N q ( P S )

5.1) q = 0 M 1 ( 1 ) M 1 q M I N q ( P S ) = K 1 i = 2 M D i

Example 5.1:

Basic Shape, M = 3:

1 × 3 × 5 ( 1 × 3 × 4 + 1 × 2 × 4 ) + 1 × 2 × 3 = 1 .

Basic Shape, M = 4:

1 × 3 × 5 × 7 ( 1 × 3 × 5 + 1 × 3 × 4 + 1 × 2 × 4 ) × 6 + ( 1 × 2 × 3 + 1 × 3 × 4 + 1 × 2 × 4 ) × 5 1 × 2 × 3 × 4 = 1.

P S = [ 5 , 10 : 10 , 2 : 3 , 3 : 10 ] :

5 × 20 × 8 × 33 ( 5 × 10 × 5 + 5 × 20 × 5 + 5 × 20 × 8 ) × 23 + ( 5 × 10 × 2 + 5 × 10 × 5 + 5 × 20 × 5 ) × 13 5 × 10 × 2 × 3 = 1500 = 5 × 10 × 3 × 10

P S = [ 1 , 1 , ] , P T = [ 2 , , M ] q = 1 M ( 1 ) M q q ! S 2 ( M , q ) = 1 .

5.2) ① M I N M 2 = 2 ( M 1 ) 3 ( 2 M 1 ) ! !

2 × M I N M 1 + M I N M 2 0 M O D ( M + 2 ) 2 , M > 3 , M is odd

[Proof]

P S = [ 2 , 3 , , M ] , P T = [ 3 , 5 , , 2 M 1 ]

H 1 ( M 2 ) = M I N M 2 = i = 1 M 1 ( X T ) × 2 i

H 2 ( M 2 ) = i = 1 M 1 ( X T ) × i = 1 2 H 1 ( M 2 )

2.1 ) H 2 ( M 2 ) = ( M 1 ) H 1 ( M 1 ) + H 1 ( M 2 )

2 × M I N M 1 + M I N M 2 = 2 ( M + 2 ) 3 × ( 2 M 1 ) ! !

q.e.d.

Example 5.2:

2 × ( 1 × 3 × 5 ) + ( 1 × 2 × 4 + 1 × 3 × 4 ) = 50 0 M O D 25

2 × ( 1 × 3 × 5 × 7 × 9 ) + ( 1 × 3 × 5 × 7 + 1 × 3 × 5 × 6 + 1 × 3 × 4 × 6 + 1 × 2 × 4 × 6 ) × 8 = 4410 0 M O D 49

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

Eg: use A for continuity, B for discontinuity

[ 1 , 2 , 3 ] = AA , [ 1 , 2 , 4 ] = AB , [ 1 , 3 , 4 ] = BA , [ 1 , 3 , 5 ] = BB .

Products of F M N + M 1 can be divided into 2 M 1 categories.

It’s easy to write them intuitively. Eg: 1 × 2 × 4 , 2 × 3 × 5 , 1 × 2 × 5 , , I 1 + 1 = I 2 , I 2 + 1 < I 3 [ 1 , 2 , 4 ] .

Each category has a simple formula 3.2 )

S U M ( N P B ( P T ) , P T , P T ) = M I N ( P T ) ( N + M T M + 1 ) .

This is the promotion of n = 0 N 1 ( n M ) = ( N M + 1 )

Traverse F M N + M 1 = S U M ( N , [ 2 , 3 , ] , [ 3 , 5 , ] ) = q = 0 M 1 M I N q ( N + M M + 1 + q ) .

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

Example 5.3:

S U M ( N , [ 1 , 1 , 1 ] , [ 1 , 3 , 5 ] ) = S U M ( N , [ 1 , 1 , 1 ] , [ 1 , 2 , 3 ] ) + S U M ( N 1 , [ 1 , 1 , 2 ] , [ 1 , 2 , 4 ] ) + S U M ( N 1 , [ 1 , 2 , 2 ] , [ 1 , 3 , 4 ] ) + S U M ( N 2 , [ 1 , 2 , 3 ] , [ 1 , 3 , 5 ] )

S U M ( N , [ 1 , 1 , 1 ] , [ 1 , 3 , 4 ] ) = S U M ( N , [ 1 , 1 , 1 ] , [ 1 , 2 , 3 ] ) + S U M ( N 1 , [ 1 , 2 , 2 ] , [ 1 , 3 , 4 ] )

The pairs of PSx and PTx compare with PS and [ 1 , 2 , , M ] , P B ( P S x ) = P B ( P T x ) , and the discontinuity at the same position. They are called having the same shape.

5.3) For Basic PT, P S 1 = [ 1 , 1 , , P S ] , P T 1 = [ 1 , 1 , , P T ] , count of 1 added = PB(PT)

H 1 ( P S 1 , P T 1 , q ) = A + B = q , P B ( P S x ) = P B ( P T x ) = A , sameshape H 1 ( P S x , P T x , B ) .

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

5.4) M I N q 0 M O D P , q > 0 , q + M = P 1

5.5) M I N q 0 M O D P , { M = P , q 0 M = P 1 , q > 0 M < P 1 , q + M P 1

[Proof]

For ③: q + M = P 1 proved by 5.4)

q + M = P : P = Max factor of M I N q holds

q + M > P : M I N q = ( Items has P ) + ( Items has no P )

( Items has no P ) = ( factors P + 1 ) × { ( factors P 1 ) }

{ ( factors P 1 ) } is a MIN that match the conditions of 5.4)

q.e.d.

5.6) P = M + 2 , ① E M N F M M + N 1 { 1 , N 1 M O D P 0 , N 1 M O D P M O D P

[Proof]

Example 4.1 E M N = q = 0 M 1 ( 1 ) M 1 q M I N q ( N + M + q N 1 ) 5.5 )

M I N 0 ( N + M N 1 ) ( P 2 ) ! ( N + P 2 N 1 ) ( P + N 2 N 1 ) M O D P

Example 4.1 F M M + N 1 = q = 0 M 1 M I N q ( N + M N 1 q ) M I N 0 ( N + P 2 P 1 ) M O D P

q.e.d.

5.7) P = M + N , ① F M M + N 1 E M N 0 M O D P , 0 < M < P 1

[Proof]

F M M + N 1 = q = 0 M 1 M I N q ( P M + 1 + q )

{ 2 M < P ( P M + 1 + q ) 0 M O D P , 0 q M 1 2 M > P , M + q P 1 5.5 ) M I N q 0 M O D P 2 M > P , M + q < P 1 ( P M + 1 + q ) 0 M O D P

q.e.d.

N + M = P def F M P 1 = ( P 1 ) F M 1 P 2 + F M P 2 ; E M N = N E M 1 N + E M N 1

(1) S 1 ( P , N ) = ( P 1 ) S 1 ( P 1 , N ) + S 1 ( P 1 , N 1 )

(2) S 2 ( P , N ) = N S 2 ( P 1 , N ) + S 2 ( P 1 , N 1 )

5.8) ① S 1 ( P 1 , q ) 1 M O D P , 1 q P 1

q ! S 2 ( P 1 , q ) ( 1 ) q + 1 M O D P , 1 q P 1

[Proof]

For ①: q = 1 , S 1 ( P 1 , q ) = 1 , holds.

If q holds, S 1 ( P , q + 1 ) 0 M O D P

S 1 ( P , q + 1 ) = ( P 1 ) S 1 ( P 1 , q + 1 ) + S 1 ( P 1 , q ) S 1 ( P 1 , q + 1 ) + 1 0 M O D P

For ②: q = 1 , q ! S 2 ( P 1 , q ) = 1 , holds.

If q holds, S 2 ( P , q + 1 ) 0 M O D P , q ! S 2 ( P , q + 1 ) 0 M O D P

q ! S 2 ( P , q + 1 ) = ( q + 1 ) ! S 2 ( P 1 , q + 1 ) + q ! S 2 ( P 1 , q ) 0 M O D P

q.e.d.

Chart of 5.6), F M M + N 1 = S 1 ( N + M , N ) , E M N = S 2 ( N + M , N )

5.9) n = 1 P 1 n P 2 0 M O D P 2 , P > 3

[Proof]

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

P P 2 + n = 1 P 1 n P 2 = n = 1 P 1 n P 2 = S U M ( P , [ 1 , , 1 ] , [ 1 , , P 2 ] ) = q = 0 P 2 q ! S 2 ( P 1 , q + 1 ) ( P q + 1 ) = q = 1 P 1 ( q 1 ) ! S 2 ( P 1 , q ) ( P q ) = q = 1 P 1 2 { ( q 1 ) ! S 2 ( P 1 , q ) ( P q ) + ( p q 1 ) ! S 2 ( P 1 , p q ) ( P p q ) }

5.8 ) q = 1 P 1 2 [ ( 1 ) q + 1 + ( 1 ) P q + 1 ] ( P q ) , this step of [1] is wrong

n = 1 P n P 2 = q = 1 P 1 ( q 1 ) ! S 2 ( P 1 , q ) ( P q ) = p q = 1 P 1 q ! S 2 ( P 1 , q ) q 2 ( P 1 q 1 ) 5.8 )

( q 1 ) ! S 2 ( P 1 , q ) ( P q ) q ! S 2 ( P 1 , q ) q 2 ( P 1 q 1 )

n = 1 P n P 2 p q = 1 P 1 ( 1 ) q + 1 q 2 ( P 1 q 1 ) ( P 1 q 1 ) ( 1 ) q 1 q = 1 P 1 1 q 2 q = 1 P 1 q 2 0 M O D P

q.e.d.

6. Coefficient Matrix

S U M ( N , P S , P T ) = q = 0 M H 1 ( q ) ( N + T M M N 1 q ) = q = 0 M H 1 ( q ) ( N + T M M T M M + 1 + q )

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

Let P = x + T M M , Q = x 1 , each row from left to right, Q is from small to large

Form 1 A 1 ( P , Q , M ) = [ ( P Q ) ( P Q M ) ( P + M Q + M ) ( P + M Q ) ]

Form 2 A 2 ( P , Q , M ) = [ ( P Q ) ( P + M Q ) ( P + M Q + M ) ( P + 2 M Q + M ) ]

Form 3 A 3 ( P , Q , M ) = [ ( P + M Q ) ( P Q M ) ( P + 2 M Q + M ) ( P + M Q ) ]

They are ( M + 1 ) × ( M + 1 ) matrices

6.1) ① A 2 ( P , Q , M ) = ( P Q ) ( P 0 ) ( P + 2 Q + 1 ) ( P + 2 1 ) ( P + 4 Q + 2 ) ( P + 4 2 ) ( P + 2 M Q + M ) ( P + 2 M M ) = A 2 ( P , P Q , M )

② Upper triangle: colq of A 2 ( 1 , 0 , M ) = [ ( q 0 ) , ( q 1 ) , ( q 2 ) , , ( q q ) , ] T

[Proof]

Row M + 1 : = Row M + 1 Row M P + M Q + M = [ 0 ( P + M + 1 Q + M ) P + M + 1 2 ( P + M + 2 Q + M ) P + M + 2 M ( P + 2 M Q + M ) P + 2 M ]

Row M : = Row M Row M 1 P + M 1 Q + M 1 = [ 0 ( P + M Q + M 1 ) P + M 2 ( P + M + 1 Q + M 1 ) P + M + 1 M ( P + 2 M 1 Q + M 1 ) P + 2 M 1 ]

Row 2 : = Row 2 Row 1 P + 1 Q + 1 = [ 0 ( P + 2 Q + 1 ) P + 2 2 ( P + 3 Q + 1 ) P + 3 M ( P + M + 1 Q + 1 ) P + M + 1 ]

Repeat the above process and change it into upper triangle.

( P Q ) ( P 0 ) ( P + 1 Q ) ( P + 1 0 ) ( P + 2 Q ) ( P + 2 0 ) ( P + 3 Q ) ( P + 3 0 ) ( P + M Q ) ( P + M 0 )

( P + 2 Q + 1 ) p + 2 1 ( P + 3 Q + 1 ) p + 3 2 ( P + 4 Q + 1 ) p + 4 3 ( P + M + 1 Q + 1 ) p + M + 1 M

( P + 4 Q + 2 ) ( p + 4 ) ( p + 3 ) 2 ! ( P + 5 Q + 2 ) ( p + 5 ) ( p + 4 ) 3 × 2 ( P + M + 2 Q + 2 ) ( p + M + 2 ) ( p + M + 1 ) M ( M 1 )

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

Row K + 1 : = Row K + 1 Row K P + K Q + K , repeat the operation K times.

q.e.d.

6.2) A 1 ( P , Q , M ) = A 2 ( P , Q , M ) = A 3 ( P , Q , M )

[Proof]

A 2 Row i + 1 : = Row i + 1 Row i and repeat change ( row 1 , col 1 ) to ( P Q )

[ ( P Q ) ( P + M Q ) ( P Q + M ) ( P + M Q + M ) ] transpose [ ( P Q ) ( P Q + M ) ( P + M Q ) ( P + M Q + M ) ] = A 1 ( P , P Q , M )

A 1 col i : = col i + col i + 1 and repeat change ( row 1 , col 1 ) to ( P + M Q ) = A 3

q.e.d.

Use A for A 1 , 2 , 3 .

6.3) A ( P , 0 , M ) = 1 ,

A ( P , 1 , M ) = ( P + M 1 + M ) , A ( P , Q > 0 , M ) = q = 0 Q 1 ( P + M q 1 + M ) ( 1 + M + q 1 + M )

[Proof]

6.1 ) A ( P , 1 , M ) = P 1 P + 1 2 P + 2 3 P + M M + 1 = ( P + M 1 + M )

q.e.d.

T M M , N [ 1 , M + 1 ] , then

Matrix of S U M ( N ) = A ( 1 + T M M , 0 , M ) , Matrix of S U M ( N ) = A ( T M M , 0 , M )

Use Cramer’s law, let y ( n ) = S U M ( N ) or S U M ( N )

H 1 ( q ) = A 1 ( P , 0 , M ) replace col q + 1 [ y ( 1 ) , , y ( M + 1 ) ] T

A 1 ( P , 0 , M ) = [ ( P 0 ) 0 ( P + M M ) ( P + M 0 ) ] = [ 1 0 ( P + M M ) 1 ]

when colq+1 replace with [ y ( 1 ) , ] T , calculate from colq+1, only { y ( 1 ) , , y ( q + 1 ) } work.

From algebraic cofactor, y(k) corresponds to 1 K 1 × A T m p × 1 M q count of rows of A T m p = ( M + 1 ) ( K 1 ) ( M q ) 1 = q K + 1

( row k , col q + 1 ) = ( P + K 1 K 1 q ) , ( q + 1 ) ( q k + 1 ) 1 = k 1

( row 0 , col 0 ) of A T m p = ( row k + 1 , col k 1 ) = ( P + K 1 )

A T m p = A 1 ( P + k , 1 , q k ) = ( P + q q + 1 k )

6.4) T M M , H 1 ( q ) = { k = 1 q + 1 ( 1 ) q + 1 + k ( 1 + T M M + q q + 1 k ) S U M ( k ) k = 1 q + 1 ( 1 ) q + 1 + k ( T M M + q q + 1 k ) S U M ( k )

S U M ( N , [ 1 , , 1 ] , [ 2 , , M ] ) = N M A 1 ( 1 , 0 , M 1 )

( q + 1 ) ! S 2 ( M , q + 1 ) = k = 1 q + 1 ( 1 ) q + 1 + k ( q + 1 q + 1 k ) k M

q ! S 2 ( M , q ) = k = 0 q ( 1 ) q + k ( q q k ) k M

x = q k q ! S 2 ( M , q ) = x = 0 q ( 1 ) x ( q x ) ( q x ) M ,

this is a known formula.

S U M ( N , [ 1 , , M ] , [ 1 , , M ] ) = ( M + N M + 1 ) ( M q ) = k = 0 q ( 1 ) k + q ( q k ) ( M + k M + 1 )

S U M ( N , [ 2 , 3 , , M ] , [ 3 , 5 , , 2 M 1 ] ) M I N q 1 = k = 0 q ( 1 ) k + q ( M + q q k ) S 1 ( k + M , k )

Similarly,

A 3 ( P , 0 , M ) = [ ( P + M 0 ) 0 ( P + 2 M M ) ( P + M 0 ) ] = [ 1 0 ( P + 2 M M ) 1 ]

y(k) corresponds to 1 K 1 × A T m p × 1 M q , count of rows of A T m p = q k + 1

( row k , col q + 1 ) = ( P + M + K 1 q K 1 q )

( row 0 , col 0 ) of A T m p = ( row k + 1 , col k 1 ) = ( P + M + 1 1 )

P + M + 1 ( q k ) = P + M + 1 q + k

A T m p = A 3 ( P + M + 1 q + K , 1 , q k ) = ( P + M + 1 q + 1 k )

6.5) T M M , H 3 ( q ) = { k = 1 q + 1 ( 1 ) q + 1 + k ( 2 + T M q + 1 k ) S U M ( k ) k = 1 q + 1 ( 1 ) q + 1 + k ( 1 + T M q + 1 k ) S U M ( k )

S U M ( N , [ 1 , , 1 ] , [ 2 , , M ] ) = N M A 3 ( 1 , 0 , M 1 )

M q = k = 1 q + 1 ( 1 ) q + k 1 ( M + 1 q + 1 k ) k M x = q + 1 k x = 0 q ( 1 ) x ( M + 1 x ) ( q + 1 x ) M

This is a known formula too.

6.1 ) A 2 ( 1 , 0 , M ) = [ ( 0 0 ) ( M 0 ) 0 ( M M ) ]

In the algebraic cofactor, ( row q + 1 , row q + 2 , , row M + 1 ) will work.

RowK corresponds to 1 q × A T m p × 1 M + 1 K count of rows of A T m p = ( M + 1 ) q ( M + 1 k ) 1 = k q 1

( row k , col q + 1 ) = ( q k 1 ) , k ( k q 1 ) = q + 1

( row 0 , col 0 ) of A T m p = ( row q + 1 , col q + 2 ) = ( q + 1 q )

A T m p = A 2 ( q + 1 , q , k q 2 ) = A 2 ( q + 1 , 1 , k q 2 ) = ( k 1 q )

It can be concluded by induction:

6.1 ) y ( k ) willchangeto z ( k ) = x = 1 k ( 1 ) k x y ( x ) ( K x )

H 2 ( q ) = k = q + 1 M + 1 ( 1 ) q + k 1 ( k 1 q ) z ( k )

S U M ( N , [ 1 , , 1 ] , [ 2 , , M ] ) = N M Z ( k ) = k ! S 2 ( M , k )

q ! S 2 ( M , q ) = k = q M ( 1 ) M + k ( k 1 q 1 ) k ! S 2 ( M , k ) , this matches 2.1)-②

7. n = 0 N 1 i = 1 M ( K i + D i q n )

We need an expression similar to ( N M ) , which is Gaussian coefficient [ N M ] q

[ N M ] q = ( q N 1 ) ( q N 1 1 ) ( q N ( M 1 ) 1 ) ( q M 1 ) ( q M 1 1 ) ( q 1 ) , q 1 , [ N 0 ] q = 1 , Abbreviated as [ N M ]

1) [ N M ] = [ N M q ]

2) [ N M ] = [ N 1 M 1 ] + q M [ N 1 M ]

7.1) ① n = 0 N 1 q n [ n + M M ] = [ N + M M + 1 ]

n = 0 N 1 q n [ n + K M ] = q M K [ N + K M + 1 ] ; n = 0 N 1 q n [ n M ] = q M [ N M + 1 ]

[Proof]

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

n = 0 N q n [ n + M M ] = [ N + M M + 1 ] + q N [ N + M M ] = ( q N + M 1 ) ( q N + M 1 1 ) ( q N 1 ) ( q M + 1 1 ) ( q M 1 ) ( q M 1 1 ) ( q 1 ) + q N ( q N + M 1 ) ( q N + M 1 1 ) ( q N + 1 1 ) ( q M 1 ) ( q M 1 1 ) ( q 1 ) = [ N + M + 1 M + 1 ]

n = 0 N 1 q n [ n + K M ] x = n + K M q M K x = 0 N 1 + K M q x [ x + M M ] = q M K [ N + K M + 1 ]

q.e.d.

n = 0 N 1 q n = q N 1 q 1 = [ N 1 ]

n = 0 N 1 q n ( K 1 + D 1 q n ) = n = 0 N 1 ( q n ( q n 1 ) D 1 + ( K 1 + D 1 ) q n ) = n = 0 N 1 ( q 1 ) q n [ N 1 ] D 1 + ( K 1 + D 1 ) q n [ N 0 ] = q ( q 1 ) D 1 [ N 2 ] + ( K 1 + D 1 ) [ N 1 ]

n = 0 N 1 q n ( K 1 + D 1 q n ) ( K 2 + D 2 q n ) = n = 0 N 1 ( D 1 D 2 q 3 n + ( K 1 D 2 + K 2 D 1 ) q 2 n + K 1 K 2 q n ) = n = 0 N 1 ( D 1 D 2 q 2 n ( q n 1 ) + ( K 1 D 2 + K 2 D 1 + D 1 D 2 ) q 2 n + K 1 K 2 q n ) = n = 0 N 1 [ D 1 D 2 q n + 1 ( q n 1 ) ( q n 1 1 ) + ( K 1 D 2 + K 2 D 1 + D 1 D 2 + q D 1 D 2 ) q n ( q n 1 ) + ( K 1 K 2 + K 1 D 2 + K 2 D 1 + D 1 D 2 ) q n ]

= D 1 D 2 q 3 ( q 2 1 ) ( q 1 ) [ N 3 ] + ( K 1 D 2 + K 2 D 1 + D 1 D 2 + q D 1 D 2 ) q ( q 1 ) [ N 2 ] + ( K 1 K 2 + K 1 D 2 + K 2 D 1 + D 1 D 2 ) [ N 1 ] = q ( q 1 ) D 1 × q 2 ( q 2 1 ) D 2 [ N 3 ] + q ( q 1 ) { ( K 1 + D 1 ) D 2 + D 1 ( K 2 + q D 2 ) } [ N 2 ] + ( K 1 + D 1 ) ( K 2 + D 2 ) [ N 1 ]

T i is arbitrary, use the Form i = 1 M ( K i + T i ) , X T = count of { X 1 , , X i } T

7.2) n = 0 N 1 q n i = 1 M ( K i + D i q n ) = g = 0 M G ( M , g ) [ N g + 1 ]

G ( M , g ) = X i with X ( T ) = g i = 1 M f ( X i )

f ( X i ) = { q X T ( q X T 1 ) D i ; X T K i + q X T 1 D i ; X K

[Proof]

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

Suppose F ( N ) = n = 0 N 1 q n i = 1 M ( K i + D i q n ) = g = 0 M G ( g ) [ N g + 1 ]

q n i = 1 M ( K i + D i q n ) = F ( n + 1 ) F ( n ) = g = 0 M G ( g ) { [ n + 1 g + 1 ] [ n g + 1 ] } = g = 0 M G ( g ) { ( q g + 1 1 ) [ n g + 1 ] + [ n g ] }

n = 0 N 1 q n i = 1 M + 1 ( K i + D i q n ) = K M + 1 n = 0 N 1 q n i = 1 M ( K i + D i q n ) + D M + 1 n = 0 N 1 q n i = 1 M + 1 ( K i + D i q n ) q n = K M + 1 g = 0 M G ( g ) [ N g + 1 ] + D M + 1 g = 0 M G ( g ) n = 0 N 1 q n { ( q g + 1 1 ) [ n g + 1 ] + [ n g ] }

7.1 ) g = 0 M G ( g ) ( K M + 1 + q g D M + 1 ) [ N g + 1 ] + g = 0 M G ( g ) q g + 1 ( q g + 1 1 ) D M + 1 [ N g + 2 ] = g = 0 M + 1 G ( M + 1 , g ) [ N g + 1 ]

q.e.d.

In the same way, use the Form = ( T 1 + K 1 ) ( T M + K M ) :

7.3) n = 0 N 1 i = 1 M ( K i + D i q n ) = g = 1 M G ( M , g ) [ N g ] + N i = 1 M K i

G ( M , g ) = X i with X ( T ) = g i = 1 M f ( X i )

f ( X i ) = { 1 ; X T , X T 1 = 0 q X T 1 ( q X T 1 1 ) D i ; X T , X T 1 > 0 K i ; X K , X T 1 = 0 K i + q X T 1 1 D i ; X K , X T 1 > 0

7.4) q M N 1 q M 1 = g = 1 M ( i = 1 g 1 q i ( q i 1 ) ) [ N g ] [ M 1 M g ]

[Proof]

n = 0 N 1 i = 1 M ( 0 + q n ) = n = 0 N 1 q M n = q M N 1 q M 1 = g = 1 M G ( M , g ) [ N g ]

In G ( M , g ) , ( X T ) = i = 1 g 1 q i ( q i 1 ) , X 1 must be T 1 , count of ( X K ) = M g , M 1 positions can be placed.

In 1916 MacMahon [6] observed that [ N K ] = w Ω ( N , K ) q i n v ( w ) , Ω ( N , K ) denotes all permutations of the multiset { 0 N K , 1 K } , that is, all words w = w 1 , , w n

with n - k zeroes and k ones, and inv(・) denotes the inversion statistic defined by i n v ( w 1 , , w n ) = | { ( i , j ) : 1 i < j n , w i > w j } | .

So in G ( M , g ) , ( X K ) = [ M 1 M g ]

q.e.d.

7.5) ① ( K + D ) M = K M + D g = 0 M 1 k g ( K + D ) M g

( K + q ) M = K M + q g = 0 M 1 k g ( K + 1 ) M 1 g + q ( q 1 ) a + b + c = M 2 , a , b , c 0 k a ( K + 1 ) b ( K + q ) c

[Proof]

n = 0 0 i = 1 M ( K + D q n ) = K M + G ( M , 1 ) [ 1 1 ]

n = 0 1 i = 1 M ( K + q n ) n = 0 0 i = 1 M ( K + q n ) = 2 K M + G ( M , 1 ) [ 2 1 ] + G ( M , 2 ) [ 2 2 ] ( K M + G ( M , 1 ) [ 1 1 ] ) = K M + G ( M , 1 ) ( q 2 1 ) ( q 1 ) + G ( M , 2 ) ( K M + G ( M , 1 ) )

q.e.d.

7.2) can be understood as use the Form = ( T 1 + K 1 ) ( T M + K M ) , P T = [ 1 , 2 , , M ]

f ( X i ) = { q T i X K 1 ( q T i X K 1 1 ) D i ; X i = T i K i + q X T 1 D i ; X i = K i

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

8. n = 0 N 1 q n ( n + M M )

8.1) n = 0 N 1 q n ( n + M M ) = q N g = 0 M ( 1 ) g ( N + M 1 g M g ) ( q 1 ) g + 1 + ( 1 ) M + 1 ( q 1 ) M + 1

[Proof]

M = 0 , n = 0 N 1 q n ( n 0 ) = q N 1 q 1 = q N ( N 1 0 ) q 1 1 q 1 , holds

M = 1 , n = 0 N 1 q n ( n + 1 1 ) = n = 0 N 1 q n ( n + 1 ) = n = 0 N 1 q n + n = 1 N 1 q n + + n = N 1 N 1 q n = N n = 0 N 1 q n ( n = 0 0 q n + n = 0 1 q n + + n = 0 N 2 q n ) = N q N 1 q 1 ( q 1 q 1 + q 2 1 q 1 + + q N 1 1 q 1 ) = N q N 1 q 1 ( 1 + q + q 2 + + q N 1 ) N q 1 = q N N q 1 q N 1 ( q 1 ) 2 = q N ( N 1 ) q 1 q N ( N 0 ) ( q 1 ) 2 + 1 ( q 1 ) 2 , holds

Suppose it holds at M − 1; When M and N = 1, n = 0 N 1 q n ( n + M M ) = 1

A = g = 0 M ( 1 ) g q N ( N + M 1 g M g ) ( q 1 ) g + 1 + ( 1 ) M + 1 ( q 1 ) M + 1 = q ( q 1 ) 1 + + ( 1 ) M q ( q 1 ) M + 1 + ( 1 ) M + 1 ( q 1 ) M + 1

( q 1 ) M + 1 A = q { ( q 1 ) M ( q 1 ) M 1 + + ( 1 ) M 1 } + ( 1 ) M + 1

7.5 ) , K = 1 = ( q 1 ) M + 1 A = 1 ; It holds when M and N = 1.

Suppose it holds at M and N

n = 0 N q n ( n + M M ) = n = 0 N q n { ( n + M 1 M ) + ( n + M 1 M 1 ) } = q n = 0 N 1 q n ( n + M M ) + n = 0 N q n ( n + M 1 M 1 ) = g = 0 M ( 1 ) g q N + 1 ( N + M 1 g M g ) ( q 1 ) g + 1 + q ( 1 ) M + 1 ( q 1 ) M + 1

+ g = 0 M 1 ( 1 ) g q N + 1 ( N + M 1 g M 1 g ) ( q 1 ) g + 1 + ( 1 ) M ( q 1 ) M = g = 0 M ( 1 ) g q N + 1 ( ( N + 1 ) + M 1 g M g ) ( q 1 ) g + 1 + ( 1 ) M + 1 ( q 1 ) M + 1

It holds when M and N + 1.

q.e.d.

Example 8.1

n = 0 N 1 q n ( n 0 ) = q N q 1 1 q 1

n = 0 N 1 q n ( n + 1 1 ) = q N ( N 1 ) q 1 q N ( q 1 ) 2 + 1 ( q 1 ) 2

n = 0 N 1 q n ( n + 2 2 ) = q N ( N + 1 2 ) q 1 q N ( N 1 ) ( q 1 ) 2 + q N ( q 1 ) 3 1 ( q 1 ) 3

8.2) n = 0 N 1 q n ( n + M K M ) = q N g = 0 M ( 1 ) g ( N K + M 1 g M g ) ( q 1 ) g + 1 + ( 1 ) M + 1 q K ( q 1 ) M + 1 , N 1 + K

[Proof]

n = 0 N 1 q n ( n + M K M ) = n = k N 1 q n ( n + M K M ) = q K n = 0 N 1 K q n ( n + M M ) = q K { q N K g = 0 M ( 1 ) g ( N K + M 1 g M g ) ( q 1 ) g + 1 + ( 1 ) M + 1 ( q 1 ) M + 1 }

q.e.d.

n = 0 N 1 q n ( n M ) = q N g = 0 M ( 1 ) g ( N 1 g M g ) ( q 1 ) g + 1 + ( 1 ) M + 1 q M ( q 1 ) M + 1 , N 1 + M

n = 0 N 1 q n ( n + M 1 M ) = q N g = 0 M ( 1 ) g ( N + M 2 g M g ) ( q 1 ) g + 1 + ( 1 ) M + 1 q ( q 1 ) M + 1 , N 2

n = 0 N 1 q n ( n 1 M ) = q N g = 0 M ( 1 ) g ( N 2 g M g ) ( q 1 ) g + 1 + ( 1 ) M + 1 q M + 1 ( q 1 ) M + 1 , N 2 + M

9. n = 0 N 1 q n n M

Define A q M = k = 0 M ( 1 q ) M k q K S 2 ( M , k ) k ! , q 0 , 1 , M 0

A 2 M = 1 , 2 , 6 , 26 , 150 , 1082 , 9366 , http://oeis.org/A000629

A 3 M = 1 , 3 , 12 , 66 , 480 , 4368 , 47712 , http://oeis.org/A123227

A 4 M = 1 , 4 , 20 , 132 , 1140 , 12324 , 160020 , http://oeis.org/A201355

A q 0 = 1 , A q 1 = q

n M = S U M ( n , [ 1 , , 1 ] [ 2 , , M ] ) Form 1 K = 0 M k ! S 2 ( M , k ) ( n K )

g ( N 1 ) M = K = g M k ! S 2 ( M , k ) ( N 1 g K g ) .

9.1) n = 0 N 1 q n n M = q N ( q 1 ) M + 1 g = 0 M ( q 1 ) M g ( 1 ) g g ( N 1 ) M + ( 1 ) M + 1 A q M ( q 1 ) M + 1

[Proof]

n = 0 N 1 q n n 0 = q N q 1 1 q 1 , holds

n = 0 N 1 q n n 1 = n = 0 N 1 q n ( n 1 ) = q N g = 0 1 ( 1 ) g ( N 1 g 1 g ) ( q 1 ) g + 1 + q ( q 1 ) 2 = q N ( N 1 ) ( q 1 ) 1 q N ( q 1 ) 2 + q ( q 1 ) 2 = q N ( q 1 ) 2 ( ( q 1 ) ( N 1 ) 1 1 ) + A q 1 ( q 1 ) 2 , holds

n = 0 N 1 q n n M = n = 0 N 1 q n K = 0 M k ! S 2 ( M , k ) ( n K ) = K = 0 M K ! S 2 ( M , K ) { q N g = 0 k ( 1 ) g ( N 1 g k g ) ( q 1 ) g + 1 + ( 1 ) k + 1 q k ( q 1 ) k + 1 }

K = 0 M K ! S 2 ( M , K ) q k ( 1 ) K + 1 ( q 1 ) K + 1 = ( 1 ) M + 1 ( q 1 ) M + 1 K = 0 M K ! S 2 ( M , K ) q k ( q 1 ) M K ( 1 ) ( M K ) = ( 1 ) M + 1 A q M ( q 1 ) M + 1

K = 0 M K ! S 2 ( M , K ) q N g = 0 k ( 1 ) g ( N 1 g k g ) ( q 1 ) g + 1 = q N ( ... ) ( q 1 ) M + 1 = q N ( q 1 ) M + 1 K = 0 M k ! S 2 ( M , k ) g = 0 k ( 1 ) g ( N 1 g K g ) ( q 1 ) M g

( ... ) = K ! S 2 ( M , M ) { ( N 1 M ) ( q 1 ) M ( N 2 M 1 ) ( q 1 ) M 1 + + ( 1 ) M ( N 1 M 0 ) } + K ! S 2 ( M , M 1 ) { ( N 1 M 1 ) ( q 1 ) M ( N 2 M 2 ) ( q 1 ) M 1 + } + + K ! S 2 ( M , 0 ) { ( N 1 0 ) ( q 1 ) M }

Verticalcalculation = ( q 1 ) M 0 ( N 1 ) M ( q 1 ) M 1 1 ( N 1 ) M

q.e.d.

9.2) A q M = q k = 0 M ( q 1 ) M k S 2 ( M , k ) k ! , M > 0

[Proof]

n M = S U M ( n , [ 1 , , 1 ] [ 1 , , M ] ) Form 2 K = 0 M ( 1 ) M K K ! S 2 ( M , K ) ( n + K 1 K )

n = 0 N 1 q n n M = n = 0 N 1 q n K = 0 M ( 1 ) M K K ! S 2 ( M , K ) ( n + K 1 K ) = K = 0 M ( 1 ) M K K ! S 2 ( M , K ) { q N g = 0 K ( 1 ) g ( N + K 2 g K g ) ( q 1 ) g + 1 + ( 1 ) K + 1 q ( q 1 ) K + 1 }

K = 0 M ( 1 ) M K K ! S 2 ( M , K ) g = 0 K ( 1 ) g q N ( N + K 2 g K g ) ( q 1 ) g + 1 Samewayas 9.1 ) = q N ( q 1 ) M + 1 g = 0 M ( q 1 ) M g ( 1 ) g g ( N 1 ) M

Compare with 9.1) K = 0 M ( 1 ) M K K ! S 2 ( M , K ) ( 1 ) K + 1 q ( q 1 ) K + 1 = ( 1 ) M + 1 A q M ( q 1 ) M + 1

q.e.d.

n M = S U M ( n , [ 1 , , 1 ] [ 1 , , M ] ) Form 1 K = 0 M k ! S 2 ( M + 1 , k + 1 ) ( n 1 K )

9.3) A q M = k = 0 M ( 1 q ) M k q K + 1 S 2 ( M + 1 , k + 1 ) k ! , M > 0

9.4) g ( N 1 ) M = k = 0 M g ( 1 ) M g k ( M k ) N K S 2 ( M K + 1 , g + 1 ) g !

[Proof]

S 2 ( M , g ) = 1 g ! k = 0 g ( 1 ) k ( g k ) ( g k ) M j = g k = 1 g ! j = 0 g ( 1 ) g j ( g j ) j M = 1 ( g 1 ) ! j = 1 g ( 1 ) g j ( g 1 j 1 ) j M 1 = 1 ( g 1 ) ! j = 0 g 1 ( 1 ) g 1 j ( g 1 j ) ( j + 1 ) M 1

g ( N 1 ) M Bydefinition j = 0 g ( 1 ) j ( g j ) ( N j 1 ) M = j = 0 g ( 1 ) j ( g j ) K = 0 M ( M k ) N k ( j + 1 ) M k ( 1 ) M K = k = 0 M ( 1 ) M k ( M k ) N k ( j = 0 g ( 1 ) j ( g j ) ( j + 1 ) M K ) = k = 0 M ( 1 ) M k g ( M k ) N k ( j = 0 g ( 1 ) g + j ( g j ) ( j + 1 ) M K ) = k = 0 M ( 1 ) M k g ( M k ) N K S 2 ( M K + 1 , g + 1 ) g !

q.e.d.

9.5) ① A q M = k = 0 M ( q 1 ) M k S 2 ( M + 1 , k + 1 ) k !

n = 0 N 1 q n n M = q N ( q 1 ) M + 1 g = 0 M ( 1 ) M g A q M g ( M g ) ( q 1 ) g N g + ( 1 ) M + 1 A q M ( q 1 ) M + 1

[Proof]

f ( N ) = n = 0 N 1 q n n M = q N ( q 1 ) M + 1 { } + ( 1 ) M + 1 A q M ( q 1 ) M + 1 = q N ( q 1 ) M + 1 { g = 0 M ( q 1 ) M g ( 1 ) g g ( N 1 ) M } + ( 1 ) M + 1 A q M ( q 1 ) M + 1

{ } 9.4 ) = g = 0 M ( q 1 ) M g ( 1 ) g k = 0 M g ( 1 ) M g k ( M k ) N K S 2 ( M K + 1 , g + 1 ) g ! = g = 0 M ( q 1 ) M g k = 0 M g ( 1 ) M k ( M k ) N K S 2 ( M K + 1 , g + 1 ) g ! = ( q 1 ) M { ( 1 ) M ( M 0 ) N 0 S 2 ( M + 1 , 1 ) 0 ! + ( 1 ) M 1 ( M 1 ) N 1 S 2 ( M , 1 ) 0 ! + } + ( q 1 ) M 1 { ( 1 ) M ( M 0 ) N 0 S 2 ( M + 1 , 2 ) 1 ! + ( 1 ) M 1 ( M 1 ) N 1 S 2 ( M , 2 ) 1 ! + } + + ( q 1 ) 0 { ( 1 ) M ( M 0 ) N 0 S 2 ( M + 1 , M + 1 ) M ! }

Arrange by Ng

= g = 0 M ( q 1 ) g N g ( M g ) ( 1 ) M g k = 0 M g ( q 1 ) M g k S 2 ( M g + 1 , k + 1 ) k !

take