Generalization of Stirling Number of the Second Kind and Combinatorial Identity

Ji Peng

Department of Electronic Information, Nanjing University, Nanjing, China.

DOI: 10.4236/oalib.1106462                

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).

Keywords

Combinatorics, Combinatorial Identity, Stirling Numbers, Calculation Formula

1. Introduction

Stirling number of the second kind $S_2\left(n,K\right)$ [1] is defined as

$t^N={\displaystyle {\sum }_{k=0}^N{S}_2\left(N,k\right){\left[t\right]}_k}$ (1*)

It has attributes:

[1] $S_2\left(N,K\right)={\displaystyle \sum 1^{C_1}{2}^{C_2}\cdots K^{C_k}}$ ( $C_1+C_2+\cdots +C_K=N-K$, $C_i\ge 0$ ) (2*)

[1] $S_2\left(N,K\right)=\frac{1}{K!}{\displaystyle {\sum }_{i=0}^{K-1}{\left(-1\right)}^i}\left(\begin{array}{c}K\\ i\end{array}\right){\left(K-i\right)}^N$ (3*)

Let $j=K-i$ $\to$ $S_2\left(N,K\right)=\frac{1}{\left(K-1\right)!}{\displaystyle {\sum }_{j=1}^K{\left(-1\right)}^{K-j}}\left(\begin{array}{c}K-1\\ K-j\end{array}\right)j^{N-1}$ (4*)

It is similar to the expansion of

${\left(X-Y\right)}^{N-1}$ (5*)

$S_2\left(0,0\right)=1$, $S_2\left(N,0\right)=0$ ( $N>0$ )

$S_2\left(N,1\right)=1$

$S_2\left(N,2\right)=\left(2^{N-1}-1^{N-1}\right)/1!$

$S_2\left(N,3\right)=\left(3^{N-1}-2\ast 2^{N-1}+1^{N-1}\right)/2!$

$S_2\left(N,4\right)=\left(4^{N-1}-3\ast 3^{N-1}+3\ast 2^{N-1}-1^{N-1}\right)/3!$

$S_2\left(N,5\right)=\left(5^{N-1}-4\ast 4^{N-1}+6\ast 3^{N-1}-4\ast 2^{N-1}+1^{N-1}\right)/4!$

$S_2\left(N,6\right)=\left(6^{N-1}-5\ast 5^{N-1}+10\ast 4^{N-1}-10\ast 3^{N-1}+5\ast 2^{N-1}-1^{N-1}\right)/5!$

$S_2\left(N,N-1\right)=\left(\begin{array}{c}N\\ 2\end{array}\right)$ (6*)

2. Main Conclusion and Proof

Definition: The generalization of Stirling number of the second kind

If $\left\{a\right\}=\left\{A_1,A_2,\cdots ,A_k\right\}$, $A\in \mathbb{Z}$, $A_i<A_j$, ( $i<j$ ), then

$G\left(N,K,\left\{a\right\}\right)={\displaystyle \sum A_1^{C_1}{A}_2^{C_2}\cdots A_k^{C_k}}$ ( $C_1+C_2+\cdots +C_K=N-K$, $C_i\ge 0$ )

$G_1\left(N,K,A\right)=G\left(N,K,\left\{A,A+1,\cdots ,A+K-1\right\}\right)$ $\to$ $S_2\left(N,K\right)=G_1\left(N,K,1\right)$

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) $\begin{array}{c}G\left(N,K,\left\{a\right\}\right)=G\left(N-1,K-1,\left\{A_1,\cdots ,A_{k-1}\right\}\right)+A_k\ast G\left(N-1,K,\left\{a\right\}\right)\\ =G\left(N-1,K-1,\left\{A_2,\cdots ,A_k\right\}\right)+A_1\ast G\left(N-1,K,\left\{a\right\}\right)\end{array}$

Proof: By definition.

The first equation corresponds to $S_2\left(n,K\right)=S_2\left(n-1,k-1\right)+k\ast S_2\left(n-1,K\right)$.

