login
A375092
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
1, 4, 24, 78, 300, 1248, 4957, 19372, 76895, 305672, 1209771, 4789866, 18985256, 75228302, 298018487, 1180748188, 4678314418, 18535510324, 73437503198, 290961862062, 1152799708533, 4567414655824, 18096197850597, 71697579703986, 284067484743757, 1125481884043816
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
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
CROSSREFS
Sequence in context: A199904 A250132 A025220 * A112742 A158494 A209456
KEYWORD
nonn,easy
AUTHOR
Adam Kleber, Jul 29 2024
EXTENSIONS
a(17) onwards from Andrew Howroyd, Jul 30 2024
STATUS
approved