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

Author

Shanzhen Gao, May 13 2010

Keywords

• nonn
• easy

Comments

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)

Links

• 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

Crossrefs

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

Cf. A035363, A088218.

Programs

Magma

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

Maple

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

Mathematica

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

Formula

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)

Extensions

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