A217701 Permanent of the n X n matrix with all diagonal entries n and all off diagonal entries 1.

1, 1, 5, 38, 393, 5144, 81445, 1512720, 32237681, 775193984, 20759213061, 612623724800, 19751688891385, 690721009155072, 26039042401938917, 1052645311044368384, 45424010394042998625, 2083972769418997760000, 101288683106200561501189, 5199006109868903819575296

Offset: 0

Author

Jim Pitman, Mar 19 2013

Keywords

• nonn

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.

Crossrefs

Also closely related to A058127.

Main diagonal of A089258.

Cf. A176043.

Programs

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

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

Extensions

a(0),a(16)-a(19) from Alois P. Heinz, Apr 23 2020