A193023 Triangle read by rows: the n-th row has length A000110(n) and contains all set partitions of an n-set in canonical order.

1, 11, 12, 111, 112, 121, 122, 123, 1111, 1112, 1121, 1122, 1123, 1211, 1212, 1213, 1221, 1222, 1223, 1231, 1232, 1233, 1234, 11111, 11112, 11121, 11122, 11123, 11211, 11212, 11213, 11221, 11222, 11223, 11231, 11232, 11233, 11234, 12111, 12112, 12113, 12121

Offset

1,2

Comments

The set partition of [1,2,3,4] given by 13/2/4 would be encoded as 1213: simply record which part i is in, for i=1..n.

To get row n, read row n-1 from left to right. If row n-1 contains a word abc...d, in which the maximal number is m, then in row n we place the words abc...d1, abc...d2, abc...d3, ..., abc...d(m+1).

This provides a canonical ordering for partitions of a labeled set.

Links

Alois P. Heinz, Rows n = 1..8, flattened

R. Kaye, A Gray code for set partitions, Info. Proc. Letts., 5 (1976), 171-173.

Example

Triangle begins:
  1;
  11,12;
  111,112,121,122,123;
  1111,1112,1121,1122,1123,1211,1212,1213,1221,1222,1223,1231,1232,1233,1234;
  11111,11112,11121,11122,11123,...

Maple

b:= proc(n) option remember;
      `if`(n=1, [[1]], map(x-> seq([x[], i], i=1..max(x[])+1), b(n-1)))
    end:
T:= n-> map(x-> parse(cat(x[])), b(n))[]:
seq(T(n), n=1..5);  # Alois P. Heinz, Sep 30 2011

Mathematica

b[n_] := b[n] = If[n == 1, {{1}}, Table[Append[#, i], {i, 1, Max[#]+1}]& /@ b[n-1] // Flatten[#, 1]&];
T[n_] := FromDigits /@ b[n];
Array[T, 8] // Flatten (* Jean-François Alcover, Feb 19 2021, after Alois P. Heinz *)

Crossrefs

This is different from A071159.

Cf. A000110, A120698.

Sequence in context: A082262 A239463 A153070 * A278985 A071159 A231873

Adjacent sequences: A193020 A193021 A193022 * A193024 A193025 A193026

Keyword

nonn,tabf

Author

N. J. A. Sloane, Jul 14 2011

Status

approved