A357706 -id:A357706 - cp's OEIS frontend

A177787 Number of paths from (0,0) to (n+2,n) using only up and right steps and avoiding two or more consecutive moves up or three or more consecutive moves right.

2, 5, 10, 18, 30, 47, 70, 100, 138, 185, 242, 310, 390, 483, 590, 712, 850, 1005, 1178, 1370, 1582, 1815, 2070, 2348, 2650, 2977, 3330, 3710, 4118, 4555, 5022, 5520, 6050, 6613, 7210, 7842, 8510, 9215, 9958, 10740, 11562, 12425, 13330, 14278, 15270

Offset: 1

Shanzhen Gao, May 13 2010

Strings of length 2n+2 over the alphabet {U, R} with n Rs and avoiding UU or RRR as substrings.
Also number of binary words with 3 1's and n 0's that do not contain the substring 101. a(2) = 5: 00111, 10011, 11001, 11100, 01110. - Alois P. Heinz, Jul 18 2013
Let (b(n)) be the p-INVERT of A010892 using p(S) = 1 - S^2; then b(n) = a(n+1) for n >= 0. See A292301. - Clark Kimberling, Sep 30 2017
From Gus Wiseman, Oct 13 2022: (Start)
Also the number of integer compositions of n+3 with half-alternating sum n-1, 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 - ... For example, the a(1) = 2 through a(4) = 10 compositions are:
  (112)   (122)    (132)
  (1111)  (212)    (222)
          (1211)   (312)
          (2111)   (1311)
          (11111)  (2211)
                   (3111)
                   (11112)
                   (12111)
                   (21111)
                   (111111)
A001700/A138364 = compositions with alternating sum 0, ranked by A344619.
A357621 = half-alternating sum of standard compositions, reverse A357622.
A357641 = compositions with half-alternating sum 0, ranked by A357625.
Cf. A357136, A357182, A357626, A357631, A357639, A357642, A357706.
(End)

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Ângela Mestre, José Agapito, Square Matrices Generated by Sequences of Riordan Arrays, J. Int. Seq., Vol. 22 (2019), Article 19.8.4.
Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1). - _R. J. Mathar_, May 22 2010

First differences of A227161. - Alois P. Heinz, Jul 18 2013

Cf. A035363, A088218.

I:=[2, 5, 10, 18]; [n le 4 select I[n] else 4*Self(n-1)-6*Self(n-2)+4*Self(n-3)-Self(n-4): n in [1..50]]; // Vincenzo Librandi, Jul 04 2012

a:= n-> n/6*(11+n^2): seq(a(n), n=1..40);

CoefficientList[Series[(2-3*x+2*x^2)/(x-1)^4,{x,0,50}],x] (* Vincenzo Librandi, Jul 04 2012 *)

a(n) = 1/6 * n (11 + n^2).
From R. J. Mathar, May 22 2010: (Start)
a(n) = A140226(n)/2.
a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4).
G.f.: x*(2-3*x+2*x^2)/(x-1)^4. (End)

More terms from R. J. Mathar, May 22 2010

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.

Original entry on oeis.org

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

David Scambler and Alois P. Heinz, Aug 18 2013

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)

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

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.

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

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

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
     +141370392*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);

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

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

cp's OEIS Frontend

A177787 Number of paths from (0,0) to (n+2,n) using only up and right steps and avoiding two or more consecutive moves up or three or more consecutive moves right.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

Extensions