A240085 -id:A240085 - cp's OEIS frontend

A373952 Number of integer compositions of n whose run-compression sums to 3.

0, 0, 0, 3, 2, 4, 5, 6, 6, 9, 8, 10, 11, 12, 12, 15, 14, 16, 17, 18, 18, 21, 20, 22, 23, 24, 24, 27, 26, 28, 29, 30, 30, 33, 32, 34, 35, 36, 36, 39, 38, 40, 41, 42, 42, 45, 44, 46, 47, 48, 48, 51, 50, 52, 53, 54, 54, 57, 56, 58, 59, 60, 60, 63, 62, 64, 65, 66

Offset: 0

Gus Wiseman, Jun 29 2024

nonn

We define the (run-) compression of a sequence to be the anti-run obtained by reducing each run of repeated parts to a single part. Alternatively, compression removes all parts equal to the part immediately to their left. For example, (1,1,2,2,1) has compression (1,2,1).

			The a(3) = 3 through a(9) = 9 compositions:
  (3)   (112)  (122)   (33)     (1222)    (11222)    (333)
  (12)  (211)  (221)   (1122)   (2221)    (22211)    (12222)
  (21)         (1112)  (2211)   (11122)   (111122)   (22221)
               (2111)  (11112)  (22111)   (221111)   (111222)
                       (21111)  (111112)  (1111112)  (222111)
                                (211111)  (2111111)  (1111122)
                                                     (2211111)
                                                     (11111112)
                                                     (21111111)

John Tyler Rascoe, Table of n, a(n) for n = 0..10000

For partitions we appear to have A137719.
Column k = 3 of A373949, rows-reversed A373951.
The compression-sum statistic is represented by A373953, difference A373954.
A003242 counts compressed compositions (anti-runs).
A011782 counts compositions.
A114901 counts compositions with no isolated parts.
A116861 counts partitions by compressed sum, by compressed length A116608.
A124767 counts runs in standard compositions, anti-runs A333381.
A240085 counts compositions with no unique parts.
A333755 counts compositions by compressed length.
A373948 represents the run-compression transformation.
Cf. A037201 (halved A373947), A106356, A124762, A238130, A238279, A238343, A285981, A333213, A333489, A373950.

