login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Number of permutations p of the multiset {0,0,1,1,2,2,...,n,n} such that p(1) = 0, p(2n+2) = n, and |p(i) - p(i-1)| is always 1 or 2.
1

%I #29 Aug 04 2024 10:13:53

%S 1,4,24,78,300,1248,4957,19372,76895,305672,1209771,4789866,18985256,

%T 75228302,298018487,1180748188,4678314418,18535510324,73437503198,

%U 290961862062,1152799708533,4567414655824,18096197850597,71697579703986,284067484743757,1125481884043816

%N Number of permutations p of the multiset {0,0,1,1,2,2,...,n,n} such that p(1) = 0, p(2n+2) = n, and |p(i) - p(i-1)| is always 1 or 2.

%C Imagine you're a whimsical little creature standing on the number line. You start at 0, and you can take steps with some constraints:

%C 1. You must always stay between 0 and some positive integer endpoint n (inclusive).

%C 2. You can only take steps of size 1 or 2 (not 0), forward or backward.

%C Your journey as a whole must also follow some constraints:

%C 3. You must end at n.

%C 4. You must stand on each integer between 0 and n (inclusive) exactly twice.

%C 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.

%C a(n) is the number of distinct paths following these constraints from 0 to n.

%H Andrew Howroyd, <a href="/A375092/b375092.txt">Table of n, a(n) for n = 1..1000</a>

%H Adam Kleber, <a href="/A375092/a375092.txt">txt Python program counting paths</a>

%H <a href="/index/Rec#order_14">Index entries for linear recurrences with constant coefficients</a>, signature (2,3,14,21,-4,-6,-4,-19,-2,4,-4,6,-2,1).

%F 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

%K nonn,easy

%O 1,2

%A _Adam Kleber_, Jul 29 2024

%E a(17) onwards from _Andrew Howroyd_, Jul 30 2024