%I #126 Sep 29 2024 10:29:58

%S 1,0,1,0,-1,1,0,2,-3,1,0,-6,11,-6,1,0,24,-50,35,-10,1,0,-120,274,-225,

%T 85,-15,1,0,720,-1764,1624,-735,175,-21,1,0,-5040,13068,-13132,6769,

%U -1960,322,-28,1,0,40320,-109584,118124,-67284,22449,-4536,546,-36,1,0,-362880,1026576,-1172700,723680,-269325,63273,-9450,870,-45,1

%N Triangle of Stirling numbers of first kind, s(n,k), n >= 0, 0 <= k <= n.

%C The unsigned numbers are also called Stirling cycle numbers: |s(n,k)| = number of permutations of n objects with exactly k cycles.

%C Mirror image of the triangle A054654. - _Philippe Deléham_, Dec 30 2006

%C Also the triangle gives coefficients T(n,k) of x^k in the expansion of C(x,n) = (a(k)*x^k)/n!. - _Mokhtar Mohamed_, Dec 04 2012

%C From _Wolfdieter Lang_, Nov 14 2018: (Start)

%C This is the Sheffer triangle of Jabotinsky type (1, log(1 + x)). See the e.g.f. of the triangle below.

%C This is the inverse Sheffer triangle of the Stirling2 Sheffer triangle A008275.

%C The a-sequence of this Sheffer triangle (see a W. Lang link in A006232)

%C is from the e.g.f. A(x) = x/(exp(x) -1) a(n) = Bernoulli(n) = A027641(n)/A027642(n), for n >= 0. The z-sequence vanishes.

%C The Boas-Buck sequence for the recurrences of columns has o.g.f. B(x) = Sum_{n>=0} b(n)*x^n = 1/((1 + x)*log(1 + x)) - 1/x. b(n) = (-1)^(n+1)*A002208(n+1)/A002209(n+1), b = {-1/2, 5/12, -3/8, 251/720, -95/288, 19087/60480,...}. For the Boas-Buck recurrence of Riordan and Sheffer triangles see the Aug 10 2017 remark in A046521, adapted to the Sheffer case, also for two references. See the recurrence and example below. - _Wolfdieter Lang_, Nov 14 2018

%C Let G(n,m,k) be the number of simple labeled graphs on [n] with m edges and k components. Then T(n,k) = Sum (-1)^m*G(n,m,k). See the Read link below. Equivalently, T(n,k) = Sum mu(0,p) where the sum is over all set partitions p of [n] containing k blocks and mu is the Moebius function in the incidence algebra associated to the set partition lattice on [n]. - _Geoffrey Critzer_, May 11 2024

%D M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 833.

%D L. Comtet, Advanced Combinatorics, Reidel, 1974; Chapter V, also p. 310.

%D J. H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, NY, 1996, p. 93.

%D F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 226.

%D R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 245.

%D J. Riordan, An Introduction to Combinatorial Analysis, p. 48.

%H T. D. Noe, <a href="/A048994/b048994.txt">Rows n=0..100 of triangle, flattened</a>

%H M. Abramowitz and I. A. Stegun, eds., <a href="https://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].

%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Barry1/barry263.html">Generalized Stirling Numbers, Exponential Riordan Arrays, and Toda Chain Equations</a>, Journal of Integer Sequences, 17 (2014), #14.2.3.

%H Fatima Zohra Bensaci, Rachid Boumahdi, and Laala Khaldi, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL27/Boumahdi/boumahdi12.html">Finite Sums Involving Fibonacci and Lucas Numbers</a>, J. Int. Seq. (2024). See p. 9.

%H R. M. Dickau, <a href="https://mathforum.org/advanced/robertd/stirling1.html">Stirling numbers of the first kind</a>. [Illustrates the unsigned Stirling cycle numbers A132393.]

%H Askar Dzhumadil'daev and Damir Yeliussizov, <a href="https://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p10">Walks, partitions, and normal ordering</a>, Electronic Journal of Combinatorics, 22(4) (2015), #P4.10.

%H Bill Gosper, <a href="/A008275/a008275.png">Colored illustrations of triangle of Stirling numbers of first kind read mod 2, 3, 4, 5, 6, 7</a>.

%H Gergő Nemes, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Nemes/nemes4.html">An Asymptotic Expansion for the Bernoulli Numbers of the Second Kind</a>, J. Int. Seq. 14 (2011), #11.4.8.

%H A. Hennessy and Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Barry6/barry161.html">Generalized Stirling Numbers, Exponential Riordan Arrays, and Orthogonal Polynomials</a>, J. Int. Seq. 14 (2011), #11.8.2 (A-number typo A048894).

%H NIST Digital Library of Mathematical Functions, <a href="https://dlmf.nist.gov/26.8">Stirling Numbers</a>

%H Ken Ono, Larry Rolen, and Florian Sprung, <a href="https://arxiv.org/abs/1602.00752">Zeta-Polynomials for modular form periods</a>, p. 6, arXiv:1602.00752 [math.NT], 2016.

%H Ricardo A. Podestá, <a href="https://arxiv.org/abs/1603.09156">New identities for binary Krawtchouk polynomials, binomial coefficients and Catalan numbers</a>, arXiv preprint arXiv:1603.09156 [math.CO], 2016.

%H Ronald Read, <a href="https://math.uchicago.edu/~michaelklug/ReadChromatic.pdf"> An Introduction to Chromatic Polynomials</a>, Journal of Combinatorial Theory, 4(1968)52-71.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Stirling_numbers_and_exponential_generating_functions">Stirling numbers and exponential generating functions</a>.

%F s(n, k) = A008275(n,k) for n >= 1, k = 1..n; column k = 0 is {1, repeat(0)}.

