A329738 -id:A329738 - cp's OEIS frontend

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

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}]

A335443 Number of compositions of n where neighboring runs have different lengths.

Original entry on oeis.org

1, 1, 2, 2, 5, 8, 13, 24, 42, 68, 122, 210, 360, 622, 1077, 1858, 3198, 5519, 9549, 16460, 28386, 49031, 84595, 145988, 251956, 434805, 750418, 1294998, 2234971, 3857106, 6656383, 11487641, 19825318, 34214136, 59046458, 101901743, 175860875, 303498779

Offset: 0

Alois P. Heinz, Jul 06 2020

nonn

			a(0) = 1: the empty composition.
a(1) = 1: 1.
a(2) = 2: 2, 11.
a(3) = 2: 3, 111.
a(4) = 5: 4, 22, 112, 211, 1111.
a(5) = 8: 5, 113, 122, 221, 311, 1112, 2111, 11111.
a(6) = 13: 6, 33, 114, 222, 411, 1113, 1221, 2112, 3111, 11112, 11211, 21111, 111111.
a(7) = 24: 7, 115, 133, 223, 322, 331, 511, 1114, 1222, 2113, 2221, 3112, 4111, 11113, 11122, 11311, 21112, 22111, 31111, 111112, 111211, 112111, 211111, 1111111.
a(8) = 42: 8, 44, 116, 224, 233, 332, 422, 611, 1115, 1223, 1331, 2114, 2222, 3113, 3221, 4112, 5111, 11114, 11222, 11411, 12221, 21113, 22211, 31112, 41111, 111113, 111122, 111221, 111311, 112112, 113111, 122111, 211112, 211211, 221111, 311111, 1111112, 1111211, 1112111, 1121111, 2111111, 11111111.

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

Cf. A003242, A011782, A329738, A329739, A329748, A329749, A329766, A335942.

b:= proc(n, l, t) option remember; `if`(n=0, 1, add(add(
      `if`(j=t, 0, b(n-i*j, i, j)), j=1..n/i), i={$1..n} minus {l}))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..40);

b[n_, l_, t_] := b[n, l, t] = If[n == 0, 1, Sum[Sum[If[j == t, 0,
     b[n-i*j, i, j]], {j, 1, n/i}], {i, Range[n]~Complement~{l}}]];
a[n_] := b[n, 0, 0];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Apr 13 2022, after Alois P. Heinz *)

A354906 Position of first appearance of n in A354579 = Number of distinct run-lengths of standard compositions.

Original entry on oeis.org

0, 1, 11, 119, 5615, 251871

Offset: 0

Gus Wiseman, Jun 23 2022

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 together with their corresponding compositions begin:
       0: ()
       1: (1)
      11: (2,1,1)
     119: (1,1,2,1,1,1)
    5615: (2,2,1,1,1,2,1,1,1,1)
  251871: (1,1,1,2,2,1,1,1,1,2,1,1,1,1,1)

The standard compositions used here are A066099, run-sums A353847/A353932.
The version for partitions is A006939, for run-sums A002110.
For run-sums instead of run-lengths we have A246534 (firsts in A353849).
For runs instead of run-lengths we have A351015 (firsts in A351014).
These are the positions of first appearances in A354579.
A005811 counts runs in binary expansion.
A333627 ranks the run-lengths of standard compositions.
A351596 ranks compositions with distinct run-lengths, counted by A329739.
A353744 ranks compositions with equal run-lengths, counted by A329738.
A353852 ranks compositions with distinct run-sums, counted by A353850.
A353853-A353859 are sequences pertaining to composition run-sum trajectory.
A353860 counts collapsible compositions.
Cf. A003242, A029837, A071625, A124767, A182857, A238279/A333755, A325278, A333381, A333489, A333629.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
pd=Table[Length[Union[Length/@Split[stc[n]]]],{n,0,10000}];
Table[Position[pd,n][[1,1]]-1,{n,0,Max@@pd}]

