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
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..386
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((k-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
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
# second Maple program:
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
# third Maple program:
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