login
Triangle read by rows: T(n,k) number of arrangements of non-attacking rooks on an n X n right triangular board where the top rook is in row k (n >= 0, 1 <= k <= n+1).
8

%I #53 May 24 2023 13:12:53

%S 1,1,1,2,2,1,5,6,3,1,15,20,12,4,1,52,74,51,20,5,1,203,302,231,104,30,

%T 6,1,877,1348,1116,564,185,42,7,1,4140,6526,5745,3196,1175,300,56,8,1,

%U 21147,34014,31443,18944,7700,2190,455,72,9,1

%N Triangle read by rows: T(n,k) number of arrangements of non-attacking rooks on an n X n right triangular board where the top rook is in row k (n >= 0, 1 <= k <= n+1).

%C Another version of A056857.

%C See Becker (1948/49) for precise definition.

%C The case of n=k+1 corresponds to the empty board where there is no top rook. - _Andrew Howroyd_, Jun 13 2017

%C T(n-1,k) is the number of partitions of [n] where exactly k blocks contain their own index element. T(3,2) = 6: 134|2, 13|24, 13|2|4, 14|23, 1|234, 1|23|4. - _Alois P. Heinz_, Jan 07 2022

%H Alois P. Heinz, <a href="/A259691/b259691.txt">Rows n = 0..140, flattened</a> (first 49 rows from Andrew Howroyd)

%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 II.

%H H. W. Becker, <a href="/A056857/a056857.pdf">Rooks and rhymes</a>, Math. Mag., 22 (1948/49), 23-26. [Annotated scanned copy]

%H Fufa Beyene, Jörgen Backelin, Roberto Mantaci, and Samuel A. Fufa, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Beyene/beyene13.html">Set Partitions and Other Bell Number Enumerated Objects</a>, J. Int. Seq., Vol. 26 (2023), Article 23.1.8.

%H Giulio Cerbai, <a href="https://arxiv.org/abs/2305.10820">Modified ascent sequences and Bell numbers</a>, arXiv:2305.10820 [math.CO], 2023. See p. 17.

%F T(n,n+1) = 1, T(n,k) = k*Sum_{i=0..n-k} binomial(n-k,i) * k^i * Bell(n-k-i) for k<=n. - _Andrew Howroyd_, Jun 13 2017

%F From _Alois P. Heinz_, Jan 07 2022: (Start)

%F T(n,k) = k * A108087(n-k,k) for 1 <= k <= n.

%F Sum_{k=1..n+1} k * T(n,k) = A350589(n+1).

%F Sum_{k=1..n+1} (k+1) * T(n,k) = A347420(n+1). (End)

%e Triangle begins:

%e 1;

%e 1, 1;

%e 2, 2, 1;

%e 5, 6, 3, 1;

%e 15, 20, 12, 4, 1;

%e 52, 74, 51, 20, 5, 1;

%e 203, 302, 231, 104, 30, 6, 1;

%e ...

%e From _Andrew Howroyd_, Jun 13 2017: (Start)

%e For n=3 the 5 solutions with the top rook in row 1 are:

%e x x x x x

%e . . . . . . . x . x

%e . . . . . x . x . . . . . . x

%e For n=3 the 6 solutions with the top rook in row 2 are:

%e . . . . . .

%e x . x . x . . x . x . x

%e . . . . x . . . x . . . x . . . . x

%e (End)

%p b:= proc(n, m) option remember; `if`(n=0, 1,

%p `if`(n<0, 1/m, m*b(n-1, m)+b(n-1, m+1)))

%p end:

%p T:= (n, k)-> k*b(n-k, k):

%p seq(seq(T(n, k), k=1..n+1), n=0..10); # _Alois P. Heinz_, Jan 07 2022

%t T[n_, k_] := If[k>n, 1, k*Sum[Binomial[n-k, i]*k^i*BellB[n-k-i], {i, 0, n - k}]];

%t Table[T[n, k], {n, 0, 10}, {k, 1, n+1}] // Flatten (* _Jean-François Alcover_, Jul 03 2018, after _Andrew Howroyd_ *)

%o (PARI)

%o bell(n) = sum(k=0, n, stirling(n, k, 2));

%o T(n,k) = if(k>n, 1, k*sum(i=0,n-k, binomial(n-k,i) * k^i * bell(n-k-i)));

%o for(n=0,6, for(k=1,n+1, print1(T(n,k),", ")); print) \\ _Andrew Howroyd_, Jun 13 2017

%Y First column is A000110.

%Y Row sums are A000110(n+1).

%Y Cf. A056857, A259697, A108087, A347420, A350589.

%K nonn,tabl

%O 0,4

%A _N. J. A. Sloane_, Jul 05 2015

%E Name edited and terms a(28) and beyond from _Andrew Howroyd_, Jun 13 2017