cp's OEIS Frontend

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.

%I A193023 #47 Jan 02 2022 19:12:43
%S A193023 1,11,12,111,112,121,122,123,1111,1112,1121,1122,1123,1211,1212,1213,
%T A193023 1221,1222,1223,1231,1232,1233,1234,11111,11112,11121,11122,11123,
%U A193023 11211,11212,11213,11221,11222,11223,11231,11232,11233,11234,12111,12112,12113,12121
%N 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.
%C A193023 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.
%C A193023 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).
%C A193023 This provides a canonical ordering for partitions of a labeled set.
%H A193023 Alois P. Heinz, <a href="/A193023/b193023.txt">Rows n = 1..8, flattened</a>
%H A193023 R. Kaye, <a href="http://dx.doi.org/10.1016/0020-0190(76)90014-4">A Gray code for set partitions</a>, Info. Proc. Letts., 5 (1976), 171-173.
%e A193023 Triangle begins:
%e A193023   1;
%e A193023   11,12;
%e A193023   111,112,121,122,123;
%e A193023   1111,1112,1121,1122,1123,1211,1212,1213,1221,1222,1223,1231,1232,1233,1234;
%e A193023   11111,11112,11121,11122,11123,...
%p A193023 b:= proc(n) option remember;
%p A193023       `if`(n=1, [[1]], map(x-> seq([x[], i], i=1..max(x[])+1), b(n-1)))
%p A193023     end:
%p A193023 T:= n-> map(x-> parse(cat(x[])), b(n))[]:
%p A193023 seq(T(n), n=1..5);  # _Alois P. Heinz_, Sep 30 2011
%t A193023 b[n_] := b[n] = If[n == 1, {{1}}, Table[Append[#, i], {i, 1, Max[#]+1}]& /@ b[n-1] // Flatten[#, 1]&];
%t A193023 T[n_] := FromDigits /@ b[n];
%t A193023 Array[T, 8] // Flatten (* _Jean-François Alcover_, Feb 19 2021, after _Alois P. Heinz_ *)
%Y A193023 This is different from A071159.
%Y A193023 Cf. A000110, A120698.
%K A193023 nonn,tabf
%O A193023 1,2
%A A193023 _N. J. A. Sloane_, Jul 14 2011