A339987 The number of labeled graphs on 2n vertices that share the same degree sequence as any unrooted binary tree on 2n vertices.

1, 4, 90, 8400, 1426950, 366153480, 134292027870, 67095690261600, 43893900947947050, 36441011093916429000, 37446160423265535041100, 46669357647008722700474400, 69367722399061403579194432500, 121238024532751529573125745790000, 246171692450596203263023527657431250

Offset

1,2

Comments

An unrooted binary tree is a tree in which all non-leaf vertices have degree 3. With 2n vertices there will be n+1 leaves and n-1 internal vertices.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..100 (terms 1..40 from Atabey Kaygun)

Atabey Kaygun, Counting Graphs with a Prescribed Degree Sequence.

Atabey Kaygun, Common LISP program that generates the sequence.

M. Kauers and C. Koutschan, Some D-finite and some possibly D-finite sequences in the OEIS, arXiv:2303.02793 [cs.SC], 2023.

Formula

Conjectured recurrence: 32*(1 + n)*(2 + n)*(1 + 2*n)*(3 + 2*n)*(5 + 2*n)*(7 + 2*n)*(9 + 2*n)*(11589 + 10844*n + 3300*n^2 + 328*n^3)*a(n) - 8*(2 + n)*(3 + 2*n)*(5 + 2*n)*(7 + 2*n)*(9 + 2*n)*(148119 + 232328*n + 129460*n^2 + 30664*n^3 + 2624*n^4)*a(n+1) - 16*(3 + n)*(5 + 2*n)*(7 + 2*n)*(9 + 2*n)*(341634 + 712135*n + 569267*n^2 + 219308*n^3 + 40852*n^4 + 2952*n^5)*a(n+2) + 8*(4 + n)*(7 + 2*n)*(9 + 2*n)*(527520 + 1057879*n + 818282*n^2 + 306380*n^3 + 55672*n^4 + 3936*n^5)*a(n+3) - 2*(5 + n)*(9 + 2*n)*(601452 + 1117119*n + 786236*n^2 + 264028*n^3 + 42472*n^4 + 2624*n^5)*a(n+4) + 3*(4 + n)*(6 + n)*(3717 + 5228*n + 2316*n^2 + 328*n^3)*a(n+5) = 0. - Manuel Kauers and Christoph Koutschan, Mar 01 2023

Conjecture: a(n) ~ 2^(5*n - 1/2) * n^(2*n - 3/2) / (sqrt(Pi) * 3^(n-1) * exp(2*n + 21/16)), based on the recurrence by Manuel Kauers and Christoph Koutschan. - Vaclav Kotesovec, Mar 07 2023

Prog

(PARI) \\ See Links in A295193 for GraphsByDegreeSeq.
a(n) = {if(n==1, 1, my(d=2*n-4, M=GraphsByDegreeSeq(n-1, 3, (p, r)-> subst(deriv(p), x, 1) >= d-6*r), z=(2*n)!/(n-1)!); sum(i=1, matsize(M)[1], my(p=M[i, 1], r=(subst(deriv(p), x, 1)-d)/2); M[i, 2]*z / (2^polcoef(p, 1) * 6^polcoef(p, 0) * 2^r * r!)))} \\ Andrew Howroyd, Mar 01 2023

Crossrefs

Cf. A001147, A001190, A002829.

Sequence in context: A304190 A362603 A274056 * A202918 A146506 A202575

Adjacent sequences: A339984 A339985 A339986 * A339988 A339989 A339990

Keyword

nonn

Author

Atabey Kaygun, Dec 25 2020

Status

approved