Back
 OALibJ  Vol.7 No.6 , June 2020
Generalization of Stirling Number of the Second Kind and Combinatorial Identity
Abstract: The Stirling numbers of second kind and related problems are widely used in combinatorial mathematics and number theory, and there are a lot of research results. This article discuss the function: ∑AC11 AC22 ···ACkk (C1+C2+···+Ck=N-K, Ci≥0), obtain its calculation formula and a series of conclusions, which generalize the results of existing literature, and further obtain the combinatorial identity: ∑(-1)K-i*C(K-1,K-i)C(A-1+i,N-1)=C(A,N-K).

1. Introduction

Stirling number of the second kind S 2 ( n , K ) [1] is defined as

t N = k = 0 N S 2 ( N , k ) [ t ] k (1*)

It has attributes:

[1] S 2 ( N , K ) = 1 C 1 2 C 2 K C k ( C 1 + C 2 + + C K = N K , C i 0 ) (2*)

[1] S 2 ( N , K ) = 1 K ! i = 0 K 1 ( 1 ) i ( K i ) ( K i ) N (3*)

Let j = K i S 2 ( N , K ) = 1 ( K 1 ) ! j = 1 K ( 1 ) K j ( K 1 K j ) j N 1 (4*)

It is similar to the expansion of

( X Y ) N 1 (5*)

S 2 ( 0 , 0 ) = 1 , S 2 ( N , 0 ) = 0 ( N > 0 )

S 2 ( N , 1 ) = 1

S 2 ( N , 2 ) = ( 2 N 1 1 N 1 ) / 1 !

S 2 ( N , 3 ) = ( 3 N 1 2 2 N 1 + 1 N 1 ) / 2 !

S 2 ( N , 4 ) = ( 4 N 1 3 3 N 1 + 3 2 N 1 1 N 1 ) / 3 !

S 2 ( N , 5 ) = ( 5 N 1 4 4 N 1 + 6 3 N 1 4 2 N 1 + 1 N 1 ) / 4 !

S 2 ( N , 6 ) = ( 6 N 1 5 5 N 1 + 10 4 N 1 10 3 N 1 + 5 2 N 1 1 N 1 ) / 5 !

S 2 ( N , N 1 ) = ( N 2 ) (6*)

2. Main Conclusion and Proof

Definition: The generalization of Stirling number of the second kind

If { a } = { A 1 , A 2 , , A k } , A , A i < A j , ( i < j ), then

G ( N , K , { a } ) = A 1 C 1 A 2 C 2 A k C k ( C 1 + C 2 + + C K = N K , C i 0 )

G 1 ( N , K , A ) = G ( N , K , { A , A + 1 , , A + K 1 } ) S 2 ( N , K ) = G 1 ( N , K , 1 )

The function has been discussed by many papers [2] [3] [4], including definition, recursive relation, generating function and so on. This article will not narrate.

1) G ( N , K , { a } ) = G ( N 1 , K 1 , { A 1 , , A k 1 } ) + A k G ( N 1 , K , { a } ) = G ( N 1 , K 1 , { A 2 , , A k } ) + A 1 G ( N 1 , K , { a } )

Proof: By definition.

The first equation corresponds to S 2 ( n , K ) = S 2 ( n 1 , k 1 ) + k S 2 ( n 1 , K ) .

2) G ( N , K , { a } ) = G ( N , K 1 , { A 2 , , A k } ) G ( N , K 1 , { A 1 , , A k 1 } ) A k A 1

Proof: From the second equation of 1).

3) G ( N , 1 , { A } ) = A N 1 , corresponds to S 2 ( N , 1 ) = 1

4) G ( N , 2 , { A 1 , A 2 } ) = A 2 N 1 A 1 N 1 A 2 A 1 = A 1 N 1 A 1 A 2 + A 2 N 1 A 2 A 1 , corresponds to

S 2 ( N , 2 ) = 2 N 1 1 = 2 N 1 1 N 1 .

Proof: G ( N , 2 , { A 1 , A 2 } ) = A 1 N 2 + A 1 N 3 A 2 + + A 2 N 2 .

5) G ( N , K , { a } ) = i = 1 K ( A i ) N 1 i j ( A i A j ) , this is the calculation formula.

Proof: Induce by 2), 3), 4).

The form is symmetrical, for example:

G ( N , 3 , { a } ) = A 1 N 1 ( A 1 A 2 ) ( A 1 A 3 ) + A 2 N 1 ( A 2 A 1 ) ( A 2 A 3 ) + A 3 N 1 ( A 3 A 1 ) ( A 3 A 2 )

[2] obtains it by generating function.

Lemma 1: if {a} is an equal difference sequence { A , A + d , , A + ( K 1 ) d } ,

