The Stirling triangles Edyta Hetmaniok, Barbara Smoleń, Roman Wituła Institute of Mathematics Silesian University of Technology Kaszubska 23, 44-100 Gliwice, Poland Email: edyta.hetmaniok@polsl.pl,barbara.smolen94@gmail.com,roman.witula@polsl.pl Abstract—The paper is devoted to the elementary discussion We will use here one more, alternative, definition of the Stirling numbers of the first kind nk , it means:   on the triangles of Stirling numbers of the first kind and the r- Stirling numbers as well. Aim of our investigations was to extract hni the numerical sequences connected with these triangles, to verify = sum of all possible products of (n − k) their presence in OEIS and to try to generate some properties k of these numbers. Moreover, we have supplemented with new different integers taken from among results the paper written by S. Falcon [4], the research object of which was the triangle of numbers given by the binomial the n - initial nonnegative integers, transformations of k-Fibonacci numbers. that is from among numbers 0, 1, . . . , n − 1. Index Terms—Pascal triangle, Stirling numbers of the first kind, r-Stirling numbers of the first kind, Catalan numbers, So we have Fibonacci numbers hni hni ≡ 0, ≡ (n − 1)!, 0 1 I. I NTRODUCTION   n−1 n X Y n−1 X (n − 1)! ≡ i= = (n − 1)!Hn−1 , Creation of this paper was directly influenced by article [17] 2 k k=1 1≤i≤n−1 k=1 which intrigued us and, in fact, imposed the subject of our   i6=k investigations. We became interested in the state of knowledge n 1 = n(n − 1) = A000217(n − 1), n = 1, 2, . . . concerning the Pascal triangles for the Stirling numbers of the n−1 2  2 n−1 first kind and the r-Stirling numbers of the first kind. Thus, as n X = k3 , the goal of our research we took the extraction of numerical n−1 k=1 sequences connected with these triangles (that is mainly the sequences of sums of elements in the rows and along the where H Pn−1 denotes the (n − 1)thharmonic number, that is n Hn := k=1 k1 . Moreover we take nn := 1 for every n ∈ N.  antidiagonals of the given triangle). Moreover, we verified the presence of such sequences in OEIS and we undertook the Let us notice that from this definition, almost immediately attempt to generate some properties of the investigated num- after multiplication of the monomials located on the left hand bers. It is worth to emphasize that we have also supplemented side, the following equality results with completely new results the paper written by Sergio Falcon Xn h i n k [4] concerning the triangle of numbers given by the binomial x (1 + x)(2 + x) . . . (n − 1 + x) = xn := x , (1) k transformations of k-Fibonacci numbers. k=0 which was taken originally by James Stirling in his monograph II. T HE S TIRLING TRIANGLE Methodus Differentialis (1730) as the definition of Stirling We begin by presenting the definition of Stirling numbers numbers of the first kind. Product of the monomials located of the first kind. on the left hand side of equality (1) defines today the so called Definition 2.1: Stirling numbers of the first kind describe the Pochhammer symbol. number of permutations on the n−element set possessing k For comparison we have the following widely known New- cycles (that is the permutations which may be decomposed into ton binomial formula exactly k separated cycles). There is no one standard notation X n   n k n for these numbers and for denoting them one can use one of (1 + x) = x , (2) k the following symbols: k=0 • s(n, k), describing the generating function for the binomial coeffi- (k) cients. • Sn , • S1 (n,k), Let us notice that by using definition 2.1 one can easily n derive the formula (recurrence relation for the Stirling numbers • , where n ∈ N, k ∈ N0 , k ≤ n. of the first kind): k In this elaboration we will use the last one from the above h n i n − 1   n−1 listed notations. = + (n − 1) . (3) k k−1 k Copyright © 2017 held by the authors 35 In other words, the selections of (n−k) different numbers from [12], pages 155-157): among n initial nonnegative integers correspond with the sum n b2c  of selections of (n − 1) − (k − 1) = n − k different numbers X n−k Fn+1 = , from among (n−1) initial nonnegative integers and selections k k=0 of (n − 1) − k = n − k − 1 different numbers from among (n − 1) initial nonnegative integers with the added number where Fn denotes the nth Fibonacci number. n − 1. Let us construct now the Pascal triangle for the Stirling 1 1  numbers of the first kind which will be called henceforward 1 1 as the Stirling triangle of the first kind  1  1 2 1 0  1 1 0 := 1     1 1 1 3 3 1  1  1 0 1     2 2 2 1 4 6 4 1 0 1 2  1  3 3 3 3 1 ... ... ... ... ... 0 1 2 3 ... ... ... ... ... Next, by executing in the Stirling triangle of the first kind the summation of elements along the antidiagonals, as it is that is the following numerical triangle presented in the following scheme (the first column containing zeros and one digit one at the zero level is omitted here): zero level −→ 1 first level −→ 0 0!=1 1 :   1  1 second level −→ 0 1!=1 1 :   2  3 1 third level −→ :   :   0 2!=2 3 1 6  11  6 1 :   :   :   fourth level −→ 0 3!=6 11 6 1 24  50  35  10 1 :   :  :  120  274  225  85 15 1 fifth level −→ 0 4!=24 50 35 10 1 :   :   720  1764  1624 735 175 21 1 :   5040  . . . ... ... ... ... ... Hence, as well as on the basis of formula (3) and in view of the alternative definition 2.1, the following summation formula 1 + 0 = 1, easily results 2 + 1 = 3, 6 + 3 = 9, n h i n−1 X  n−1 X n − 1 X n n−1 24 + 11 + 1 = 36, = n! = (n − 1) + k k k 120 + 50 + 6 = 176, k=0 k=1 k=0 n−1 X n − 1  720 + 274 + 35 + 1 = 1030, =n . 5040 + 1764 + 225 + 10 = 7039, k etc. k=0 (4) For contrast, from the Pascal triangle for the binomial coeffi- we obtain the sequence of natural numbers labeled by symbol cients (also called by us the classic Pascal triangle) we have A237653 in the Sloane’s OEIS encyclopaedia. In other words the following summation formula we have  hni n − 1 n − 2  1, when n = 2r, n   n−1 X + + +... + (r + 1)!,  X n n−1 =2 . 0 1 2 when n = 2r + 1,  k k k=0 k=0 =A237653(n) Obviously, the above formula also arises easily from the for every n = 1, 2, . . .. classic recurrence relation (equivalent formula for (3) but for Remark 2.1: In the classic Pascal triangle the numbers at the binomial coefficient): the given level n (starting with the zero level) represent the coefficients in the expansion of number (b + 1)n in the given       n n−1 n−1 = + . numerical base b (we assume that all the coefficients at level k k k−1 n are ≤ b) which results from the binomial formula (2). Executing in the classic Pascal triangle the summation over Whereas in the Stirling triangle of the first kind the numbers the antidiagonals we obtain the next unexpected formula (see at the given level n (starting with the zero level) represent the 36 n−1 coefficients in the expansion of number Q (bk + 1) in the We observe also that the sum of elements on antidiagonals of k=0 T form three known sequences defined in the OEIS, that is given numerical base b (under the assumptions that that all the the sequence of all sums coefficients at level n are ≤ b) which results from formula (1) (one should substitute x = 1b and multiply by 10n on both {1, 1, 3, 4, 9, 14, 28, 47, 89, 155, 286, . . .} = A006053 sides). What is interesting, Slone’s OEIS reports the sequences: which satisfies the linear recurrence relation of the third order n−1 Q n−1 Q A144773(n) = (10k + 1), A008548(n) = (5k + 1), an = an−1 + 2an−2 − an−3 , k=0 k=0 n−1 Q A007559(n) = (3k + 1). where A006053(n) := an , n = 1, 2, . . . And next the k=0 Remark 2.2: Sergio Falcon in paper [4] considers the following sequences obtained by bisection of {an } : triangle T of the polynomial coefficients n   {a2n−1 } = {1, 3, 9, 28, 89, 286, . . .} = A094790 X n {a2n } = {1, 4, 14, 47, 155, . . .} = A094789 pn (k) := Fk,n−j , n ∈ N, j=0 j which satisfy both the same recurrence relation of the third which form the binomial transforms of rows of the following order triangle of k-Fibonacci numbers where Fk,n , k ∈ R, k > 0, and n ∈ N0 : an = 5an−1 − 6an−2 + an−3 . Fk,0 Let us set T 2 = [tkn ]N×N . If n > k then tkn = 0. We also Fk,1 Fk,0 verified that Xn Fk,2 Fk,1 Fk,0 tnk ≤ A030240(n − 1), k=1 Fk,3 Fk,2 Fk,1 Fk,0 ... ... ... ... ... where equality holds only for n = 1, 2, 3, 4 and We have 5 X Fk,n+1 = kFk,n + Fk,n−1 , Fk,0 = 0, Fk,1 = 1, t5k = A030240(4) + 1. k=1 for every n ∈ N. The following results give a supplement for the Falcon’s paper [4]. We find that the polynomials pn (k) Remark 2.3: In the context of problems discussed in this satisfy the double recurrence relation section it is also worth to mention the Narayana numbers  defined in the way given below (see [6]): pn+1 (k) = (k + 1)pn (k) + qn (k), qn+1 (k) = pn (k) + qn (k), N (0, 0) = 1, N (n, 0) = 0, for every n ∈ N, where p1 (k) = q1 (k) ≡ 1, p2 (k) =    1 n n k + 2, q2 (k) ≡ 2. N (n, k) = , k, n ∈ N, k ≤ n. Hence, after simple algebra we get the recursive relation for n k k−1 polynomials pn (k) : n Creating the Narayana triangle we find one more beautiful X result. The sums of elements in the rows of the Narayana pn+1 (k) = 1 + kpn (k) + pj (k), n ∈ N, j=1 triangle are equal to the Catalan numbers and the recurence relation for pn (k) n X N (n, k) = Cn . pn+2 (k) = (k + 2)pn+1 (k) − kpn (k), n ∈ N. k=1 The triangle T has the form 1 In result of summation over the antidiagonals of 1 2 Narayana triangle we get the generalized Catalan numbers n−1 1 3 4 ∗ X (Cn+1 = Cn∗ + Ck∗ Cn−1−k ∗ , n ∈ N0 , the sequence 1 4 8 8 k=1 1 5 13 20 16 A004148(n) in OEIS), i.e. 1 6 19 38 48 32 1 7 26 63 104 112 64 b n−1 2 c X 1 8 34 96 192 272 256 128 N (n − k, k + 1) = Cn∗ . 1 ... ... ... ... ... ... ... ... k=0 37 III. R-S TIRLING TRIANGLE OF THE FIRST KIND Let us notice that By using the analogical properties of r-Stirling numbers we   n−1 n X 1 get a little bit more general results. The r-Stirling numbers of = k= (n − 2)(n + 1), the first kind are defined as follows n−1 2 2 k=2 Definition 3.1: We take = A000096(n − 2), n = 3, 4, . . .       n−1 n n n X 1 = 0, n < r, = δk,r , n = r, = k= (n − 3)(n + 2) k r k r n−1 3 2       (5) k=3 n n−1 n−1 = (n − 1) + , n > r. = A055998(n − 2), n = 4, 5 . . . k r k r k−1 r   n We also take nk 0 = nk 1 := nk .       = A00170k(n − k − 1), n−k−1 2 The combinatoric description of  these numbers is presented in paper [1]. So, the number nk r denotes the number of per- for every k = 1, 2 and n = k + 3, k + 4, mutations of set {1, 2, . . . , n} possessing exactly k mutually disjoint cycles and such that the numbers 1, 2, . . . , r belong to   n different cycles. = A02418k(n − k − 1), The above description implies that n−k+1 3 n h i X n for every k = 3, 4, 5 and n = k + 2, k + 3, . . .. On the basis = number of all permutations of set {1, 2, . . . , n} of formula (5) we can construct the r-Stirling triangle of the k r k=0 first kind so that the numbers 1, . . . , r are in different, 0 mutually disjoint cycles. 0 r 1 1 0 r 1 r Moreover, by using the definition of r-Stirling numbers of the 2 2 2 first kind we easily derive the recurrence relation 0 r 1 r 2 r 3 3 3 3 n h n−1 X  n−1 X  0 r 1 r 2 r 3 r X ni n−1 n−1 = (n − 1) + ... ... ... ... ... k r k r k r k=0 k=1 k=0 n−1 (6) X n − 1  =n , Let us consider the case for r=2, that is k r k=0 0 for every r ≥ 1, which is the generalization of identity (4). 0 0 One can check that we have then 0 0 1 n h 0 0 2 1 X ni n! = , 0 0 6 5 1 k r r! k=0 0 0 24 26 9 1 0 0 120 154 71 14 1 for n ≥ r. Broder in [1] gave the generating function for the 0 0 720 1044 580 155 20 1 r-Stirling numbers of the first kind 0 0 ... ... ... ... ... ... ... n    X n xr (x + r)n−r , n ≥ r ≥ 0, Now, by summing the elements along the antidiagonals in the xk = (7) k r 0, otherwise, above triangle k=0 0 + 0 = 0, where, let us recall, the Pochhammer symbol xn is applied. 0 + 0 = 0, This formula results from the alternative definition of the 0 + 0 + 1 = 1, r− Stirling numbers of the first kind, namely 0 + 0 + 2 = 2, hni 6 + 1 = 7, = sum of all possible products of exactly 24 + 5 = 29, k r (n − k) different natural numbers from among 120 + 26 + 1 = 147, 720 + 154 + 9 = 883, the numbers r, r + 1, . . . , n − 1. etc. 38 we obtain the sequence of natural numbers not existing in for every n = 3, 4 . . .. OEIS. We have We have verified numerically (but again, basing on premises   resulting from the algebraic estimation) that this sequence     1, when n = 2m, satisfies for 7 ≤ n ≤ 500 the following inequalities        n n−1 n−2  1 + + + ...+ (m − 1)(m + 2), 0 2 1 2 2 2   2 (n − 5)! < A∅∅∅∅∅2(n) < (n − 4)!.     when n = 2m + 1,  Remark 3.1: In case of the r-Stirling numbers the numbers = A∅∅∅∅∅1(n), at one level n represent the coefficients in the expansion of n−1 for every n = 2, 3 . . .. Notation A∅∅∅∅∅k, k ∈ N, k ≤ 9, Q number (bk + 1) in the given numerical base b (under the with the empty sets, is the notation invented by us to denote k=r assumption that all the coefficients at level n are ≤ b) which the sequences {A∅∅∅∅∅k(n), n ∈ N, }, k ∈ N, k ≤ 9 not results from formula (7) (analogically like in the previous included in OEIS. case). We have verified numerically (although basing on premises resulting from the algebraic estimation) that for 5 ≤ n ≤ 500 the above sequence satisfies the following inequalities IV. T RIANGLES FOR THE POWERS OF S TIRLING NUMBERS (n − 2)! (n − 2)! < A∅∅∅∅∅1(n) < . AND THE BINOMIAL COEFFICIENTS n 2 Next we construct the analogical triangle for the case r = 3. Thus we have Properties of the classic Pascal triangle are studied in [8] together with the presentation of Fibonacci sequence with the 0 aid of binomial coefficients. Let us turn our attention into the 0 0 Pascal triangle for the powers of binomial coefficients. For 0 0 0 example, for the squares of binomial coefficients we receive 0 0 0 1 0 0 0 3 1 0 2  0 0 0 12 7 1 0 0 0 0 60 47 12 1 1 2 1 2   0 1 0 0 0 360 342 119 18 1 2 2 2 2 2 2    0 0 0 2520 2754 1175 245 25 1 0 1 2 0 0 0 ... ... ... ... ... ... ... 3 2  3 2  3 2  3 2  0 1 2 3 Summing the elements along the antidiagonals in the above triangle we get ... ... ... ... ... 0 or directly 0 + 0 = 0, 0 + 0 + 0 = 0, 1 0 + 0 + 0 + 1 = 1, 1 1 0 + 0 + 0 + 3 = 3, 1 4 1 12 + 1 = 13, 1 9 9 1 60 + 7 = 67, 1 16 36 16 1 360 + 47 + 1 = 408, 1 25 100 100 25 1 and so on. 1 36 225 1 400 225 36 The obtained sequence of natural numbers is not included 1 ... ... ... ... ... ... ... either in OEIS. We have  Summing the elements along the antidiagonals we find      1, when n = 2m, 1,        n n−1 n−2  1 1 + 4 = 5, + + + ...+ (m − 2)(m + 3), 0 3 1 3 2 3   2 1 + 9 + 1 = 11, 1 + 16 + 9 = 26,     when n = 2m + 1  1 + 25 + 36 + 1 = 63, 1 + 36 + 100 + 16 = 153, = A∅∅∅∅∅2(n), etc. 39 This is the sequence labeled by symbol A051286 in the Next, by summing the  elements along the antidiagonals in 3 Sloane’s OEIS encyclopaedia. In other words we have the Pascal triangle for nk we receive the sequence  2  2  2 n n−1 n−2 0 + 1 = 1, + + + ... 0  1 2 0 + 1 = 1,  1, when n = 2m,  8 + 1 = 9, 216 + 27 = 243,   + (m + 1)2 , = A051286(n). 13824 + 1331 + 1 = 15156,  and so on,    when n = 2m + 1, that is Summing the elements along the antidiagonals in the ana-  logical triangle for the cubes of binomial coefficients we  3  n n−1 3  n−2 3  1, when n = 2r, obtain 1, 2, 9, 29, 92, 343, 1281, 4720, . . ., that is the sequence + + +... + ((r + 1)!)3 , 0 1 2 when n = 2r + 1,  denoted by A181545 in Sloane’s OEIS encyclopaedia. In other words = A∅∅∅∅∅4(n),  3  3  3 n n−1 n−2 again not present in OEIS. + + + ... 0  1 2 As before we have checked numerically that for 4 ≤ n ≤    1, when n = 2m, 500 the above sequence satisfies the inequalities   3 + (m + 1)3 , = A181545(n). n! < A∅∅∅∅∅4(n) < n! . 3 3     when n = 2m + 1, V. C ONCLUSION Let us consider now the analogical triangles for the Stirling In the paper the number of elementary properties of the numbers of the first kind. For the start we take the squares of numerical triangles connected with the Stirling numbers and these numbers the k-Fibonacci numbers is presented. We linked the discussed sequences with the sequences included in OEIS. The obtained 1 results summarize some state of research. In the future we 0 1 intend to refer to these numerical triangles from the algebraic 0 1 1 side, similarly like, among others, the authors of papers [2], 0 4 9 1 [3], [9], [10] and [14] did it in case of the classic Pascal 0 36 121 36 1 triangle. In the future we also plan to analyze paper [13] and 0 576 2500 1225 100 1 the drawn conclusions will be included in our next publication. 0 14400 75076 50625 7225 225 1 0 ... ... ... ... ... ... ... Acknowledgments Executing the summation of elements over the antidiagonals, The Authors want to express their sincere thanks to the similarly as in the cases of previous numerical triangles, we Referees for their constructive reports with many essential get the sequence remarks and advices concerning the references. 0 + 1 = 1, R EFERENCES 0 + 1 = 1, [1] A. Z. Broder, The r-Stirling numbers, Discrete Math. 49 (1984), 241–259. 4 + 1 = 5, [2] G.S. Call, D.J. Velleman, Pascal’s matrices, Amer. Math. Monthly 100 36 + 9 = 45, No. 4 (1993), 372–376. [3] K. S. Davis, W. A. Webb, Pascal’s triangle modulo 4, Fibonacci Quart. 576 + 121 + 1 = 698, 29 (1991), 79-83. 14400 + 2500 + 36 = 16936, [4] S. Falcon, On the complex k-Fibonacci numbers, Cogent Mathematics and so on, (2016), 3:1201944. [5] R.L. Graham, D.E. Knuth, O. Patashnik, Concrete Mathematics, Addi- that is the sequence not included in OEIS son–Wesley, Reading, MA, 1989.  [6] R.P. Grimaldi, Fibonacci and Catalan Numbers, Wiley, 2012.  2  n n−1 2  n−2 2  1, when n = 2r, [7] R. Grzymkowski, R. Wituła, Complex functions and Laplace trans- + + +... + ((r + 1)!)2 , formations - examples and exercises, Pracownia Komputerowa Jacka 0 1 2 Skalmierskiego (PKJS), Gliwice 2010 (in Polish). when n = 2r + 1,  [8] R. Hoshino, Riveting Properties of Pascal’a Triangle, Canadian Mathe- = A∅∅∅∅∅3(n), matical Society, Crux Mathematicorum, 24 (March), 1998. [9] J. G. Huard, B. K. Spearman, K. S. Williams, Pascal’s triangle (mod 8), for every n = 1, 2, . . .. Europ. J. Combinatorics 19 (1998), 45–62. [10] J. G. Huard, B. K. Spearman, K. S. Williams, Pascal’s triangle (mod Moreover, we have checked numerically that for 4 ≤ n ≤ 9), Acta Arith. 78 No. 4 (1997), 331-348. 500 the above sequence satisfies the inequalities [11] C. Napoli, G. Pappalardo, E. Tramontana, A mathematical model for file  2 fragment diffusion and a neural predictor to manage priority queues over n! n! bittorrent, International Journal of Applied Mathematics and Computer < A∅∅∅∅∅3(n) < . Science 26 No. 1 (2016), 147–160. 5 5 40 [12] T. Koshy, Fibonacci and Lucas Numbers with Applications, Wiley, New York 2001. [13] W. Lang, On generalizations of the Stirling number triangles, J. Integer Seq. 3 (2000), Article 00.2.4. [14] B. Lewis, Revisiting the Pascal Matrix, Amer. Math. Monthly 117 (2010), 50–66. [15] G. Capizzi, G. Lo Sciuto, C. Napoli, E. Tramontana, M. Wozniak, Automatic classification of fruit defects based on co-occurrence matrix and neural networks, IEEE Federated Conference on Computer Science and Information Systems (FedCSIS), 861–867. [16] A.Sofo, Finite sums in Pascal’s triangle, The FIbonacci Quarterly 50 No. 4 (2012), 337–345. [17] T. Wright, Pascal’s triangle gets its genes from Stirling numbers of the first kind, College Math. J. 26 No. 5 (1995), 368–371. 41