OFFSET
1,3
COMMENTS
A contraction in the complement of any set of paths reduces the total number of edges in the complement by at most 4. This gives an upper bound for the Hadwiger number which is obtainable for all path lengths except 4 and 5. In particular, for n >= 6, the complement of a P_n reduces to the complement of a P_{n-4} union 3 universal nodes by contracting the second and second to last nodes of the path. With P_8 and P_9 the 2nd and 6th nodes should be contracted (instead of reducing to P_4 or P_5 respectively). - Andrew Howroyd, Jun 18 2025
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Hadwiger Number.
Eric Weisstein's World of Mathematics, Path Complement Graph.
Index entries for linear recurrences with constant coefficients, signature (1,0,0,1,-1).
FORMULA
a(n) = floor((3*n + 1)/4) = A037915(n+1) for n >= 6. - Andrew Howroyd, Jun 18 2025
From Elmo R. Oliveira, Apr 12 2026: (Start)
a(n) = a(n-1) + a(n-4) - a(n-5).
G.f.: x*(1 + x^2 + x^5 + x^7 - x^9)/((1 - x)*(1 - x^4)). (End)
E.g.f.: (30*((3*x - 1)*cosh(x) + cos(x) + sin(x) + 3*x*sinh(x)) - x^4*(x + 5))/120. - Stefano Spezia, Apr 12 2026
PROG
(PARI) a(n) = (3*n + 1)\4 - (n==4||n==5) \\ Andrew Howroyd, Jun 18 2025
CROSSREFS
KEYWORD
nonn,easy,changed
AUTHOR
Eric W. Weisstein, Apr 30 2022
EXTENSIONS
a(16) onwards from Andrew Howroyd, Jun 18 2025
STATUS
approved