A259691 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).

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, 6, 1, 877, 1348, 1116, 564, 185, 42, 7, 1, 4140, 6526, 5745, 3196, 1175, 300, 56, 8, 1, 21147, 34014, 31443, 18944, 7700, 2190, 455, 72, 9, 1

Offset: 0

Author

N. J. A. Sloane, Jul 05 2015

Keywords

• nonn
• tabl

Comments

Another version of A056857.

See Becker (1948/49) for precise definition.

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

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

Examples

			Triangle begins:
    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, 6, 1;
  ...
From _Andrew Howroyd_, Jun 13 2017: (Start)
For n=3 the 5 solutions with the top rook in row 1 are:
  x      x      x      x      x
  . .    . .    . .    . x    . x
  . . .  . . x  . x .  . . .  . . x
For n=3 the 6 solutions with the top rook in row 2 are:
  .      .      .      .      .      .
  x .    x .    x .    . x    . x    . x
  . . .  . x .  . . x  . . .  x . .  . . x
(End)
		

Links

• Alois P. Heinz, Rows n = 0..140, flattened (first 49 rows from Andrew Howroyd)
• H. W. Becker, Rooks and rhymes, Math. Mag., 22 (1948/49), 23-26. See Table II.
• H. W. Becker, Rooks and rhymes, Math. Mag., 22 (1948/49), 23-26. [Annotated scanned copy]
• Fufa Beyene, Jörgen Backelin, Roberto Mantaci, and Samuel A. Fufa, Set Partitions and Other Bell Number Enumerated Objects, J. Int. Seq., Vol. 26 (2023), Article 23.1.8.
• Giulio Cerbai, Modified ascent sequences and Bell numbers, arXiv:2305.10820 [math.CO], 2023. See p. 17.

Crossrefs

First column is A000110.

Row sums are A000110(n+1).

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

Programs

Maple

b:= proc(n, m) option remember; `if`(n=0, 1,
     `if`(n<0, 1/m, m*b(n-1, m)+b(n-1, m+1)))
    end:
T:= (n, k)-> k*b(n-k, k):
seq(seq(T(n, k), k=1..n+1), n=0..10);  # Alois P. Heinz, Jan 07 2022

Mathematica

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

PARI

bell(n) = sum(k=0, n, stirling(n, k, 2));
T(n,k) = if(k>n, 1, k*sum(i=0,n-k, binomial(n-k,i) * k^i * bell(n-k-i)));
for(n=0,6, for(k=1,n+1, print1(T(n,k),", ")); print) \\ Andrew Howroyd, Jun 13 2017

Formula

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

From Alois P. Heinz, Jan 07 2022: (Start)

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

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

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

Extensions

Name edited and terms a(28) and beyond from Andrew Howroyd, Jun 13 2017