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

Author

Don Knuth, Jul 25 2014

Keywords

• nonn
• easy

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).

Examples

			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 + ...
		

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).

Programs

Magma

[1] cat [(3+5*(-1)^n+8*n+2*n^2)/4: n in [3..70]]; // Vincenzo Librandi, Aug 05 2014

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 *)

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

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