A002831 -id:A002831 - cp's OEIS frontend

A246598 Erroneous version of A002831.

1, 4, 11, 60, 362, 2987

Offset: 1

N. J. A. Sloane, Sep 08 2014

dead

Included in accordance with the OEIS policy of listing published but incorrect sequences, to serve as pointers to the correct entries.

R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.
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. C. Read, Letter to N. J. A. Sloane, Feb 04 1971

A002829 Number of trivalent (or cubic) labeled graphs with 2n nodes.

Original entry on oeis.org

1, 0, 1, 70, 19355, 11180820, 11555272575, 19506631814670, 50262958713792825, 187747837889699887800, 976273961160363172131825, 6840300875426184026353242750, 62870315446244013091262178375075, 741227949070136911068308523257857500

Offset: 0

N. J. A. Sloane

nonn

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 411.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 279.
I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983.
R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1977.
R. W. Robinson, Computer print-out, no date. Gives first 30 terms.
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).

Alois P. Heinz, Table of n, a(n) for n = 0..160 (first 31 terms from R. W. Robinson)
F. Chyzak, M. Mishna and B. Salvy, Effective D-Finite Symmetric Functions, FPSAC '02 (2002) # 19.12, see Maple output prior to the References.
Élie de Panafieu, Asymptotic expansion of regular and connected regular graphs, arXiv:2408.12459 [math.CO], 2024. See p. 9.
Oleg Evnin and Weerawit Horinouchi, A Gaussian integral that counts regular graphs, arXiv:2403.04242 [cond-mat.stat-mech], 2024. See p. 12.
I. P. Goulden and D. M. Jackson, Labelled graphs with small vertex degrees and P-recursiveness, SIAM J. Algebraic Discrete Methods 7(1986), no. 1, 60-66. MR0819706 (87k:05093)
I. P. Goulden, D. M. Jackson, and J. W. Reilly, The Hammond series of a symmetric function and its application to P-recursiveness, SIAM J. Algebraic Discrete Methods 4 (1983), no. 2, 179-193.
Atabey Kaygun, Enumerating Labeled Graphs that Realize a Fixed Degree Sequence, arXiv:2101.02299 [math.CO], 2021.
Igor Pak, Complexity problems in enumerative combinatorics, arXiv:1803.06636 [math.CO], 2018.
R. C. Read, Letter to N. J. A. Sloane, Feb 04 1971 (gives initial terms of this sequence)
R. W. Robinson, Cubic labeled graphs, computer print-out, n.d.
N. C. Wormald, Enumeration of labelled graphs II: cubic graphs with a given connectivity, J. Lond Math Soc s2-20 (1979) 1-7, eq. (2.6).

A diagonal of A059441. Cf. A005814.

See A004109 for connected graphs of this type.

From R. J. Mathar, Oct 31 2010: (Start)
A002829aux := proc(i) local a,j,k ; a := 0 ; for j from 0 to i do for k from 0 to 2*(i-j) do a := a+(-1)^(j+k)/j!*doublefactorial(2*i+2*k-1)/3^k/k!/(2*i-2*j-k)! ; end do: end do: a*3^i/2^i ; end proc:
A002829 := proc(n) (2*n)!/6^n*add( A002829aux(i)/(n-i)!,i=0..n) ; end proc: seq(A002829(n),n=0..6) ; (End)
egf := hypergeom([1/6, 5/6],[],12*x/(x^2+8*x+4)^(3/2)) * exp(-ln(1/4*x^2+2*x+1)/4 - x/3 + (x^2+8*x+4)^(3/2)/(24*x) - 1/(3*x) - x^2/24 - 1):
ser := convert(series(egf,x=0,30),polynom):
seq(coeff(ser,x,i) * (2*i)!, i=0..degree(ser)); # Mark van Hoeij, Nov 07 2011

Flatten[{1,RecurrenceTable[{2 (-3+n) (-2+n) (-1+n) (-7+2 n) (-5+2 n) (-3+2 n) (-1+2 n) (-4+3 n) (-1+3 n) a[-4+n]-2 (-2+n) (-1+n) (-5+2 n) (-3+2 n) (-1+2 n) (-1+3 n) (43-42 n+9 n^2) a[-3+n]-(-1+n) (-3+2 n) (-1+2 n) (-104+501 n-441 n^2+108 n^3) a[-2+n]-9 (-1+n) (-1+2 n) (-7+3 n) (2-4 n+3 n^2) a[-1+n]+3 (-7+3 n) (-4+3 n) a[n]==0,a[1]==0,a[2]==1,a[3]==70,a[4]==19355},a,{n,1,15}]}] (* Vaclav Kotesovec, Mar 11 2014 *)
terms = 14;
egf = HypergeometricPFQ[{1/6, 5/6}, {}, 12x/(x^2 + 8x + 4)^(3/2)] Exp[-Log[ 1/4 x^2 + 2x + 1]/4 - x/3 + (x^2 + 8x + 4)^(3/2)/(24x) - 1/(3x) - x^2/24 - 1] + O[x]^terms;
CoefficientList[egf, x] (2 Range[0, terms-1])! (* Jean-François Alcover, Nov 23 2018, after Mark van Hoeij *)

