|
|
A007808
|
|
Number of directed column-convex polyominoes of height n: a(k+1)=(k+1)*a(k)+(a(1)+...+a(k)).
|
|
11
|
|
|
1, 1, 3, 13, 69, 431, 3103, 25341, 231689, 2345851, 26065011, 315386633, 4128697741, 58145826519, 876660153671, 14089181041141, 240455356435473, 4343224875615731, 82776756452911579, 1660133837750060001, 34950186057896000021, 770651602576606800463
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
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: A088368 A196794 A184818 * 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
|
|
|
|