A329744 -id:A329744 - cp's OEIS frontend

A329748 Number of complete compositions of n whose multiplicities cover an initial interval of positive integers.

1, 1, 0, 2, 3, 3, 6, 12, 12, 42, 114, 210, 60, 360, 720, 1320, 1590, 3690, 6450, 16110, 33120, 59940, 61320, 112980, 171780, 387240, 803880, 769440, 1773240, 2823240, 5790960, 9916200, 19502280, 28244160, 56881440, 130548600, 279578880, 320554080, 541323720

Offset: 0

Gus Wiseman, Nov 21 2019

nonn

A composition of n is a finite sequence of positive integers with sum n. It is complete if it covers an initial interval of positive integers.

			The a(1) = 1 through a(8) = 12 compositions (empty column not shown):
  (1)  (12)  (112)  (122)  (123)  (1123)  (1223)
       (21)  (121)  (212)  (132)  (1132)  (1232)
             (211)  (221)  (213)  (1213)  (1322)
                           (231)  (1231)  (2123)
                           (312)  (1312)  (2132)
                           (321)  (1321)  (2213)
                                  (2113)  (2231)
                                  (2131)  (2312)
                                  (2311)  (2321)
                                  (3112)  (3122)
                                  (3121)  (3212)
                                  (3211)  (3221)

Looking at run-lengths instead of multiplicities gives A329749.
The non-complete version is A329741.
Complete compositions are A107429.
Cf. A008965, A098504, A244164, A274174, A329740, A329744, A329766.

normQ[m_]:=Or[m=={},Union[m]==Range[Max[m]]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],normQ[#]&&normQ[Length/@Split[Sort[#]]]&]],{n,0,10}]

a(21)-a(38) from Alois P. Heinz, Jul 06 2020

A329866 Numbers whose binary expansion has its runs-resistance equal to its cuts-resistance minus 1.

Original entry on oeis.org

1, 3, 16, 30, 33, 48, 55, 56, 59, 60, 67, 68, 72, 79, 95, 97, 110, 112, 118, 120, 121, 125, 134, 135, 137, 143, 145, 158, 160, 195, 196, 219, 220, 225, 231, 241, 250, 258, 270, 280, 286, 291, 292, 315, 316, 351, 381, 382, 390, 391, 393, 399, 415, 416, 431, 432

Offset: 1

Gus Wiseman, Nov 23 2019

nonn

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

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:
    1:         1
    3:        11
   16:     10000
   30:     11110
   33:    100001
   48:    110000
   55:    110111
   56:    111000
   59:    111011
   60:    111100
   67:   1000011
   68:   1000100
   72:   1001000
   79:   1001111
   95:   1011111
   97:   1100001
  110:   1101110
  112:   1110000
  118:   1110110
  120:   1111000
For example, 79 has runs-resistance 3 because we have (1001111) -> (124) -> (111) -> (3), while the cuts-resistance is 4 because we have (1001111) -> (0111) -> (11) -> (1) -> (), so 79 is in the sequence.

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

Positions of -1's in A329867.
The version for runs-resistance equal to cuts-resistance is A329865.
Compositions with runs-resistance equal to cuts-resistance are A329864.
Compositions with runs-resistance = cuts-resistance minus 1 are A329869.
Runs-resistance of binary expansion is A318928.
Cuts-resistance of binary expansion is A319416.
Compositions counted by runs-resistance are A329744.
Compositions counted by cuts-resistance are A329861.
Binary words counted by runs-resistance are A319411 and A329767.
Binary words counted by cuts-resistance are A319421 and A329860.
Cf. A000975, A003242, A107907, A164707, A329738, A329868.

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

A329868 Sorted positions of first appearances in A329867 (difference between the runs-resistance and the cuts-resistance of binary expansion) of each element in the image.

Original entry on oeis.org

0, 1, 2, 7, 11, 15, 18, 31, 63, 75, 127, 255, 511, 1023, 1234, 2047, 4095, 8191, 9638, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607

Offset: 1

Gus Wiseman, Nov 23 2019

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

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:
      0:
      1:                1
      2:               10
      7:              111
     11:             1011
     15:             1111
     18:            10010
     31:            11111
     63:           111111
     75:          1001011
    127:          1111111
    255:         11111111
    511:        111111111
   1023:       1111111111
   1234:      10011010010
   2047:      11111111111
   4095:     111111111111
   8191:    1111111111111
   9638:   10010110100110
  16383:   11111111111111
  32767:  111111111111111
  65535: 1111111111111111

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

Sorted positions of first appearances in A329867.
Compositions with runs-resistance equal to cuts-resistance are A329864.
Runs-resistance of binary expansion is A318928.
Cuts-resistance of binary expansion is A319416.
Compositions counted by runs-resistance are A329744.
Compositions counted by cuts-resistance are A329861.
Binary words counted by runs-resistance are A319411 and A329767.
Binary words counted by cuts-resistance are A319421 and A329860.
Cf. A000975, A003242, A107907, A164707, A329738, A329865, A329866.

runsres[q_]:=Length[NestWhileList[Length/@Split[#]&,q,Length[#]>1&]]-1;
degdep[q_]:=Length[NestWhileList[Join@@Rest/@Split[#]&,q,Length[#]>0&]]-1;
das=Table[If[n==0,0,runsres[IntegerDigits[n,2]]-degdep[IntegerDigits[n,2]]],{n,0,1000000}];
Table[Position[das,i][[1,1]]-1,{i,First/@Gather[das]}]

A332274 Number of totally strong compositions of n.

Original entry on oeis.org

1, 1, 2, 4, 7, 11, 22, 33, 56, 93, 162, 264, 454, 765, 1307, 2237, 3849, 6611, 11472, 19831, 34446, 59865, 104293, 181561, 316924

Offset: 0

Gus Wiseman, Feb 11 2020

A sequence is totally strong if either it is empty, equal to (1), or its run-lengths are weakly decreasing (strong) and are themselves a totally strong sequence.
A composition of n is a finite sequence of positive integers with sum n.
Also the number of totally co-strong compositions of n.

			The a(1) = 1 through a(5) = 11 compositions:
  (1)  (2)   (3)    (4)     (5)
       (11)  (12)   (13)    (14)
             (21)   (22)    (23)
             (111)  (31)    (32)
                    (121)   (41)
                    (211)   (122)
                    (1111)  (131)
                            (212)
                            (311)
                            (2111)
                            (11111)

The case of partitions is A316496.
The co-strong case is A332274 (this sequence).
The case of reversed partitions is A332275.
The alternating version is A332338.
Cf. A100883, A107429, A317245, A317256, A317491, A329744, A332272, A332279, A332289, A332292, A332336, A332337, A332339, A332340.

tni[q_]:=Or[q=={},q=={1},And[GreaterEqual@@Length/@Split[q],tni[Length/@Split[q]]]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],tni]],{n,0,15}]

A333192 Number of compositions of n with strictly increasing run-lengths.

Original entry on oeis.org

1, 1, 2, 2, 4, 5, 7, 10, 14, 16, 24, 31, 37, 51, 67, 76, 103, 129, 158, 199, 242, 293, 370, 450, 538, 652, 799, 953, 1147, 1376, 1635, 1956, 2322, 2757, 3271, 3845, 4539, 5336, 6282, 7366, 8589, 10046, 11735, 13647, 15858, 18442, 21354, 24716, 28630, 32985

Offset: 0

Gus Wiseman, May 17 2020

nonn

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

			The a(1) = 1 through a(8) = 14 compositions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)
       (11)  (111)  (22)    (122)    (33)      (133)      (44)
                    (211)   (311)    (222)     (322)      (233)
                    (1111)  (2111)   (411)     (511)      (422)
                            (11111)  (3111)    (1222)     (611)
                                     (21111)   (4111)     (2222)
                                     (111111)  (22111)    (5111)
                                               (31111)    (11222)
                                               (211111)   (41111)
                                               (1111111)  (122111)
                                                          (221111)
                                                          (311111)
                                                          (2111111)
                                                          (11111111)
For example, the composition (1,2,2,1,1,1) has run-lengths (1,2,3), so is counted under a(8).

Giovanni Resta, Table of n, a(n) for n = 0..1000

The case of partitions is A100471.
The non-strict version is A332836.
Strictly increasing compositions are A000009.
Unimodal compositions are A001523.
Strict compositions are A032020.
Partitions with strictly increasing run-lengths are A100471.
Partitions with strictly decreasing run-lengths are A100881.
Compositions with equal run-lengths are A329738.
Compositions whose run-lengths are unimodal are A332726.
Compositions with strictly increasing or decreasing run-lengths are A333191.
Numbers with strictly increasing prime multiplicities are A334965.
Cf. A072706, A098859, A100882, A100883, A304686, A329744, A329766, A332726, A332833, A332834, A332835, A333147, A333149, A333190.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Less@@Length/@Split[#]&]],{n,0,15}]
b[n_, lst_, v_] := b[n, lst, v] = If[n == 0, 1, If[n <= lst, 0, Sum[If[k == v, 0, b[n - k pz, pz, k]], {pz, lst + 1, n}, {k, Floor[n/pz]}]]]; a[n_] := b[n, 0, 0]; a /@ Range[0, 50] (* Giovanni Resta, May 18 2020 *)

Terms a(26) and beyond from Giovanni Resta, May 18 2020

A333630 Least STC-number of a composition whose sequence of run-lengths has STC-number n.

Original entry on oeis.org

0, 1, 3, 5, 7, 14, 11, 13, 15, 30, 43, 29, 23, 46, 27, 45, 31, 62, 122, 61, 87, 117, 59, 118, 47, 94, 107, 93, 55, 110, 91, 109, 63, 126, 250, 125, 343, 245, 123, 246, 175, 350, 235, 349, 119, 238, 347, 237, 95, 190, 378, 189, 215, 373, 187, 374, 111, 222, 363

Offset: 0

Gus Wiseman, Mar 31 2020

nonn

All terms belong to A003754.

A composition of n is a finite sequence of positive integers summing to n. The composition with STC-number k (row k of 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 sequence together with the corresponding compositions begins:
   0: ()
   1: (1)
   3: (1,1)
   5: (2,1)
   7: (1,1,1)
  14: (1,1,2)
  11: (2,1,1)
  13: (1,2,1)
  15: (1,1,1,1)
  30: (1,1,1,2)
  43: (2,2,1,1)
  29: (1,1,2,1)
  23: (2,1,1,1)
  46: (2,1,1,2)
  27: (1,2,1,1)
  45: (2,1,2,1)
  31: (1,1,1,1,1)
  62: (1,1,1,1,2)

Position of first appearance of n in A333627.
All of the following pertain to compositions in standard order (A066099):
- The length is A000120.
- Compositions without terms > 2 are A003754.
- Compositions without ones are ranked by A022340.
- The partial sums from the right are A048793.
- The sum is A070939.
- Adjacent equal pairs are counted by A124762.
- Equal runs are counted by A124767.
- Strict compositions are ranked by A233564.
- The partial sums from the left are A272020.
- Constant compositions are ranked by A272919.
- Normal compositions are ranked by A333217.
- Heinz number is A333219.
- Anti-runs are counted by A333381.
- Adjacent unequal pairs are counted by A333382.
- Runs-resistance is A333628.
- First appearances of run-resistances are A333629.
Cf. A029931, A098504, A114994, A225620, A228351, A238279, A242882, A318928, A329744, A329747, A333489.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
seq=Table[Total[2^(Accumulate[Reverse[Length/@Split[stc[n]]]])]/2,{n,0,1000}];
Table[Position[seq,i][[1,1]],{i,First[Split[Union[seq],#1+1==#2&]]}]-1

A337565 Irregular triangle read by rows where row k is the sequence of maximal anti-run lengths in the k-th composition in standard order.

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Sep 07 2020

An anti-run is a sequence with no adjacent equal parts.

A composition of n is a finite sequence of positive integers summing to n. 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 first column below lists various selected n; the second column gives the corresponding composition; the third column gives the corresponding row of the triangle, i.e., the anti-run lengths.
    1:           (1) -> (1)
    3:         (1,1) -> (1,1)
    5:         (2,1) -> (2)
    7:       (1,1,1) -> (1,1,1)
   11:       (2,1,1) -> (2,1)
   13:       (1,2,1) -> (3)
   14:       (1,1,2) -> (1,2)
   15:     (1,1,1,1) -> (1,1,1,1)
   23:     (2,1,1,1) -> (2,1,1)
   27:     (1,2,1,1) -> (3,1)
   29:     (1,1,2,1) -> (1,3)
   30:     (1,1,1,2) -> (1,1,2)
   31:   (1,1,1,1,1) -> (1,1,1,1,1)
   43:     (2,2,1,1) -> (1,2,1)
   45:     (2,1,2,1) -> (4)
   46:     (2,1,1,2) -> (2,2)
   47:   (2,1,1,1,1) -> (2,1,1,1)
   55:   (1,2,1,1,1) -> (3,1,1)
   59:   (1,1,2,1,1) -> (1,3,1)
   61:   (1,1,1,2,1) -> (1,1,3)
   62:   (1,1,1,1,2) -> (1,1,1,2)
   63: (1,1,1,1,1,1) -> (1,1,1,1,1,1)
For example, the 119th composition is (1,1,2,1,1,1), with maximal anti-runs ((1),(1,2,1),(1),(1)), so row 119 is (1,3,1,1).

A000120 gives row sums.
A333381 gives row lengths.
A333769 is the version for runs.
A003242 counts anti-run compositions.
A011782 counts compositions.
A106351 counts anti-run compositions by length.
A329744 is a triangle counting compositions by runs-resistance.
A333755 counts compositions by number of runs.
All of the following pertain to compositions in standard order (A066099):
- Sum is A070939.
- Adjacent equal pairs are counted by A124762.
- Runs are counted by A124767.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Patterns are A333217.
- Heinz number is A333219.
- Anti-runs are counted by A333381.
- Anti-run compositions are A333489.
- Runs-resistance is A333628.
- Combinatory separations are A334030.
Cf. A106356, A113835, A114994, A124767, A181819, A228351, A238279, A318928, A333216, A333627, A333630.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[Length/@Split[stc[n],UnsameQ],{n,0,50}]

A335517 Number of matching pairs of patterns, the longest having length n.

Original entry on oeis.org

1, 2, 9, 64, 623, 7866, 122967

Offset: 0

Gus Wiseman, Jun 23 2020

We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217. A sequence S is said to match a pattern P if there is a not necessarily contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) matches (1,1,2), (2,1,1), and (2,1,2), but avoids (1,2,1), (1,2,2), and (2,2,1).

			The a(0) = 1 through a(2) = 9 pairs of patterns:
  ()<=()    ()<=(1)      ()<=(1,1)
           (1)<=(1)      ()<=(1,2)
                         ()<=(2,1)
                        (1)<=(1,1)
                        (1)<=(1,2)
                        (1)<=(2,1)
                      (1,1)<=(1,1)
                      (1,2)<=(1,2)
                      (2,1)<=(2,1)

Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

Row sums of A335518.
Patterns are counted by A000670 and ranked by A333217.
Patterns matched by a standard composition are counted by A335454.
Patterns contiguously matched by compositions are counted by A335457.
Minimal patterns avoided by a standard composition are counted by A335465.
Patterns matched by prime indices are counted by A335549.
Cf. A011782, A034691, A056986, A124771, A269134, A329744, A333257, A334299.

mstype[q_]:=q/.Table[Union[q][[i]]->i,{i,Length[Union[q]]}];
allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
Table[Sum[Length[Union[mstype/@Subsets[y]]],{y,Join@@Permutations/@allnorm[n]}],{n,0,5}]

A329749 Number of complete compositions of n whose run-lengths cover an initial interval of positive integers.

Original entry on oeis.org

1, 1, 0, 2, 3, 5, 11, 23, 40, 80, 180, 344, 661, 1321, 2657, 5268, 10481, 20903, 41572, 82734, 164998, 328304, 654510, 1305421, 2598811, 5182174, 10332978, 20594318, 41066611, 81897091, 163309679, 325707492, 649648912, 1295827380, 2584941276, 5156774487

Offset: 0

Gus Wiseman, Nov 21 2019

nonn

A composition of n is a finite sequence of positive integers with sum n. It is complete if it covers an initial interval of positive integers.

			The a(0) = 1 through a(6) = 11 compositions (empty column not shown):
  ()  (1)  (1,2)  (1,1,2)  (1,2,2)    (1,2,3)
           (2,1)  (1,2,1)  (2,1,2)    (1,3,2)
                  (2,1,1)  (2,2,1)    (2,1,3)
                           (1,1,2,1)  (2,3,1)
                           (1,2,1,1)  (3,1,2)
                                      (3,2,1)
                                      (1,2,1,2)
                                      (1,2,2,1)
                                      (2,1,1,2)
                                      (2,1,2,1)
                                      (1,1,2,1,1)

Looking at  multiplicities instead of run-lengths gives A329748.
The non-complete version is A329766.
Complete compositions are A107429.
Cf. A000740, A008965, A098504, A244164, A274174, A329738, A329739, A329740, A329741, A329744.

normQ[m_]:=Or[m=={},Union[m]==Range[Max[m]]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],normQ[#]&&normQ[Length/@Split[#]]&]],{n,0,10}]

a(21)-a(35) from Alois P. Heinz, Jul 06 2020

A329869 Number of compositions of n with runs-resistance equal to cuts-resistance minus 1.

Original entry on oeis.org

0, 1, 2, 1, 2, 1, 4, 5, 11, 19, 36, 77, 138, 252, 528, 1072, 2204, 4634, 9575, 19732, 40754

Offset: 0

Gus Wiseman, Nov 23 2019

A composition of n is a finite sequence of positive integers summing to n.
For the operation of taking the sequence of run-lengths of a finite sequence, runs-resistance is defined to be the number of applications required to reach a singleton.
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(1) = 1 through a(9) = 19 compositions:
  1   2   3   4   5   6      7       8        9
      11      22      33     11113   44       11115
                      11112  31111   11114    12222
                      21111  111211  41111    22221
                             112111  111122   51111
                                     111311   111222
                                     113111   111411
                                     211112   114111
                                     221111   211113
                                     1111121  222111
                                     1211111  311112
                                              1111131
                                              1111221
                                              1112112
                                              1121112
                                              1221111
                                              1311111
                                              2111211
                                              2112111
For example, the runs-resistance of (1221111) is 3 because we have: (1221111) -> (124) -> (111) -> (3), while the cuts-resistance is 4 because we have: (1221111) -> (2111) -> (11) -> (1) -> (), so (1221111) is counted under a(9).

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

The version for binary indices is A329866.
Compositions counted by runs-resistance are A329744.
Compositions counted by cuts-resistance are A329861.
Cf. A003242, A098504, A114901, A242882, A318928, A319411, A319416, A319420, A319421, A329864, A329865, A329867, A329868.

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

cp's OEIS Frontend

A329748 Number of complete compositions of n whose multiplicities cover an initial interval of positive integers.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A329866 Numbers whose binary expansion has its runs-resistance equal to its cuts-resistance minus 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A329868 Sorted positions of first appearances in A329867 (difference between the runs-resistance and the cuts-resistance of binary expansion) of each element in the image.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A332274 Number of totally strong compositions of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A333192 Number of compositions of n with strictly increasing run-lengths.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A333630 Least STC-number of a composition whose sequence of run-lengths has STC-number n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A337565 Irregular triangle read by rows where row k is the sequence of maximal anti-run lengths in the k-th composition in standard order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A335517 Number of matching pairs of patterns, the longest having length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A329749 Number of complete compositions of n whose run-lengths cover an initial interval of positive integers.