OFFSET
0,3
COMMENTS
a(n) is the number of terms that appear before cancellations occur in the evaluation of the determinant of an n X n matrix by the usual sum over permutations of [n], for a matrix whose off diagonal entries are specified, and each of whose diagonal entries is minus the sum of the negatives of the off diagonal entries and one additional term, as in the usual presentation of the matrix in the Matrix Tree Theorem.
The number a(n-1) - n^(n-2) (A000272) is the number of terms which cancel in Zeilberger's proof of the Matrix Tree Theorem. This number is even, as the terms which cancel are equal in magnitude with opposite sign, and as is also apparent from the formula in terms of A087981(n) which is a corollary of Zeilberger's proof.
Formula involves the derangement numbers A000166 which count permutations with no fixed points, also the number A087981 of colored permutations with no fixed points of n elements where each cycle is one of two colors.
Number of permutations of [n] where the fixed points are n-colored and all other points are unicolored. - Alois P. Heinz, Apr 23 2020
a(n) - (n-1)^n is the number of cyclic nodes in all endofunctions on [n] with no non-cyclic preimages. - Natalia L. Skirrow, Mar 16 2026
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..386
Philippe Flajolet, Peter J. Grabner, Peter Kirschenhofer, and Helmut Prodinger, On Ramanujan's Q-function, Journal of Computational and Applied Mathematics, vol. 58, iss. 1 (1995-03-20), pp. 103-116.
Eric Weisstein, Exponential Sum Function, MathWorld.
Doron Zeilberger, A combinatorial approach to matrix algebra, Discrete Mathematics, 56 (1985), 61-72.
FORMULA
a(n) = Sum_{k=0..n} C(n,k)*D_{n-k}*n^k, where D_n = A000166(n).
a(n) = Sum_{j=0..n} C(n,k)*D_{n-k,2} (n+1)^(j-1) (n-j+1) where D_{n,2} = A087981(n).
a(n) = n! * [x^n] exp((n-1)*x)/(1-x). - Alois P. Heinz, Apr 23 2020
a(n) = exp(n-1)*Gamma(n+1, n-1). - Peter Luschny, Dec 24 2021
From Natalia L. Skirrow, Mar 16 2026: (Start)
E.g.f.: e^(-T)/(1-T)^2, where T = T(x) is the e.g.f. of A000169.
a(n) = n!*e_n(n-1), with e_n the exponential sum function.
a(n) = (n*(Q(n-1)+2) - 1)*(n-1)^(n-1), where Q(n) = Sum_{k=1..n} n!/(k!*n^k) = A063169/n^n is Ramanujan's Q function.
a(n) ~ n!*e^(n-1)/2 * (1 + 5*sqrt(2/(Pi*n))/3 + O(n^(-3/2))).
a(n) = n*A089901(n-1) - (n-1)^(n+1). (End)
MAPLE
a:= n-> n!*coeff(series(exp((n-1)*x)/(1-x), x, n+1), x, n):
seq(a(n), n=0..23); # Alois P. Heinz, Apr 23 2020
# Alternative:
b:= proc(n, k) option remember; `if`(n<1, 1-n,
(n+k-1)*b(n-1, k)+(k-1)*(1-n)*b(n-2, k))
end:
a:= n-> b(n$2):
seq(a(n), n=0..23); # Alois P. Heinz, Apr 23 2020
# Alternative:
b:= proc(n, k) option remember;
`if`(min(n, k)<0, 0, n*b(n-1, k)+(k-1)^n)
end:
a:= n-> b(n$2):
seq(a(n), n=0..23); # Alois P. Heinz, Apr 23 2020
MATHEMATICA
derange[0, z_]:=1; derange[n_, z_]:= Pochhammer[z, n] - Sum[ Binomial[n, k] z^(n-k) derange[k, z], {k, 0, n-1}]; a[n_]:= Sum[ Binomial[n, k] derange[n-k, 1] n^k, {k, 0, n}] ; a/@ Range[0, 10]
derange[0, z_]:=1; derange[n_, z_]:= Pochhammer[z, n] - Sum[ Binomial[n, k] z^(n-k) derange[k, z], {k, 0, n-1}]; a[n_]:= Sum[ Binomial[n, j] derange[n-j, 2] (n+1)^(j-1) (n-j+1), {j, 0, n}]; a/@ Range[0, 10]
(* Alternative: *)
a[n_] := Exp[n - 1] Gamma[n + 1, n - 1];
Table[a[n], {n, 0, 19}] (* Peter Luschny, Dec 24 2021 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Jim Pitman, Mar 19 2013
EXTENSIONS
a(0),a(16)-a(19) from Alois P. Heinz, Apr 23 2020
STATUS
approved