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
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.
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
Diagonals give reversed rows of A111999.
KEYWORD
tabf,nonn,nice,easy
AUTHOR
EXTENSIONS
More terms from Larry Reeves (larryr(AT)acm.org), Feb 16 2001
STATUS
approved