A000800 Sum of upward diagonals of Eulerian triangle.

1, 1, 1, 2, 5, 13, 38, 125, 449, 1742, 7269, 32433, 153850, 772397, 4088773, 22746858, 132601933, 807880821, 5132235182, 33925263901, 232905588441, 1657807491222, 12215424018837, 93042845392105, 731622663432978, 5931915237693517, 49535826242154973

Offset: 0

Author

Tony Harkin [ harkin(AT)mit.edu, tharkin(AT)vortex.weather.brockport.edu ]

Keywords

• nonn
• easy
• nice

Examples

			1 = 1, 1 = 1, 1 = 1 + 0, 2 = 1 + 1, 5 = 1 + 4 + 0, etc.
G.f. = 1 + x + x^2 + 2*x^3 + 5*x^4 + 13*x^5 + 38*x^6 + 125*x^7 + 449*x^8 + 1742*x^9 + ...
		

References

• L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 243.
• R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 254.
• J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 215.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..600 (first 201 terms from Vincenzo Librandi)

Crossrefs

Cf. A173018.

Programs

Maple

b:= proc(n, k) option remember; `if`(k=0 and n>=0, 1,
      `if`(k<0 or k>n, 0, (n-k)*b(n-1, k-1)+(k+1)*b(n-1, k)))
    end:
a:= n-> add(b(n-k, k), k=0..n):
seq(a(n), n=0..30);  # Alois P. Heinz, Jan 23 2018

Mathematica

t[n_ /; n >= 0, 0] = 1; t[n_, k_] /; k < 0 || k > n = 0; t[n_, k_] := t[n, k] = (n-k)*t[n-1, k-1] + (k+1)*t[n-1, k]; a[n_] := Sum[t[n-k, k], {k, 0, n}]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Dec 14 2011, after Michael Somos *)
Table[Sum[Sum[(-1)^j*(k-j+1)^(n-k)*Binomial[n-k+1, j], {j, 0, k}], {k, 0, n}], {n, 0, 25}] (* Vaclav Kotesovec, Aug 15 2015 *)

Maxima

a(n):=sum(m!*sum((binomial(n-m-k,k)*stirling2(n-k,m)*(-1)^(-n+m)),k,0,(n-m)/2),m,0,n); /* Vladimir Kruchinin, Jan 23 2018 */

Formula

G.f.: 1/(1-x/(1-x^2/(1-2x/(1-2x^2/(1-3x/(1-3x^2/(1-... (continued fraction). - Paul Barry, Mar 24 2010

a(n) = Sum_{k} A173018(n-k, k). - Michael Somos, Mar 17 2011

G.f.: 1/Q(0), where Q(k) = 1 - x*(k+1)/(1 - x^2*(k+1)/Q(k+1)); (continued fraction). - Sergei N. Gladkovskii, Apr 14 2013

G.f.: 1/Q(0), where Q(k) = 1 - x - x*(x+1)*k - x^3*(k+1)^2/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Apr 14 2013

a(n) = Sum_{m=0..n} (-1)^(n-m)*m!*Sum_{k=0..floor((n-m)/2)} C(n-m-k,k)*Stirling2(n-k,m). - Vladimir Kruchinin, Jan 23 2018

Extensions

More terms from David W. Wilson