A006014 a(n+1) = (n+1)*a(n) + Sum_{k=1..n-1} a(k)*a(n-k). (Formerly M1790)

1, 2, 7, 32, 178, 1160, 8653, 72704, 679798, 7005632, 78939430, 965988224, 12762344596, 181108102016, 2748049240573, 44405958742016, 761423731533286, 13809530704348160, 264141249701936818, 5314419112717217792, 112201740111374359516, 2480395343617443024896

Offset

1,2

References

D. E. Knuth, personal communication.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Michael De Vlieger, Table of n, a(n) for n = 1..449

Jimmy Devillet and Bruno Teheux, Associative, idempotent, symmetric, and order-preserving operations on chains, arXiv:1805.11936 [math.RA], 2018.

E. Duchi, V. Guerrini, S. Rinaldi, and G. Schaeffer, Fighting fish, J. Phys. A, Math. Theor. 50, No. 2, Article ID 024002, 16 p. (2017), chapter 4.

Formula

G.f. A(x) satisfies A(x) = x * (1 + A(x) + A(x)^2 + x * A'(x)). - Michael Somos, Jul 24 2011

Conjecture: a(n) = Sum_{k=0..2^(n-1) - 1} A379818(k). - Mikhail Kurkov, Nov 19 2021 [Rewritten by Mikhail Kurkov, Mar 27 2026]

a(n) ~ cosh(sqrt(3)*Pi/2) * n! / Pi = A073017 * n!. - Vaclav Kotesovec, Nov 21 2024

Example

G.f. = x + 2*x^2 + 7*x^3 + 32*x^4 + 178*x^5 + 1160*x^6 + 8653*x^7 + 72704*x^8 + ...

Mathematica

Nest[Append[#1, #1[[-1]] (#2 + 1) + Total@ Table[#1[[k]] #1[[#2 - k]], {k, #2 - 1}]] & @@ {#, Length@ #} &, {1}, 17] (* Michael De Vlieger, Aug 22 2018 *)
(* or *)
a[1] = 1; a[n_] := a[n] = n a[n-1] + Sum[a[k] a[n-1-k], {k, n-2}]; Array[a, 18] (* Giovanni Resta, Aug 23 2018 *)

Prog

(PARI) {a(n) = local(A); if( n<1, 0, A = vector(n); A[1] = 1; for( k=2, n, A[k] = k * A[k-1] + sum( j=1, k-2, A[j] * A[k-1-j])); A[n])} /* Michael Somos, Jul 24 2011 */
(Python)
from sage.all import *
@CachedFunction
def a(n): # a = A006014
    if n<5: return (pow(5, n-1) + 3)//4
    else: return n*a(n-1) + 2*sum(a(k)*a(n-k-1) for k in range(1, (n//2))) + (n%2)*pow(a((n-1)//2), 2)
print([a(n) for n in range(1, 61)]) # G. C. Greubel, Jan 10 2025

Crossrefs

Cf. A073017, A379818.

Sequence in context: A059439 A385287 A190123 * A121555 A265165 A351813

Adjacent sequences: A006011 A006012 A006013 * A006015 A006016 A006017

Keyword

nonn,easy

Author

N. J. A. Sloane

Status

approved