a(n) = sum(i=0, 2*n, sum(k=0, min(floor((3*n-i)/3), floor((2*n-i)/2)), sum(j=0, min(floor((3*n-i-3*k)/2), floor((2*n-i-2*k)/2)), ((-1)^(i+j)*(2*n)!*(2*(3*n-i-2*j-3*k))!)/(2^(5*n-i-2*j-4*k)*3^(2*n-i-2*j-k)*(3*n-i-2*j-3*k)!*i!*j!*k!*(2*n-i-2*j-2*k)!)))); \\ Michel Marcus, Jan 18 2018

From Vladeta Jovovic, Mar 25 2001: (Start)
E.g.f. f(x) = Sum_{n >= 0} a(2 * n) * x^n/(2 * n)! satisfies differential equation 6 * x^2 * (-x^2 - 2 * x + 2) * (d^2/dx^2)f(x) - (x^5 + 6 * x^4 + 6 * x^3 - 32 * x + 8) * (d/dx)f(x) + (x/6) * (-x^2 - 2 * x + 2)^2 * f(x) = 0.
Recurrence: a(2 * n) = (2 * n)!/n! * v(n) where 48 * v(n) + (-72 * n^2 + 24 * n + 48) * v(n - 1) + (72 * n^3 - 432 * n^2 + 788 * n - 428) * v(n - 2) + (36 * n^4 - 324 * n^3 + 1052 * n^2 - 1428 * n + 664) * v(n - 3) + (36 * n^4 - 360 * n^3 + 1260 * n^2 - 1800 * n + 864) * v(n - 4) + (6 * n^5 - 94 * n^4 + 550 * n^3 - 1490 * n^2 + 1844 * n - 816) * v(n - 5) + (-n^5 + 15 * n^4 - 85 * n^3 + 225 * n^2 - 274 * n + 120) * v(n - 6) = 0. (End)
a(n) = Sum_{i=0..2*n} Sum_{k=0..min(floor((3*n-i)/3), floor((2*n-i)/2))} Sum_{j=0..min(floor((3*n-i-3*k)/2), floor((2*n-i-2*k)/2))} ((-1)^(i+j)*(2*n)!*(2*(3*n-i-2*j-3*k))!)/(2^(5*n-i-2*j-4*k)*3^(2*n-i-2*j-k)*(3*n-i-2*j-3*k)!*i!*j!*k!*(2*n-i-2*j-2*k)!). - Shanzhen Gao, Jun 05 2009
E.g.f.: hypergeom([1/6, 5/6],[],12*x/(x^2+8*x+4)^(3/2))*exp(-log(1/4*x^2+2*x+1)/4 - x/3 + (x^2+8*x+4)^(3/2)/(24*x) - 1/(3*x) - x^2/24 - 1). Multiply x^i by (2*i)! to get the generating function. - Mark van Hoeij, Nov 07 2011
From Vaclav Kotesovec, Mar 11 2014: (Start)
D-finite with recurrence: 3*(3*n-7)*(3*n-4)*a(n) = 9*(n-1)*(2*n-1)*(3*n-7)*(3*n^2 - 4*n + 2)*a(n-1) + (n-1)*(2*n-3)*(2*n-1)*(108*n^3 - 441*n^2 + 501*n - 104)*a(n-2) + 2*(n-2)*(n-1)*(2*n-5)*(2*n-3)*(2*n-1)*(3*n-1)*(9*n^2 - 42*n + 43)*a(n-3) - 2*(n-3)*(n-2)*(n-1)*(2*n-7)*(2*n-5)*(2*n-3)*(2*n-1)*(3*n-4)*(3*n-1)*a(n-4).
a(n) ~ sqrt(2) * 6^n * n^(3*n) / exp(3*n+2). (End)

More terms from Vladeta Jovovic, Mar 25 2001

A054499 Number of pairings on a bracelet; number of chord diagrams that can be turned over and having n chords.

