A228248 - OEIS

%I #31 Dec 23 2024 14:53:43

%S 1,0,1,3,9,30,103,357,1257,4494,16246,59246,217719,805389,2996113,

%T 11200113,42047593,158452138,599113966,2272065638,8639763574,

%U 32933685102,125817012366,481631387438,1847110931703,7095928565405,27302745922817,105204285608025

%N Number of 2n-step lattice paths from (0,0) to (0,0) using steps in {N, S, E, W} starting with East, then always moving straight ahead or turning left.

%C From _Gus Wiseman_, Oct 13 2022: (Start)

%C Also the number of integer compositions of 2n whose half-alternating and skew-alternating sums are both 0, where we define the half-alternating sum of a sequence (A, B, C, D, E, F, G, ...) to be A + B - C - D + E + F - G - ..., and the skew-alternating sum to be A - B - C + D + E - F - G + ... For example, the a(0) = 1 through a(4) = 9 compositions are:

%C   ()  .  (1111)  (1212)   (1313)

%C                  (2121)   (2222)

%C                  (11211)  (3131)

%C                           (11312)

%C                           (12221)

%C                           (21311)

%C                           (112211)

%C                           (1112111)

%C                           (11111111)

%C For skew-alternating only: A001700, ranked by A357627, reverse A357628.

%C For partitions: A035363, half only A357639, skew only A357640.

%C For half-alternating only: A357641, ranked by A357625, reverse A357626.

%C These compositions are ranked by A357706.

%C (End)

%H Alois P. Heinz, <a href="/A228248/b228248.txt">Table of n, a(n) for n = 0..1000</a>

%H David Scambler et al., <a href="https://web.archive.org/web/*/http://list.seqfan.eu/oldermail/seqfan/2013-May/011133.html">A new lattice walk</a> and follow-up messages on the SeqFan list, May 08 2013.

%F a(n) ~ 2^(2n-1)/(Pi*n). - _Vaclav Kotesovec_, Jul 16 2014

%e a(0) = 1: [], the empty path.

%e a(1) = 0.

%e a(2) = 1: ENWS.

%e a(3) = 3: EENWWS, ENNWSS, ENWWSE.

%p b:= proc(x, y, n) option remember; `if`(abs(x)+abs(y)>n, 0,

%p       `if`(n=0, 1, b(x+1, y, n-1) +b(y+1, -x, n-1)))

%p     end:

%p a:= n-> ceil(b(0, 0, 2*n)/2):

%p seq(a(n), n=0..40);

%p # second Maple program:

%p a:= proc(n) option remember; `if`(n<5, [1, 0, 1, 3, 9][n+1],

%p      ((n-1)*(414288-1901580*n+186029*n^6-869551*n^5+2393807*n^4

%p      -3938624*n^3+3753546*n^2+1050*n^8-21605*n^7)*a(n-1)

%p      +(-17751540*n-12215020*n^5+3494038*n^6+3777840+27478070*n^4

%p      -39711374*n^3+35488098*n^2-2700*n^9+62370*n^8-621126*n^7)*a(n-2)

%p      +(-18193248+77490792*n-9138800*n^6+35323128*n^5-88122332*n^4

%p      +141370392*n^3-140075264*n^2+5400*n^9-135540*n^8+1476432*n^7)*a(n-3)

%p      +(-192473328*n+48577536+17091500*n^6-70036368*n^5+184890672*n^4

%p      -313388816*n^3+328043052*n^2-8400*n^9+224440*n^8-2600032*n^7)*a(n-4)

%p      +8*(n-5)*(150*n^6-2015*n^5+10852*n^4-29867*n^3+44208*n^2-33540*n

%p      +10416)*(-9+2*n)^2*a(n-5)) / (n^2*(396988*n-487261*n^2+150*n^7

%p      -3065*n^6+26092*n^5-119602*n^4+317746*n^3-131048)))

%p     end:

%p seq(a(n), n=0..40);

%t b[x_, y_, n_] := b[x, y, n] = If[Abs[x] + Abs[y] > n, 0, If[n == 0, 1, b[x + 1, y, n - 1] + b[y + 1, -x, n - 1]]];

%t a[n_] := Ceiling[b[0, 0, 2n]/2];

%t a /@ Range[0, 40] (* _Jean-François Alcover_, May 14 2020, after Maple *)

%t halfats[f_]:=Sum[f[[i]]*(-1)^(1+Ceiling[i/2]),{i,Length[f]}];

%t skats[f_]:=Sum[f[[i]]*(-1)^(1+Ceiling[(i+1)/2]),{i,Length[f]}];

%t Table[Length[Select[Join@@Permutations/@IntegerPartitions[2n],halfats[#]==0&&skats[#]==0&]],{n,0,7}] (* _Gus Wiseman_, Oct 12 2022 *)

%Y Cf. A004006 (same rules, but self-avoiding).

%Y Cf. A000583, A001511, A001700, A088218, A357136, A357182, A357642.

%K nonn,easy

%O 0,4

%A _David Scambler_ and _Alois P. Heinz_, Aug 18 2013