A333175 -id:A333175 - cp's OEIS frontend

A325535 Number of inseparable partitions of n; see Comments.

0, 0, 1, 1, 2, 2, 5, 5, 8, 11, 16, 19, 28, 35, 48, 60, 79, 99, 131, 161, 205, 256, 324, 397, 498, 609, 755, 921, 1131, 1372, 1677, 2022, 2452, 2952, 3561, 4260, 5116, 6102, 7291, 8667, 10309, 12210, 14477, 17087, 20177, 23752, 27957, 32804, 38496, 45049, 52704

Offset: 0

Clark Kimberling, May 08 2019

Definition: a partition is separable if there is an ordering of its parts in which no consecutive parts are identical; otherwise the partition is inseparable.

A partition with k parts is inseparable if and only if there is a part whose multiplicity is greater than ceiling(k/2). - Andrew Howroyd, Jan 17 2024

			For n=5, the partition 1+2+2 is separable as 2+1+2, and 2+1+1+1 is inseparable.
From _Gus Wiseman_, Jun 27 2020: (Start)
The a(2) = 2 through a(9) = 11 inseparable partitions:
  11   111   22     2111    33       2221      44         333
             1111   11111   222      4111      2222       3222
                            3111     31111     5111       6111
                            21111    211111    41111      22221
                            111111   1111111   221111     51111
                                               311111     321111
                                               2111111    411111
                                               11111111   2211111
                                                          3111111
                                                          21111111
                                                          111111111
(End)

Andrew Howroyd, Table of n, a(n) for n = 0..1000

The Heinz numbers of these partitions are given by A335448.
Strict partitions are counted by A000009 and are all separable.
Anti-run compositions are counted by A003242.
Anti-run patterns are counted by A005649.
Partitions whose differences are an anti-run are A238424.
Separable partitions are counted by A325534.
Anti-run compositions are ranked by A333489.
Anti-run permutations of prime indices are counted by A335452.
Cf. A000041, A106356, A238594, A261962, A292884, A332668, A333175.