2) $G\left(N,K,\left\{a\right\}\right)=\frac{G\left(N,K-1,\left\{A_2,\cdots ,A_k\right\}\right)-G\left(N,K-1,\left\{A_1,\cdots ,A_{k-1}\right\}\right)}{A_k-A_1}$

Proof: From the second equation of 1).

3) $G\left(N,1,\left\{A\right\}\right)=A^{N-1}$, corresponds to $S_2\left(N,1\right)=1$

4) $G\left(N,2,\left\{A_1,A_2\right\}\right)=\frac{A_2^{N-1}-A_1^{N-1}}{A_2-A_1}=\frac{A_1^{N-1}}{A_1-A_2}+\frac{A_2^{N-1}}{A_2-A_1}$, corresponds to

$S_2\left(N,2\right)=2^{N-1}-1=2^{N-1}-1^{N-1}$.

Proof: $G\left(N,2,\left\{A_1,A_2\right\}\right)=A_1^{N-2}+A_1^{N-3}{A}_2+\cdots +A_2^{N-2}$.

5) $G\left(N,K,\left\{a\right\}\right)={\displaystyle {\sum }_{i=1}^K\frac{{\left(A_i\right)}^{N-1}}{{{\displaystyle \prod }}_{i\ne j}\left(A_i-A_j\right)}}$, this is the calculation formula.

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

The form is symmetrical, for example:

$G\left(N,3,\left\{a\right\}\right)=\frac{A_1^{N-1}}{\left(A_1-A_2\right)\left(A_1-A_3\right)}+\frac{A_2^{N-1}}{\left(A_2-A_1\right)\left(A_2-A_3\right)}+\frac{A_3^{N-1}}{\left(A_3-A_1\right)\left(A_3-A_2\right)}$

[2] obtains it by generating function.

Lemma 1: if {a} is an equal difference sequence $\left\{A,A+d,\cdots ,A+\left(K-1\right)d\right\}$,

$\frac{1}{{{\displaystyle \prod }}_{i=m,i\ne j}\left(A_i-A_j\right)}=\frac{{\left(-1\right)}^{K-m}}{d^{K-1}\left(K-1\right)!}\left(\begin{array}{c}K-1\\ K-m\end{array}\right)$.

Proof: $\begin{array}{c}\frac{1}{{{\displaystyle \prod }}_{i=m,i\ne j}\left(A_i-A_j\right)}=\frac{1}{{{\displaystyle \prod }}_{i=m,j<m}\left(A_i-A_j\right)}\frac{1}{{{\displaystyle \prod }}_{i=m,j>m}\left(A_i-A_j\right)}\\ =\frac{1}{d^{K-1}}\frac{1}{\left(m-1\right)!}\frac{{\left(-1\right)}^{K-m}}{\left(K-m\right)!}\\ =\frac{{\left(-1\right)}^{K-m}\left(K-1\right)!}{d^{K-1}\left(K-1\right)!\left(m-1\right)!\left(k-m\right)!}\\ =\frac{{\left(-1\right)}^{K-m}}{d^{K-1}\left(K-1\right)!}\left(\begin{array}{c}K-1\\ K-m\end{array}\right)\end{array}$

6) If $\left\{a\right\}=\left\{A,A+d,\cdots ,A+\left(K-1\right)d\right\}$,

$G\left(N,K,\left\{a\right\}\right)=\frac{1}{d^{K-1}\left(K-1\right)!}{\displaystyle {\sum }_{j=1}^K{\left(-1\right)}^{K-j}}\left(\begin{array}{c}K-1\\ K-j\end{array}\right)A_j^{N-1}$.

Proof: By 5) and Lemma 1.

It is similar to the expansion of ${\left(X-Y\right)}^{N-1}$, in particular:

