A165413 -id:A165413 - cp's OEIS frontend

A353403 Number of compositions of n whose own reversed run-lengths are a subsequence (not necessarily consecutive).

1, 1, 0, 0, 3, 2, 5, 12, 16, 30, 45, 94, 159, 285, 477, 864, 1487, 2643

Offset: 0

Gus Wiseman, May 15 2022

			The a(0) = 1 through a(7) = 12 compositions:
  ()  (1)  .  .  (22)   (1121)  (1113)  (1123)
                 (112)  (1211)  (1122)  (1132)
                 (211)          (1221)  (2311)
                                (2211)  (3211)
                                (3111)  (11131)
                                        (11212)
                                        (11221)
                                        (12112)
                                        (12211)
                                        (13111)
                                        (21121)
                                        (21211)

The non-reversed version is A353390, ranked by A353402, partitions A325702.
The non-reversed recursive version is A353391, ranked by A353431.
The non-reversed consecutive case is A353392, ranked by A353432.
The non-reversed recursive consecutive version is A353430.
A003242 counts anti-run compositions, ranked by A333489.
A011782 counts compositions.
A169942 counts Golomb rulers, ranked by A333222.
A325676 counts knapsack compositions, ranked by A333223, partitions A108917.
A325705 counts partitions containing all of their distinct multiplicities.
A329739 counts compositions with all distinct run-lengths, for runs A351013.
Cf. A005811, A032020, A103295, A114640, A165413, A324572, A333755, A353400, A353401, A353426.

