A007808 Number of directed column-convex polyominoes of height n: a(k+1)=(k+1)*a(k)+(a(1)+...+a(k)).

1, 1, 3, 13, 69, 431, 3103, 25341, 231689, 2345851, 26065011, 315386633, 4128697741, 58145826519, 876660153671, 14089181041141, 240455356435473, 4343224875615731, 82776756452911579, 1660133837750060001, 34950186057896000021, 770651602576606800463

Offset

0,3

Comments

a(n) is also the number of outcomes to a race with n contestants in which there is at most one tie (of at least two contestants). - Walden Freedman, Aug 21 2014

Let M(n) denote the n X n matrix with ones along the subdiagonal, ones everywhere above the main diagonal, the integers 3, 4, etc., along the main diagonal, and zeros everywhere else. Then equals a(n) equals the permanent of M(n-1) for n >= 2. - John M. Campbell, Apr 20 2021

Links

Alois P. Heinz, Table of n, a(n) for n = 0..448

E. Barcucci, A. Del Lungo and R. Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, 159, 1996, 29-42.

E. Barcucci, A. Del Lungo, R. Pinzani and R. Sprugnoli, La hauteur des polyominos dirigés verticalement convexes, Actes du 31e Séminaire Lotharingien de Combinatoire, Publ. IRMA, Université Strasbourg I (1993).

Formula

E.g.f.: (exp(x) - 2 * x) / (1 - x)^2. - Michael Somos, Oct 20 2011

a(n) = A056542(n+1) - A056542(n).

a(n) = (a(n-1)^2 - 2 * a(n-2)^2 + a(n-2) * a(n-3) - 4 * a(n-1) * a(n-3)) / (a(n-2) - a(n-3)) if n>3. - Michael Somos, Oct 20 2011

a(n) = (n^2*a(n-1)-1)/(n-1). - Vladeta Jovovic, Apr 26 2003

a(n) = n!*n*[1-Sum(1/(j*(j+1)*(j+1)!), j=1..n-1)). - Emeric Deutsch, Aug 07 2006

Conjectures: E.g.f.: (-(x^2+1)*exp(-x)+1)*exp(x)/(-1+x)^2; a(n) = round(n!*n*(exp(1)-2)). - Simon Plouffe, Dec 08 2009

a(n) = n! + n!*sum(j=1..n-1, (n-j)/(j+1)! ). - Walden Freedman, Aug 21 2014

Asymptotic approximation: a(n) ~ n!(1 + (n - 1)(e - 2)). - Walden Freedman, Aug 23 2014

Example

1 + x + 3*x^2 + 13*x^3 + 69*x^4 + 431*x^5 + 3103*x^6 + 25341*x^7 + 231689*x^8 + ...

Maple

a:=n->n!*n*(1-add(1/j/(j+1)/(j+1)!, j=1..n-1)): seq(a(n), n=1..22); # Emeric Deutsch, Aug 07 2006
# second Maple program:
a:= proc(n) option remember; `if`(n<2, 1,
      (n^2*a(n-1)-1)/(n-1))
    end:
seq(a(n), n=0..23);  # Alois P. Heinz, Sep 03 2020

Mathematica

a[ n_] := If[ n<0, 0, n! SeriesCoefficient[ (Exp[x] - 2 x) / (1 - x)^2, {x, 0, n}]] (* Michael Somos, Oct 20 2011 *)
a[n_] := n! + n!*Sum[(n - j)/(j + 1)!, {j, 1, n - 1}] (* Walden Freedman, Aug 21 2014 *)

Prog

(PARI) {a(n) = if( n<0, 0, n! * polcoeff( (exp(x + x * O(x^n)) - 2 * x) / (1 - x)^2, n))} /* Michael Somos, Oct 20 2011 */

Crossrefs

Cf. A056542.

Sequence in context: A196794 A184818 A352370 * A104989 A119906 A059726

Adjacent sequences: A007805 A007806 A007807 * A007809 A007810 A007811

Keyword

nonn

Author

Paul Zimmermann

Extensions

Added a(0) = 1. - Michael Somos, Oct 20 2011

Status

approved