A329745 -id:A329745 - cp's OEIS frontend

A351291 Numbers k such that the k-th composition in standard order does not have all distinct runs.

13, 22, 25, 45, 46, 49, 53, 54, 59, 76, 77, 82, 89, 91, 93, 94, 97, 101, 102, 105, 108, 109, 110, 115, 118, 141, 148, 150, 153, 156, 162, 165, 166, 173, 177, 178, 180, 181, 182, 183, 187, 189, 190, 193, 197, 198, 201, 204, 205, 209, 210, 213, 214, 216, 217

Offset: 1

Gus Wiseman, Feb 12 2022

nonn

The n-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 n, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The terms together with their binary expansions and corresponding compositions begin:
  13:     1101  (1,2,1)
  22:    10110  (2,1,2)
  25:    11001  (1,3,1)
  45:   101101  (2,1,2,1)
  46:   101110  (2,1,1,2)
  49:   110001  (1,4,1)
  53:   110101  (1,2,2,1)
  54:   110110  (1,2,1,2)
  59:   111011  (1,1,2,1,1)
  76:  1001100  (3,1,3)
  77:  1001101  (3,1,2,1)
  82:  1010010  (2,3,2)
  89:  1011001  (2,1,3,1)
  91:  1011011  (2,1,2,1,1)
  93:  1011101  (2,1,1,2,1)
  94:  1011110  (2,1,1,1,2)

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

The version for Heinz numbers of partitions is A130092, complement A130091.
Normal multisets with a permutation of this type appear to be A283353.
Partitions w/o permutations of this type are A351204, complement A351203.
The version using binary expansions is A351205, complement A175413.
The complement is A351290, counted by A351013.
A005811 counts runs in binary expansion, distinct A297770.
A011782 counts integer compositions.
A044813 lists numbers whose binary expansion has all distinct run-lengths.
A085207 represents concatenation of standard compositions, reverse A085208.
A333489 ranks anti-runs, complement A348612, counted by A003242.
A345167 ranks alternating compositions, counted by A025047.
Counting words with all distinct runs:
- A351016 = binary words, for run-lengths A351017.
- A351018 = binary expansions, for run-lengths A032020.
- A351200 = patterns, for run-lengths A351292.
- A351202 = permutations of prime factors.
Selected statistics of standard compositions (A066099, reverse A228351):
- Length is A000120.
- Sum is A070939.
- Runs are counted by A124767, distinct A351014.
- Heinz number is A333219.
- Number of distinct parts is A334028.
Selected classes of standard compositions:
- Partitions are A114994, strict A333256.
- Multisets are A225620, strict A333255.
- Strict compositions are A233564.
- Constant compositions are A272919.
Cf. A098859, A106356, A113835, A116608, A238279, A242882, A318928, A325545, A328592, A329745, A350952, A351015, A351201.

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

A319411 Triangle read by rows: T(n,k) = number of binary vectors of length n with runs-resistance k (1 <= k <= n).

Original entry on oeis.org

2, 2, 2, 2, 2, 4, 2, 4, 6, 4, 2, 2, 12, 12, 4, 2, 6, 30, 18, 8, 0, 2, 2, 44, 44, 32, 4, 0, 2, 6, 82, 76, 74, 16, 0, 0, 2, 4, 144, 138, 172, 52, 0, 0, 0, 2, 6, 258, 248, 350, 156, 4, 0, 0, 0, 2, 2, 426, 452, 734, 404, 28, 0, 0, 0, 0, 2, 10, 790, 752, 1500, 938, 104, 0, 0, 0, 0, 0

Offset: 1

N. J. A. Sloane, Sep 20 2018

"Runs-resistance" is defined in A318928.
Row sums are 2,4,8,16,... (the binary vectors may begin with 0 or 1).
This is similar to A329767 but without the k = 0 column and with a different row n = 1. - Gus Wiseman, Nov 25 2019

			Triangle begins:
2,
2, 2,
2, 2, 4,
2, 4, 6, 4,
2, 2, 12, 12, 4,
2, 6, 30, 18, 8, 0,
2, 2, 44, 44, 32, 4, 0,
2, 6, 82, 76, 74, 16, 0, 0,
2, 4, 144, 138, 172, 52, 0, 0, 0,
2, 6, 258, 248, 350, 156, 4, 0, 0, 0,
2, 2, 426, 452, 734, 404, 28, 0, 0, 0, 0,
2, 10, 790, 752, 1500, 938, 104, 0, 0, 0, 0, 0,
...
Lenormand gives the first 20 rows.
The calculation of row 4 is as follows.
We may assume the first bit is a 0, and then double the answers.
vector / runs / steps to reach a single number:
0000 / 4 / 1
0001 / 31 -> 11 -> 2 / 3
0010 / 211 -> 12 -> 11 -> 2 / 4
0011 / 22 -> 2 / 2
0100 / 112 -> 21 -> 11 -> 2 / 4
0101 / 1111 -> 4 / 2
0110 / 121 -> 111 -> 3 / 3
0111 / 13 -> 11 -> 2 / 3
and we get 1 (once), 2 (twice), 3 (three times) and 4 (twice).
So row 4 is: 2,4,6,4.

