A038731 Number of columns in all directed column-convex polyominoes of area n+1.

1, 3, 10, 32, 99, 299, 887, 2595, 7508, 21526, 61251, 173173, 486925, 1362627, 3797374, 10543724, 29180067, 80521055, 221610563, 608468451, 1667040776, 4558234018, 12441155715, 33900136297, 92230468249, 250570010499, 679844574322, 1842280003640

Offset

0,2

Comments

Apply Riordan array (1/(1-x), x/(1-x)^2) to n+1. - Paul Barry, Oct 13 2009

Binomial transform of (A001629 shifted left twice). - R. J. Mathar, Feb 06 2010

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..200

E. Barcucci, R. Pinzani and R. Sprugnoli, Directed column-convex polyominoes by recurrence relations, Lecture Notes in Computer Science, No. 668, Springer, Berlin (1993), pp. 282-298.

É. Czabarka, R. Flórez, L. Junes, and J. L. Ramírez, Enumeration of peaks and valleys on non-decreasing Dyck paths, Disc. Math. 341(10) (2018), 2789-2807; see Theorem 2 on p. 2791.

J. Salas and A. D. Sokal, Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models. V. Further Results for the Square-Lattice Chromatic Polynomial, J. Stat. Phys. 135 (2009) 279-373, arXiv:0711.1738. Mentions this sequence. - N. J. A. Sloane, Mar 14 2014

Index entries for linear recurrences with constant coefficients, signature (6,-11,6,-1)

Formula

5*a(n) = (2n+1)*F(2n+2) - (n-4)*F(2n+1), where the F(n)'s are the Fibonacci numbers, F(0)=0, F(1)=1.

a(n) = Sum_{k=1..n+1} k*binomial(n+k-1, 2k-2). - Emeric Deutsch, Jun 11 2003

From Paul Barry, Oct 13 2009: (Start)

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

a(n) = Sum_{k=0..n} binomial(n+k, 2k)*(k+1). (End)

a(n) = 6*a(n-1) - 11*a(n-2) + 6*a(n-3) - a(n-4). - R. J. Mathar, Feb 06 2010

a(n) = Sum_{k=0..n} (F(2k)+0^k)*F(2n-2k+1). - Paul Barry, Jun 23 2010

Mathematica

Table[Sum[Binomial[n, k]*CoefficientList[Series[1/(1 - x - x^2)^2, {x, 0, k}], x][[-1]], {k, 0, n}], {n, 0, 27}] (* Arkadiusz Wesolowski, Feb 03 2012 *)
LinearRecurrence[{6, -11, 6, -1}, {1, 3, 10, 32}, 30] (* Vincenzo Librandi, Feb 04 2012 *)

Prog

(Magma) I:=[1, 3, 10, 32]; [n le 4 select I[n] else 6*Self(n-1)-11*Self(n-2)+6*Self(n-3)-Self(n-4): n in [1..30]]; // Vincenzo Librandi, Feb 04 2012
(Haskell)
a038731 n = a038731_list !! n
a038731_list = c [1] $ tail a000045_list where
   c us vs'@(v:vs) = (sum $ zipWith (*) us vs') : c (v:us) vs
-- Reinhard Zumkeller, Oct 31 2013

Crossrefs

Row-sums of array T as in A038730.

First differences of A030267.

Row sums of A318942(n+1).

Cf. A000045.

Sequence in context: A080406 A036682 A104270 * A244762 A053581 A247595

Adjacent sequences: A038728 A038729 A038730 * A038732 A038733 A038734

Keyword

nonn,easy

Author

Clark Kimberling, May 02 2000

Extensions

Entry improved by comments from Emeric Deutsch, Jun 14 2001

Status

approved