login
A339987
The number of labeled graphs on 2n vertices that share the same degree sequence as any unrooted binary tree on 2n vertices.
3
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)
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
KEYWORD
nonn
AUTHOR
Atabey Kaygun, Dec 25 2020
STATUS
approved