A245578 The number of permutations of {0,0,1,1,...,n-1,n-1} that begin with 0 and in which adjacent elements are adjacent mod n.

1, 10, 18, 22, 32, 38, 50, 58, 72, 82, 98, 110, 128, 142, 162, 178, 200, 218, 242, 262, 288, 310, 338, 362, 392, 418, 450, 478, 512, 542, 578, 610, 648, 682, 722, 758, 800, 838, 882, 922, 968, 1010, 1058, 1102, 1152, 1198, 1250, 1298, 1352, 1402, 1458, 1510, 1568, 1622, 1682, 1738, 1800, 1858, 1922, 1982, 2048, 2110

Offset

2,2

Comments

a(n) is also the number of random walks of length 2n in which every residue class mod n occurs twice (except that there are 8 such walks when n=2).

Links

Joerg Arndt, Table of n, a(n) for n = 2..1006

Index entries for linear recurrences with constant coefficients, signature (2,0,-2,1).

Formula

a(n) = 2 * A209350(n) if n>2. - Michael Somos, Jul 26 2014

G.f.: x^2 * (1+8*x-2*x^2-12*x^3+7*x^4) / ((1+x) * (1-x)^3). - Joerg Arndt, Jul 26 2014

a(n) = (3+5*(-1)^n+8*n+2*n^2)/4 if n>2. - Peter Luschny, Jul 26 2014

E.g.f.: (5*exp(-x)+exp(x)*(2*x*(x+5)+3)-(14*x^2+8*(x+1)))/4. - Peter Luschny, Aug 04 2014

Example

a(3)=10 because of the solutions 012012,012021,012102,012120,010212, and their complements mod 3.
G.f. = x^2 + 10*x^3 + 18*x^4 + 22*x^5 + 32*x^6 + 38*x^7 + 50*x^8 + 58*x^9 + ...

Maple

A245578 := n -> `if`(n=2, 1, (3+5*(-1)^n+8*n+2*n^2)/4);
seq(A245578(n), n = 2..63); # Peter Luschny, Jul 26 2014

Mathematica

CoefficientList[Series[(1 + 8 x - 2 x^2 - 12 x^3 + 7 x^4)/((1 + x) (1 - x)^3), {x, 0, 40}], x] (* Vincenzo Librandi, Aug 05 2014 *)

Prog

(PARI) Vec( x^2 * (1+8*x-2*x^2-12*x^3+7*x^4) / ((1+x) * (1-x)^3) + O(x^66) ) \\ Joerg Arndt, Jul 26 2014
(Magma) [1] cat [(3+5*(-1)^n+8*n+2*n^2)/4: n in [3..70]]; // Vincenzo Librandi, Aug 05 2014

Crossrefs

Sequence in context: A055481 A213717 A333999 * A165250 A257512 A125689

Adjacent sequences: A245575 A245576 A245577 * A245579 A245580 A245581

Keyword

nonn,easy

Author

Don Knuth, Jul 25 2014

Status

approved