A385214 Number of subsets of {1..n} without all equal lengths of maximal runs of consecutive elements increasing by 1.

Original entry on oeis.org

0, 0, 0, 0, 2, 8, 25, 66, 159, 361, 791, 1688, 3539, 7328, 15040, 30669, 62246, 125896, 253975, 511357, 1028052

Offset: 0

Gus Wiseman, Jun 25 2025

			The maximal runs of S = {1,2,4,5,6,8,9} are ((1,2),(4,5,6),(8,9)), with lengths (2,3,2), so S is counted under a(9).
The a(0) = 0 through a(5) = 8 subsets:
  .  .  .  .  {1,2,4}  {1,2,4}
              {1,3,4}  {1,2,5}
                       {1,3,4}
                       {1,4,5}
                       {2,3,5}
                       {2,4,5}
                       {1,2,3,5}
                       {1,3,4,5}

These subsets are ranked by A164708, complement A164707
The complement is counted by A243815.
For distinct instead of equal lengths we have A384176, complement A384175.
For anti-runs instead of runs we have complement of A384889, for partitions A384888.
For permutations instead of subsets we have complement of A384892, distinct A384891.
For partitions instead of subsets we have complement of A384904, strict A384886.
A034839 counts subsets by number of maximal runs, for strict partitions A116674.
A049988 counts partitions with equal run-lengths, distinct A325325.
A329738 counts compositions with equal run-lengths, distinct A329739.
A384177 counts subsets with all distinct lengths of maximal anti-runs, ranks A384879.
A384887 counts partitions with equal lengths of gapless runs, distinct A384884.
A384893 counts subsets by number of maximal anti-runs, for partitions A268193, A384905.
Cf. A010027, A044813, A164710, A383013, A384885.

Table[Length[Select[Subsets[Range[n]],!SameQ@@Length/@Split[#,#2==#1+1&]&]],{n,0,10}]

A357877 The a(n)-th composition in standard order is the sequence of run-sums of the prime indices of n.

Original entry on oeis.org

0, 1, 2, 2, 4, 6, 8, 4, 8, 12, 16, 10, 32, 24, 20, 8, 64, 24, 128, 20, 40, 48, 256, 18, 32, 96, 32, 40, 512, 52, 1024, 16, 80, 192, 72, 40, 2048, 384, 160, 36, 4096, 104, 8192, 80, 68, 768, 16384, 34, 128, 96, 320, 160, 32768, 96, 144, 72, 640, 1536, 65536, 84

Offset: 1

Gus Wiseman, Oct 17 2022

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.
The sequence of runs of a sequence consists of its maximal consecutive constant subsequences when read left-to-right. 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 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 prime indices of 24 are (1,1,1,2), with run-sums (3,2), and this is the 18th composition in standard order, so a(24) = 18.

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

The version for prime indices instead of standard compositions is A353832.
The version for standard compositions instead of prime indices is A353847.
A ranking of the rows of A354584.
A001222 counts prime factors, distinct A001221.
A011782 counts compositions.
A047966 counts uniform partitions, compositions A329738.
A056239 adds up prime indices, row sums of A112798.
A066099 lists standard compositions.
A351014 counts distinct runs in standard compositions.
Cf. A118914, A181819, A238279, A239312, A275870, A300273, A304405, A304442, A304660, A333755, A353743-A354912, A357875.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
stcinv[q_]:=Total[2^(Accumulate[Reverse[q]])]/2;
Table[stcinv[Total/@Split[primeMS[n]]],{n,100}]

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A335443 Number of compositions of n where neighboring runs have different lengths.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A354906 Position of first appearance of n in A354579 = Number of distinct run-lengths of standard compositions.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A385214 Number of subsets of {1..n} without all equal lengths of maximal runs of consecutive elements increasing by 1.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A357877 The a(n)-th composition in standard order is the sequence of run-sums of the prime indices of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica