login
Number of trivalent bipartite labeled graphs with 2n labeled nodes.
(Formerly M4757)
2

%I M4757 #26 Feb 17 2024 05:45:49

%S 10,840,257040,137260200,118273755600,154712104747200,

%T 292311804557572800,766931112143320924800,2706462791802644002128000,

%U 12512595130808078973370704000,74130965352250071944327288640000,552334353713465817349513210512960000,5092566798555894395129552704613028960000

%N Number of trivalent bipartite labeled graphs with 2n labeled nodes.

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

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

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Andrew Howroyd, <a href="/A006714/b006714.txt">Table of n, a(n) for n = 3..50</a>

%H R. C. Read, <a href="/A002831/a002831.pdf">Letter to N. J. A. Sloane, Feb 04 1971</a> (gives initial terms of this sequence)

%F 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

%F a(n) ~ 3^(n + 1/2) * n^(3*n) / (sqrt(2) * exp(3*n+2)). - _Vaclav Kotesovec_, Feb 17 2024

%t (* 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;

%t (* 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}];

%t a[n_] := a[n] = c[n] + Sum[Binomial[2n-1, 2k-1] c[k] a[n-k], {k, 1, n-1}];

%t Table[a[n], {n, 3, 20}] (* _Jean-François Alcover_, Jul 07 2018, after _Andrew Howroyd_ *)

%o (PARI) \\ here b(n) is A001501

%o 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))}

%o 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

%Y Cf. A001501, A002829, A004109, A246599.

%K nonn

%O 3,1

%A _N. J. A. Sloane_

%E a(7)-a(8) corrected and a(9)-a(12) computed with nauty by _Sean A. Irvine_, Jun 27 2017

%E Terms a(13) and beyond from _Andrew Howroyd_, May 22 2018