login
A095684
Triangle read by rows. There are 2^(m-1) rows of length m, for m = 1, 2, 3, ... The rows are in lexicographic order. The rows have the property that the first entry is 1, the second distinct entry (reading from left to right) is 2, the third distinct entry is 3, etc.
11
1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 2, 1, 2, 3, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 3, 1, 2, 2, 2, 1, 2, 2, 3, 1, 2, 3, 3, 1, 2, 3, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 2, 3, 1, 1, 2, 2, 2, 1, 1, 2, 2, 3, 1, 1, 2, 3, 3, 1, 1, 2, 3, 4, 1, 2, 2, 2, 2, 1, 2, 2, 2, 3, 1, 2, 2, 3, 3
OFFSET
1,5
COMMENTS
Row k is the unique multiset that covers an initial interval of positive integers and has multiplicities equal to the parts of the k-th composition in standard order (graded reverse-lexicographic, A066099). This composition is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. For example, the 13th composition is (1,2,1), so row 13 is {1,2,2,3}. - Gus Wiseman, Apr 26 2020
LINKS
J. C. Kieffer, W. Szpankowski and E.-H. Yang, Problems on sequences: information theory and computer science interface, IEEE Trans. Inform. Theory, 50 (No. 7, 2004), 1385-1392.
EXAMPLE
1, 11, 12, 111, 112, 122, 123, 1111, 1112, 1122, 1123, 1222, 1223, 1233, ...
The 8 strings of length 4 are 1111, 1112, 1122, 1123, 1222, 1223, 1233, 1234.
From Gus Wiseman, Apr 26 2020: (Start)
The triangle read by columns begins:
1:{1} 2:{1,1} 4:{1,1,1} 8:{1,1,1,1} 16:{1,1,1,1,1}
3:{1,2} 5:{1,1,2} 9:{1,1,1,2} 17:{1,1,1,1,2}
6:{1,2,2} 10:{1,1,2,2} 18:{1,1,1,2,2}
7:{1,2,3} 11:{1,1,2,3} 19:{1,1,1,2,3}
12:{1,2,2,2} 20:{1,1,2,2,2}
13:{1,2,2,3} 21:{1,1,2,2,3}
14:{1,2,3,3} 22:{1,1,2,3,3}
15:{1,2,3,4} 23:{1,1,2,3,4}
24:{1,2,2,2,2}
25:{1,2,2,2,3}
26:{1,2,2,3,3}
27:{1,2,2,3,4}
28:{1,2,3,3,3}
29:{1,2,3,3,4}
30:{1,2,3,4,4}
31:{1,2,3,4,5}
(End)
MATHEMATICA
stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
ptnToNorm[y_]:=Join@@Table[ConstantArray[i, y[[i]]], {i, Length[y]}];
Table[ptnToNorm[stc[n]], {n, 15}] (* Gus Wiseman, Apr 26 2020 *)
CROSSREFS
See A096299 for another version.
The number of distinct parts in row n is A000120(n), also the maximum part.
Row sums are A029931.
Heinz numbers of rows are A057335.
Row lengths are A070939.
Row products are A284001.
The version for prime indices is A305936.
There are A333942(n) multiset partitions of row n.
Multisets of compositions are counted by A034691.
Combinatory separations of normal multisets are A269134.
All of the following pertain to compositions in standard order (A066099):
- Necklaces are A065609.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Lyndon words are A275692.
- Dealings are counted by A333939.
- Distinct parts are counted by A334028.
Sequence in context: A305501 A184170 A025919 * A205565 A064531 A274468
KEYWORD
nonn,easy,tabf
AUTHOR
N. J. A. Sloane, Jun 25 2004
STATUS
approved