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

Author

Clark Kimberling, May 02 2000

Keywords

• nonn
• easy

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
• Elena Barcucci, Renzo Pinzani, and Renzo Sprugnoli , Directed column-convex polyominoes by recurrence relations, Lecture Notes in Computer Science, No. 668, Springer, Berlin (1993), pp. 282-298.
• Éva Czabarka, Rigoberto Flórez, Leandro Junes, and José 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.
• Rigoberto Flórez, Leandro Junes, Luisa M. Montoya, and José L. Ramírez, Counting Subwords in Non-Decreasing Dyck Paths, Journal of Integer Sequences, Vol. 28 (2025), Article 25.1.6. See pp. 5, 15, 17, 19.
• Jesus Salas and Alan 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).

Crossrefs

Row-sums of array T as in A038730.

First differences of A030267.

Row sums of A318942(n+1).

Cf. A000045.

Programs

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

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

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

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

E.g.f.: exp(3*x/2)*(5*(5 + 4*x)*cosh(sqrt(5)*x/2) + sqrt(5)*(7 + 10*x)*sinh(sqrt(5)*x/2))/25. - Stefano Spezia, Mar 04 2025

Extensions

Entry improved by comments from Emeric Deutsch, Jun 14 2001