login
a(n) = Sum_{k=0..n-1} {[x^k] A(x)^(n-k)} * {[x^(n-k-1)] A(x)^(k+1)} for n>0, with a(0)=1, where g.f. A(x) = Sum_{n>=0} a(n)*x^n.
1

%I #4 Apr 19 2012 14:38:13

%S 1,1,2,8,46,333,2822,26884,280778,3162129,37962174,481796692,

%T 6424120440,89561323131,1300606338522,19614272779492,306422062160964,

%U 4948682216714809,82474329755007710,1416291364674413764,25027636488359996744,454585893218323184316

%N a(n) = Sum_{k=0..n-1} {[x^k] A(x)^(n-k)} * {[x^(n-k-1)] A(x)^(k+1)} for n>0, with a(0)=1, where g.f. A(x) = Sum_{n>=0} a(n)*x^n.

%C The notation [x^n] F(x) denotes the coefficient of x^n in F(x).

%e G.f.: A(x) = 1 + x + 2*x^2 + 8*x^3 + 46*x^4 + 333*x^5 + 2822*x^6 +...

%e The table of coefficients in powers A(x)^n, n>=1, begin:

%e A^1: [1, 1, 2, 8, 46, 333, 2822, 26884, 280778, ...];

%e A^2: [1, 2, 5, 20, 112, 790, 6558, 61480, 634056, ...];

%e A^3: [1, 3, 9, 37, 204, 1407, 11450, 105627, 1075440, ...];

%e A^4: [1, 4, 14, 60, 329, 2228, 17796, 161572, 1623756, ...];

%e A^5: [1, 5, 20, 90, 495, 3306, 25960, 232050, 2301680, ...];

%e A^6: [1, 6, 27, 128, 711, 4704, 36383, 320376, 3136476, ...];

%e A^7: [1, 7, 35, 175, 987, 6496, 49595, 430550, 4160856, ...];

%e A^8: [1, 8, 44, 232, 1334, 8768, 66228, 567376, 5413977, ...];

%e A^9: [1, 9, 54, 300, 1764, 11619, 87030, 736596, 6942591, ...]; ...

%e where a(n) is obtained from the antidiagonals in the above table like so:

%e a(1) = 1*1 = 1;

%e a(2) = 1*1 + 1*1 = 2;

%e a(3) = 1*2 + 2*2 + 2*1 = 8;

%e a(4) = 1*8 + 3*5 + 5*3 + 8*1 = 46;

%e a(5) = 1*46 + 4*20 + 9*9 + 20*4 + 46*1 = 333;

%e a(6) = 1*333 + 5*112 + 14*37 + 37*14 + 112*5 + 333*1 = 2822;

%e a(7) = 1*2822 + 6*790 + 20*204 + 60*60 + 204*20 + 790*6 + 2822*1 = 26884.

%o (PARI) {a(n)=local(A=1 + sum(j=1, n-1, a(j)*x^j)+x*O(x^n));if(n==0, 1, sum(k=0, n-1, polcoeff(A^(n-k), k)*polcoeff(A^(k+1), n-k-1)))}

%o for(n=0,25,print1(a(n),", "))

%K nonn

%O 0,3

%A _Paul D. Hanna_, Jun 21 2009