A276921 Number A(n,k) of ordered set partitions of [n] with at most k elements per block; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 0, 1, 1, 0, 1, 1, 2, 0, 1, 1, 3, 6, 0, 1, 1, 3, 12, 24, 0, 1, 1, 3, 13, 66, 120, 0, 1, 1, 3, 13, 74, 450, 720, 0, 1, 1, 3, 13, 75, 530, 3690, 5040, 0, 1, 1, 3, 13, 75, 540, 4550, 35280, 40320, 0, 1, 1, 3, 13, 75, 541, 4670, 45570, 385560, 362880, 0

Offset

0,9

Links

Alois P. Heinz, Antidiagonals n = 0..140, flattened

Daniel Birmajer, Juan B. Gil, David S. Kenepp, and Michael D. Weiner, Restricted generating trees for weak orderings, arXiv:2108.04302 [math.CO], 2021.

Formula

E.g.f. of column k: 1/(1-Sum_{i=1..k} x^i/i!).

A(n,k) = Sum_{j=0..k} A276922(n,j).

Example

Square array A(n,k) begins:
  1,    1,     1,     1,     1,     1,     1,     1, ...
  0,    1,     1,     1,     1,     1,     1,     1, ...
  0,    2,     3,     3,     3,     3,     3,     3, ...
  0,    6,    12,    13,    13,    13,    13,    13, ...
  0,   24,    66,    74,    75,    75,    75,    75, ...
  0,  120,   450,   530,   540,   541,   541,   541, ...
  0,  720,  3690,  4550,  4670,  4682,  4683,  4683, ...
  0, 5040, 35280, 45570, 47110, 47278, 47292, 47293, ...

Maple

A:= proc(n, k) option remember; `if`(n=0, 1, add(
       A(n-i, k)*binomial(n, i), i=1..min(n, k)))
    end:
seq(seq(A(n, d-n), n=0..d), d=0..12);

Mathematica

A[n_, k_] := A[n, k] = If[n==0, 1, Sum[A[n-i, k]*Binomial[n, i], {i, 1, Min[n, k]}]]; Table[A[n, d-n], {d, 0, 12}, {n, 0, d}] // Flatten (* Jean-François Alcover, Feb 03 2017, translated from Maple *)

Crossrefs

Columns k=0..10 give: A000007, A000142, A080599, A189886, A276924, A276925, A276926, A276927, A276928, A276929, A276930.

Main diagonal gives A000670.

Cf. A276922.

Sequence in context: A261440 A295684 A276890 * A339677 A333158 A293135

Adjacent sequences: A276918 A276919 A276920 * A276922 A276923 A276924

Keyword

nonn,tabl

Author

Alois P. Heinz, Sep 22 2016

Status

approved