A181306 Number of 2-compositions of n having no increasing columns. 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.

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,3

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.

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

References

G. Castiglione, A. Frosini, E. Munarini, A. Restivo and S. Rinaldi, Combinatorial aspects of L-convex polyominoes, European Journal of Combinatorics, 28, 2007, 1724-1741.

Links

Table of n, a(n) for n=0..29.

Index entries for linear recurrences with constant coefficients, signature (2, 2, -2).

Formula

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

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) [From Harvey P. Dale, Mar 07 2012]

Example

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

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

Crossrefs

Cf. A181304.

Sequence in context: A262321 A182995 A027967 * A178035 A000226 A291734

Adjacent sequences: A181303 A181304 A181305 * A181307 A181308 A181309

Keyword

nonn

Author

Emeric Deutsch, Oct 13 2010

Extensions

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

Status

approved