A307804 -id:A307804 - cp's OEIS frontend

A000681 Number of n X n matrices with nonnegative entries and every row and column sum 2.

1, 1, 3, 21, 282, 6210, 202410, 9135630, 545007960, 41514583320, 3930730108200, 452785322266200, 62347376347779600, 10112899541133589200, 1908371363842760216400, 414517594539154672566000, 102681435747106627787376000, 28772944645196614863048048000

Offset: 0

N. J. A. Sloane, Simon Plouffe

Or, number of labeled 2-regular pseudodigraphs (multiple arcs and loops allowed) of order n.

Also, number of permutations of the multiset {1^2,2^2,...,n^2} with the descent set consisting of multiples of 2. - Max Alekseyev, Apr 28 2014

			G.f. = 1 + x + 3*x^2 + 21*x^3 + 282*x^4 + 6210*x^5 + 202410*x^6 + 9135630*x^7 + ...

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 125, #25, a_n.
I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983, section 3.5.10.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1982.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Cor. 5.5.11 (a).
M. L. Stein and P. R. Stein, Enumeration of Stochastic Matrices with Integer Elements. Report LA-4434, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Jun 1970.
C. B. Tompkins, Methods of successive restrictions in computational problems involving discrete variables. 1963, Proc. Sympos. Appl. Math., Vol. XV pp. 95-106; Amer. Math. Soc., Providence, R.I.

Alois P. Heinz, Table of n, a(n) for n = 0..250 (first 49 terms from R. W. Robinson)
H. Anand, V. C. Dumir and H. Gupta, A combinatorial distribution problem, Duke Math. J., 33 (1996), 757-769.
Esther M. Banaian, Generalized Eulerian Numbers and Multiplex Juggling Sequences, (2016). All College Thesis Program. Paper 24.
E. Banaian, S. Butler, C. Cox, J. Davis, J. Landgraf and S. Ponce A generalization of Eulerian numbers via rook placements, arXiv:1508.03673 [math.CO], 2015.
S. Cockburn and J. Lesperance, Deranged socks, Mathematics Magazine, 86 (2013), 97-109.
Ira Gessel, Enumerative applications of symmetric functions, Séminaire Lotharingien de Combinatoire, B17a (1987), 17 pp.
William George Griffiths, On Integer Solutions to Linear Equations, Annals of Combinatorics 12:1 (2008), pp. 53-70.
Rui-Li Liu, Feng-Zhen Zhao, New Sufficient Conditions for Log-Balancedness, With Applications to Combinatorial Sequences, J. Int. Seq., Vol. 21 (2018), Article 18.5.7.
Richard J. Mathar, 2-regular Digraphs of the Lovelock Lagrangian, arXiv:1903.12477 [math.GM], 2019.
M. L. Stein and P. R. Stein, Enumeration of Stochastic Matrices with Integer Elements, Report LA-4434, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Jun 1970. [Annotated scanned copy]
Index entries for sequences related to magic squares

Column k=2 of A257493.
Row sums of A269742 and A307804.
Row and column sums equal s: A000142 (s=1), A001500 (s=3), A172806 (s=4), A172862 (s=5), A172894 (s=6), A172919 (s=7), A172944 (s=8), A172958 (s=9).
Cf. A001499, A005650, A123544.

A000681 := proc(n)
    coeftayl( exp(x/2)/sqrt(1-x),x=0,n) ;
    %*(n!)^2 ;
end proc:
seq(A000681(n),n=0..10) ; # R. J. Mathar, May 01 2019

a[n_] := Sum[ ((2*i)!*n!^2) / (2^i*(i!^2*(n - i)!)), {i, 0, n}]/2^n; Table[ a[n], {n, 0, 17}] (* Jean-François Alcover, Dec 08 2011 *)
a[n_] := n!*HypergeometricPFQ[{1/2, -n}, {}, -2]/2^n; Table[a[n], {n, 0, 17}] (* Jean-François Alcover, Aug 08 2012 *)

