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

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

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.

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)

Example

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)

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

Prog

(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

Crossrefs

First column is A000110.

Row sums are A000110(n+1).

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

Sequence in context: A328646 A171670 A124644 * A056857 A175579 A129100

Adjacent sequences: A259688 A259689 A259690 * A259692 A259693 A259694

Keyword

nonn,tabl

Author

N. J. A. Sloane, Jul 05 2015

Extensions

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

Status

approved