cp's OEIS Frontend

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

%I A007808 #65 Aug 03 2024 07:10:15
%S A007808 1,1,3,13,69,431,3103,25341,231689,2345851,26065011,315386633,
%T A007808 4128697741,58145826519,876660153671,14089181041141,240455356435473,
%U A007808 4343224875615731,82776756452911579,1660133837750060001,34950186057896000021,770651602576606800463
%N A007808 Number of directed column-convex polyominoes of height n: a(k+1)=(k+1)*a(k)+(a(1)+...+a(k)).
%C A007808 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 A007808 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 A007808 Alois P. Heinz, <a href="/A007808/b007808.txt">Table of n, a(n) for n = 0..448</a>
%H A007808 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 A007808 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 A007808 E.g.f.: (exp(x) - 2 * x) / (1 - x)^2. - _Michael Somos_, Oct 20 2011
%F A007808 a(n) = A056542(n+1) - A056542(n).
%F A007808 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 A007808 a(n) = (n^2*a(n-1)-1)/(n-1). - _Vladeta Jovovic_, Apr 26 2003
%F A007808 a(n) = n!*n*(1-Sum_{j=1..n-1} 1/(j*(j+1)*(j+1)!)). - _Emeric Deutsch_, Aug 07 2006
%F A007808 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 A007808 a(n) = n! + n!*Sum_{j=1..n-1} (n-j)/(j+1)!. - _Walden Freedman_, Aug 21 2014
%F A007808 Asymptotic approximation: a(n) ~ n!(1 + (n - 1)(e - 2)). - _Walden Freedman_, Aug 23 2014
%e A007808 1 + x + 3*x^2 + 13*x^3 + 69*x^4 + 431*x^5 + 3103*x^6 + 25341*x^7 + 231689*x^8 + ...
%p A007808 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 A007808 # second Maple program:
%p A007808 a:= proc(n) option remember; `if`(n<2, 1,
%p A007808       (n^2*a(n-1)-1)/(n-1))
%p A007808     end:
%p A007808 seq(a(n), n=0..23);  # _Alois P. Heinz_, Sep 03 2020
%t A007808 a[ n_] := If[ n<0, 0, n! SeriesCoefficient[ (Exp[x] - 2 x) / (1 - x)^2, {x, 0, n}]] (* _Michael Somos_, Oct 20 2011 *)
%t A007808 a[n_] := n! + n!*Sum[(n - j)/(j + 1)!, {j, 1, n - 1}] (* _Walden Freedman_, Aug 21 2014 *)
%o A007808 (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 A007808 Cf. A056542.
%K A007808 nonn
%O A007808 0,3
%A A007808 _Paul Zimmermann_
%E A007808 Added a(0) = 1. - _Michael Somos_, Oct 20 2011