A271423 Number T(n,k) of set partitions of [n] with maximal block length multiplicity equal to k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 1, 1, 0, 4, 0, 1, 0, 5, 9, 0, 1, 0, 16, 25, 10, 0, 1, 0, 82, 70, 35, 15, 0, 1, 0, 169, 406, 245, 35, 21, 0, 1, 0, 541, 2093, 1036, 385, 56, 28, 0, 1, 0, 2272, 10935, 4984, 2331, 504, 84, 36, 0, 1, 0, 17966, 41961, 37990, 13335, 3717, 840, 120, 45, 0, 1

Offset

0,8

Comments

At least one block length occurs exactly k times, and all block lengths occur at most k times.

Links

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

Wikipedia, Partition of a set

Example

T(4,1) = 5: 1234, 123|4, 124|3, 134|2, 1|234.
T(4,2) = 9: 12|34, 12|3|4, 13|24, 13|2|4, 14|23, 1|23|4, 14|2|3, 1|24|3, 1|2|34.
T(4,4) = 1: 1|2|3|4.
Triangle T(n,k) begins:
  1;
  0,     1;
  0,     1,     1;
  0,     4,     0,     1;
  0,     5,     9,     0,     1;
  0,    16,    25,    10,     0,    1;
  0,    82,    70,    35,    15,    0,   1;
  0,   169,   406,   245,    35,   21,   0,   1;
  0,   541,  2093,  1036,   385,   56,  28,   0,  1;
  0,  2272, 10935,  4984,  2331,  504,  84,  36,  0, 1;
  0, 17966, 41961, 37990, 13335, 3717, 840, 120, 45, 0, 1;
  ...

Maple

with(combinat):
b:= proc(n, i, k) option remember; `if`(n=0, 1,
      `if`(i<1, 0, add(multinomial(n, n-i*j, i$j)
        *b(n-i*j, i-1, k)/j!, j=0..min(k, n/i))))
    end:
T:= (n, k)-> b(n$2, k)-`if`(k=0, 0, b(n$2, k-1)):
seq(seq(T(n, k), k=0..n), n=0..12);

Mathematica

multinomial[n_, k_List] := n!/Times @@ (k!); b[n_, i_, k_] := b[n, i, k] = If[n==0, 1, If[i<1, 0, Sum[multinomial[n, Join[{n-i*j}, Array[i&, j]]] * b[n - i*j, i - 1, k]/j!, {j, 0, Min[k, n/i]}]]]; T[n_, k_] := b[n, n, k] - If[k == 0, 0, b[n, n, k - 1]]; Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jan 06 2017, after Alois P. Heinz *)

Crossrefs

Columns k=0-10 give: A000007, A007837 (for n>0), A271731, A271732, A271733, A271734, A271735, A271736, A271737, A271738, A271739.

Row sums give A000110.

Main diagonal gives A000012.

T(2n,n) gives A271425.

Cf. A271424.

Sequence in context: A147311 A147312 A352771 * A372762 A019974 A344373

Adjacent sequences: A271420 A271421 A271422 * A271424 A271425 A271426

Keyword

nonn,tabl

Author

Alois P. Heinz, Apr 07 2016

Status

approved