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,5

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

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]

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

Example

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)

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

Prog

(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

Crossrefs

Right edge is A000110.

Column k=1 is A005001.

Row sums are A000110(n+1).

Cf. A011971, A259691.

Sequence in context: A247311 A113547 A218580 * A330664 A330843 A115313

Adjacent sequences: A259694 A259695 A259696 * A259698 A259699 A259700

Keyword

nonn,tabl

Author

N. J. A. Sloane, Jul 05 2015

Extensions

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

Status

approved