Hiroaki Yamanouchi, Table of n, a(n) for n = 1..1830
Claude Lenormand, Deux transformations sur les mots, Preprint, 5 pages, Nov 17 2003. Apparently unpublished. This is a scanned copy of the version that the author sent to me in 2003.

Row sums are A000079.
Column k = 2 is 2 * A032741 = A319410.
Column k = 3 is 2 * A329745 (because runs-resistance 2 for compositions corresponds to runs-resistance 3 for binary words).
The version for compositions is A329744.
The version for partitions is A329746.
The number of nonzero entries in row n > 0 is A319412(n).
The runs-resistance of the binary expansion of n is A318928.
Cf. A096365, A225485, A245563, A319413, A319414, A319415, A325280, A329747, A329750, A329767, A329870.

runsresist[q_]:=If[Length[q]==1,1,Length[NestWhileList[Length/@Split[#]&,q,Length[#]>1&]]-1];
Table[Length[Select[Tuples[{0,1},n],runsresist[#]==k&]],{n,10},{k,n}] (* Gus Wiseman, Nov 25 2019 *)

A329767 Triangle read by rows where T(n,k) is the number of binary words of length n >= 0 with runs-resistance k, 0 <= k <= n.

Original entry on oeis.org

1, 2, 0, 0, 2, 2, 0, 2, 2, 4, 0, 2, 4, 6, 4, 0, 2, 2, 12, 12, 4, 0, 2, 6, 30, 18, 8, 0, 0, 2, 2, 44, 44, 32, 4, 0, 0, 2, 6, 82, 76, 74, 16, 0, 0, 0, 2, 4, 144, 138, 172, 52, 0, 0, 0, 0, 2, 6, 258, 248, 350, 156, 4, 0, 0, 0, 0, 2, 2, 426, 452, 734, 404, 28, 0, 0, 0, 0

Offset: 0

Gus Wiseman, Nov 21 2019

A composition of n is a finite sequence of positive integers with sum n.
For the operation of taking the sequence of run-lengths of a finite sequence, runs-resistance is defined as the number of applications required to reach a singleton.
Except for the k = 0 column and the n = 0 and n = 1 rows, this is the triangle appearing on page 3 of Lenormand, which is A319411. Unlike A318928, we do not here require that a(n) >= 1.
The n = 0 row is chosen to ensure that the row-sums are A000079, although the empty word arguably has indeterminate runs-resistance.

			Triangle begins:
   1
   2   0
   0   2   2
   0   2   2   4
   0   2   4   6   4
   0   2   2  12  12   4
   0   2   6  30  18   8   0
   0   2   2  44  44  32   4   0
   0   2   6  82  76  74  16   0   0
   0   2   4 144 138 172  52   0   0   0
   0   2   6 258 248 350 156   4   0   0   0
   0   2   2 426 452 734 404  28   0   0   0   0
For example, row n = 4 counts the following words:
  0000  0011  0001  0010
  1111  0101  0110  0100
        1010  0111  1011
        1100  1000  1101
              1001
              1110

Claude Lenormand, Deux transformations sur les mots, Preprint, 5 pages, Nov 17 2003.

Row sums are A000079.
Column k = 2 is A319410.
Column k = 3 is 2 * A329745.
The version for compositions is A329744.
The version for partitions is A329746.
The number of nonzero entries in row n > 0 is A319412(n).
The runs-resistance of the binary expansion of n is A318928.
Cf. A001037, A096365, A225485, A245563, A319411, A325280, A329747, A329750.

runsres[q_]:=If[Length[q]==1,0,Length[NestWhileList[Length/@Split[#]&,q,Length[#]>1&]]-1];
Table[Length[Select[Tuples[{0,1},n],runsres[#]==k&]],{n,0,10},{k,0,n}]

A329862 Positive integers whose binary expansion has cuts-resistance 2.

Original entry on oeis.org

3, 4, 6, 9, 11, 12, 13, 18, 19, 20, 22, 25, 26, 37, 38, 41, 43, 44, 45, 50, 51, 52, 53, 74, 75, 76, 77, 82, 83, 84, 86, 89, 90, 101, 102, 105, 106, 149, 150, 153, 154, 165, 166, 169, 171, 172, 173, 178, 179, 180, 181, 202, 203, 204, 205, 210, 211, 212, 213

Offset: 1

Gus Wiseman, Nov 23 2019

nonn

For the operation of shortening all runs by 1, cuts-resistance is defined to be the number of applications required to reach an empty word.

			The sequence of terms together with their binary expansions begins:
   3:      11
   4:     100
   6:     110
   9:    1001
  11:    1011
  12:    1100
  13:    1101
  18:   10010
  19:   10011
  20:   10100
  22:   10110
  25:   11001
  26:   11010
  37:  100101
  38:  100110
  41:  101001
  43:  101011
  44:  101100
  45:  101101
  50:  110010

Claude Lenormand, Deux transformations sur les mots, Preprint, 5 pages, Nov 17 2003.

Positions of 2's in A319416.
Numbers whose binary expansion has cuts-resistance 1 are A000975.
Binary words with cuts-resistance 2 are conjectured to be A027383.
Compositions with cuts-resistance 2 are A329863.
Cuts-resistance of binary expansion without first digit is A319420.
Binary words counted by cuts-resistance are A319421 and A329860.
Compositions counted by cuts-resistance are A329861.
Cf. A107907, A114901, A164707, A318928, A319411, A329745, A329865, A329866.

degdep[q_]:=Length[NestWhileList[Join@@Rest/@Split[#]&,q,Length[#]>0&]]-1;
Select[Range[100],degdep[IntegerDigits[#,2]]==2&]

A329863 Number of compositions of n with cuts-resistance 2.

Original entry on oeis.org

0, 0, 1, 0, 3, 6, 9, 22, 47, 88, 179, 354, 691, 1344, 2617, 5042, 9709, 18632, 35639, 68010, 129556, 246202, 467188, 885036, 1674211, 3163094, 5969022, 11251676, 21189382, 39867970, 74950464, 140798302, 264313039, 495861874, 929709687, 1742193854, 3263069271, 6108762316

Offset: 0

Gus Wiseman, Nov 23 2019

nonn

A composition of n is a finite sequence of positive integers summing to n.

For the operation of shortening all runs by 1, cuts-resistance is defined to be the number of applications required to reach an empty word.

			The a(2) = 1 through a(7) = 22 compositions (empty column not shown):
  (1,1)  (2,2)    (1,1,3)    (3,3)      (1,1,5)
         (1,1,2)  (1,2,2)    (1,1,4)    (1,3,3)
         (2,1,1)  (2,2,1)    (4,1,1)    (2,2,3)
                  (3,1,1)    (1,1,2,2)  (3,2,2)
                  (1,1,2,1)  (1,1,3,1)  (3,3,1)
                  (1,2,1,1)  (1,2,2,1)  (5,1,1)
                             (1,3,1,1)  (1,1,2,3)
                             (2,1,1,2)  (1,1,3,2)
                             (2,2,1,1)  (1,1,4,1)
                                        (1,4,1,1)
                                        (2,1,1,3)
                                        (2,1,2,2)
                                        (2,2,1,2)
                                        (2,3,1,1)
                                        (3,1,1,2)
                                        (3,2,1,1)
                                        (1,1,2,1,2)
                                        (1,1,2,2,1)
                                        (1,2,1,1,2)
                                        (1,2,2,1,1)
                                        (2,1,1,2,1)
                                        (2,1,2,1,1)

Claude Lenormand, Deux transformations sur les mots, Preprint, 5 pages, Nov 17 2003.

Column k = 2 of A329861.
Compositions with cuts-resistance 1 are A003242.
Compositions with runs-resistance 2 are A329745.
Numbers whose binary expansion has cuts-resistance 2 are A329862.
Binary words with cuts-resistance 2 are conjectured to be A027383.
Cuts-resistance of binary expansion is A319416.
Binary words counted by cuts-resistance are A319421 and A329860.
Cf. A000975, A003242, A032020, A114901, A240085, A261983, A319420, A329738, A329744, A329864.

degdep[q_]:=Length[NestWhileList[Join@@Rest/@Split[#]&,q,Length[#]>0&]]-1;
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],degdep[#]==2&]],{n,0,10}]

Ca(N) = {1/(1-sum(k=1, N, x^k/(1+x^k)))}
A_x(N) = {my(x='x+O('x^N)); concat([0,0],Vec(-1+(1+sum(m=1,N, Ca(N)*x^(2*m)*(Ca(N)-1)/(1+x^m*(2+x^m*(1+Ca(N))))))/(1-sum(m=1,N, Ca(N)*x^(2*m)/(1+x^m*(2+x^m*(1+Ca(N))))))))}
A_x(38) \\ John Tyler Rascoe, Feb 20 2025

G.f.: -1 + (1 + Ca(x) * Sum_{m>0} x^(2*m) * (Ca(x)-1)/(1 + x^m * (2 + x^m * (1+Ca(x)))))/(1 - Ca(x) * Sum_{m>0} x^(2*m)/(1 + x^m * (2 + x^m * (1+Ca(x))))) where Ca(x) is the g.f. for A003242. - John Tyler Rascoe, Feb 20 2025

a(21) onwards from John Tyler Rascoe, Feb 20 2025

A329750 Triangle read by rows where T(n,k) is the number of compositions of n >= 1 with runs-resistance n - k, 1 <= k <= n.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 2, 3, 2, 1, 2, 6, 6, 1, 1, 0, 4, 9, 15, 3, 1, 0, 2, 16, 22, 22, 1, 1, 0, 0, 8, 37, 38, 41, 3, 1, 0, 0, 0, 26, 86, 69, 72, 2, 1, 0, 0, 0, 2, 78, 175, 124, 129, 3, 1, 0, 0, 0, 0, 14, 202, 367, 226, 213, 1, 1, 0, 0, 0, 0, 0, 52, 469, 750, 376, 395, 5, 1

Offset: 1

Gus Wiseman, Nov 21 2019

A composition of n is a finite sequence of positive integers with sum n.

For the operation of taking the sequence of run-lengths of a finite sequence, runs-resistance is defined as the number of applications required to reach a singleton.

			Triangle begins:
   1
   1   1
   2   1   1
   2   3   2   1
   2   6   6   1   1
   0   4   9  15   3   1
   0   2  16  22  22   1   1
   0   0   8  37  38  41   3   1
   0   0   0  26  86  69  72   2   1
   0   0   0   2  78 175 124 129   3   1
   0   0   0   0  14 202 367 226 213   1   1
   0   0   0   0   0  52 469 750 376 395   5   1
Row n = 6 counts the following compositions:
  (1,1,3,1)    (1,1,4)      (1,5)      (3,3)          (6)
  (1,3,1,1)    (4,1,1)      (2,4)      (2,2,2)
  (1,1,1,2,1)  (1,1,1,3)    (4,2)      (1,1,1,1,1,1)
  (1,2,1,1,1)  (1,2,2,1)    (5,1)
               (2,1,1,2)    (1,2,3)
               (3,1,1,1)    (1,3,2)
               (1,1,1,1,2)  (1,4,1)
               (1,1,2,1,1)  (2,1,3)
               (2,1,1,1,1)  (2,3,1)
                            (3,1,2)
                            (3,2,1)
                            (1,1,2,2)
                            (1,2,1,2)
                            (2,1,2,1)
                            (2,2,1,1)

Row sums are A000079.
Column sums are A329768.
The version with rows reversed is A329744.
Cf. A000740, A008965, A098504, A242882, A318928, A329745, A329746, A329747, A329767.

runsres[q_]:=Length[NestWhileList[Length/@Split[#]&,q,Length[#]>1&]]-1;
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],runsres[#]==n-k&]],{n,10},{k,n}]

A329743 Number of compositions of n with runs-resistance n - 3.

Original entry on oeis.org

0, 0, 0, 1, 2, 6, 9, 16, 8

Offset: 0

Gus Wiseman, Nov 21 2019

A composition of n is a finite sequence of positive integers with sum n.

For the operation of taking the sequence of run-lengths of a finite sequence, runs-resistance is defined as the number of applications required to reach a singleton.

			The a(3) = 1 through a(8) = 8 compositions:
  (3)  (22)    (14)   (114)    (1123)    (12113)
       (1111)  (23)   (411)    (1132)    (12212)
               (32)   (1113)   (1141)    (13112)
               (41)   (1221)   (1411)    (21131)
               (131)  (2112)   (2122)    (21221)
               (212)  (3111)   (2212)    (31121)
                      (11112)  (2311)    (121112)
                      (11211)  (3211)    (211121)
                      (21111)  (11131)
                               (11212)
                               (11221)
                               (12211)
                               (13111)
                               (21211)
                               (111121)
                               (121111)
For example, repeatedly taking run-lengths starting with (1,2,1,1,3) gives (1,2,1,1,3) -> (1,1,2,1) -> (2,1,1) -> (1,2) -> (1,1) -> (2), which is 5 steps, and 5 = 8 - 3, so (1,2,1,1,3) is counted under a(8).

Column k = n - 3 of A329744.
Column k = 3 of A329750.
Compositions with runs-resistance 2 are A329745.
Cf. A000740, A008965, A098504, A242882, A318928, A329746, A329747, A329767.

runsres[q_]:=If[Length[q]==1,0,Length[NestWhileList[Length/@Split[#]&,q,Length[#]>1&]]-1];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],runsres[#]==n-3&]],{n,10}]

A329768 Number of finite sequences of positive integers whose sum minus runs-resistance is n.

Original entry on oeis.org

8, 17, 42, 104, 242, 541, 1212, 2664, 5731, 12314

Offset: 1

Gus Wiseman, Nov 21 2019

A composition of n is a finite sequence of positive integers with sum n.

For the operation of taking the sequence of run-lengths of a finite sequence, runs-resistance is defined as the number of applications required to reach a singleton.

			The a(1) = 8 and a(2) = 17 compositions whose sum minus runs-resistance is n:
  (1)        (2)
  (1,1)      (1,3)
  (1,2)      (3,1)
  (2,1)      (1,1,1)
  (1,1,2)    (1,1,3)
  (2,1,1)    (1,2,1)
  (1,1,2,1)  (1,2,2)
  (1,2,1,1)  (2,2,1)
             (3,1,1)
             (1,1,1,2)
             (1,1,3,1)
             (1,3,1,1)
             (2,1,1,1)
             (1,1,1,2,1)
             (1,2,1,1,1)
             (1,2,1,1,2)
             (2,1,1,2,1)

Claude Lenormand, Deux transformations sur les mots, Preprint, 5 pages, Nov 17 2003.

Column sums of A329750.

Cf. A000740, A008965, A098504, A242882, A318928, A329744, A329745, A329746, A329747, A329767.

A330028 Number of compositions of n with cuts-resistance <= 2.

Original entry on oeis.org

1, 1, 2, 3, 7, 13, 23, 45, 86, 159, 303, 568, 1069, 2005, 3769, 7066, 13251, 24821, 46482, 86988, 162758

Offset: 0

Gus Wiseman, Nov 27 2019

A composition of n is a finite sequence of positive integers summing to n.

For the operation of shortening all runs by 1, cuts-resistance is defined to be the number of applications required to reach an empty word.

			The a(0) = 1 through a(5) = 13 compositions:
  ()  (1)  (2)    (3)    (4)      (5)
           (1,1)  (1,2)  (1,3)    (1,4)
                  (2,1)  (2,2)    (2,3)
                         (3,1)    (3,2)
                         (1,1,2)  (4,1)
                         (1,2,1)  (1,1,3)
                         (2,1,1)  (1,2,2)
                                  (1,3,1)
                                  (2,1,2)
                                  (2,2,1)
                                  (3,1,1)
                                  (1,1,2,1)
                                  (1,2,1,1)

Sum of first three columns of A329861.
Compositions with cuts-resistance 1 are A003242.
Compositions with cuts-resistance 2 are A329863.
Compositions with runs-resistance 2 are A329745.
Numbers whose binary expansion has cuts-resistance 2 are A329862.
Binary words with cuts-resistance 2 are A027383.
Cuts-resistance of binary expansion is A319416.
Binary words counted by cuts-resistance are A319421 or A329860.
Cf. A000975, A003242, A032020, A114901, A240085, A261983, A319420, A329738, A329744, A329864.

degdep[q_]:=Length[NestWhileList[Join@@Rest/@Split[#]&,q,Length[#]>0&]]-1;
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],degdep[#]<=2&]],{n,0,10}]

cp's OEIS Frontend

A351291 Numbers k such that the k-th composition in standard order does not have all distinct runs.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A319411 Triangle read by rows: T(n,k) = number of binary vectors of length n with runs-resistance k (1 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A329767 Triangle read by rows where T(n,k) is the number of binary words of length n >= 0 with runs-resistance k, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A329862 Positive integers whose binary expansion has cuts-resistance 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A329863 Number of compositions of n with cuts-resistance 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A329750 Triangle read by rows where T(n,k) is the number of compositions of n >= 1 with runs-resistance n - k, 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A329743 Number of compositions of n with runs-resistance n - 3.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A329768 Number of finite sequences of positive integers whose sum minus runs-resistance is n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs