login
Numbers k such that the k-th composition in standard order is empty, a singleton, or has its own run-lengths as a subsequence (not necessarily consecutive) that is already counted.
9

%I #8 May 17 2022 17:48:00

%S 0,1,2,4,8,10,16,32,43,58,64,128,256,292,349,442,512,586,676,697,826,

%T 1024,1210,1338,1393,1394,1396,1594,2048,2186,2234,2618,2696,2785,

%U 2786,2792,3130,4096,4282,4410,4666,5178,5569,5570,5572,5576,5584,6202,8192

%N Numbers k such that the k-th composition in standard order is empty, a singleton, or has its own run-lengths as a subsequence (not necessarily consecutive) that is already counted.

%C First differs from A353696 (the consecutive version) in having 22318, corresponding to the binary word 101011100101110 and standard composition (2,2,1,1,3,2,1,1,2), whose run-lengths (2,2,1,1,2,1) are subsequence but not a consecutive subsequence.

%C The k-th composition in standard order (graded reverse-lexicographic, A066099) 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. This gives a bijective correspondence between nonnegative integers and integer compositions.

%e The initial terms, their binary expansions, and the corresponding standard compositions:

%e 0: 0 ()

%e 1: 1 (1)

%e 2: 10 (2)

%e 4: 100 (3)

%e 8: 1000 (4)

%e 10: 1010 (2,2)

%e 16: 10000 (5)

%e 32: 100000 (6)

%e 43: 101011 (2,2,1,1)

%e 58: 111010 (1,1,2,2)

%e 64: 1000000 (7)

%e 128: 10000000 (8)

%e 256: 100000000 (9)

%e 292: 100100100 (3,3,3)

%e 349: 101011101 (2,2,1,1,2,1)

%e 442: 110111010 (1,2,1,1,2,2)

%e 512: 1000000000 (10)

%e 586: 1001001010 (3,3,2,2)

%e 676: 1010100100 (2,2,3,3)

%e 697: 1010111001 (2,2,1,1,3,1)

%t stc[n_]:=Differences[Prepend[Join@@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;

%t rorQ[y_]:=Length[y]<=1||MemberQ[Subsets[y],Length/@Split[y]]&& rorQ[Length/@Split[y]];

%t Select[Range[0,100],rorQ[stc[#]]&]

%Y The non-recursive version for partitions is A325755, counted by A325702.

%Y These compositions are counted by A353391.

%Y The version for partitions A353393, counted by A353426, w/o primes A353389.

%Y The non-recursive version is A353402, counted by A353390.

%Y The non-recursive consecutive case is A353432, counted by A353392.

%Y The consecutive case is A353696, counted by A353430.

%Y A005811 counts runs in binary expansion.

%Y A011782 counts compositions.

%Y A066099 lists compositions in standard order, rev A228351, run-lens A333769.

%Y A329738 counts uniform compositions, partitions A047966.

%Y Statistics of standard compositions:

%Y - Length is A000120, sum A070939.

%Y - Runs are counted by A124767, distinct A351014.

%Y - Subsequences are counted by A334299, contiguous A124770/A124771.

%Y - Runs-resistance is A333628.

%Y Classes of standard compositions:

%Y - Partitions are A114994, multisets A225620, strict A333255, sets A333256.

%Y - Constant compositions are A272919, counted by A000005.

%Y - Golomb rulers are A333222, counted by A169942.

%Y - Knapsack compositions are A333223, counted by A325676.

%Y - Anti-runs are A333489, counted by A003242.

%Y Cf. A032020, A044813, A114640, A165413, A181819, A329739, A318928, A325705, A333224, A353427, A353403.

%K nonn

%O 1,3

%A _Gus Wiseman_, May 16 2022