OFFSET
1,2
COMMENTS
Imagine you're a whimsical little creature standing on the number line. You start at 0, and you can take steps with some constraints:
1. You must always stay between 0 and some positive integer endpoint n (inclusive).
2. You can only take steps of size 1 or 2 (not 0), forward or backward.
Your journey as a whole must also follow some constraints:
3. You must end at n.
4. You must stand on each integer between 0 and n (inclusive) exactly twice.
Starting at 0 counts as standing on 0 once, meaning you have to revisit it once. Ending on n means you visit n at the end, so you must therefore visit it once sometime during your journey and then return at the end.
a(n) is the number of distinct paths following these constraints from 0 to n.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..1000
Adam Kleber, txt Python program counting paths
Index entries for linear recurrences with constant coefficients, signature (2,3,14,21,-4,-6,-4,-19,-2,4,-4,6,-2,1).
FORMULA
G.f.: x*(1 + 2*x + 13*x^2 + 4*x^3 - 5*x^4 - 2*x^5 - 13*x^6 - x^8 + 2*x^9 + x^10)/(1 - 2*x - 3*x^2 - 14*x^3 - 21*x^4 + 4*x^5 + 6*x^6 + 4*x^7 + 19*x^8 + 2*x^9 - 4*x^10 + 4*x^11 - 6*x^12 + 2*x^13 - x^14). - Andrew Howroyd, Jul 30 2024
MATHEMATICA
CoefficientList[Series[x (1+2x+13x^2+4x^3-5x^4-2x^5-13x^6-x^8+2x^9+x^10)/(1-2x-3x^2-14x^3-21x^4+4x^5+6x^6+4x^7+19x^8+2x^9-4x^10+4x^11-6x^12+2x^13-x^14), {x, 0, 30}], x] (* Harvey P. Dale, Jun 09 2025 *)
(* Alternative: *)
LinearRecurrence[{2, 3, 14, 21, -4, -6, -4, -19, -2, 4, -4, 6, -2, 1}, {0, 1, 4, 24, 78, 300, 1248, 4957, 19372, 76895, 305672, 1209771, 4789866, 18985256}, 30] (* Harvey P. Dale, Jun 09 2025 *)
CROSSREFS
KEYWORD
nonn,easy,changed
AUTHOR
Adam Kleber, Jul 29 2024
EXTENSIONS
a(17) onwards from Andrew Howroyd, Jul 30 2024
STATUS
approved