login
Square array, read by antidiagonals, used to recursively calculate the number of minimax trees A080795.
6

%I #14 Sep 24 2022 13:38:00

%S 1,4,1,20,5,1,128,32,6,1,1024,256,46,7,1,9856,2464,432,62,8,1,110720,

%T 27680,4784,662,80,9,1,1421312,355328,60864,8224,952,100,10,1,

%U 20525056,5131264,873664,116128,13048,1308,122,11,1

%N Square array, read by antidiagonals, used to recursively calculate the number of minimax trees A080795.

%C The table entries T(n,k), for n,k>=1, are defined by means of the recurrence relation

%C (1)... T(n+1,k) = (2*k+2)*T(n,k+1)-(k-1)*T(n,k-1),

%C with boundary condition T(1,k) = 1.

%C The first column of the table gives A080795.

%C For similarly defined tables used to calculate the zigzag numbers A000111 and the Springer numbers A001586 see A185414 and A185418, respectively.

%C See also A185416.

%F (1)... T(n,k) = M(n,k)/k with M(n,x) the polynomials described in A185419.

%F (2)... First column: T(n,1) = A080795(n).

%F (3)... Second column: T(n,2) = (1/4)*A080795(n+1).

%e Square array begins

%e n\k|......1.......2.......3........4.......5.........6

%e ======================================================

%e ..1|......1.......1.......1........1........1........1

%e ..2|......4.......5.......6........7........8........9

%e ..3|.....20......32......46.......62.......80......100

%e ..4|....128.....256.....432......662......952.....1308

%e ..5|...1024....2464....4784.....8224....13048....19544

%e ..6|...9856...27680...60864...116128...201632...327096

%e ..7|.110720..355328..873664..1833728..3460640..6046720

%e ..

%e Examples of recurrence relation:

%e T(4,3) = 432 = 8*T(3,4) - 2*T(3,2) = 8*62 - 2*32;

%e T(6,2) = 27680 = 6*T(5,3) - 1*T(5,1) = 6*4784 - 1*1024.

%p #A185420

%p M := proc(n,x) option remember;

%p description 'minimax polynomials M(n,x)'

%p if n = 0

%p return 1

%p else return

%p x*(2*M(n-1,x+1)-M(n-1,x-1))

%p end proc:

%p for n from 1 to 10 do

%p seq(M(n,k)/k, k = 1..10);

%p end do;

%t M[n_, x_] := M[n, x] = If[n == 0, 1, x (2 M[n - 1, x + 1] - M[n - 1, x - 1])];

%t T[n_, k_] := M[n, k]/k;

%t Table[T[d - k + 1, k], {d, 1, 9}, {k, 1, d}] // Flatten (* _Jean-François Alcover_, Sep 24 2022 *)

%o (PARI) {T(n,k)=if(n<1|k<1,0,if(n==1,1,(2*k+2)*T(n-1,k+1)-(k-1)*T(n-1,k-1)))}

%Y Cf. A080795, A185414, A185416, A185418, A185419.

%K nonn,easy,tabl

%O 1,2

%A _Peter Bala_, Jan 30 2011