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