%F s(n, k) = s(n-1, k-1) - (n-1)*s(n-1, k), n, k >= 1; s(n, 0) = s(0, k) = 0; s(0, 0) = 1.

%F The unsigned numbers a(n, k)=|s(n, k)| satisfy a(n, k)=a(n-1, k-1)+(n-1)*a(n-1, k), n, k >= 1; a(n, 0) = a(0, k) = 0; a(0, 0) = 1.

%F Triangle (signed) = [0, -1, -1, -2, -2, -3, -3, -4, -4, ...] DELTA [1, 0, 1, 0, 1, 0, 1, 0, ...]; Triangle(unsigned) = [0, 1, 1, 2, 2, 3, 3, 4, 4, ...] DELTA [1, 0, 1, 0, 1, 0, 1, 0, ...]; where DELTA is Deléham's operator defined in A084938.

%F Sum_{k=0..n} (-m)^(n-k)*s(n, k) = A000142(n), A001147(n), A007559(n), A007696(n), ... for m = 1, 2, 3, 4, ... .- _Philippe Deléham_, Oct 29 2005

%F A008275*A007318 as infinite lower triangular matrices. - _Gerald McGarvey_, Aug 20 2009

%F T(n,k) = n!*[x^k]([t^n]exp(x*log(1+t))). - _Peter Luschny_, Dec 30 2010, updated Jun 07 2020

%F From _Wolfdieter Lang_, Nov 14 2018: (Start)

%F Recurrence from the Sheffer a-sequence (see a comment above): s(n, k) = (n/k)*Sum_{j=0..n-k} binomial(k-1+j, j)*Bernoulli(j)*s(n-1, k-1+j), for n >= 1 and k >= 1, with s(n, 0) = 0 if n >= 1, and s(0,0) = 1.

%F Boas-Buck type recurrence for column k: s(n, k) = (n!*k/(n - k))*Sum_{j=k..n-1} b(n-1-j)*s(j, k)/j!, for n >= 1 and k = 0..n-1, with input s(n, n) = 1. For sequence b see the Boas-Buck comment above. (End)

%F T(n,k) = Sum_{j=k..n} (-1)^(n-j)*A271705(n,j)*A216294(j,k). - _Mélika Tebni_, Feb 23 2023

%e Triangle begins:

%e n\k 0 1 2 3 4 5 6 7 8 9 ...

%e 0 1

%e 1 0 1

%e 2 0 -1 1

%e 3 0 2 -3 1

%e 4 0 -6 11 -6 1

%e 5 0 24 -50 35 -10 1

%e 6 0 -120 274 -225 85 -15 1

%e 7 0 720 -1764 1624 -735 175 -21 1

%e 8 0 -5040 13068 -13132 6769 -1960 322 -28 1

%e 9 0 40320 -109584 118124 -67284 22449 -4536 546 -36 1

%e ... - _Wolfdieter Lang_, Aug 22 2012

%e ------------------------------------------------------------------

%e From _Wolfdieter Lang_, Nov 14 2018: (Start)

%e Recurrence: s(5,2)= s(4, 1) - 4*s(4, 2) = -6 - 4*11 = -50.

%e Recurrence from the a- and z-sequences: s(6, 3) = 2*(1*1*(-50) + 3*(-1/2)*35 + 6*(1/6)*(-10) + 10*0*1) = -225.

%e Boas-Buck recurrence for column k = 3, with b = {-1/2, 5/12, -3/8, ...}:

%e s(6, 3) = 6!*((-3/8)*1/3! + (5/12)*(-6)/4! + (-1/2)*35/5!) = -225. (End)

%p A048994:= proc(n,k) combinat[stirling1](n,k) end: # _R. J. Mathar_, Feb 23 2009

%p seq(print(seq(coeff(expand(k!*binomial(x,k)),x,i),i=0..k)),k=0..9); # _Peter Luschny_, Jul 13 2009

%p A048994_row := proc(n) local k; seq(coeff(expand(pochhammer(x-n+1,n)), x,k), k=0..n) end: # _Peter Luschny_, Dec 30 2010

%t Table[StirlingS1[n, m], {n, 0, 9}, {m, 0, n}] (* _Peter Luschny_, Dec 30 2010 *)

%o (PARI) a(n,k) = if(k<0 || k>n,0, if(n==0,1,(n-1)*a(n-1,k)+a(n-1,k-1)))

%o (PARI) trg(nn)=for (n=0, nn-1, for (k=0, n, print1(stirling(n,k,1), ", ");); print();); \\ _Michel Marcus_, Jan 19 2015

%o (Maxima) create_list(stirling1(n,k),n,0,12,k,0,n); /* _Emanuele Munarini_, Mar 11 2011 */

%o (Haskell)

%o a048994 n k = a048994_tabl !! n !! k

%o a048994_row n = a048994_tabl !! n

%o a048994_tabl = map fst $ iterate (\(row, i) ->

%o (zipWith (-) ([0] ++ row) $ map (* i) (row ++ [0]), i + 1)) ([1], 0)

%o -- _Reinhard Zumkeller_, Mar 18 2013

%Y See especially A008275 which is the main entry for this triangle. A132393 is an unsigned version, and A008276 is another version.

%Y Cf. A008277, A039814-A039817, A048993, A084938.

%Y A000142(n) = Sum_{k=0..n} |s(n, k)| for n >= 0.

%Y Row sums give A019590(n+1).

%Y Cf. A002209, A027641/A027642, A216294, A271705.

%K sign,tabl,nice

%O 0,8

%A _N. J. A. Sloane_

%E Offset corrected by _R. J. Mathar_, Feb 23 2009

%E Formula corrected by _Philippe Deléham_, Sep 10 2009