cp's OEIS Frontend

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

%I A259697 #49 Jun 18 2025 10:07:41
%S A259697 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,
%T A259697 203,203,1,279,354,451,575,726,877,877,1,1156,1434,1786,2232,2792,
%U A259697 3466,4140,4140,1,5296,6451,7883,9664,11881,14621,17884,21147,21147
%N A259697 Triangle read by rows: T(n,k) = number of rook patterns on n X n board where bottom rook is in column k.
%C A259697 See Becker (1948/49) for precise definition.
%C A259697 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
%H A259697 Andrew Howroyd, <a href="/A259697/b259697.txt">Table of n, a(n) for n = 0..1274</a>
%H A259697 H. W. Becker, <a href="http://www.jstor.org/stable/3029709">Rooks and rhymes</a>, Math. Mag. 22 (1948/49), 23-26. See Table V.
%H A259697 H. W. Becker, <a href="/A056857/a056857.pdf">Rooks and rhymes</a>, Math. Mag., 22 (1948/49), 23-26. [Annotated scanned copy]
%F A259697 T(n,0) = 1, T(n,k) = Sum_{i=k..n} A011971(i-1,k-1) for k>0. - _Andrew Howroyd_, Jun 13 2017
%e A259697 Triangle begins:
%e A259697   1,
%e A259697   1,  1,
%e A259697   1,  2,  2,
%e A259697   1,  4,  5,   5,
%e A259697   1,  9, 12,  15,  15,
%e A259697   1, 24, 32,  42,  52,  52,
%e A259697   1, 76, 99, 129, 166, 203, 203,
%e A259697   ...
%e A259697 From _Andrew Howroyd_, Jun 13 2017: (Start)
%e A259697 For n=3, the four solutions with the bottom rook in column 1 are:
%e A259697   .      .      .      x
%e A259697   . .    . x    x .    . .
%e A259697   x . .  x . .  . . .  . . .
%e A259697 For n=3, the five solutions with the bottom rook in column 2 are:
%e A259697   .      .      x      .       x
%e A259697   . .    x .    . .    . x     . x
%e A259697   . x .  . x .  . x .  . . .   . . .
%e A259697 (End)
%t A259697 a11971[n_, k_] := Sum[Binomial[k, i]*BellB[n - k + i], {i, 0, k}];
%t A259697 T[_, 0] = 1; T[n_, k_] := Sum[a11971[i - 1, k - 1], {i, k, n}];
%t A259697 Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Jul 07 2018, after _Andrew Howroyd_ *)
%o A259697 (PARI)
%o A259697 A(N)={my(T=matrix(N,N),U=matrix(N,N));T[1,1]=1;U[1,1]=1;
%o A259697 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}
%o A259697 {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
%o A259697 (Python)
%o A259697 from sympy import bell, binomial
%o A259697 def a011971(n, k): return sum([binomial(k, i)*bell(n - k + i) for i in range(k + 1)])
%o A259697 def T(n, k): return 1 if k==0 else sum([a011971(i - 1, k - 1) for i in range(k, n + 1)])
%o A259697 for n in range(10): print([T(n, k) for k in range(n + 1)]) # _Indranil Ghosh_, Jun 17 2017
%Y A259697 Right edge is A000110.
%Y A259697 Column k=1 is A005001.
%Y A259697 Row sums are A000110(n+1).
%Y A259697 Cf. A011971, A259691.
%K A259697 nonn,tabl
%O A259697 0,5
%A A259697 _N. J. A. Sloane_, Jul 05 2015
%E A259697 Terms a(28) and beyond from _Andrew Howroyd_, Jun 13 2017