Original entry on oeis.org

1, 1, 2, 5, 17, 79, 554, 5283, 65346, 966156, 16411700, 312700297, 6589356711, 152041845075, 3811786161002, 103171594789775, 2998419746654530, 93127358763431113, 3078376375601255821, 107905191542909828013, 3997887336845307589431

Offset: 0

Christian G. Bower, Apr 06 2000 based on a problem by Wouter Meeussen

Place 2n points equally spaced on a circle. Draw lines to pair up all the points so that each point has exactly one partner. Allow turning over.

			For n=3, there are 5 bracelets with 3 pairs of beads. They are represented by the words aabbcc, aabcbc, aabccb, abacbc, and abcabc. All of the 6!/(2*2*2) = 90 combinations can be derived from these by some combination of relabeling the pairs, rotation, and reflection. So a(3) = 5. - _Michael B. Porter_, Jul 27 2016

R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.

W. Y.-C. Chen, D. C. Torney, Equivalence classes of matchings and lattice-square designs, Discr. Appl. Math. 145 (3) (2005) 349-357.
Étienne Ghys, A Singular Mathematical Promenade, arXiv:1612.06373 [math.GT], 2016-2017. See p. 252.
A. Khruzin, Enumeration of chord diagrams, arXiv:math/0008209 [math.CO], 2000.
V. A. Liskovets, Some easily derivable sequences, J. Integer Sequences, 3 (2000), #00.2.2.
R. J. Mathar, Chord Diagrams A054499 (2018)
R. J. Mathar, Feynman diagrams of the QED vacuum polarization, vixra:1901.0148 (2019)
R. C. Read, Letter to N. J. A. Sloane, Feb 04 1971 (gives initial terms of this sequence)
Alexander Stoimenow, On the number of chord diagrams, Discr. Math. 218 (2000), 209-233.
Index entries for sequences related to bracelets

Cf. A007769, A104256, A279207, A279208, A003437 (loopless chord diagrams), A322176 (marked chords), A362657, A362658, A362659 (three, four, five instances of each color rather than two), A371305 (Multiset Transf.), A260847 (directed chords).

max = 19;
alpha[p_, q_?EvenQ] := Sum[Binomial[p, 2*k]*q^k*(2*k-1)!!, {k, 0, max}];
alpha[p_, q_?OddQ] := q^(p/2)*(p-1)!!;
a[0] = 1;
a[n_] := 1/4*(Abs[HermiteH[n-1, I/2]] + Abs[HermiteH[n, I/2]] + (2*Sum[Block[{q = (2*n)/p}, alpha[p, q]*EulerPhi[q]], {p, Divisors[ 2*n]}])/(2*n));
Table[a[n], {n, 0, max}] (* Jean-François Alcover, Sep 05 2013, after R. J. Mathar; corrected by Andrey Zabolotskiy, Jul 27 2016 *)

a(n) = (2*A007769(n) + A047974(n) + A047974(n-1))/4 for n > 0.

Corrected and extended by N. J. A. Sloane, Oct 29 2006

a(0)=1 prepended back again by Andrey Zabolotskiy, Jul 27 2016

A001501 Number of n X n 0-1 matrices with all column and row sums equal to 3.

Original entry on oeis.org

1, 0, 0, 1, 24, 2040, 297200, 68938800, 24046189440, 12025780892160, 8302816499443200, 7673688777463632000, 9254768770160124288000, 14255616537578735986867200, 27537152449960680597739468800, 65662040698002721810659005184000

Offset: 0

N. J. A. Sloane

Also, for n >= 3, number of bicubical graphs on 2n labeled nodes of two colors [Read, 1958, 1971] - N. J. A. Sloane, Sep 08 2014

Also number of ways to arrange 3n rooks on an n X n chessboard, with no more than 3 rooks in each row and column (no 4 in a line). - Vaclav Kotesovec, Aug 03 2013

			G.f. = 1 + x^3 + 24*x^4 + 2040*x^5 + 297200*x^6 + 68938800*x^7 + ...

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 236, P(n,3).
R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.
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, Wadsworth, Vol. 1, 1986; see Example 1.1.3, page 2, f(n).
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.

Alois P. Heinz, Table of n, a(n) for n = 0..185 (first 51 terms from T. D. Noe)
R. C. Read, Letter to N. J. A. Sloane, Feb 04 1971 (gives initial terms of this sequence)
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]
Bo-Ying Wang, Fuzhen Zhang, On the precise number of (0,1)-matrices in A(R,S), Discrete Math. 187 (1998), no. 1-3, 211--220. MR1630720 (99f:05010). - From _N. J. A. Sloane_, Jun 07 2012
Index entries for sequences related to binary matrices

