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

Author

N. J. A. Sloane, Jul 14 2011

Keywords

• nonn
• tabf

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.

Examples

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

Links

• Alois P. Heinz, Rows n = 1..8, flattened
• R. Kaye, A Gray code for set partitions, Info. Proc. Letts., 5 (1976), 171-173.

Crossrefs

This is different from A071159.

Cf. A000110, A120698.

Programs

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