1 i = m , i j ( A i A j ) = ( 1 ) K m d K 1 ( K 1 ) ! ( K 1 K m ) .

Proof: 1 i = m , i j ( A i A j ) = 1 i = m , j < m ( A i A j ) 1 i = m , j > m ( A i A j ) = 1 d K 1 1 ( m 1 ) ! ( 1 ) K m ( K m ) ! = ( 1 ) K m ( K 1 ) ! d K 1 ( K 1 ) ! ( m 1 ) ! ( k m ) ! = ( 1 ) K m d K 1 ( K 1 ) ! ( K 1 K m )

6) If { a } = { A , A + d , , A + ( K 1 ) d } ,

G ( N , K , { a } ) = 1 d K 1 ( K 1 ) ! j = 1 K ( 1 ) K j ( K 1 K j ) A j N 1 .

Proof: By 5) and Lemma 1.

It is similar to the expansion of ( X Y ) N 1 , in particular:

7) G 1 ( N , K , A ) = 1 ( K 1 ) ! i = 1 K ( 1 ) K i ( K 1 K i ) ( A 1 + i ) N 1 similar to (4*), (5*)

8) G 1 ( N , K , 1 ) = S 2 ( N , K ) = 1 ( K 1 ) ! i = 1 K ( 1 ) K i ( K 1 K i ) i N 1 equal to (4*), (5*)

9) G ( N , K , { d , 2 d , , K d } ) = d N K ( K 1 ) ! i = 1 K ( 1 ) K i ( K 1 K i ) i N 1 = d N K S 2 ( N , K )

10) G 1 ( K + 1 , K , A ) = A + ( A + 1 ) + + ( A + K 1 ) = K A + ( K 2 ) corresponds to (6*)

Theorem 1: G 1 ( N < K , K , { a } ) = 0 ; G 1 ( K , K , { a } ) = 1 .

Proof:

7) G 1 ( 1 , K 1 , A ) = 1 ( K 1 ) ! i = 1 K ( 1 ) K i ( K 1 K i ) = 0

4) G 1 ( 2 , 2 , A ) = 1

Suppose G 1 ( X , K 1 , A ) match the theorem:

3) G 1 ( N < K 1 , K , A ) = G 1 ( N , K 1 , { A 2 , , A k } ) G 1 ( N , K 1 , { A 1 , , A k 1 } ) A k A 1 = 0 0 K 1 = 0

G 1 ( N = K 1 , K , A ) = G 1 ( N , K 1 , { A 2 , , A k } ) G 1 ( N , K 1 , { A 1 , , A k 1 } ) A k A 1 = 1 1 K 1 = 0

G 1 ( N = K , K , A ) = G 1 ( N , K 1 { A 2 , , A k } ) G 1 ( N , K 1 , { A 1 , , A k 1 } ) A k A 1 = ( K 1 ) ( A + 1 ) + ( K 2 ) ( K 1 ) A ( K 2 ) K 1 = 1

Induction proved.

q.e.d.

The theorem verify the definition, A can be any integer.

Definition: A Z , G 2 ( N , K , A ) = i = 1 K ( 1 ) K i ( K 1 K i ) ( A 1 + i N 1 )

Theorem 2: G 2 ( N + K , K , A ) = ( A N )

Proof:

Let F ( N ) = ( N 1 ) ! G 2 ( N , K , A ) = i = 1 K ( 1 ) K i ( K 1 K i ) [ A 1 + i ] N 1 .

Substitution (1*) to 7), use Theorem 1:

G 1 ( 1 , K , A ) = 0 , K > 1 F ( 1 ) = 0 G 2 ( 1 , K > 1 , A ) = 0

G 1 ( 2 , K , A ) = 0 , K > 2 , F ( 1 ) = 0 F ( 2 ) = 0 G 2 ( 2 , K > 2 , A ) = 0

G 1 ( K , K , { a } ) = 1 F ( K ) = ( K 1 ) ! G 2 ( K , K , A ) = 1 = ( A 0 )

10)

G 1 ( 1 + K , K , A ) = K A + ( K 2 ) = S 2 ( K , K ) F ( K + 1 ) + S 2 ( K , K 1 ) F ( K ) ( K 1 ) !

F ( 1 + K ) = A K ! G 2 ( 1 + K , K , A ) = A = ( A 1 )

( A N + 1 ) = ( A 1 N ) + ( A 1 N + 1 )

G 2 ( N + 1 + K , K , A ) = G 2 ( N + K , K , A 1 ) + G 2 ( N + 1 + K , K , A 1 )

G 2 ( N + K , K , A ) = ( A N )

q.e.d.

Record in [5]:

k = 0 m 1 ( 1 ) k ( m k ) ( m + n k 1 n ) = ( n 1 m 1 ) (**)

