A181306 Number of 2-compositions of n having no increasing columns.

1, 1, 3, 7, 18, 44, 110, 272, 676, 1676, 4160, 10320, 25608, 63536, 157648, 391152, 970528, 2408064, 5974880, 14824832, 36783296, 91266496, 226449920, 561866240, 1394099328, 3459031296, 8582528768, 21294921472, 52836837888, 131098461184

Offset: 0

Author

Emeric Deutsch, Oct 13 2010

Keywords

• nonn
• easy

Comments

Also, number of 2-compositions of n that have no odd entries in the top row.

A 2-composition of n is a nonnegative matrix with two rows, such that each column has at least one nonzero entry and whose entries sum up to n.

From Sean A. Irvine, Jun 05 2025: (Start)

Also, for n>=1 the number of walks of length n-1 starting at vertex 1 in the graph:

1-2

/| |

0 | |

\| |

4-3. (End)

Examples

			a(2) = 3 because we have (1/1), (2/0), and (1,1/0,0) (the 2-compositions are written as (top row / bottom row)).
Alternatively, a(2) = 3 because we have (0/2), (2,0), and (0,0/1,1) (the 2-compositions are written as (top row/bottom row)).
		

Links

• G. Castiglione, A. Frosini, E. Munarini, A. Restivo and S. Rinaldi, Combinatorial aspects of L-convex polyominoes, European J. Combin. 28 (2007), no. 6, 1724-1741.
• Sean A. Irvine, Walks on Graphs.
• Index entries for linear recurrences with constant coefficients, signature (2,2,-2).

Crossrefs

Cf. A181304.

Programs

Maple

g := (1+z)*(1-z)^2/(1-2*z-2*z^2+2*z^3): gser := series(g, z = 0, 35): seq(coeff(gser, z, n), n = 0 .. 32);

Mathematica

CoefficientList[Series[((1+x)(1-x)^2)/(1-2x-2x^2+2x^3),{x,0,30}],x] (* or *) Join[{1},LinearRecurrence[{2,2,-2},{1,3,7},30]] (* Harvey P. Dale, Mar 07 2012 *)

Formula

G.f.: (1+z)*(1-z)^2/(1-2*z-2*z^2+2*z^3).

a(n) = A181304(n,0).

a(0)=1, a(1)=1, a(2)=3, a(3)=7, a(n)=2*a(n-1)+2*a(n-2)-2*a(n-3). - Harvey P. Dale, Mar 07 2012

Extensions

Edited by N. J. A. Sloane, Oct 15 2010