cp's OEIS Frontend

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

%I A217701 #31 Dec 24 2021 09:44:07
%S A217701 1,1,5,38,393,5144,81445,1512720,32237681,775193984,20759213061,
%T A217701 612623724800,19751688891385,690721009155072,26039042401938917,
%U A217701 1052645311044368384,45424010394042998625,2083972769418997760000,101288683106200561501189,5199006109868903819575296
%N A217701 Permanent of the n X n matrix with all diagonal entries n and all off diagonal entries 1.
%C A217701 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.
%C A217701 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.
%C A217701 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.
%C A217701 Number of permutations of [n] where the fixed points are n-colored and all other points are unicolored. - _Alois P. Heinz_, Apr 23 2020
%H A217701 Alois P. Heinz, <a href="/A217701/b217701.txt">Table of n, a(n) for n = 0..386</a>
%H A217701 Doron Zeilberger, <a href="https://doi.org/10.1016/0012-365X(85)90192-X">A combinatorial approach to matrix algebra</a>, Discrete Mathematics, 56 (1985), 61-72.
%F A217701 a(n) = Sum_{k=0..n} C(n,k)*D_{n-k}*n^k, where D_n = A000166(n).
%F A217701 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).
%F A217701 a(n) = n! * [x^n] exp((k-1)*x)/(1-x). - _Alois P. Heinz_, Apr 23 2020
%F A217701 a(n) = exp(n-1)*Gamma(n+1, n-1). - _Peter Luschny_, Dec 24 2021
%p A217701 a:= n-> n!*coeff(series(exp((n-1)*x)/(1-x), x, n+1), x, n):
%p A217701 seq(a(n), n=0..23);  # _Alois P. Heinz_, Apr 23 2020
%p A217701 # second Maple program:
%p A217701 b:= proc(n, k) option remember; `if`(n<1, 1-n,
%p A217701       (n+k-1)*b(n-1, k)+(k-1)*(1-n)*b(n-2, k))
%p A217701     end:
%p A217701 a:= n-> b(n$2):
%p A217701 seq(a(n), n=0..23);  # _Alois P. Heinz_, Apr 23 2020
%p A217701 # third Maple program:
%p A217701 b:= proc(n, k) option remember;
%p A217701       `if`(min(n, k)<0, 0, n*b(n-1, k)+(k-1)^n)
%p A217701     end:
%p A217701 a:= n-> b(n$2):
%p A217701 seq(a(n), n=0..23);  # _Alois P. Heinz_, Apr 23 2020
%t A217701 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]
%t A217701 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]
%t A217701 (* Alternative: *)
%t A217701 a[n_] := Exp[n - 1] Gamma[n + 1, n - 1];
%t A217701 Table[a[n], {n, 0, 19}]  (* _Peter Luschny_, Dec 24 2021 *)
%Y A217701 Also closely related to A058127.
%Y A217701 Main diagonal of A089258.
%Y A217701 Cf. A176043.
%K A217701 nonn
%O A217701 0,3
%A A217701 _Jim Pitman_, Mar 19 2013
%E A217701 a(0),a(16)-a(19) from _Alois P. Heinz_, Apr 23 2020