u=Table[Length[Select[Map[Quotient[(1 + Length[#]), Max[Map[Length, Split[#]]]] &,
IntegerPartitions[nn]], # > 1 &]], {nn, 50}]
Table[PartitionsP[n] - u[[n]], {n, 1, Length[u]}]
(* Peter J. C. Moses, May 07 2019 *)
Table[Length[Select[IntegerPartitions[n],Select[Permutations[#],!MatchQ[#,{_,x_,x_,_}]&]=={}&]],{n,10}] (* Gus Wiseman, Jun 27 2020 *)

seq(n) = {Vec(sum(k=1, (n+1)\2, x^(2*k-1)*(1 + x - x^(k-1))/((1-x^(k+1))*prod(j=1, k-1, 1 - x^j, 1 + O(x^(n-2*k+2)))), O(x*x^n)), -(n+1))} \\ Andrew Howroyd, Jan 17 2024

a(n) = A000041(n) - A325534(n).

a(n) = Sum_{k>=1} x^(2*k-1)*(1 + x - x^(k-1))/((1-x^(k+1))*Product_{j=1..k-1} (1 - x^j)). - Andrew Howroyd, Jan 17 2024

a(0)=0 prepended by Andrew Howroyd, Jan 31 2024

A274174 Number of compositions of n if all summand runs are kept together.

Original entry on oeis.org

1, 1, 2, 4, 7, 12, 22, 36, 60, 97, 162, 254, 406, 628, 974, 1514, 2305, 3492, 5254, 7842, 11598, 17292, 25294, 37090, 53866, 78113, 112224, 161092, 230788, 328352, 466040, 658846, 928132, 1302290, 1821770, 2537156, 3536445, 4897310, 6777806, 9341456, 12858960, 17625970, 24133832, 32910898, 44813228, 60922160, 82569722

Offset: 0

Gregory L. Simay, Jun 12 2016

nonn

a(n^2) is odd. - Gregory L. Simay, Jun 23 2019

Also the number of compositions of n avoiding the patterns (1,2,1) and (2,1,2). - Gus Wiseman, Jul 07 2020

			If the summand runs are blocked together, there are 22 compositions of a(6): 6; 5+1, 1+5, 4+2, 2+4, (3+3), 4+(1+1), (1+1)+4, 1+2+3, 1+3+2, 2+1+3, 2+3+1, 3+1+2, 3+2+1, (2+2+2), 3+(1+1+1), (1+1+1)+3, (2+2)+(1+1), (1+1)+(2+2), 2+(1+1+1+1), (1+1+1+1)+2, (1+1+1+1+1+1).
a(0)=1; a(1)= 1; a(4) = 7; a(9) = 97; a(16) = 2305; a(25) = 78113 and a(36) = 3536445. - _Gregory L. Simay_, Jun 23 2019

Alois P. Heinz, Table of n, a(n) for n = 0..5000
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

Cf. A000070, A101880, A116608.
The version for patterns is A001339.
The version for prime indices is A333175.
The complement (i.e., the matching version) is A335548.
Anti-run compositions are A003242.
(1,2,1)- and (2,1,2)-matching permutations of prime indices are A335462.
(1,2,1)-matching compositions are A335470.
(1,2,1)-avoiding compositions are A335471.
(2,1,2)-matching compositions are A335472.
(2,1,2)-avoiding compositions are A335473.
Cf. A000670, A056986, A181796, A335451, A335452, A335460, A335463.

b:= proc(n, i, p) option remember; `if`(n=0, p!, `if`(i<1, 0,
       add(b(n-i*j, i-1, p+`if`(j=0, 0, 1)), j=0..n/i)))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..50);  # Alois P. Heinz, Jun 12 2016

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Length[Split[#]]==Length[Union[#]]&]],{n,0,10}] (* Gus Wiseman, Jul 07 2020 *)
b[n_, i_, p_] := b[n, i, p] = If[n == 0, p!, If[i < 1, 0,
    Sum[b[n - i*j, i - 1, p + If[j == 0, 0, 1]], {j, 0, n/i}]]];
a[n_] := b[n, n, 0];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Jul 11 2021, after Alois P. Heinz *)

a(n) = Sum_{k>=0} k! * A116608(n,k). - Joerg Arndt, Jun 12 2016

Terms a(9) and beyond from Joerg Arndt, Jun 12 2016

A374249 Numbers k such that the k-th composition in standard order has its equal parts contiguous.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 26, 28, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 47, 48, 50, 52, 56, 58, 60, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 78, 79, 80, 81, 83, 84, 85

Offset: 1

Gus Wiseman, Jul 13 2024

nonn

These are compositions avoiding the patterns (1,2,1) and (2,1,2).

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 standard compositions begin:
   0: ()
   1: (1)
   2: (2)
   3: (1,1)
   4: (3)
   5: (2,1)
   6: (1,2)
   7: (1,1,1)
   8: (4)
   9: (3,1)
  10: (2,2)
  11: (2,1,1)
  12: (1,3)
  14: (1,1,2)
  15: (1,1,1,1)
  16: (5)
See A374253 for the complement: 13, 22, 25, 27, 29, ...

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

The strict (also anti-run) case is A233564, counted by A032020.
Compositions of this type are counted by A274174.
Permutations of prime indices of this type are counted by A333175.
The complement is A374253 (anti-run A374254), counted by A335548.
A003242 counts anti-run compositions, ranks A333489.
A011782 counts compositions.
A066099 lists compositions in standard order.
A124767 counts runs in standard compositions, anti-runs A333381.
A333755 counts compositions by number of runs.
A335454 counts patterns matched by standard compositions.
A335462 counts (1,2,1)- and (2,1,2)-matching permutations of prime indices.
- A335470 counts (1,2,1)-matching compositions, ranks A335466.
- A335471 counts (1,2,1)-avoiding compositions, ranks A335467.
- A335472 counts (2,1,2)-matching compositions, ranks A335468.
- A335473 counts (2,1,2)-avoiding compositions, ranks A335469.
Cf. A106356, A124762, A238130, A238279, A261982, A272919, A333382, A335450, A335460, A335524, A335525.

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

Equals A335467 /\ A335469.

A335548 Number of compositions of n with at least one non-contiguous value.

Original entry on oeis.org

0, 0, 0, 0, 1, 4, 10, 28, 68, 159, 350, 770, 1642, 3468, 7218, 14870, 30463, 62044, 125818, 254302, 512690, 1031284, 2071858, 4157214, 8334742, 16699103, 33442208, 66947772, 133986940, 268107104, 536404872, 1073082978, 2146555516, 4293665006, 8588112822

Offset: 0

Gus Wiseman, Jul 08 2020

nonn

Also the number of compositions of n matching the pattern (1,2,1) or (2,1,2).

			The a(4) = 1 through a(6) = 10 compositions:
  (121)  (131)   (141)
         (212)   (1131)
         (1121)  (1212)
         (1211)  (1221)
                 (1311)
                 (2112)
                 (2121)
                 (11121)
                 (11211)
                 (12111)

The complement is A274174.
The version for prime indices is A335460.
Anti-run compositions are A003242.
(1,2,1) and (2,1,2)-matching permutations of prime indices are A335462.
(1,2,1)-matching compositions are A335470.
(1,2,1)-avoiding compositions are A335471.
(2,1,2)-matching compositions are A335472.
(2,1,2)-avoiding compositions are A335473.
Cf. A000670, A001339, A011782, A131044, A261983, A333175, A335451, A335460, A335463.

b:= proc(n, i, p) option remember; `if`(n=0, p!, `if`(i<1, 0,
       add(b(n-i*j, i-1, p+`if`(j=0, 0, 1)), j=0..n/i)))
    end:
a:= n-> ceil(2^(n-1))-b(n$2, 0):
seq(a(n), n=0..50);  # Alois P. Heinz, Jul 09 2020

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Length[Split[#]]>Length[Union[#]]&]],{n,0,10}]
(* Second program: *)
b[n_, i_, p_] := b[n, i, p] = If[n == 0, p!, If[i<1, 0,
     Sum[b[n-i*j, i-1, p + If[j == 0, 0, 1]], {j, 0, n/i}]]];
a[n_] := Ceiling[2^(n-1)] - b[n, n, 0];
a /@ Range[0, 50] (* Jean-François Alcover, May 21 2021, after Alois P. Heinz *)

a(n) = A011782(n) - A274174(n). - Alois P. Heinz, Jul 09 2020

More terms from Alois P. Heinz, Jul 09 2020

A374630 Sum of leaders of weakly increasing runs in the n-th composition in standard order.

Original entry on oeis.org

0, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 3, 1, 2, 1, 1, 5, 5, 5, 4, 2, 3, 3, 3, 1, 2, 1, 2, 1, 2, 1, 1, 6, 6, 6, 5, 3, 6, 4, 4, 2, 3, 2, 3, 3, 4, 3, 3, 1, 2, 3, 2, 1, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1, 1, 7, 7, 7, 6, 7, 7, 5, 5, 3, 4, 5, 6, 4, 5, 4, 4, 2, 3, 4, 3, 2, 3, 3

Offset: 0

Gus Wiseman, Jul 20 2024

nonn

The leaders of weakly increasing runs in a sequence are obtained by splitting it into maximal weakly increasing subsequences and taking the first term of each.

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 maximal weakly increasing subsequences of the 1234567th composition in standard order are ((3),(2),(1,2,2),(1,2,5),(1,1,1)), so a(1234567) = 8.

Gus Wiseman, Sequences counting and ranking compositions by their leaders (for six types of runs).

For length instead of sum we have A124766.
For leaders of constant runs we have A373953, excess A373954.
For leaders of anti-runs we have A374516.
Row-sums of A374629.
Counting compositions by this statistic gives A374637.
For leaders of strictly increasing runs we have A374684.
For leaders of weakly decreasing runs we have A374741.
For leaders of strictly decreasing runs we have A374758
A011782 counts compositions.
A238130, A238279, A333755 count compositions by number of runs.
A335456 counts patterns matched by compositions.
A373949 counts compositions by run-compressed sum, opposite A373951.
All of the following pertain to compositions in standard order:
- Ones are counted by A000120.
- Sum is A029837 (or sometimes A070939).
- Listed by A066099.
- Length is A070939.
- Number of adjacent equal pairs is A124762, unequal A333382.
- Number of max runs: A124765, A124766, A124767, A124768, A124769, A333381.
- Ranks of strict compositions are A233564, counted by A032020.
- Constant compositions are ranked by A272919.
- Ranks of anti-run compositions are A333489, counted by A003242.
- Run-length transform is A333627.
- Run-compression transform is A373948.
Cf. A065120, A106356, A188920, A189076, A238343, A333175, A333213, A374631, A374633, A374635.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[Total[First/@Split[stc[n],LessEqual]],{n,0,100}]

A335460 Number of (1,2,1) or (2,1,2)-matching permutations of the prime indices of n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 2, 0, 0, 0, 1, 1, 0, 0, 3, 0, 1, 0, 1, 0, 2, 0, 2, 0, 0, 0, 6, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 8, 0, 0, 1, 1, 0, 0, 0, 3, 0, 0, 0, 6, 0, 0, 0

Offset: 1

Gus Wiseman, Jun 20 2020

nonn

Depends only on sorted prime signature (A118914).
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.
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(n) compositions for n = 12, 24, 48, 36, 60, 72:
  (121)  (1121)  (11121)  (1212)  (1213)  (11212)
         (1211)  (11211)  (1221)  (1231)  (11221)
                 (12111)  (2112)  (1312)  (12112)
                          (2121)  (1321)  (12121)
                                  (2131)  (12211)
                                  (3121)  (21112)
                                          (21121)
                                          (21211)

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

Positions of zeros are A303554.
The (1,2,1)-matching part is A335446.
The (2,1,2)-matching part is A335453.
Replacing "or" with "and" gives A335462.
Permutations of prime indices are counted by A008480.
Unsorted prime signature is A124010. Sorted prime signature is A118914.
STC-numbers of permutations of prime indices are A333221.
(1,2,1) and (2,1,2)-avoiding permutations of prime indices are A333175.
Patterns matched by standard compositions are counted by A335454.
(1,2,1) and (2,1,2)-matching permutations of prime indices are A335462.
Dimensions of downsets of standard compositions are A335465.
Cf. A056239, A056986, A112798, A158005, A181796, A335451, A335452, A335463.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Table[Length[Select[Permutations[primeMS[n]],MatchQ[#,{_,x_,_,y_,_,x_,_}/;x!=y]&]],{n,100}]

A374633 Numbers k such that the leaders of weakly increasing runs in the k-th composition in standard order (A066099) are identical.

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 7, 8, 10, 12, 13, 14, 15, 16, 20, 24, 25, 26, 27, 28, 29, 30, 31, 32, 36, 40, 42, 48, 49, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 72, 80, 82, 84, 96, 97, 99, 100, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 115

Offset: 1

Gus Wiseman, Jul 21 2024

nonn

The leaders of weakly increasing runs in a sequence are obtained by splitting it into maximal weakly increasing subsequences and taking the first term of each.

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 maximal weakly increasing subsequences of the 26165th composition in standard order are ((1,3),(1,4),(1,2,2),(1)), with leaders (1,1,1,1), so 26165 is in the sequence.
The sequence together with the corresponding compositions begins:
   0: ()
   1: (1)
   2: (2)
   3: (1,1)
   4: (3)
   6: (1,2)
   7: (1,1,1)
   8: (4)
  10: (2,2)
  12: (1,3)
  13: (1,2,1)
  14: (1,1,2)
  15: (1,1,1,1)
  16: (5)
  20: (2,3)
  24: (1,4)
  25: (1,3,1)
  26: (1,2,2)
  27: (1,2,1,1)

Gus Wiseman, Sequences counting and ranking compositions by their leaders (for six types of runs).

For strictly decreasing leaders we appear to have A188920.
For weakly decreasing leaders we appear to have A189076.
Other types of runs: A272919 (counted by A000005), A374519 (counted by A374517), A374685 (counted by A374686), A374744 (counted by A374742), A374759 (counted by A374760).
Positions of constant rows in A374629 (which has sums A374630).
Compositions of this type are counted by A374631.
For strictly increasing leaders see A374634.
For all different leaders we have A374768, counted by A374632.
A011782 counts compositions.
A238130, A238279, A333755 count compositions by number of runs.
A374637 counts compositions by sum of leaders of weakly increasing runs.
All of the following pertain to compositions in standard order:
- Ones are counted by A000120.
- Sum is A029837 (or sometimes A070939).
- Parts are listed by A066099.
- Length is A070939.
- Adjacent equal pairs are counted by A124762, unequal A333382.
- Number of max runs: A124765, A124766, A124767, A124768, A124769, A333381.
- Ranks of anti-run compositions are A333489, counted by A003242.
- Run-length transform is A333627.
- Run-compression transform is A373948, sum A373953, excess A373954.
- Ranks of contiguous compositions are A374249, counted by A274174.
Cf. A065120, A106356, A238343, A333175, A333213, A373949, A374635.

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

A374253 Numbers k such that the k-th composition in standard order matches the patterns (1,2,1) or (2,1,2).

Original entry on oeis.org

13, 22, 25, 27, 29, 45, 46, 49, 51, 53, 54, 55, 57, 59, 61, 76, 77, 82, 86, 89, 90, 91, 93, 94, 97, 99, 101, 102, 103, 105, 107, 108, 109, 110, 111, 113, 115, 117, 118, 119, 121, 123, 125, 141, 148, 150, 153, 155, 156, 157, 162, 165, 166, 173, 174, 177, 178

Offset: 1

Gus Wiseman, Jul 13 2024

nonn

Such a composition cannot be strict.

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 standard compositions begin:
  13: (1,2,1)
  22: (2,1,2)
  25: (1,3,1)
  27: (1,2,1,1)
  29: (1,1,2,1)
  45: (2,1,2,1)
  46: (2,1,1,2)
  49: (1,4,1)
  51: (1,3,1,1)
  53: (1,2,2,1)
  54: (1,2,1,2)
  55: (1,2,1,1,1)
  57: (1,1,3,1)
  59: (1,1,2,1,1)
  61: (1,1,1,2,1)
  76: (3,1,3)
  77: (3,1,2,1)
  82: (2,3,2)
  86: (2,2,1,2)
  89: (2,1,3,1)

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

Permutations of prime indices of this type are counted by A335460.
Compositions of this type are counted by A335548.
The complement is A374249, counted by A274174.
The anti-run case is A374254.
A003242 counts anti-run compositions, ranks A333489.
A011782 counts compositions.
A025047 counts wiggly compositions, ranks A345167.
A066099 lists compositions in standard order.
A124767 counts runs in standard compositions, anti-runs A333381.
A233564 ranks strict compositions, counted by A032020.
A333755 counts compositions by number of runs.
A335454 counts patterns matched by standard compositions.
A335456 counts patterns matched by compositions.
A335462 counts (1,2,1)- and (2,1,2)-matching permutations of prime indices.
A335465 counts minimal patterns avoided by a standard composition.
- A335470 counts (1,2,1)-matching compositions, ranks A335466.
- A335471 counts (1,2,1)-avoiding compositions, ranks A335467.
- A335472 counts (2,1,2)-matching compositions, ranks A335468.
- A335473 counts (2,1,2)-avoiding compositions, ranks A335469.
A373948 encodes run-compression using compositions in standard order.
A373949 counts compositions by run-compressed sum, opposite A373951.
A373953 gives run-compressed sum of standard compositions, excess A373954.
Cf. A106356, A124762, A238130, A238279, A261982, A333175, A333382, A333627, A335463, A335524, A335525.

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

Equals A335466 \/ A335468.

A128695 Number of compositions of n with parts in N which avoid the adjacent pattern 111.

Original entry on oeis.org

1, 1, 2, 3, 7, 13, 24, 46, 89, 170, 324, 618, 1183, 2260, 4318, 8249, 15765, 30123, 57556, 109973, 210137, 401525, 767216, 1465963, 2801115, 5352275, 10226930, 19541236, 37338699, 71345449, 136324309, 260483548, 497722578, 951030367

Offset: 0

Ralf Stephan, May 08 2007

nonn

			From _Gus Wiseman_, Jul 06 2020: (Start)
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)
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..1000
S. Heubach and T. Mansour, Enumeration of 3-letter patterns in compositions, arXiv:math/0603285 [math.CO], 2006
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

Column k=0 of A232435.
Cf. A091616, A232432.
The matching version is A335464.
Contiguously (1,1)-avoiding compositions is A003242.
Contiguously (1,1)-matching compositions are A261983.
Compositions with some part > 2 are A008466
Compositions by number of adjacent equal parts are A106356.
Compositions where each part is adjacent to an equal part are A114901.
Compositions with adjacent parts coprime are A167606.
Compositions with equal parts contiguous are A274174.
Patterns contiguously matched by compositions are A335457.
Patterns contiguously matched by a given partition are A335516.
Cf. A005251, A032020, A131044, A178470, A242882, A333175, A335455.

b:= proc(n, t) option remember; `if`(n=0, 1, add(`if`(abs(t)<>j,
       b(n-j, j), `if`(t=-j, 0, b(n-j, -j))), j=1..n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..40);  # Alois P. Heinz, Nov 23 2013

nn=33;CoefficientList[Series[1/(1-Sum[(x^i+x^(2i))/(1+x^i+x^(2i)),{i,1,nn}]),{x,0,nn}],x] (* Geoffrey Critzer, Nov 23 2013 *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MatchQ[#,{_,x_,x_,x_,_}]&]],{n,13}] (* Gus Wiseman, Jul 06 2020 *)

G.f.: 1/(1-Sum(i>=1, x^i*(1+x^i)/(1+x^i*(1+x^i)) ) ).
a(n) ~ c * d^n, where d is the root of the equation Sum_{k>=1} 1/(d^k + 1/(1 + d^k)) = 1, d=1.9107639262818041675000243699745706859615884029961947632387839..., c=0.4993008137128378086219448701860326113802027003939127932922782... - Vaclav Kotesovec, May 01 2014, updated Jul 07 2020
For n>=2, a(n) = A091616(n) + A003242(n). - Vaclav Kotesovec, Jul 07 2020

A188900 Number of compositions of n that avoid the pattern 12-3.

Original entry on oeis.org

1, 1, 2, 4, 8, 16, 31, 60, 114, 215, 402, 746, 1375, 2520, 4593, 8329, 15036, 27027, 48389, 86314, 153432, 271853, 480207, 845804, 1485703, 2603018, 4549521, 7933239, 13803293, 23966682, 41530721, 71830198, 124010381, 213725823, 367736268, 631723139, 1083568861

Offset: 0

Nathaniel Johnston, Apr 17 2011

nonn

First differs from the non-dashed version A102726 at a(9) = 215, A102726(9) = 214, due to the composition (1,3,2,3).
The value a(11) = 7464 in Heubach et al. is a typo.
Theorem: A composition avoids 3-12 iff its leaders of maximal weakly decreasing runs are weakly increasing. For example, the composition q = (1,1,2,1,2,2,1,3) has maximal weakly decreasing runs ((1,1),(2,1),(2,2,1),(3)), with leaders (1,2,2,3), which are weakly increasing, so q is counted under a(13); also q avoids 3-12, as required. On the other hand, the composition q = (3,2,1,2,2,1,2) has maximal weakly decreasing runs ((3,2,1),(2,2,1),(2)), with leaders (3,2,2), which are not weakly increasing, so q is not counted under a(13); also q matches 3-12, as required. - Gus Wiseman, Aug 21 2024

			The initial terms are too dense, but see A375406 for the complement. - _Gus Wiseman_, Aug 21 2024

Nathaniel Johnston, Table of n, a(n) for n = 0..200
S. Heubach, T. Mansour and A. O. Munagi, Avoiding Permutation Patterns of Type (2,1) in Compositions, Online Journal of Analytic Combinatorics, 4 (2009).

The non-dashed version A102726, non-ranks A335483.
For 23-1 we have A189076.
The non-ranks are a subset of A335479 and do not include 404, 788, 809, ...
For strictly increasing leaders we have A358836, ranks A326533.
The strict version is A374762.
The complement is counted by A375406.
A003242 counts anti-run compositions, ranks A333489.
A011782 counts compositions.
A238130, A238279, A333755 count compositions by number of runs.
A335456 counts patterns matched by compositions.
Cf. A106356, A188920, A238343, A261982, A333175, A333213, A374630, A374679, A374688, A374740, A374741.

with(PolynomialTools):n:=20:taypoly:=taylor(mul(1/(1 - x^i/mul(1-x^j,j=1..i-1)),i=1..n),x=0,n+1):seq(coeff(taypoly,x,m),m=0..n);

m = 35;
Product[1/(1 - x^i/Product[1 - x^j, {j, 1, i - 1}]), {i, 1, m}] + O[x]^m // CoefficientList[#, x]& (* Jean-François Alcover, Mar 31 2020 *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], LessEqual@@First/@Split[#,GreaterEqual]&]],{n,0,15}] (* Gus Wiseman, Aug 21 2024 *)

G.f.: Product_{i>=1} (1/(1 - x^i/Product_{j=1..i-1} (1 - x^j))).

a(n) = 2^(n-1) - A375406(n). - Gus Wiseman, Aug 22 2024

cp's OEIS Frontend

A325535 Number of inseparable partitions of n; see Comments.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A274174 Number of compositions of n if all summand runs are kept together.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A374249 Numbers k such that the k-th composition in standard order has its equal parts contiguous.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A335548 Number of compositions of n with at least one non-contiguous value.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A374630 Sum of leaders of weakly increasing runs in the n-th composition in standard order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A335460 Number of (1,2,1) or (2,1,2)-matching permutations of the prime indices of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A374633 Numbers k such that the leaders of weakly increasing runs in the k-th composition in standard order (A066099) are identical.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica