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,2

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

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

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)

Example

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

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

Prog

(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
(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

Crossrefs

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

Diagonals: A000142, A000276, A000483.

Diagonals give reversed rows of A111999.

Sequence in context: A304085 A302783 A364318 * A231171 A331431 A248120

Adjacent sequences: A008303 A008304 A008305 * A008307 A008308 A008309

Keyword

tabf,nonn,nice,easy

Author

N. J. A. Sloane

Extensions

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

Status

approved