Cf. A001499. Column 3 of A008300. Row sums of A284990.

a:= n-> n!^2/6^n *add(add((-1)^b *2^a *3^b *(3*n-3*a-2*b)!/
        (a! *b! *(n-a-b)!^2 *6^(n-a-b)), b=0..n-a), a=0..n):
seq(a(n), n=0..20);  # Alois P. Heinz, Mar 20 2011
# second Maple program:
a:= proc(n) option remember; `if`(n<4, (n-1)*(n-2)/2,
      n*(n-1)*(9*(3*n^2-5*n+4)*a(n-1)+(3*n-6)*(3*n+1)*
      (n-1)*a(n-2)+(9*n^2-30*n+13)*(n-1)*(n-2)^2*a(n-3)
      -(3*n-2)*(n-1)*(n-2)^2*(n-3)^2*a(n-4))/(36*n-60))
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, Mar 13 2017

Table[6^(-n) Total[Map[(-1)^#[[2]] n!^2 (#[[2]] + 3 #[[3]])! 2^#[[1]] 3^#[[2]]/(#[[1]]! #[[2]]! #[[3]]!^2 6^#[[3]]) &, Compositions[n, 3]]], {n, 0, 20}] (* Geoffrey Critzer, Mar 19 2011 *)
a[n_] := n!^2*Sum[2^(2k-n)*3^(k-n)*(3(n-k))!*HypergeometricPFQ[{k-n, k-n}, {3(k-n)/2, 1/2 + 3(k-n)/2}, -9/2]/(k! (n-k )!^2), {k, 0, n}]/6^n;
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jul 07 2018 *)

{a(n) = local(k); if( n<0, 0, n!^2 * sum(j=0, n, sum(i=0, n-j, if(1, k=n-i-j; (j + 3*k)! / (3^i * 36^k * i! * k!^2))) / (j! * (-2)^j)))}; /* Michael Somos, May 28 2002 */

a(n) = n!^2/6^n * Sum_{a=0..n} Sum_{b=0..n-a} (-1)^b * 2^a * 3^b * (3*n-3*a-2*b)! / (a! * b! * (n-a-b)!^2 * 6^(n-a-b)). - Shanzhen Gao, Feb 19 2010
D-finite with recurrence: 12*(3*n-5)*a(n) = 9*n*(3*n^2-5*n+4)*(n-1)*a(n-1) + 3*(n-2)*n*(3*n+1)*(n-1)^2*a(n-2) + (n-2)^2*n*(9*n^2-30*n+13)*(n-1)^2*a(n-3) - (n-3)^2*(n-2)^2*n*(3*n-2)*(n-1)^2*a(n-4). - Vaclav Kotesovec, Aug 03 2013
a(n) ~ sqrt(6*Pi) * (3/4)^n * n^(3*n+1/2) / exp(3*n+2). - Vaclav Kotesovec, Aug 03 2013

Additional comments from Michael Somos, May 28 2002

A000940 Number of n-gons with n vertices.

Original entry on oeis.org

1, 2, 4, 12, 39, 202, 1219, 9468, 83435, 836017, 9223092, 111255228, 1453132944, 20433309147, 307690667072, 4940118795869, 84241805734539, 1520564059349452, 28963120073957838, 580578894859915650, 12217399235411398127, 269291841184184374868, 6204484017822892034404

Offset: 3

N. J. A. Sloane

Number of inequivalent undirected Hamiltonian cycles in complete graph on n labeled nodes under action of dihedral group of order 2n acting on nodes.

			Label the vertices of a regular n-gon 1,2,...,n.
For n=3,4,5 representatives for the polygons counted here are:
  (1,2,3,1),
  (1,2,3,4,1), (1,2,4,3,1),
  (1,2,3,4,5,1), (1,2,3,5,4,1), (1,2,4,5,3,1), (1,3,5,2,4,1).
For n=6:
  (1,2,3,4,5,6,1), (1,2,3,4,6,5,1), (1,2,3,5,6,4,1),
  (1,2,3,6,5,4,1), (1,2,4,3,6,5,1), (1,2,4,6,3,5,1),
  (1,2,4,6,5,3,1), (1,2,5,3,6,4,1), (1,2,5,4,6,3,1),
  (1,2,5,6,3,4,1), (1,2,6,4,5,3,1), (1,3,5,2,6,4,1).

J. H. Kwak and J. Lee, Enumeration of graph coverings, surface branched coverings and related group theory, in Combinatorial and Computational Mathematics (Pohang, 2000), ed. S. Hong et al., World Scientific, Singapore 2001, pp. 97-161.
R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.
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).

Ludovic Schwob, Table of n, a(n) for n = 3..500 (terms 3..100 from T. D. Noe).
S. W. Golomb and L. R. Welch, On the enumeration of polygons, Amer. Math. Monthly, 67 (1960), 349-353.
S. W. Golomb and L. R. Welch, On the enumeration of polygons, Amer. Math. Monthly, 67 (1960), 349-353. [Annotated scanned copy]
Samuel Herman and Eirini Poimenidou, Orbits of Hamiltonian Paths and Cycles in Complete Graphs, arXiv:1905.04785 [math.CO], 2019.
E. M. Palmer and R. W. Robinson, Enumeration under two representations of the wreath product, Acta Math., 131 (1973), 123-143.
R. C. Read, Letter to N. J. A. Sloane, Feb 04 1971 (gives initial terms of this sequence, except he has a(6)=7 instead of 12)
R. C. Read, Letter to N. J. A. Sloane, 1992
R. C. Read, Combinatorial problems in theory of music, Discrete Math. 167 (1997), 543-551.
Ludovic Schwob, On the enumeration of double cosets and self-inverse double cosets, arXiv:2506.04007 [math.CO], 2025. See p. 9.
N. J. A. Sloane, Illustration of initial terms [Annotated page from Golomb-Welch article]
Venta Terauds and J. Sumner, Circular genome rearrangement models: applying representation theory to evolutionary distance calculations, arXiv preprint arXiv:1712.00858 [q-bio.PE], 2017.
Venta Terauds and Jeremy Sumner, A new algebraic approach to genome rearrangement models, arXiv:2012.11665 [q-bio.PE], 2020.

Cf. A000939, A007619. Bisections give A094156, A094157.

For permutation classes under various symmetries see A089066, A262480, A002619.

with(numtheory);
# for n odd:
Sd:=proc(n) local t1,d; t1:=2^((n-1)/2)*n^2*((n-1)/2)!; for d from 1 to n do if n mod d = 0 then t1:=t1+phi(n/d)^2*d!*(n/d)^d; fi; od: t1/(4*n^2); end;
# for n even:
Se:=proc(n) local t1,d; t1:=2^(n/2)*n*(n+6)*(n/2)!/4; for d from 1 to n do if n mod d = 0 then t1:=t1+phi(n/d)^2*d!*(n/d)^d; fi; od: t1/(4*n^2); end;
A000940:=n-> if n mod 2 = 0 then Se(n) else Sd(n); fi;

a[n_] := (t1 = If[OddQ[n], 2^((n - 1)/2)*n^2*((n - 1)/2)!, 2^(n/2)*n*(n + 6)*(n/2)!/4]; For[ d = 1 , d <= n, d++, If[Mod[n, d] == 0, t1 = t1 + EulerPhi[n/d]^2*d!*(n/d)^d]]; t1/(4*n^2)); Table[a[n], {n, 3, 25}] (* Jean-François Alcover, Jun 19 2012, after Maple *)

a(n)={if(n<3, 0, (2^(n\2-2)*(n\2)!*n*if(n%2, 4*n, n + 6) + sumdiv(n, d, eulerphi(n/d)^2*d!*(n/d)^d))/(4*n^2))} \\ Andrew Howroyd, Sep 09 2018

from sympy import factorial, divisors, totient
def A000940(n): return 1 if n == 3 else ((sum(totient(m:=n//d)**2*factorial(d)*m**d for d in divisors(n,generator=True))+(1<<(k:=n>>1)-2)*n*(n<<2 if n&1 else (n+6))*factorial(k))>>2)//n//n # Chai Wah Wu, Nov 07 2022

For formula see Maple lines.
a(p) = ((((p-1)! + 1)/p) + p - 2 + (2^((p-1)/2)*((p-1)/2)!))/4 for prime p. See A007619. - Ian Mooney, Oct 05 2022
a(n) ~ sqrt(2*Pi)/4 * n^(n-3/2) / e^n. - Ludovic Schwob, Nov 03 2022

More terms from Pab Ter (pabrlos(AT)yahoo.com), May 05 2004

A001500 Number of stochastic matrices of integers: n X n arrays of nonnegative integers with all row and column sums equal to 3.

Original entry on oeis.org

1, 1, 4, 55, 2008, 153040, 20933840, 4662857360, 1579060246400, 772200774683520, 523853880779443200, 477360556805016931200, 569060910292172349004800, 868071731152923490921728000, 1663043727673392444887284377600, 3937477620391471128913917360384000

Offset: 0

N. J. A. Sloane

Also, number of bicubical multigraphs on 2n labeled nodes of two colors [Read, 1958, 1971]. - N. J. A. Sloane, Sep 09 2014

			a(2) = 4 with: [0 3]    [1 2]    [2 1]    [3 0]
               [3 0],   [2 1],   [1 2],   [0 3]. - _Bernard Schott_, Oct 15 2019

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 125, Problem 25(4), b_n (but beware errors).
I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983.
R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.
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).
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.

Alois P. Heinz, Table of n, a(n) for n = 0..180
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.
Petter Brändén, Jonathan Leake, Igor Pak, Lower bounds for contingency tables via Lorentzian polynomials, arXiv:2008.05907 [math.CO], 2020.
I. P. Goulden, D. M. Jackson, and J. W. Reilly, The Hammond series of a symmetric function and its application to P-recursiveness, SIAM J. Algebraic Discrete Methods 4 (1983), no. 2, 179-193.
R. C. Read, Letter to N. J. A. Sloane, Feb 04 1971 (gives initial terms of this sequence, although there are errors)
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

Row sums of A269743 and of A344379.
Column k=3 of A257493.
Cf. A000681, A246970.

a[n_] := 6^(-n) Sum[2^j 3^k n!^2 (3n - 2k - 3j)!/(j! k! (n - j - k)!^2 * 6^(n - j - k)), {j, 0, n}, {k, 0, n - j}];
a /@ Range[0, 15] (* Jean-François Alcover, Oct 15 2019, after Shanzhen Gao *)

From Vladeta Jovovic, Mar 26 2001: (Start)
E.g.f. y(x) = Sum_{n >= 0} a(n)*x^n/(n!)^2 satisfies differential equation 81*x^5*(x^4 - x^2 + x + 4)*(d^4/dx^4)y(x) + 324*x^4*(x^4 - x^2 + x + 4)*(d^3/dx^3)y(x) - 9*x*(x^10 - 4*x^9 + 22*x^8 - 8*x^7 - 22*x^6 + 8*x^5 + 106*x^4 + 234*x^3 + 48*x^2 - 320*x + 64)*(d^2/dx^2)y(x) - 9*(x^10 - 4*x^9 + 22*x^8 - 8*x^7 - 4*x^6 + 8*x^5 + 88*x^4 + 252*x^3 + 120*x^2 - 320*x + 64)*(d/dx)y(x) + (x^11 - 7*x^10 + 30*x^9 - 16*x^8 - 43*x^7 + 51*x^6 + 238*x^5 + 630*x^4 + 36*x^3 - 1944*x^2 - 1152*x + 576)*y(x) = 0.
Recurrence: a(n) = n!*v(n) where v(n) = 1/(576*n)*((-198*n^9 + 8712*n^8 - 165175*n^7 + 1764196*n^6 - 11643772*n^5 + 48965728*n^4 - 130257475*n^3 + 209370724*n^2 - 182126340*n + 64083600)*v(n - 8) + (36*n^10 - 1944*n^9 + 45884*n^8 - 621504*n^7 + 5330892*n^6 - 30123576*n^5 + 112954596*n^4 - 275612976*n^3 + 415021552*n^2 - 343920960*n + 116928000)*v(n - 9) + (-9*n^11 + 585*n^10 - 16800*n^9 + 280800*n^8 - 3027357*n^7 + 22034565*n^6 - 110039130*n^5 + 375129450*n^4 - 849926784*n^3 + 1208298600*n^2 - 958439520*n + 315705600)*v(n - 10) + (-7*n^10 + 385*n^9 - 9240*n^8 + 127050*n^7 - 1104411*n^6 + 6314385*n^5 - 23918510*n^4 + 58866500*n^3 - 89275032*n^2 + 74400480*n - 25401600)*v(n - 11) + (-81*n^7 + 1944*n^6 - 20232*n^5 + 115578*n^4 - 383283*n^3 + 724230*n^2 - 708372*n + 270216)*v(n - 4) + (-72*n^6 + 1440*n^5 - 10890*n^4 + 40500*n^3 - 78678*n^2 + 75780*n - 28080)*v(n - 5) + (81*n^9 - 3321*n^8 + 59004*n^7 - 594054*n^6 + 3718687*n^5 - 14927199*n^4 + 38152096*n^3 - 59311746*n^2 + 50236612*n - 17330160)*v(n - 6) + (72*n^8 - 2520*n^7 + 37347*n^6 - 304479*n^5 + 1484133*n^4 - 4394565*n^3 + 7642248*n^2 - 7039116*n + 2576880)*v(n - 7) + (n^11 - 66*n^10 + 1925*n^9 - 32670*n^8 + 357423*n^7 - 2637558*n^6 + 13339535*n^5 - 45995730*n^4 + 105258076*n^3 - 150917976*n^2 + 120543840*n - 39916800)*v(n - 12) + (2880*n^2 - 5760*n + 3456)*v(n - 1) + (324*n^5 - 3564*n^4 + 14148*n^3 - 26028*n^2 + 21312*n - 6192)*v(n - 2) + (81*n^6 - 1377*n^5 + 7209*n^4 - 13203*n^3 - 3402*n^2 + 32076*n - 21384)*v(n - 3)). (End)
a(n) = 6^(-n) * Sum_{ alpha = 0..n, beta = 0..n-alpha } (2^alpha*3^beta*(n!)^2*(-2*beta+3*n-3*alpha)!)/(alpha!*beta!*(n-alpha-beta)!^2*6^(n-alpha-beta)). - Shanzhen Gao, Nov 05 2007
a(n) ~ sqrt(Pi) * 3^(n + 1/2) * n^(3*n + 1/2) / (2^(2*n - 1/2) * exp(3*n - 2)). - Vaclav Kotesovec, Oct 15 2019

More terms from Vladeta Jovovic, Mar 26 2001

A004109 Number of connected trivalent (or cubic) labeled graphs with 2n nodes.

Original entry on oeis.org

1, 0, 1, 70, 19320, 11166120, 11543439600, 19491385914000, 50233275604512000, 187663723374359232000, 975937986889287117696000, 6838461558851342749449120000, 62856853767402275979616458240000, 741099150663748252073618880960000000, 10997077750618335243742188527076864000000

Offset: 0

N. J. A. Sloane

			From _R. J. Mathar_, Oct 18 2018: (Start)
For n=3, 2*n=6, the A002851(n)=2 graphs have multiplicities of 10 and 60 (sum 70).
For n=4, 2*n=8, the A002851(n)=5 graphs have multiplicities of 3360, 840, 2520, 10080 and 2520, (sum 19320). (The orders of the five Aut-groups are 8!/3360 =12, 8!/840=48, 8!/2520 =16, 8!/10080=4 and 8!/2520=16, i.e., all larger than 1 as indicated in A204328). (End)

R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
R. W. Robinson, Computer print-out, no date. Gives first 29 terms.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 0..100 (terms 1..29 from R. W. Robinson)
Élie de Panafieu, Asymptotic expansion of regular and connected regular graphs, arXiv:2408.12459 [math.CO], 2024. See p. 13.
R. C. Read, Letter to N. J. A. Sloane, Feb 04 1971 (gives initial terms of this sequence)
R. W. Robinson, Cubic labeled graphs, computer print-out, n.d.

See A002829 for not-necessarily-connected graphs, A002851 for connected unlabeled cases.

Cf. A324163.

Conjecture: a(n) ~ 2^(n + 1/2) * 3^n * n^(3*n) / exp(3*n+2). - Vaclav Kotesovec, Feb 17 2024

a(0)=1 prepended by Andrew Howroyd, Sep 02 2019

A006712 Number of 3-edge-colored trivalent graphs with 2n labeled nodes.

Original entry on oeis.org

6, 480, 197820, 150474240, 208857587400, 471804812519040, 1625459273858019600, 8112729590064978278400, 56342429224416522460072800, 527075322501595757416502976000, 6466573585901882433727764077860800, 101749747195531624711768653503416320000

Offset: 2

N. J. A. Sloane

nonn

R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 2..50
Sean A. Irvine, Illustration of initial terms
R. C. Read, Letter to N. J. A. Sloane, Feb 04 1971 (gives initial terms of this sequence)

Cf. A006713 (for connected cases), A248361 (for the incorrect values). See also A002830, A002831, A005638.

dpermcount(v) = {my(m=1,s=0,k=0,t); for(i=1,#v,t=v[i]; k=if(i>1&&t==v[i-1],k+1,1); m*=2*t*k;s+=2*t); s!/m}
S(n,x)={vector(n, n, if(n>1, sum(k=0, n, binomial(2*n-k,k)*2*n/(2*n-k)*x^k), 0))}
q(n,s)={my(t=0); if(n>1, forpart(p=n, t+=dpermcount(p)*prod(i=1, #p, s[p[i]]), [2,n])); t}
a(n)={my(p=q(n,S(n,x))); sum(i=0, poldegree(p), polcoeff(p,n-i)*(-1)^(n-i)*(2*i)!/(2^i*i!))} \\ Andrew Howroyd, Dec 18 2017

a(5)-a(6) corrected and a(7)-a(10) from Sean A. Irvine, Oct 05 2014

Terms a(11) and beyond from Andrew Howroyd, Dec 18 2017

A006713 Number of 3-edge-colored connected trivalent graphs with 2n labeled nodes.

Original entry on oeis.org

6, 480, 196560, 149869440, 208166112000, 470619551001600, 1622357050938624000, 8100931274981056512000, 56279222605087617687552000, 526611567858781597240688640000, 6462027944190599588931310387200000, 101691538301880025620001692844032000000

Offset: 2

N. J. A. Sloane

nonn

R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 2..50
R. C. Read, Letter to N. J. A. Sloane, Feb 04 1971 (gives initial terms of this sequence)

Cf. A006712 (for not necessarily connected graphs), A248362 (for the incorrect values). See also A002830, A002831, A002851.

a(5)-a(6) corrected and a(7)-a(10) from Sean A. Irvine, Oct 05 2014

Terms a(11) and beyond from Andrew Howroyd, Dec 18 2017

A002830 Number of 3-edge-colored trivalent graphs with 2n nodes.

Original entry on oeis.org

1, 1, 5, 16, 86, 448, 3580, 34981, 448628, 6854130, 121173330, 2403140605, 52655943500, 1260724587515, 32726520985365, 915263580719998, 27432853858637678, 877211481667946811, 29807483816421710806, 1072542780403547030073, 40739888428757581326987

Offset: 0

N. J. A. Sloane

nonn

R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.
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).

Andrew Howroyd, Table of n, a(n) for n = 0..200
Nicholas Dub, Enumeration of triangulations modulo symmetries and of rooted triangulations counted by their number of (d - 2)-simplices in dimension d ≥ 2, tel-03641958 [cs.OH], Université Paris-Nord - Paris XIII, 2021.
Sean A. Irvine, Illustration of initial terms
R. C. Read, Letter to N. J. A. Sloane, Feb 04 1971 (gives initial terms of this sequence)

Cf. A002831, A006712, A006713.

permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t k; s += t]; s!/m];
b[k_, q_] := If[OddQ[q], If[OddQ[k], 0, j = k/2; q^j (2 j)!/(j! 2^j)], Sum[ Binomial[k, 2 j] q^j (2 j)!/(j! 2^j), {j, 0, Quotient[k, 2]}]];
pm[v_] := Module[{p = Total[x^v]}, Product[b[Coefficient[p, x, i], i], {i, 1, Exponent[p, x]}]];
a[n_] := Module[{s = 0}, Do[s += permcount[p] pm[p]^3, {p, IntegerPartitions[2 n]}]; s/(2 n)!];
Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 1, 30}] (* Jean-François Alcover, Jul 02 2018, after Andrew Howroyd *)

b(k,r) = {if(k%2, if(r%2, 0, my(j=r/2); k^j*(2*j)!/(j!*2^j)), sum(j=0, r\2, binomial(r, 2*j)*k^j*(2*j)!/(j!*2^j)))}
g(n,k)={sum(r=0, n\k,  x^(k*r)*b(k,r)^3/(r!*k^r)) + O(x*x^n)}
seq(n)={Vec(substpol(prod(k=1, 2*n, g(2*n,k)), x^2, x))} \\ Andrew Howroyd, Dec 14 2017; updated May 02 2023

G.f.: exp(Sum_{k >= 1} F(x^k) / k) where F(x) is the g.f. for A002831. - Sean A. Irvine, Sep 09 2014

a(7)-a(8) from Sean A. Irvine, Sep 08 2014
Terms a(9) and beyond from Andrew Howroyd, Dec 14 2017
a(0)=1 prepended by Andrew Howroyd, May 02 2023

cp's OEIS Frontend

A246598 Erroneous version of A002831.

Views

Author

Keywords

Comments

References

Links

A002829 Number of trivalent (or cubic) labeled graphs with 2n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A054499 Number of pairings on a bracelet; number of chord diagrams that can be turned over and having n chords.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A001501 Number of n X n 0-1 matrices with all column and row sums equal to 3.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A000940 Number of n-gons with n vertices.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A001500 Number of stochastic matrices of integers: n X n arrays of nonnegative integers with all row and column sums equal to 3.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A004109 Number of connected trivalent (or cubic) labeled graphs with 2n nodes.

Views