7) $G1\left(N,K,A\right)=\frac{1}{\left(K-1\right)!}{\displaystyle {\sum }_{i=1}^K{\left(-1\right)}^{K-i}}\left(\begin{array}{c}K-1\\ K-i\end{array}\right){\left(A-1+i\right)}^{N-1}$ similar to (4*), (5*)

8) $G_1\left(N,K,1\right)=S_2\left(N,K\right)=\frac{1}{\left(K-1\right)!}{\displaystyle {\sum }_{i=1}^K{\left(-1\right)}^{K-i}}\left(\begin{array}{c}K-1\\ K-i\end{array}\right)i^{N-1}$ equal to (4*), (5*)

9) $G\left(N,K,\left\{d,2d,\cdots ,Kd\right\}\right)=\frac{d^{N-K}}{\left(K-1\right)!}{\displaystyle {\sum }_{i=1}^K{\left(-1\right)}^{K-i}}\left(\begin{array}{c}K-1\\ K-i\end{array}\right)i^{N-1}=d^{N-K}{S}_2\left(N,K\right)$

10) $G_1\left(K+1,K,A\right)=A+\left(A+1\right)+\cdots +\left(A+K-1\right)=K\ast A+\left(\begin{array}{c}K\\ 2\end{array}\right)$ corresponds to (6*)

Theorem 1: $G_1\left(N<K,K,\left\{a\right\}\right)=0$ ; $G_1\left(K,K,\left\{a\right\}\right)=1$.

Proof:

7) $\to$ $G_1\left(1,K\ge 1,A\right)=\frac{1}{\left(K-1\right)!}{\displaystyle {\sum }_{i=1}^K{\left(-1\right)}^{K-i}}\left(\begin{array}{c}K-1\\ K-i\end{array}\right)=0$

4) $\to$ $G_1\left(2,2,A\right)=1$

Suppose $G_1\left(X,K-1,A\right)$ match the theorem:

3) $\to$ $\begin{array}{l}{G}_1\left(N<K-1,K,A\right)\\ =\frac{G_1\left(N,K-1,\left\{A_2,\cdots ,A_k\right\}\right)-G_1\left(N,K-1,\left\{A_1,\cdots ,A_{k-1}\right\}\right)}{A_k-A_1}=\frac{0-0}{K-1}=0\end{array}$

$\begin{array}{l}{G}_1\left(N=K-1,K,A\right)\\ =\frac{G_1\left(N,K-1,\left\{A_2,\cdots ,A_k\right\}\right)-G_1\left(N,K-1,\left\{A_1,\cdots ,A_{k-1}\right\}\right)}{A_k-A_1}=\frac{1-1}{K-1}=0\end{array}$

$\begin{array}{c}{G}_1\left(N=K,K,A\right)\\ =\frac{G_1\left(N,K-1\left\{A_2,\cdots ,A_k\right\}\right)-G_1\left(N,K-1,\left\{A_1,\cdots ,A_{k-1}\right\}\right)}{A_k-A_1}\\ =\frac{\left(K-1\right)\left(A+1\right)+\left(\begin{array}{c}K\\ 2\end{array}\right)-\left(K-1\right)\ast A-\left(\begin{array}{c}K\\ 2\end{array}\right)}{K-1}=1\end{array}$

Induction proved.

q.e.d.

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

Definition: $A\in Z$, $G_2\left(N,K,A\right)={\displaystyle {\sum }_{i=1}^K{\left(-1\right)}^{K-i}\left(\begin{array}{c}K-1\\ K-i\end{array}\right)\left(\begin{array}{c}A-1+i\\ N-1\end{array}\right)}$

Theorem 2: $G_2\left(N+K,K,A\right)=(\; A\; N\; )$

Proof:

Let $F\left(N\right)=\left(N-1\right)!G_2\left(N,K,A\right)={\displaystyle {\sum }_{i=1}^K{\left(-1\right)}^{K-i}\left(\begin{array}{c}K-1\\ K-i\end{array}\right){\left[A-1+i\right]}_{N-1}}$.

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