Vec( serlaplace(serlaplace( exp(x/2)/sqrt(1-x) )) ) /* Max Alekseyev, Apr 28 2014 */

from sage.combinat.integer_matrices import IntegerMatrices
def a(n): return IntegerMatrices([2]*n, [2]*n).cardinality() # Ralf Stephan, Mar 02 2014

Sum_{n >= 0} a(n) x^n / n!^2 = exp(x/2) / sqrt(1-x).
D-finite with recurrence a(n) = n^2*a(n-1) - (1/2)*n*(n-1)^2*a(n-2).
a(n) is asymptotic to c/sqrt(n)*(n!)^2 where c=0.93019... - Benoit Cloitre, Jun 25 2004
a(n) = sum(i=0..n, 2^(i-2*n) * C(n, i)^2 * (2*n-2*i)! * i! ).
a(n) = 2^(-n) * sum(i=0..n, ((n!)^2*(2*i)!) / ((i!)^2*((n-i)!*2^i)) ). - Shanzhen Gao, Nov 05 2007
In Cloitre's formula is c = exp(1/2)/sqrt(Pi) = 0.9301913671026328586. - Vaclav Kotesovec, Aug 12 2013
With c as used above by Cloitre and Kotesovec, a(n) is asymptotic to c/sqrt(n)*(n!)^2 * (1 + 2/(16*n) + 50/(16*n)^2 + 1100/(16*n)^3 + 32438/(16*n)^4 + 1185660/(16*n)^5 + 50498228/(16*n)^6 + 2438464600/(16*n)^7 + 131323987366/(16*n)^8 + 7782036656108/(16*n)^9 + 501905392385436/(16*n)^10 + ...). - Jon E. Schoenfield, Mar 03 2014
E.g.f.: 2/((2-x)*W(0)), where W(k) = 1 - (2*k+1)*x/(2-x-2*(k+1)*x/W(k+1)); (continued fraction). - Sergei N. Gladkovskii, Nov 25 2014

More terms from David W. Wilson

A123543 Number of connected labeled 2-regular pseudodigraphs (multiple arcs and loops allowed) of order n.

Original entry on oeis.org

0, 1, 2, 14, 201, 4704, 160890, 7538040, 462869190, 36055948320, 3474195588360, 405786523413600, 56502317464777800, 9248640671612865600, 1758505909558569771600, 384399253128691423022400, 95737858067835530264718000, 26952922550751326069548608000

Offset: 0

N. J. A. Sloane, Nov 13 2006

nonn

R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1982.

Alois P. Heinz, Table of n, a(n) for n = 0..253 (first 49 terms from R. W. Robinson)

Connected version of A000681.
First column of A307804.
Cf. A123544.

b:= proc(n) option remember; `if`(n<2, 1,
      n^2*b(n-1)-n*(n-1)^2*b(n-2)/2)
    end:
a:= proc(n) option remember; `if`(n=0, 0, b(n)-
      add(j*binomial(n, j)*b(n-j)*a(j), j=1..n-1)/n)
    end:
seq(a(n), n=0..17);  # Alois P. Heinz, Mar 22 2025

m = 16;
a681[n_] := n!*HypergeometricPFQ[{1/2, -n}, {}, -2]/2^n;
egf = Log[1 + Sum[a681[k] x^k/k!, {k, 1, m}]];
CoefficientList[egf + O[x]^m, x] Range[0, m-1]! (* Jean-François Alcover, Aug 26 2019 *)

seq(n)={Vec(serlaplace(log(serlaplace(exp(x/2 + O(x*x^n))/sqrt(1-x + O(x*x^n))))), -(n+1))}; \\ Andrew Howroyd, Sep 09 2018

E.g.f.: log(1 + Sum_{k>0} A000681(k)*x^k/k!). - Andrew Howroyd, Sep 09 2018