Let A = n 1 , m = K − 1, i = K − k left = i = 0 K ( 1 ) K i ( K 1 K i ) ( A 1 + i A + 1 ) .

Let K + N 1 = A + 1

left = i = 0 K ( 1 ) K i ( K 1 K i ) ( A 1 + i K + N 1 ) = ( n 1 m 1 ) = ( A A N ) = ( A N ) .

(**) has 2 variables (m, n), it is G 2 ( K + A + 2 , K , A ) actually.

Theorem 2 has 3 variables, is promotion of (**).

11) G 2 ( N + K , K , A ) : The Inclusion-Exclusion Principle.

G 2 ( N + K , K , A ) = ( A N ) is independent of K.

Choice N from A, one way is:

( A N ) = ( A 1 N 1 ) + ( A 1 N ) = ( A 1 N 1 ) + ( A 2 N 1 ) + + ( N 1 N 1 )

Another way is: ( A N ) = ( A + 1 N + 1 ) ( A N + 1 ) = G 2 ( N + 2 , 2 , A ) = { ( A + 2 N + 2 ) ( A + 1 N + 2 ) } { ( A + 1 N + 2 ) ( A N + 2 ) } = G 2 ( N + 3 , 3 , A )

12) G ( N + K , K , { a } ) ( A i ) G ( N + K 1 , K , { a } ) + ( A i A j ) G ( N + K 1 , K , { a } ) + + ( 1 ) K ( A 1 A 2 A k ) G ( N , K , { a } ) = 0

Proof:

0 = G 1 ( N , 0 , { a } ) = G ( N + 1 , 1 , { a } ) A 1 G ( N , 1 , { a } ) = { G ( N + 2 , 2 , A ) A 2 G 1 ( N + 1 , 2 , A ) } A 1 { G ( N + 1 , 2 , A ) A 2 G 1 ( N , 2 , A ) } = G ( N + 2 , 2 , A ) ( A 1 + A 2 ) G 1 ( N + 1 , 2 , A ) + A 1 A 2 G 1 ( N , 2 , A )

Induction proved.

q.e.d.

This is similar to the Inclusion-Exclusion Principle,in particular:

13) S 2 ( N , K ) S 1 ( K + 1 , K ) S 2 ( N 1 , K ) + + ( 1 ) K S 1 ( K + 1 , 1 ) S 2 ( N K , K ) = 0

S1 is unsigned Stirling number of the first kind.

14) G 1 ( N , K , A ) = t = K 1 N 1 S 2 ( N 1 , t ) ( A t + 1 K ) [ K ] t + 1 K

Proof:

Substitution (1*) to 7), use Theorem 2:

G 1 ( N , K , A ) = 1 ( K 1 ) ! i = 1 K ( 1 ) K i ( K 1 K i ) ( A 1 + i ) N 1 = 1 ( K 1 ) ! i = 1 K ( 1 ) K i ( K 1 K i ) t = 0 N 1 S 2 ( N 1 , t ) [ A 1 + i ] t = t = 0 N 1 S 2 ( N 1 , t ) i = 1 K ( 1 ) K i ( K 1 K i ) ( A 1 + i t ) t ! ( K 1 ) ! = t = 0 N 1 S 2 ( N 1 , t ) G 2 ( t + 1 , K , A ) [ K ] t + 1 K = t = 0 N 1 S 2 ( N 1 , t ) ( A t + 1 K ) [ K ] t + 1 K

q.e.d.

S 2 ( N , K ) = G 1 ( N , K , 1 ) = K S 2 ( N 1 , K ) + S 2 ( N 1 , K 1 )

3. Conclusions

This paper starting from (4*), (5*), discusses the problems from different perspectives.

The introduced function has good characteristics, can be further studied.

Cite this paper: Peng, J. (2020) Generalization of Stirling Number of the Second Kind and Combinatorial Identity. Open Access Library Journal, 7, 1-6. doi: 10.4236/oalib.1106462.
References

[1]   Hardy, G.H. (2010) An Introduction to the Theory of Numbers. 6th Edition. Zhang, F. Translation. People’s Post and Telecommunications Press, Beijing.

[2]   Li, C.X. (1995) The Expression of Stirling Number of the Second Kind and Others. Journal of Hubei Normal University: Philosophy and Social Sciences, 6, 72-76.

[3]   Huang, R.H. and Chen, B.E. (2011) Some Conclusions on the Generalized Stirling Number of the Second Kind. Journal of Hanshan Normal University, 3, 29-31.

[4]   Zhang, F.L. (2011) An Identity of Stirling Numbers of the Second Kind. Journal of Weinan Teachers College, 12, 14-16.

[5]   Editorial Board of Handbook of Modern Applied Mathematics (2002) Handbook of Modern Applied Mathematics Discrete Mathematics Volume. Tsinghua University Press, Beijing.

 
 
Top