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

Author

Paul Zimmermann

Keywords

• nonn

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

Examples

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

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

Crossrefs

Cf. A056542.

Programs

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

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

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_{j=1..n-1} 1/(j*(j+1)*(j+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

Extensions

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