A259697 Triangle read by rows: T(n,k) = number of rook patterns on n X n board where bottom rook is in column k.

1, 1, 1, 1, 2, 2, 1, 4, 5, 5, 1, 9, 12, 15, 15, 1, 24, 32, 42, 52, 52, 1, 76, 99, 129, 166, 203, 203, 1, 279, 354, 451, 575, 726, 877, 877, 1, 1156, 1434, 1786, 2232, 2792, 3466, 4140, 4140, 1, 5296, 6451, 7883, 9664, 11881, 14621, 17884, 21147, 21147

Offset: 0

Author

N. J. A. Sloane, Jul 05 2015

Keywords

• nonn
• tabl

Comments

See Becker (1948/49) for precise definition.

This is the number of arrangements of non-attacking rooks on an n X n right triangular board where the bottom rook is in column k. The case of k=0 corresponds to the empty board where there is no bottom rook. - Andrew Howroyd, Jun 13 2017

Examples

			Triangle begins:
  1,
  1,  1,
  1,  2,  2,
  1,  4,  5,   5,
  1,  9, 12,  15,  15,
  1, 24, 32,  42,  52,  52,
  1, 76, 99, 129, 166, 203, 203,
  ...
From _Andrew Howroyd_, Jun 13 2017: (Start)
For n=3, the four solutions with the bottom rook in column 1 are:
  .      .      .      x
  . .    . x    x .    . .
  x . .  x . .  . . .  . . .
For n=3, the five solutions with the bottom rook in column 2 are:
  .      .      x      .       x
  . .    x .    . .    . x     . x
  . x .  . x .  . x .  . . .   . . .
(End)
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..1274
• H. W. Becker, Rooks and rhymes, Math. Mag. 22 (1948/49), 23-26. See Table V.
• H. W. Becker, Rooks and rhymes, Math. Mag., 22 (1948/49), 23-26. [Annotated scanned copy]

Crossrefs

Right edge is A000110.

Column k=1 is A005001.

Row sums are A000110(n+1).

Cf. A011971, A259691.

Programs

Mathematica

a11971[n_, k_] := Sum[Binomial[k, i]*BellB[n - k + i], {i, 0, k}];
T[, 0] = 1; T[n, k_] := Sum[a11971[i - 1, k - 1], {i, k, n}];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 07 2018, after Andrew Howroyd *)

PARI

A(N)={my(T=matrix(N,N),U=matrix(N,N));T[1,1]=1;U[1,1]=1;
for(n=2,N,for(k=1,n, T[n,k]=if(k==1,T[n-1,n-1],T[n-1,k-1]+T[n,k-1]); U[n,k]=T[n,k]+U[n-1,k]));U}
{my(T=A(10));for(n=0,length(T),for(k=0,n,print1(if(k==0,1,T[n,k]),", "));print)} \\ Andrew Howroyd, Jun 13 2017

Python

from sympy import bell, binomial
def a011971(n, k): return sum([binomial(k, i)*bell(n - k + i) for i in range(k + 1)])
def T(n, k): return 1 if k==0 else sum([a011971(i - 1, k - 1) for i in range(k, n + 1)])
for n in range(10): print([T(n, k) for k in range(n + 1)]) # Indranil Ghosh, Jun 17 2017

Formula

T(n,0) = 1, T(n,k) = Sum_{i=k..n} A011971(i-1,k-1) for k>0. - Andrew Howroyd, Jun 13 2017

Extensions

Terms a(28) and beyond from Andrew Howroyd, Jun 13 2017