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