Table[Length[Select[Join@@Permutations /@ IntegerPartitions[n],Total[First/@Split[#]]==3&]],{n,0,10}]

A_x(N)={my(x='x+O('x^N)); concat([0, 0, 0], Vec(x^3 *(3-x-x^2-x^3)/((1-x)*(1-x^2)*(1-x^3))))}
A_x(50) \\ John Tyler Rascoe, Jul 01 2024

G.f.: x^3 * (3-x-x^2-x^3)/((1-x)*(1-x^2)*(1-x^3)). - John Tyler Rascoe, Jul 01 2024

a(26) onwards from John Tyler Rascoe, Jul 01 2024

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

A363224 Number of integer compositions of n in which the least part appears more than once.

Original entry on oeis.org

0, 1, 1, 5, 8, 21, 44, 94, 197, 416, 857, 1766, 3621, 7392, 15032, 30493, 61708, 124646, 251359, 506203, 1018279, 2046454, 4109534, 8246985, 16540791, 33160051, 66451484, 133122753, 266612828, 533839069, 1068701695, 2139110054, 4281063708, 8566862025

Offset: 1

Gus Wiseman, Jun 04 2023

nonn

Also the number of multisets of length n covering an initial interval of positive integers with more than one co-mode.

			The a(1) = 0 through a(6) = 21 compositions:
  .  (11)  (111)  (22)    (113)    (33)
                  (112)   (131)    (114)
                  (121)   (311)    (141)
                  (211)   (1112)   (222)
                  (1111)  (1121)   (411)
                          (1211)   (1113)
                          (2111)   (1122)
                          (11111)  (1131)
                                   (1212)
                                   (1221)
                                   (1311)
                                   (2112)
                                   (2121)
                                   (2211)
                                   (3111)
                                   (11112)
                                   (11121)
                                   (11211)
                                   (12111)
                                   (21111)
                                   (111111)

John Tyler Rascoe, Table of n, a(n) for n = 1..1000

The complement is counted by A105039.
For partitions instead of compositions we have A117989.
Row sums of columns k > 1 of A238342.
If all parts appear more than once we have A240085, for partitions A007690.
If the least part appears exactly twice we have A241862.
For greatest instead of least we have A363262, see triangle A238341.
A000041 counts integer partitions, strict A000009.
A032020 counts strict compositions.
A067029 gives last exponent in prime factorization, first A071178.
A261982 counts compositions with some part appearing more than once.
A362607 counts partitions with multiple modes, co-modes A362609.
A362608 counts partitions with a unique mode, co-mode A362610.
Cf. A002865, A008284, A097979, A243737.

Table[Length[Select[Join@@Permutations /@ IntegerPartitions[n],Count[#,Min@@#]>1&]],{n,15}]

C_x(N)={my(x='x+O('x^N), h=sum(i=1,N,(x^(2*i)*(x-1)^3)/((x^i+x-1)*(x^(i+1)+x-1)^2))); concat([0],Vec(h))}
C_x(35) \\ John Tyler Rascoe, Jul 06 2024

G.f.: Sum_{i>0} (x^(2*i) * (x-1)^3)/((x^i + x - 1)*(x^(i+1) + x - 1)^2). - John Tyler Rascoe, Jul 06 2024

A363262 Number of integer compositions of n in which the greatest part appears more than once.

Original entry on oeis.org

0, 1, 1, 2, 4, 9, 18, 37, 73, 145, 287, 570, 1134, 2264, 4526, 9061, 18152, 36374, 72884, 146011, 292416, 585422, 1171632, 2344136, 4688821, 9376832, 18749169, 37485358, 74939850, 149813328, 299492966, 598729533, 1196987066, 2393137399, 4784846896, 9567357951

Offset: 1

Gus Wiseman, Jun 04 2023

nonn

Also the number of multisets of length n covering an initial interval of positive integers with more than one mode.

			The a(2) = 1 through a(6) = 9 compositions:
  (11)  (111)  (22)    (122)    (33)
               (1111)  (212)    (222)
                       (221)    (1122)
                       (11111)  (1212)
                                (1221)
                                (2112)
                                (2121)
                                (2211)
                                (111111)

For partitions instead of compositions we have A002865.
The complement is counted by A097979 shifted left.
Row sums of columns k > 1 of A238341.
If all parts appear more than once we have A240085, for partitions A007690.
If the greatest part appears exactly twice we have A243737.
For least instead of greatest we have A363224, see triangle A238342.
A000041 counts integer partitions, strict A000009.
A032020 counts strict compositions.
A067029 gives last exponent in prime factorization, first A071178.
A261982 counts compositions with some part appearing more than once.
Cf. A008284, A105039, A117989, A362607, A362608, A362612, A362614.

Table[Length[Select[Join@@Permutations /@ IntegerPartitions[n],Count[#,Max@@#]>1&]],{n,15}]

A373950 Number of integer compositions of n containing two adjacent ones and no other runs.

Original entry on oeis.org

0, 0, 1, 0, 2, 4, 5, 14, 26, 46, 92, 176, 323, 610, 1145, 2108, 3912, 7240, 13289, 24418, 44778, 81814, 149356, 272222, 495144, 899554, 1632176, 2957332, 5352495, 9677266, 17477761, 31536288, 56852495, 102403134, 184302331, 331452440, 595659234, 1069742760

Offset: 0

Gus Wiseman, Jun 28 2024

nonn

Also the number of integer compositions of n such that replacing each run of repeated parts with a single part (run-compression) results in a composition of n-1.

			The a(0) = 0 through a(7) = 14 compositions:
  .  .  (11)  .  (112)  (113)   (114)   (115)
                 (211)  (311)   (411)   (511)
                        (1121)  (1131)  (1123)
                        (1211)  (1311)  (1132)
                                (2112)  (1141)
                                        (1411)
                                        (2113)
                                        (2311)
                                        (3112)
                                        (3211)
                                        (11212)
                                        (12112)
                                        (21121)
                                        (21211)

John Tyler Rascoe, Table of n, a(n) for n = 0..1000

For any run (not just of ones) we have A003242.
Subdiagonal of A373949.
These compositions are ranked by A373956.
A003242 counts compressed compositions.
A114901 counts compositions with no isolated parts.
A116861 counts partitions by compressed sum, by compressed length A116608.
A333755 counts compositions by compressed length (number of runs).
A373948 represents the run-compression transformation.
Cf. A106356, A238130, A238279, A238343, A240085, A285981, A333213, A333489, A373951, A373952.

Table[Length[Select[Join@@Permutations /@ IntegerPartitions[n], Total[First/@Split[#]]==n-1&]],{n,0,10}]

A_x(N)={my(x='x+O('x^N), h=x/((1+x)^2*(1-sum(i=1,N, (x^i /(1+x^i))))^2)); concat([0, 0], Vec(h))}
A_x(40) \\ John Tyler Rascoe, Jul 02 2024

a(n>0) = A373949(n,n-1).

G.f.: x/((1-x)^2 * (1 - Sum_{i>0} (x^i/(1+x^i)))^2). - John Tyler Rascoe, Jul 02 2024

a(26) onwards from John Tyler Rascoe, Jul 02 2024

A240315 Triangular array read by rows: T(n,k) is the number of compositions of n into exactly k parts in which no part is unique (each part occurs at least twice).

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 6, 0, 1, 0, 0, 0, 0, 0, 10, 0, 1, 0, 0, 1, 0, 7, 10, 15, 0, 1, 0, 0, 0, 1, 0, 10, 20, 21, 0, 1, 0, 0, 1, 0, 12, 1, 30, 35, 28, 0, 1, 0, 0, 0, 0, 0, 20, 0, 56, 56, 36, 0, 1, 0, 0, 1, 1, 13, 10, 126, 21, 98, 84, 45, 0, 1

Offset: 0

Geoffrey Critzer, Apr 03 2014

Row sums = A240085.

			Triangle begins:
  1;
  0, 0;
  0, 0, 1;
  0, 0, 0, 1;
  0, 0, 1, 0,  1;
  0, 0, 0, 0,  0,  1;
  0, 0, 1, 1,  6,  0,   1;
  0, 0, 0, 0,  0, 10,   0,  1;
  0, 0, 1, 0,  7, 10,  15,  0,  1;
  0, 0, 0, 1,  0, 10,  20, 21,  0,  1;
  0, 0, 1, 0, 12,  1,  30, 35, 28,  0,  1;
  0, 0, 0, 0,  0, 20,   0, 56, 56, 36,  0, 1;
  0, 0, 1, 1, 13, 10, 126, 21, 98, 84, 45, 0, 1;
  ...
T(8,4) = 7 because we have: 3+3+1+1, 3+1+3+1, 3+1+1+3, 1+3+3+1, 1+3+1+3, 1+1+3+3, 2+2+2+2.

S. Heubach and T. Mansour, Combinatorics of Compositions and Words, Chapman and Hall, 2009 page 87.

Alois P. Heinz, Rows n = 0..140, flattened

b:= proc(n, i, t) option remember; `if`(n=0, t!, `if`(i<1, 0,
      expand(b(n, i-1, t)+add(x^j*b(n-i*j, i-1, t+j)/j!, j=2..n/i))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n$2, 0)):
seq(T(n), n=0..14);  # Alois P. Heinz, Apr 03 2014

nn=10;Table[Take[Transpose[Range[0,nn]!CoefficientList[Series[ Product[Exp[x^i y]-x^i y,{i,1,nn}],{y,0,nn}],{y,x}]],nn+1][[j,Range[1,j]]],{j,1,nn}]//Grid

Product_{i>=1} exp(x^i*y) - x^i*y = Sum_{k>=0} A_k(x)*y^k/k!, where A_k(x) is the o.g.f. for the number of compositions of n into k parts in which no part is unique. In other words, A_k(x) is the o.g.f. for column k.

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

A373955 Numbers k such that the k-th integer composition in standard order contains two adjacent ones and no other runs.

Original entry on oeis.org

3, 11, 14, 19, 27, 28, 29, 35, 46, 51, 56, 57, 67, 75, 78, 83, 91, 92, 93, 99, 110, 112, 113, 114, 116, 118, 131, 139, 142, 155, 156, 157, 163, 179, 184, 185, 195, 203, 206, 211, 219, 220, 221, 224, 225, 226, 229, 230, 232, 233, 236, 237, 259, 267, 270, 275

Offset: 1

Gus Wiseman, Jun 29 2024

nonn

Also numbers k such that the excess compression of the k-th integer composition in standard order is 1.
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.
postn of 1 in

			The terms and corresponding compositions begin:
    3: (1,1)
   11: (2,1,1)
   14: (1,1,2)
   19: (3,1,1)
   27: (1,2,1,1)
   28: (1,1,3)
   29: (1,1,2,1)
   35: (4,1,1)
   46: (2,1,1,2)
   51: (1,3,1,1)
   56: (1,1,4)
   57: (1,1,3,1)
   67: (5,1,1)
   75: (3,2,1,1)
   78: (3,1,1,2)
   83: (2,3,1,1)
   91: (2,1,2,1,1)
   92: (2,1,1,3)
   93: (2,1,1,2,1)
   99: (1,4,1,1)

Gus Wiseman, Statistics, classes, and transformations of standard compositions

These compositions are counted by A373950.
Positions of ones in A373954.
A003242 counts compressed compositions (or anti-runs).
A114901 counts compositions with no isolated parts.
A116861 counts partitions by compressed sum, by compressed length A116608.
A124767 counts runs in standard compositions, anti-runs A333381.
A240085 counts compositions with no unique parts.
A333755 counts compositions by compressed length.
A373948 encodes compression using compositions in standard order.
A373949 counts compositions by compression-sum.
A373953 gives compression-sum of standard compositions.
Cf. A106356, A124762, A238130, A238279, A238343, A285981, A333382, A333489, A373951, A373952.

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

cp's OEIS Frontend

A373952 Number of integer compositions of n whose run-compression sums to 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

A363224 Number of integer compositions of n in which the least part appears more than once.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A363262 Number of integer compositions of n in which the greatest part appears more than once.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A373950 Number of integer compositions of n containing two adjacent ones and no other runs.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A240315 Triangular array read by rows: T(n,k) is the number of compositions of n into exactly k parts in which no part is unique (each part occurs at least twice).

Views

Author

Keywords

Comments

Examples

References

Links

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A373955 Numbers k such that the k-th integer composition in standard order contains two adjacent ones and no other runs.

Views