login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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

%I #30 Sep 08 2022 08:46:09

%S 1,10,18,22,32,38,50,58,72,82,98,110,128,142,162,178,200,218,242,262,

%T 288,310,338,362,392,418,450,478,512,542,578,610,648,682,722,758,800,

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

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

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

%H Joerg Arndt, <a href="/A245578/b245578.txt">Table of n, a(n) for n = 2..1006</a>

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,-2,1).

%F a(n) = 2 * A209350(n) if n>2. - _Michael Somos_, Jul 26 2014

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

%F a(n) = (3+5*(-1)^n+8*n+2*n^2)/4 if n>2. - _Peter Luschny_, Jul 26 2014

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

%e a(3)=10 because of the solutions 012012,012021,012102,012120,010212, and their complements mod 3.

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

%p A245578 := n -> `if`(n=2, 1, (3+5*(-1)^n+8*n+2*n^2)/4);

%p seq(A245578(n), n = 2..63); # _Peter Luschny_, Jul 26 2014

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

%o (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

%o (Magma) [1] cat [(3+5*(-1)^n+8*n+2*n^2)/4: n in [3..70]]; // _Vincenzo Librandi_, Aug 05 2014

%K nonn,easy

%O 2,2

%A _Don Knuth_, Jul 25 2014