$G_1\left(1,K,A\right)=0,K>1$ $\to$ $F\left(1\right)=0$ $\to$ $G_2\left(1,K>1,A\right)=0$

$G_1\left(2,K,A\right)=0,K>2,F\left(1\right)=0$ $\to$ $F\left(2\right)=0$ $\to$ $G_2\left(2,K>2,A\right)=0$

…

$G_1\left(K,K,\left\{a\right\}\right)=1$ $\to$ $F\left(K\right)=\left(K-1\right)!$ $\to$ $G_2\left(K,K,A\right)=1=(\; A\; 0\; )$

10) $\to$

$G_1\left(1+K,K,A\right)=K\ast A+\left(\begin{array}{c}K\\ 2\end{array}\right)=\frac{S_2\left(K,K\right)F\left(K+1\right)+S_2\left(K,K-1\right)F\left(K\right)}{\left(K-1\right)!}$ $\to$

$F\left(1+K\right)=A\ast K!$ $\to$ $G_2\left(1+K,K,A\right)=A=(\; A\; 1\; )$

$\left(\begin{array}{c}A\\ N+1\end{array}\right)=\left(\begin{array}{c}A-1\\ N\end{array}\right)+\left(\begin{array}{c}A-1\\ N+1\end{array}\right)$ $\to$

$G_2\left(N+1+K,K,A\right)=G_2\left(N+K,K,A-1\right)+G_2\left(N+1+K,K,A-1\right)$ $\to$

$G_2\left(N+K,K,A\right)=(\; A\; N\; )$

q.e.d.

Record in [5]:

${\displaystyle {\sum }_{k=0}^{m-1}{\left(-1\right)}^k}\left(\begin{array}{c}m\\ k\end{array}\right)\left(\begin{array}{c}m+n-k-1\\ n\end{array}\right)=\left(\begin{array}{c}n-1\\ m-1\end{array}\right)$ (**)

Let $A=n-1$, m = K − 1, i = K − k $\to$ $\text{left}={\displaystyle {\sum }_{i=0}^K{\left(-1\right)}^{K-i}\left(\begin{array}{c}K-1\\ K-i\end{array}\right)\left(\begin{array}{c}A-1+i\\ A+1\end{array}\right)}$.

Let $K+N-1=A+1$ $\to$

$\text{left}={\displaystyle {\sum }_{i=0}^K{\left(-1\right)}^{K-i}}\left(\begin{array}{c}K-1\\ K-i\end{array}\right)\left(\begin{array}{c}A-1+i\\ K+N-1\end{array}\right)=\left(\begin{array}{c}n-1\\ m-1\end{array}\right)=\left(\begin{array}{c}A\\ A-N\end{array}\right)=\left(\begin{array}{c}A\\ N\end{array}\right)$.

(**) has 2 variables (m, n), it is $G_2\left(K+A+2,K,A\right)$ actually.

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

11) $G_2\left(N+K,K,A\right)$ : The Inclusion-Exclusion Principle.

$G_2\left(N+K,K,A\right)=\left(\begin{array}{c}A\\ N\end{array}\right)$ is independent of K.

Choice N from A, one way is:

$\left(\begin{array}{c}A\\ N\end{array}\right)=\left(\begin{array}{c}A-1\\ N-1\end{array}\right)+\left(\begin{array}{c}A-1\\ N\end{array}\right)=\left(\begin{array}{c}A-1\\ N-1\end{array}\right)+\left(\begin{array}{c}A-2\\ N-1\end{array}\right)+\cdots +\left(\begin{array}{c}N-1\\ N-1\end{array}\right)$

