A181545 G.f.: A(x) = Sum_{n>=0} (3n)!/(n!)^3 * x^(3n)/(1-x-x^2)^(3n+1).

1, 1, 2, 9, 29, 92, 343, 1281, 4720, 17899, 68933, 266364, 1037423, 4072439, 16065148, 63658521, 253356763, 1012049086, 4055596343, 16299779331, 65683233938, 265310551667, 1073968967929, 4355988107100, 17699727361051

Offset

0,3

Comments

Limit_{n->oo} a(n+1)/a(n) = (Fibonacci(3)*sqrt(5) + Lucas(3))/2 = sqrt(5) + 2.

Links

Iain Fox, Table of n, a(n) for n = 0..1600

C. Banderier, P. Hitczenko, Enumeration and asymptotics of restricted compositions having the same number of parts, Disc. Appl. Math. 160 (18) (2012) 2542-2554. Proposition 3.1.

Steffen Eger, On the Number of Many-to-Many Alignments of N Sequences, arXiv:1511.00622 [math.CO], 2015.

Edyta Hetmaniok, Barbara Smoleń, Roman Wituła, The Stirling triangles, Proceedings of the Symposium for Young Scientists in Technology, Engineering and Mathematics (SYSTEM 2017), Kaunas, Lithuania, April 28, 2017, p. 35-41.

Formula

a(n) = Sum_{k=0..floor(n/2)} binomial(n-k,k)^3.

G.f.: Sum_{n>=0} x^n * Sum_{k=0..n} binomial(n,k)^3 * x^k.

G.f.: A(x) = G( x^3/(1-x-x^2)^3 )/(1-x-x^2) where G(x) satisfies:

* G(x^3) = G( x*(1+3*x+9*x^2)/(1+6*x)^3 )/(1+6*x)

and G(x) is the g.f. of A006480.

Recurrence: (n-3)*n^2*a(n) = (n-3)*(3*n^2 - 3*n + 1)*a(n-1) - (n-1)*a(n-2) + 2*(n-2)*(11*n^2 - 44*n + 34)*a(n-3) + (n-3)*a(n-4) + (n-1)*(3*n^2 - 21*n + 37)*a(n-5) + (n-4)^2*(n-1)*a(n-6). - Vaclav Kotesovec, Jul 31 2014

a(n) ~ sqrt((9+4*sqrt(5))/12) * (2+sqrt(5))^n / (Pi*n). - Vaclav Kotesovec, Jul 31 2014

Equivalently, a(n) ~ phi^(3*n + 3) / (2*sqrt(3)*Pi*n), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Dec 08 2021

Example

G.f. A(x) = 1 + x + 2*x^2 + 9*x^3 + 29*x^4 + 92*x^5 + 343*x^6 + ...
which equals the series:
A(x) = 1/(1-x-x^2) + 3!/1!^3*x^3/(1-x-x^2)^4 + 6!/2!^3*x^6/(1-x-x^2)^7 + 9!/3!^3*x^9/(1-x-x^2)^10 + 12!/4!^3*x^12/(1-x-x^2)^13 + ...
The g.f. also equals the series:
A(x) = 1 +
x*(1 + x) +
x^2*(1 + 2^3*x + x^2) +
x^3*(1 + 3^3*x + 3^3*x^2 + x^3) +
x^4*(1 + 4^3*x + 6^3*x^2 + 4^3*x^3 + x^4) +
x^5*(1 + 5^3*x + 10^3*x^2 + 10^3*x^3 + 5^3*x^4 + x^5) + ...
The terms begin:
a(0) = a(1) = 1^3;
a(2) = 1^3 + 1^3 = 2;
a(3) = 1^3 + 2^3 = 9;
a(4) = 1^3 + 3^3 + 1^3 = 29;
a(5) = 1^3 + 4^3 + 3^3 = 92;
a(6) = 1^3 + 5^3 + 6^3 + 1^3 = 343;
a(7) = 1^3 + 6^3 + 10^3 + 4^3 = 1281; ...

Mathematica

Table[Sum[Binomial[n-k, k]^3, {k, 0, Floor[n/2]}], {n, 0, 20}] (* Vaclav Kotesovec, Jul 31 2014 *)

Prog

(PARI) {a(n)=sum(k=0, n\2, binomial(n-k, k)^3)}
(PARI) {a(n)=polcoeff(sum(m=0, n+1, x^m*sum(k=0, m, binomial(m, k)^3*x^k + x*O(x^n))), n)}
(PARI) {a(n)=polcoeff(sum(m=0, n, x^(3*m)/(1-x-x^2+x*O(x^n))^(3*m+1)*(3*m)!/(m!)^3), n)}

Crossrefs

Cf. A006480, A217421, A181546, A051286.

Sequence in context: A062452 A265440 A152891 * A069006 A351191 A241774

Adjacent sequences: A181542 A181543 A181544 * A181546 A181547 A181548

Keyword

nonn

Author

Paul D. Hanna, Oct 29 2010

Status

approved