A008306 Triangle T(n,k) read by rows: associated Stirling numbers of first kind (n >= 2, 1 <= k <= floor(n/2)).

1, 2, 6, 3, 24, 20, 120, 130, 15, 720, 924, 210, 5040, 7308, 2380, 105, 40320, 64224, 26432, 2520, 362880, 623376, 303660, 44100, 945, 3628800, 6636960, 3678840, 705320, 34650, 39916800, 76998240, 47324376, 11098780, 866250, 10395

Offset: 2

Author

N. J. A. Sloane

Keywords

• tabf
• nonn
• nice
• easy

Comments

Also, T(n,k) is the number of derangements (permutations with no fixed points) of {1..n} with k cycles.

The sum of the n-th row is the n-th subfactorial: A000166(n). - Gary Detlefs, Jul 14 2010

Examples

			Rows 2 through 7 are:
    1;
    2;
    6,   3;
   24,  20;
  120, 130,  15;
  720, 924, 210;
		

References

• L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 256.
• J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 75.

Links

• Reinhard Zumkeller, Rows n = 2..125 of table, flattened
• J. Fernando Barbero G., Jesús Salas, and Eduardo J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. I. General Structure, arXiv:1307.2010 [math.CO], 2013.
• W. Carlitz, On some polynomials of Tricomi, Bollettino dell'Unione Matematica Italiana, Serie 3, Vol. 13, (1958), n. 1, p. 58-64
• Tom Copeland, Generators, Inversion, and Matrix, Binomial, and Integral Transforms
• W. Gautschi, The incomplete gamma functions since Tricomi (Cf. p. 206-207.)
• P. Gniewek and B. Jeziorski, Convergence properties of the multipole expansion of the exchange contribution to the interaction energy, arXiv preprint arXiv:1601.03923 [physics.chem-ph], 2016.
• S. Karlin and J. McGregor, Many server queuing processes with Poisson input and exponential service times, Pacific Journal of Mathematics, Vol. 8, No. 1, p. 87-118, March (1958). Cf. p. 117.
• R. Paris, A uniform asymptotic expansion for the incomplete gamma function, Journal of Computational and Applied Mathematics, 148 (2002), p. 223-239. (See 333. From Tom Copeland, Jan 03 2016)
• M. Z. Spivey, On Solutions to a General Combinatorial Recurrence, J. Int. Seq. 14 (2011) # 11.9.7.
• N. Temme, A class of polynomials related to those of Laguerre
• N. Temme, Traces to Tricomi in recent work on special functions and asymptotics of integrals
• A. Topuzoglu, The Carlitz rank of permutations of finite fields: A survey, Journal of Symbolic Computation, Online, Dec 07, 2013.
• Eric Weisstein's World of Mathematics, Permutation Cycle
• Eric Weisstein's World of Mathematics, Stirling Number of the First Kind
• Shawn L. Witte, Link Nomenclature, Random Grid Diagrams, and Markov Chain Methods in Knot Theory, Ph. D. Dissertation, University of California-Davis (2020).

Crossrefs

Cf. A000166, A106828 (another version), A079510 (rearranged triangle), A235706 (specializations).

Diagonals: A000142, A000276, A000483.

Diagonals give reversed rows of A111999.

Programs

Haskell

a008306 n k = a008306_tabf !! (n-2) !! (k-1)
a008306_row n = a008306_tabf !! (n-2)
a008306_tabf = map (fst . fst) $ iterate f (([1], [2]), 3) where
   f ((us, vs), x) =
     ((vs, map (* x) $ zipWith (+) ([0] ++ us) (vs ++ [0])), x + 1)
-- Reinhard Zumkeller, Aug 05 2013

Maple

A008306 := proc(n,k) local j;
add(binomial(j,n-2*k)*A008517(n-k,j),j=0..n-k) end;
seq(print(seq(A008306(n,k),k=1..iquo(n,2))),n=2..12):
# Peter Luschny, Apr 20 2011

Mathematica

t[0, 0] = 1; t[n_, 0] = 0; t[n_, k_] /; k > n/2 = 0; t[n_, k_] := t[n, k] = (n - 1)*(t[n - 1, k] + t[n - 2, k - 1]); A008306 = Flatten[ Table[ t[n, k], {n, 2, 12}, {k, 1, Quotient[n, 2]}]] (* Jean-François Alcover, Jan 25 2012, after David Callan *)

PARI

{ A008306(n,k) = (-1)^(n+k) * sum(i=0,k, (-1)^i * binomial(n,i) * stirling(n-i,k-i,1) ); } \\ Max Alekseyev, Sep 08 2018

Formula

T(n,k) = Sum_{i=0..k} (-1)^i * binomial(n,i) * |stirling1(n-i,k-i)| = (-1)^(n+k) * Sum_{i=0..k} (-1)^i * binomial(n,i) * A008275(n-i,k-i). - Max Alekseyev, Sep 08 2018

E.g.f.: 1 + Sum_{1 <= 2*k <= n} T(n, k)*t^n*u^k/n! = exp(-t*u)*(1-t)^(-u).

Recurrence: T(n, k) = (n-1)*(T(n-1, k) + T(n-2, k-1)) for 1 <= k <= n/2 with boundary conditions T(0,0) = 1, T(n,0) = 0 for n >= 1, and T(n,k) = 0 for k > n/2. - David Callan, May 16 2005

E.g.f. for column k: B(A(x)) where A(x) = log(1/1-x)-x and B(x) = x^k/k!.

From Tom Copeland, Jan 05 2016: (Start)

The row polynomials of this signed array are the orthogonal NL(n,x;x-n) = n! Sum_{k=0..n} binomial(x,n-k)*(-x)^k/k!, the normalized Laguerre polynomials of order (x-n) as discussed in Gautschi (the Temme, Carlitz, and Karlin and McGregor references come from this paper) in regard to asymptotic expansions of the upper incomplete gamma function--Tricomi's Cinderella of special functions.

e^(x*t)*(1-t)^x = Sum_{n>=0} NL(n,x;x-n)*x^n/n!.

The first few are

NL(0,x) = 1

NL(1,x) = 0

NL(2,x) = -x

NL(3,x) = 2*x

NL(4,x) = -6*x + 3*x^2.

With D=d/dx, :xD:^n = x^n D^n, :Dx:^n = D^n x^n, and K(a,b,c), the Kummer confluent hypergeometric function, NL(n,x;y-n) = n!*e^x binomial(xD+y,n)*e^(-x) = n!*e^x Sum_{k=0..n} binomial(k+y,n) (-x)^k/k! = e^x x^(-y+n) D^n (x^y e^(-x)) = e^x x^(-y+n) :Dx:^n x^(y-n)*e^(-x) = e^x*x^(-y+n)*n!*L(n,:xD:,0)*x^(y-n)*e^(-x) = n! binomial(y,n)*K(-n,y-n+1,x) = n!*e^x*(-1)^n*binomial(-xD-y+n-1,n)*e^(-x). Evaluate these expressions at y=x after the derivative operations to obtain NL(n,x;x-n). (End)

Extensions

More terms from Larry Reeves (larryr(AT)acm.org), Feb 16 2001