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

1, 4, 1, 20, 5, 1, 128, 32, 6, 1, 1024, 256, 46, 7, 1, 9856, 2464, 432, 62, 8, 1, 110720, 27680, 4784, 662, 80, 9, 1, 1421312, 355328, 60864, 8224, 952, 100, 10, 1, 20525056, 5131264, 873664, 116128, 13048, 1308, 122, 11, 1

Offset: 1

Author

Peter Bala, Jan 30 2011

Keywords

• nonn
• easy
• tabl

Comments

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

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

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

The first column of the table gives A080795.

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

See also A185416.

Examples

			Square array begins
n\k|......1.......2.......3........4.......5.........6
======================================================
..1|......1.......1.......1........1........1........1
..2|......4.......5.......6........7........8........9
..3|.....20......32......46.......62.......80......100
..4|....128.....256.....432......662......952.....1308
..5|...1024....2464....4784.....8224....13048....19544
..6|...9856...27680...60864...116128...201632...327096
..7|.110720..355328..873664..1833728..3460640..6046720
..
Examples of recurrence relation:
T(4,3) = 432 = 8*T(3,4) - 2*T(3,2) = 8*62 - 2*32;
T(6,2) = 27680 = 6*T(5,3) - 1*T(5,1) = 6*4784 - 1*1024.
		

Crossrefs

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

Programs

Maple

#A185420
M := proc(n,x) option remember;
description 'minimax polynomials M(n,x)'
if n = 0
return 1
else return
x*(2*M(n-1,x+1)-M(n-1,x-1))
end proc:
for n from 1 to 10 do
seq(M(n,k)/k, k = 1..10);
end do;

Mathematica

M[n_, x_] := M[n, x] = If[n == 0, 1, x (2 M[n - 1, x + 1] - M[n - 1, x - 1])];
T[n_, k_] := M[n, k]/k;
Table[T[d - k + 1, k], {d, 1, 9}, {k, 1, d}] // Flatten (* Jean-François Alcover, Sep 24 2022 *)

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)))}

Formula

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

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

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