Another way is: $\begin{array}{c}\left(\begin{array}{c}A\\ N\end{array}\right)=\left(\begin{array}{c}A+1\\ N+1\end{array}\right)-\left(\begin{array}{c}A\\ N+1\end{array}\right)=G_2\left(N+2,2,A\right)\\ =\left\{\left(\begin{array}{c}A+2\\ N+2\end{array}\right)-\left(\begin{array}{c}A+1\\ N+2\end{array}\right)\right\}-\left\{\left(\begin{array}{c}A+1\\ N+2\end{array}\right)-\left(\begin{array}{c}A\\ N+2\end{array}\right)\right\}\\ =G_2\left(N+3,3,A\right)\end{array}$

…

12) $\begin{array}{l}G\left(N+K,K,\left\{a\right\}\right)-\left({\displaystyle \sum A_i}\right)G\left(N+K-1,K,\left\{a\right\}\right)\\ +\left({\displaystyle \sum A_i{A}_j}\right)G\left(N+K-1,K,\left\{a\right\}\right)+\cdots \\ +{\left(-1\right)}^K\left(A_1{A}_2\cdots A_k\right)G\left(N,K,\left\{a\right\}\right)=0\end{array}$

Proof:

$\begin{array}{c}0=G_1\left(N,0,\left\{a\right\}\right)=G\left(N+1,1,\left\{a\right\}\right)-A_{1}G\left(N,1,\left\{a\right\}\right)\\ =\left\{G\left(N+2,2,A\right)-A_2{G}_1\left(N+1,2,A\right)\right\}-A_1\left\{G\left(N+1,2,A\right)-A_2{G}_1\left(N,2,A\right)\right\}\\ =G\left(N+2,2,A\right)-\left(A_1+A_2\right)G_1\left(N+1,2,A\right)+A_1{A}_2{G}_1\left(N,2,A\right)\end{array}$

Induction proved.

q.e.d.

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

13) $S_2\left(N,K\right)-S_1\left(K+1,K\right)S_2\left(N-1,K\right)+\cdots +{\left(-1\right)}^K{S}_1\left(K+1,1\right)S_2\left(N-K,K\right)=0$

S₁ is unsigned Stirling number of the first kind.

14) $G_1\left(N,K,A\right)={\displaystyle {\sum }_{t=K-1}^{N-1}{S}_2\left(N-1,t\right)\left(\begin{array}{c}A\\ t+1-K\end{array}\right){\left[K\right]}^{t+1-K}}$

Proof:

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

$\begin{array}{c}{G}_1\left(N,K,A\right)=\frac{1}{\left(K-1\right)!}{\displaystyle {\sum }_{i=1}^K{\left(-1\right)}^{K-i}}\left(\begin{array}{c}K-1\\ K-i\end{array}\right){\left(A-1+i\right)}^{N-1}\\ =\frac{1}{\left(K-1\right)!}{\displaystyle {\sum }_{i=1}^K{\left(-1\right)}^{K-i}}\left(\begin{array}{c}K-1\\ K-i\end{array}\right){\displaystyle {\sum }_{t=0}^{N-1}{S}_2\left(N-1,t\right){\left[A-1+i\right]}_t}\\ ={\displaystyle {\sum }_{t=0}^{N-1}{S}_2\left(N-1,t\right)}{\displaystyle {\sum }_{i=1}^K{\left(-1\right)}^{K-i}}\left(\begin{array}{c}K-1\\ K-i\end{array}\right)\left(\begin{array}{c}A-1+i\\ t\end{array}\right)\frac{t!}{\left(K-1\right)!}\\ ={\displaystyle {\sum }_{t=0}^{N-1}{S}_2\left(N-1,t\right)G_2\left(t+1,K,A\right){\left[K\right]}^{t+1-K}}\\ ={\displaystyle {\sum }_{t=0}^{N-1}{S}_2\left(N-1,t\right)\left(\begin{array}{c}A\\ t+1-K\end{array}\right){\left[K\right]}^{t+1-K}}\end{array}$

q.e.d.

$\to S_2\left(N,K\right)=G_1\left(N,K,1\right)=K\ast S_2\left(N-1,K\right)+S_2\left(N-1,K-1\right)$

3. Conclusions

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

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

Conflicts of Interest

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

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.