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

1, 0, 1, 3, 9, 30, 103, 357, 1257, 4494, 16246, 59246, 217719, 805389, 2996113, 11200113, 42047593, 158452138, 599113966, 2272065638, 8639763574, 32933685102, 125817012366, 481631387438, 1847110931703, 7095928565405, 27302745922817, 105204285608025

Offset: 0

Author

David Scambler and Alois P. Heinz, Aug 18 2013

Keywords

• nonn
• easy

Comments

From Gus Wiseman, Oct 13 2022: (Start)

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:

() . (1111) (1212) (1313)

(2121) (2222)

(11211) (3131)

(11312)

(12221)

(21311)

(112211)

(1112111)

(11111111)

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

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

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

These compositions are ranked by A357706.

(End)

Examples

			a(0) = 1: [], the empty path.
a(1) = 0.
a(2) = 1: ENWS.
a(3) = 3: EENWWS, ENNWSS, ENWWSE.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• David Scambler et al., A new lattice walk and follow-up messages on the SeqFan list, May 08 2013.

Crossrefs

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

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

Programs

Maple

b:= proc(x, y, n) option remember; `if`(abs(x)+abs(y)>n, 0,
      `if`(n=0, 1, b(x+1, y, n-1) +b(y+1, -x, n-1)))
    end:
a:= n-> ceil(b(0, 0, 2*n)/2):
seq(a(n), n=0..40);
# second Maple program:
a:= proc(n) option remember; `if`(n<5, [1, 0, 1, 3, 9][n+1],
     ((n-1)*(414288-1901580*n+186029*n^6-869551*n^5+2393807*n^4
     -3938624*n^3+3753546*n^2+1050*n^8-21605*n^7)*a(n-1)
     +(-17751540*n-12215020*n^5+3494038*n^6+3777840+27478070*n^4
     -39711374*n^3+35488098*n^2-2700*n^9+62370*n^8-621126*n^7)*a(n-2)
     +(-18193248+77490792*n-9138800*n^6+35323128*n^5-88122332*n^4
     [phone]*n^3-140075264*n^2+5400*n^9-135540*n^8+1476432*n^7)*a(n-3)
     +(-192473328*n+48577536+17091500*n^6-70036368*n^5+184890672*n^4
     -313388816*n^3+328043052*n^2-8400*n^9+224440*n^8-2600032*n^7)*a(n-4)
     +8*(n-5)*(150*n^6-2015*n^5+10852*n^4-29867*n^3+44208*n^2-33540*n
     +10416)*(-9+2*n)^2*a(n-5)) / (n^2*(396988*n-487261*n^2+150*n^7
     -3065*n^6+26092*n^5-119602*n^4+317746*n^3-131048)))
    end:
seq(a(n), n=0..40);

Mathematica

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]]];
a[n_] := Ceiling[b[0, 0, 2n]/2];
a /@ Range[0, 40] (* Jean-François Alcover, May 14 2020, after Maple *)
halfats[f_]:=Sum[f[[i]]*(-1)^(1+Ceiling[i/2]),{i,Length[f]}];
skats[f_]:=Sum[f[[i]]*(-1)^(1+Ceiling[(i+1)/2]),{i,Length[f]}];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[2n],halfats[#]==0&&skats[#]==0&]],{n,0,7}] (* Gus Wiseman, Oct 12 2022 *)

Formula

a(n) ~ 2^(2n-1)/(Pi*n). - Vaclav Kotesovec, Jul 16 2014