Table[Length[Select[Join@@Permutations/@ IntegerPartitions[n],MemberQ[Subsets[#],Reverse[Length/@Split[#]]]&]],{n,0,15}]

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

Original entry on oeis.org

0, 1, 2, 4, 8, 10, 16, 32, 43, 58, 64, 128, 256, 292, 349, 442, 512, 586, 676, 697, 826, 1024, 1210, 1338, 1393, 1394, 1396, 1594, 2048, 2186, 2234, 2618, 2696, 2785, 2786, 2792, 3130, 4096, 4282, 4410, 4666, 5178, 5569, 5570, 5572, 5576, 5584, 6202, 8192

Offset: 1

Gus Wiseman, May 16 2022

nonn

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.

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.

			The initial terms, their binary expansions, and the corresponding standard compositions:
     0:           0  ()
     1:           1  (1)
     2:          10  (2)
     4:         100  (3)
     8:        1000  (4)
    10:        1010  (2,2)
    16:       10000  (5)
    32:      100000  (6)
    43:      101011  (2,2,1,1)
    58:      111010  (1,1,2,2)
    64:     1000000  (7)
   128:    10000000  (8)
   256:   100000000  (9)
   292:   100100100  (3,3,3)
   349:   101011101  (2,2,1,1,2,1)
   442:   110111010  (1,2,1,1,2,2)
   512:  1000000000  (10)
   586:  1001001010  (3,3,2,2)
   676:  1010100100  (2,2,3,3)
   697:  1010111001  (2,2,1,1,3,1)

The non-recursive version for partitions is A325755, counted by A325702.
These compositions are counted by A353391.
The version for partitions A353393, counted by A353426, w/o primes A353389.
The non-recursive version is A353402, counted by A353390.
The non-recursive consecutive case is A353432, counted by A353392.
The consecutive case is A353696, counted by A353430.
A005811 counts runs in binary expansion.
A011782 counts compositions.
A066099 lists compositions in standard order, rev A228351, run-lens A333769.
A329738 counts uniform compositions, partitions A047966.
Statistics of standard compositions:
- Length is A000120, sum A070939.
- Runs are counted by A124767, distinct A351014.
- Subsequences are counted by A334299, contiguous A124770/A124771.
- Runs-resistance is A333628.
Classes of standard compositions:
- Partitions are A114994, multisets A225620, strict A333255, sets A333256.
- Constant compositions are A272919, counted by A000005.
- Golomb rulers are A333222, counted by A169942.
- Knapsack compositions are A333223, counted by A325676.
- Anti-runs are A333489, counted by A003242.
Cf. A032020, A044813, A114640, A165413, A181819, A329739, A318928, A325705, A333224, A353427, A353403.

stc[n_]:=Differences[Prepend[Join@@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
rorQ[y_]:=Length[y]<=1||MemberQ[Subsets[y],Length/@Split[y]]&& rorQ[Length/@Split[y]];
Select[Range[0,100],rorQ[stc[#]]&]

A353432 Numbers k such that the k-th composition in standard order has its own run-lengths as a consecutive subsequence.

Original entry on oeis.org

0, 1, 10, 21, 26, 43, 58, 107, 117, 174, 186, 292, 314, 346, 348, 349, 373, 430, 442, 570, 585, 586, 629, 676, 696, 697, 804, 826, 860, 861, 885, 1082, 1141, 1173, 1210, 1338, 1387, 1392, 1393, 1394, 1396, 1594, 1653, 1700, 1720, 1721, 1882, 2106, 2165, 2186

Offset: 1

Gus Wiseman, May 16 2022

nonn

First differs from A353402 (the non-consecutive version) in lacking 53.

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.

			The initial terms, their binary expansions, and the corresponding standard compositions:
     0:          0  ()
     1:          1  (1)
    10:       1010  (2,2)
    21:      10101  (2,2,1)
    26:      11010  (1,2,2)
    43:     101011  (2,2,1,1)
    58:     111010  (1,1,2,2)
   107:    1101011  (1,2,2,1,1)
   117:    1110101  (1,1,2,2,1)
   174:   10101110  (2,2,1,1,2)
   186:   10111010  (2,1,1,2,2)
   292:  100100100  (3,3,3)
   314:  100111010  (3,1,1,2,2)
   346:  101011010  (2,2,1,2,2)
   348:  101011100  (2,2,1,1,3)
   349:  101011101  (2,2,1,1,2,1)
   373:  101110101  (2,1,1,2,2,1)
   430:  110101110  (1,2,2,1,1,2)
   442:  110111010  (1,2,1,1,2,2)

These compositions are counted by A353392.
This is the consecutive case of A353402, counted by A353390.
The non-consecutive recursive version is A353431, counted by A353391.
The recursive version is A353696, counted by A353430.
A005811 counts runs in binary expansion.
A011782 counts compositions.
A066099 lists compositions in standard order, rev A228351, run-lens A333769.
A329738 counts uniform compositions, partitions A047966.
Statistics of standard compositions:
- Length is A000120, sum A070939.
- Runs are counted by A124767, distinct A351014.
- Subsequences are counted by A334299, contiguous A124770/A124771.
- Runs-resistance is A333628.
Classes of standard compositions:
- Partitions are A114994, strict A333255, rev A225620, strict rev A333256.
- Runs are A272919, counted by A000005.
- Golomb rulers are A333222, counted by A169942.
- Anti-runs are A333489, counted by A003242.
Cf. A044813, A165413, A181819, A318928, A325702, A325705, A325755, A333224, A333755, A353389, A353393, A353403.

stc[n_]:=Differences[Prepend[Join@@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
rorQ[y_]:=Length[y]==0||MemberQ[Join@@Table[Take[y,{i,j}],{i,Length[y]},{j,i,Length[y]}],Length/@Split[y]];
Select[Range[0,10000],rorQ[stc[#]]&]

A353430 Number of integer compositions of n that are empty, a singleton, or whose own run-lengths are a consecutive subsequence that is already counted.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 3, 1, 1, 4, 5, 7, 9, 11, 15, 16, 22, 25, 37, 37, 45

Offset: 0

Gus Wiseman, May 16 2022

			The a(n) compositions for selected n (A..E = 10..14):
  n=4:  n=6:    n=9:      n=10:     n=12:     n=14:
-----------------------------------------------------------
  (4)   (6)     (9)       (A)       (C)       (E)
  (22)  (1122)  (333)     (2233)    (2244)    (2255)
        (2211)  (121122)  (3322)    (4422)    (5522)
                (221121)  (131122)  (151122)  (171122)
                          (221131)  (221124)  (221126)
                                    (221142)  (221135)
                                    (221151)  (221153)
                                    (241122)  (221162)
                                    (421122)  (221171)
                                              (261122)
                                              (351122)
                                              (531122)
                                              (621122)
                                              (122121122)
                                              (221121221)

Non-recursive non-consecutive version: counted by A353390, ranked by A353402, reverse A353403, partitions A325702.
Non-consecutive version: A353391, ranked by A353431, partitions A353426.
Non-recursive version: A353392, ranked by A353432.
A003242 counts anti-run compositions, ranked by A333489.
A011782 counts compositions.
A114901 counts compositions with no runs of length 1.
A169942 counts Golomb rulers, ranked by A333222.
A325676 counts knapsack compositions, ranked by A333223.
A329738 counts uniform compositions, partitions A047966.
A329739 counts compositions with all distinct run-lengths.
Cf. A005811, A032020, A103295, A114640, A165413, A242882, A325705, A333755, A351013, A353400, A353401.

yoyQ[y_]:=Length[y]<=1||MemberQ[Join@@Table[Take[y,{i,j}],{i,Length[y]},{j,i,Length[y]}],Length/@Split[y]]&&yoyQ[Length/@Split[y]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],yoyQ]],{n,0,15}]

A353929 Number of distinct sums of runs (of 0's or 1's) in the binary expansion of n.

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 3, 2, 3, 2, 1, 2, 2, 2, 3, 2, 2, 3, 3, 2, 3, 3, 2, 2, 3, 2, 1, 2, 2, 2, 3, 2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 2, 3, 3, 3, 2, 3, 2, 1, 2, 2, 2, 3, 2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 3, 3, 2, 2, 2, 3, 2, 2, 3

Offset: 0

Gus Wiseman, Jun 26 2022

Assuming the binary digits are not all 1, this is one more than the number of different lengths of runs of 1's in the binary expansion of n.

			The binary expansion of 183 is (1,0,1,1,0,1,1,1), with runs (1), (0), (1,1), (0), (1,1,1), with sums 1, 0, 2, 0, 3, of which four are distinct, so a(183) = 4.

Mathematics Stack Exchange, What is a sequence run? (answered 2011-12-01)

For lengths of all runs we have A165413, firsts A165933.
Numbers whose binary expansion has distinct runs are A175413.
For runs instead of run-sums we have A297770, firsts A350952.
For prime indices we have A353835, weak A353861, firsts A006939.
For standard compositions we have A353849, firsts A246534.
Positions of first appearances are A353930.
A005811 counts runs in binary expansion.
A044813 lists numbers with distinct run-lengths in binary expansion.
A318928 gives runs-resistance of binary expansion.
A351014 counts distinct runs in standard compositions.
Cf. A215203, A353743, A353832, A353847, A353932, A354579.

Table[Length[Union[Total/@Split[IntegerDigits[n,2]]]],{n,0,100}]

from itertools import groupby
def A353929(n): return len(set(sum(map(int,y[1])) for y in groupby(bin(n)[2:]))) # Chai Wah Wu, Jun 26 2022

A353427 Numbers k such that the k-th composition in standard order has all run-lengths > 1.

Original entry on oeis.org

0, 3, 7, 10, 15, 31, 36, 42, 43, 58, 63, 87, 122, 127, 136, 147, 170, 171, 175, 228, 234, 235, 250, 255, 292, 295, 343, 351, 471, 484, 490, 491, 506, 511, 528, 547, 586, 591, 676, 682, 683, 687, 698, 703, 904, 915, 938, 939, 943, 983, 996, 1002, 1003, 1018

Offset: 1

Gus Wiseman, May 16 2022

nonn

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.

			The terms and corresponding compositions begin:
     0: ()
     3: (1,1)
     7: (1,1,1)
    10: (2,2)
    15: (1,1,1,1)
    31: (1,1,1,1,1)
    36: (3,3)
    42: (2,2,2)
    43: (2,2,1,1)
    58: (1,1,2,2)
    63: (1,1,1,1,1,1)
    87: (2,2,1,1,1)
   122: (1,1,1,2,2)
   127: (1,1,1,1,1,1,1)

The version for partitions is A001694, counted by A007690.
The version for parts instead of lengths is A022340, counted by A212804.
These compositions are counted by A114901.
A subset of A348612 (counted by A261983).
The case of all run-lengths = 2 is A351011.
The case of all run-lengths > 2 is counted by A353400.
A005811 counts runs in binary expansion.
A011782 counts compositions.
A066099 lists compositions in standard order, reverse A228351.
Statistics of standard compositions:
- Length is A000120, sum A070939.
- Runs are counted by A124767.
- Runs-resistance is A333628.
- Run-lengths are A333769.
Cf. A044813, A128695, A165413, A240085, A244164, A274174, A318928, A333489, A333755, A353402, A353432.

stc[n_]:=Differences[Prepend[Join@@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Select[Range[0,100],!MemberQ[Length/@Split[stc[#]],1]&]

A353930 Smallest number whose binary expansion has n distinct run-sums.

Original entry on oeis.org

1, 2, 11, 183, 5871, 375775, 48099263, 12313411455, 6304466665215, 6455773865180671, 13221424875890015231, 54154956291645502388223, 443637401941159955564326911, 7268555193403964711965932118015, 238176016577461115681699663643131903, 15609103422420491677315869156516292427775

Offset: 1

Gus Wiseman, Jun 07 2022

nonn

Every sequence can be uniquely split into a sequence of non-overlapping runs. For example, the runs of (2,2,1,1,1,3,2,2) are ((2,2),(1,1,1),(3),(2,2)), with sums (4,3,3,4).

			The terms, binary expansions, and standard compositions begin:
       1:                    1  (1)
       2:                   10  (2)
      11:                 1011  (2,1,1)
     183:             10110111  (2,1,2,1,1,1)
    5871:        1011011101111  (2,1,2,1,1,2,1,1,1,1)
  375775:  1011011101111011111  (2,1,2,1,1,2,1,1,1,2,1,1,1,1,1)

Mathematics Stack Exchange, What is a sequence run? (answered 2011-12-01)

Essentially the same as A215203.
For prime indices instead of binary expansion we have A006939.
For lengths instead of sums of runs we have A165933 = firsts in A165413.
Numbers whose binary expansion has all distinct runs are A175413.
For standard compositions we have A246534, firsts of A353849.
For runs instead of run-sums we have A350952, firsts of A297770.
These are the positions of first appearances in A353929.
A005811 counts runs in binary expansion.
A242882 counts compositions with distinct multiplicities.
A318928 gives runs-resistance of binary expansion.
A351014 counts distinct runs in standard compositions.
A353835 counts partitions with all distinct run-sums, weak A353861.
A353864 counts rucksack partitions.
Cf. A044813, A073093, A181819, A304442, A353743, A353840, A353841, A353842, A353847, A353848, A353850, A353853, A353932, A354582.

qe=Table[Length[Union[Total/@Split[IntegerDigits[n,2]]]],{n,1,10000}];
Table[Position[qe,i][[1,1]],{i,Max@@qe}]

a(n) = {my(t=1); if(n==2, t<<=1, for(k=3, n, t = (t<Andrew Howroyd, Jan 01 2023

Offset corrected and terms a(7) and beyond from Andrew Howroyd, Jan 01 2023

A353428 Number of integer compositions of n with all parts and all run-lengths > 2.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 2, 0, 0, 2, 1, 0, 2, 0, 2, 4, 0, 0, 8, 3, 0, 10, 4, 4, 15, 4, 8, 24, 7, 8, 42, 16, 10, 59, 31, 27, 87, 37, 52, 149, 62, 66, 233, 121, 111, 342, 207, 204, 531, 308, 351, 864, 487, 536, 1373, 864, 865, 2057, 1440, 1509, 3232

Offset: 0

Gus Wiseman, May 16 2022

nonn

			The a(n) compositions for selected n:
  n=16:   n=18:     n=20:    n=21:      n=24:
----------------------------------------------------
  (4444)  (666)     (5555)   (777)      (888)
          (333333)  (44444)  (333444)   (6666)
                             (444333)   (333555)
                             (3333333)  (444444)
                                        (555333)
                                        (3333444)
                                        (4443333)
                                        (33333333)

Alois P. Heinz, Table of n, a(n) for n = 0..2000

Allowing any multiplicities gives A078012, partitions A008483.
The version for no (instead of all) parts or run-lengths > 2 is A137200.
Allowing any parts gives A353400, partitions A100405.
The version for partitions is A353501, ranked by A353502.
The version for > 1 instead of > 2 is A353508, partitions A339222.
A003242 counts anti-run compositions, ranked by A333489.
A008466 counts compositions with some part > 2.
A011782 counts compositions.
A114901 counts compositions with no runs of length 1, ranked by A353427.
A128695 counts compositions with no run-lengths > 2.
A261983 counts non-anti-run compositions.
A335464 counts compositions with a run-length > 2.
Cf. A032020, A044813, A098859, A165413, A318928, A329738, A329739, A333755, A353390, A353429.

b:= proc(n, h) option remember; `if`(n=0, 1, add(
     `if`(i=h, 0, add(b(n-i*j, i), j=3..n/i)), i=3..n/3))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..80);  # Alois P. Heinz, May 18 2022

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MemberQ[#,1|2]&&!MemberQ[Length/@Split[#],1|2]&]],{n,0,15}]

a(26)-a(66) from Alois P. Heinz, May 17 2022

A165414 a(n) = number of run-lengths that each occur only once in the binary representation of n.

Original entry on oeis.org

1, 0, 1, 2, 0, 2, 1, 2, 1, 0, 1, 0, 1, 2, 1, 2, 1, 1, 1, 1, 0, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 3, 0, 1, 0, 3, 1, 1, 0, 1, 0, 1, 1, 1, 2, 3, 0, 0, 0, 1, 0, 3, 0, 3, 1, 3, 2, 1, 2, 1, 2, 1, 1, 3, 2, 1, 2, 1, 2, 0, 1, 0, 1, 0, 2, 3, 1, 1, 1, 0, 1, 0, 1, 1, 2, 0, 1, 0, 2, 1, 1, 1, 2, 3, 2, 1, 1, 0, 1, 1, 2, 0

Offset: 1

Leroy Quet, Sep 17 2009

			92 in binary is 1011100. There is a run of one 1, followed by a run of one 0, then a run of three 1's, then finally a run of two 0's. The run lengths are therefore (1,1,3,2). The values of these run lengths that each only occur once are (3,2). Since there are 2 values that occur once, then a(92) = 2.

Gheorghe Coserea, Table of n, a(n) for n = 1..10000

Cf. A005811, A165413.

Table[Count[Tally[Length/@Split[IntegerDigits[n,2]]],?(#[[2]]==1&)],{n,120}] (* _Harvey P. Dale, May 11 2017 *)

binruns(n) = {
  if (n == 0, return([1, 0]));
  my(bag = List(), v=0);
  while(n != 0,
        v = valuation(n,2); listput(bag, v); n >>= v; n++;
        v = valuation(n,2); listput(bag, v); n >>= v; n--);
  return(Vec(bag));
};
a(n) = {
    my(v = binruns(n), hist = vector(1+logint(n+1, 2)));
    for (i = 1, #v, if (v[i] != 0, hist[v[i]]++));
    #select(k->(k==1), hist)
};
vector(105, i, a(i))  \\ Gheorghe Coserea, Sep 24 2015

Extended by Ray Chandler, Mar 13 2010

cp's OEIS Frontend

A353403 Number of compositions of n whose own reversed run-lengths are a subsequence (not necessarily consecutive).

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A353432 Numbers k such that the k-th composition in standard order has its own run-lengths as a consecutive subsequence.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A353430 Number of integer compositions of n that are empty, a singleton, or whose own run-lengths are a consecutive subsequence that is already counted.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A353929 Number of distinct sums of runs (of 0's or 1's) in the binary expansion of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

A353427 Numbers k such that the k-th composition in standard order has all run-lengths > 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A353930 Smallest number whose binary expansion has n distinct run-sums.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A353428 Number of integer compositions of n with all parts and all run-lengths > 2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A165414 a(n) = number of run-lengths that each occur only once in the binary representation of n.

Views