login
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.
2

%I #10 Jul 28 2015 16:53:13

%S 1,1,3,7,18,44,110,272,676,1676,4160,10320,25608,63536,157648,391152,

%T 970528,2408064,5974880,14824832,36783296,91266496,226449920,

%U 561866240,1394099328,3459031296,8582528768,21294921472,52836837888,131098461184

%N 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.

%C 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.

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

%D 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.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2, 2, -2).

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

%F 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]

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

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

%p 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);

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

%Y Cf. A181304.

%K nonn

%O 0,3

%A _Emeric Deutsch_, Oct 13 2010

%E Edited by _N. J. A. Sloane_, Oct 15 2010