A006714 Number of trivalent bipartite labeled graphs with 2n labeled nodes.

10, 840, 257040, 137260200, 118273755600, 154712104747200, 292311804557572800, 766931112143320924800, 2706462791802644002128000, 12512595130808078973370704000, 74130965352250071944327288640000, 552334353713465817349513210512960000, 5092566798555894395129552704613028960000

Offset: 3

Author

N. J. A. Sloane

Keywords

• nonn

Comments

R. C. Read incorrectly has a(7) = 118257539400 and a(8) = 154678050727200 which he calculated by hand. - Sean A. Irvine, Jun 27 2017

References

• 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).

Links

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

Crossrefs

Cf. A001501, A002829, A004109, A246599.

Programs

Mathematica

(* b stands for A001501 *) b[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;
(* c stands for A246599 *) c[n_] := c[n] = Binomial[2n-1, n] b[n] - Sum[ Binomial[2n-1, 2k] Binomial[2k, k] b[k] c[n-k], {k, 1, n-1}];
a[n_] := a[n] = c[n] + Sum[Binomial[2n-1, 2k-1] c[k] a[n-k], {k, 1, n-1}];
Table[a[n], {n, 3, 20}] (* Jean-François Alcover, Jul 07 2018, after Andrew Howroyd *)

PARI

\\ here b(n) is A001501
b(n) = {n!^2 * sum(j=0, n, sum(i=0, n-j, my(k=n-i-j); (j + 3*k)! / (3^i * 36^k * i! * k!^2)) / (j! * (-2)^j))}
seq(n)={my(v=vector(n,n,b(n)*binomial(2*n-1,n)), u=vector(n), s=vector(n)); for(n=1, #u, u[n]=v[n] - sum(k=3, n-3, 2*binomial(2*n-1,2*k)*v[k]*u[n-k]); s[n]=u[n] + sum(k=3, n-3, binomial(2*n-1,2*k-1)*u[k]*s[n-k])); s[3..n]} \\ Andrew Howroyd, May 22 2018

Formula

a(n) = A246599(n) + Sum_{k=1..n-1} binomial(2*n-1,2*k-1)*A246599(k)*a(n-k). - Andrew Howroyd, May 22 2018

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

Extensions

a(7)-a(8) corrected and a(9)-a(12) computed with nauty by Sean A. Irvine, Jun 27 2017

Terms a(13) and beyond from Andrew Howroyd, May 22 2018