A289666 a(n) = number of weakly threshold graphs on n nodes.

0, 1, 2, 4, 9, 21, 52, 134, 355, 957, 2608, 7154, 19701, 54379, 150302, 415762, 1150609, 3185147, 8818620, 24418128, 67615743, 187239359, 518506932, 1435875288, 3976322869, 11011542937, 30494088494, 84446895364, 233857897749, 647620493541

Offset: 0

Author

N. J. A. Sloane, Jul 25 2017

Keywords

• nonn
• easy

Links

• Colin Barker, Table of n, a(n) for n = 0..1000
• Michael D. Barrus, Weakly threshold graphs, arXiv preprint arXiv:1608.01358 [math.CO], 2016. See W(x).
• Index entries for linear recurrences with constant coefficients, signature (4,-3,-1,0,-1).

Programs

Mathematica

a = DifferenceRoot[Function[{a, n}, {a[n] + a[n+2] + 3a[n+3] - 4a[n+4] + a[n+5] == 0, a[0]==0, a[1]==1, a[2]==2, a[3]==4, a[4]==9, a[5]==21}]];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jan 09 2019 *)
LinearRecurrence[{4,-3,-1,0,-1},{0,1,2,4,9,21},30] (* Harvey P. Dale, Sep 15 2024 *)

PARI

concat(0, Vec(x*(1 - 2*x - x^2 - x^4) / ((1 - x - x^2)*(1 - 3*x + x^2 - x^3)) + O(x^30))) \\ Colin Barker, Jul 26 2017

Formula

G.f.: -(x^4+x^2+2*x-1)*x/((x^2+x-1)*(x^3-x^2+3*x-1)).

a(n) = 4*a(n-1) - 3*a(n-2) - a(n-3) - a(n-5) for n>5. - Colin Barker, Jul 26 2017

3*a(n) = 2*A000045(n+1) + A200752(n+3) -2*A200752(n+2), n>0. - R. J. Mathar, Aug 05 2017