a(n) ~ 2 * sqrt(Pi) * n^(2*n + 1/2) / exp(2*n - 1/2). - Vaclav Kotesovec, Jul 11 2025

A344379 Triangle read by rows: T(n,k) is the number of labeled 3-regular digraphs (multiple arcs and loops allowed) on n nodes with k components.

Original entry on oeis.org

1, 3, 1, 45, 9, 1, 1782, 207, 18, 1, 142164, 10260, 585, 30, 1, 19943830, 953424, 35235, 1305, 45, 1, 4507660380, 151369792, 3731049, 93555, 2520, 63, 1, 1540185346560, 38205961380, 657600076, 11122209, 211680, 4410, 84, 1, 757560406751120, 14455803484728

Offset: 1

R. J. Mathar, May 16 2021

Derived by interpreting A001500 as the number of labeled 3-regular digraphs (in-degree and out-degree at each node=3), without regarding the trace (which means loops are allowed) and no limit on the individual entries (so multiple arcs in the same direction between nodes are allowed).

Then the formula of A123543 (Gilbert's article) allows these values to be refined by the number of weakly connected components.

			Triangle begins:
              1;
              3,           1;
             45,           9,         1;
           1782,         207,        18,        1;
         142164,       10260,       585,       30,      1;
       19943830,      953424,     35235,     1305,     45,    1;
     4507660380,   151369792,   3731049,    93555,   2520,   63,  1;
  1540185346560, 38205961380, 657600076, 11122209, 211680, 4410, 84, 1;
...

E. N. Gilbert, Enumeration of labelled graphs, Can. J. Math. 8 (1956) 405-411.

Cf. A307804 (2-regular analog), A001500 (row sums), A045943 (subdiagonal).

# Given a list L[1], L[2],... for labeled not necessarily connected graphs, generate
# triangle of labeled graphs with k weakly connected components.
lblNonc := proc(L::list)
    local k,x,g,Lkx,t,Lkxt,n,c ;
    add ( op(k,L)*x^k/k!,k=1..nops(L)) ;
    log(1+%) ; # formula from A123543
    g := taylor(%,x=0,nops(L)) ;
    seq( coeftayl(g,x=0,i)*i!,i=1..nops(L)) ;
    print(lc) ;# first column
    Lkx := add ( coeftayl(g,x=0,i)*x^i,i=1..nops(L)) ;
    Lkxt := exp(t*%) ;
    for n from 0 to nops(L)-1 do
        tmp := coeftayl(Lkxt,x=0,n) ;
        for c from 0 to n do
            printf("%a ", coeftayl(tmp,t=0,c)*n!) ;
        end do:
        printf("\n") ;
    end do:
end proc:
L := [1, 4, 55, 2008, 153040, 20933840, 4662857360, 1579060246400, 772200774683520, 523853880779443200, 477360556805016931200, 569060910292172349004800, 868071731152923490921728000, 1663043727673392444887284377600, 3937477620391471128913917360384000] ;
lblNonc(L) ;

T(n,n) = 1. [n nodes, each with a triple loop].
T(n,n-1) = A045943(n-1). [n-1 isolated nodes, one labeled pair with n(n-1)/2 choices of labels and 3 choices of zero, one or two loops at the lower label].
T(n,k) = Sum_{Compositions n=n_1+n_2+...n_k, n_i>=1} multinomial(n; n_1,n_2,...,n_k) * T(n_1,1) * T(n_2,1) * ... *T(n_k,1) / k!.

cp's OEIS Frontend

A000681 Number of n X n matrices with nonnegative entries and every row and column sum 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

Extensions

A123543 Number of connected labeled 2-regular pseudodigraphs (multiple arcs and loops allowed) of order n.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A344379 Triangle read by rows: T(n,k) is the number of labeled 3-regular digraphs (multiple arcs and loops allowed) on n nodes with k components.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula