A007808 - OEIS

%I #65 Aug 03 2024 07:10:15

%S 1,1,3,13,69,431,3103,25341,231689,2345851,26065011,315386633,

%T 4128697741,58145826519,876660153671,14089181041141,240455356435473,

%U 4343224875615731,82776756452911579,1660133837750060001,34950186057896000021,770651602576606800463

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

%C 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

%C 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

%H Alois P. Heinz, <a href="/A007808/b007808.txt">Table of n, a(n) for n = 0..448</a>

%H E. Barcucci, A. Del Lungo and R. Pinzani, <a href="http://dx.doi.org/10.1016/0304-3975(95)00199-9">"Deco" polyominoes, permutations and random generation</a>, Theoretical Computer Science, 159, 1996, 29-42.

%H E. Barcucci, A. Del Lungo, R. Pinzani and R. Sprugnoli, <a href="http://www.emis.de/journals/SLC/opapers/s31barc.html">La hauteur des polyominos dirigés verticalement convexes</a>, Actes du 31e Séminaire Lotharingien de Combinatoire, Publ. IRMA, Université Strasbourg I (1993).

%F E.g.f.: (exp(x) - 2 * x) / (1 - x)^2. - _Michael Somos_, Oct 20 2011

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

%F 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

%F a(n) = (n^2*a(n-1)-1)/(n-1). - _Vladeta Jovovic_, Apr 26 2003

%F a(n) = n!*n*(1-Sum_{j=1..n-1} 1/(j*(j+1)*(j+1)!)). - _Emeric Deutsch_, Aug 07 2006

%F 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

%F a(n) = n! + n!*Sum_{j=1..n-1} (n-j)/(j+1)!. - _Walden Freedman_, Aug 21 2014

%F Asymptotic approximation: a(n) ~ n!(1 + (n - 1)(e - 2)). - _Walden Freedman_, Aug 23 2014

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

%p 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

%p # second Maple program:

%p a:= proc(n) option remember; `if`(n<2, 1,

%p       (n^2*a(n-1)-1)/(n-1))

%p     end:

%p seq(a(n), n=0..23);  # _Alois P. Heinz_, Sep 03 2020

%t a[ n_] := If[ n<0, 0, n! SeriesCoefficient[ (Exp[x] - 2 x) / (1 - x)^2, {x, 0, n}]] (* _Michael Somos_, Oct 20 2011 *)

%t a[n_] := n! + n!*Sum[(n - j)/(j + 1)!, {j, 1, n - 1}] (* _Walden Freedman_, Aug 21 2014 *)

%o (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 */

%Y Cf. A056542.

%K nonn

%O 0,3

%A _Paul Zimmermann_

%E Added a(0) = 1. - _Michael Somos_, Oct 20 2011