A019472 -id:A019472 - cp's OEIS frontend

A335508 Number of patterns of length n matching the pattern (1,1,1).

0, 0, 0, 1, 9, 91, 993, 12013, 160275, 2347141, 37496163, 649660573, 12142311195, 243626199181, 5224710549243, 119294328993853, 2889836999693355, 74037381200415901, 2000383612949821323, 56850708386783835133, 1695491518035158123115, 52949018580275965241821

Offset: 0

Gus Wiseman, Jun 18 2020

nonn

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(3) = 1 through a(4) = 9 patterns:
  (1,1,1)  (1,1,1,1)
           (1,1,1,2)
           (1,1,2,1)
           (1,2,1,1)
           (1,2,2,2)
           (2,1,1,1)
           (2,1,2,2)
           (2,2,1,2)
           (2,2,2,1)

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

The complement A080599 is the avoiding version.
Permutations of prime indices matching this pattern are counted by A335510.
Compositions matching this pattern are counted by A335455 and ranked by A335512.
Patterns are counted by A000670 and ranked by A333217.
Patterns matching the pattern (1,1) are counted by A019472.
Combinatory separations are counted by A269134.
Patterns matched by standard compositions are counted by A335454.
Minimal patterns avoided by a standard composition are counted by A335465.
Patterns matching (1,2,3) are counted by A335515.
Cf. A034691, A056986, A232464, A238279, A292884, A333175, A333755, A335451, A335456, A335457, A335458.
Cf. A276922.

b:= proc(n, k) option remember; `if`(n=0, 1, add(
      b(n-i, k)*binomial(n, i), i=1..min(n, k)))
    end:
a:= n-> b(n$2)-b(n, 2):
seq(a(n), n=0..21);  # Alois P. Heinz, Jan 28 2024

allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
Table[Length[Select[Join@@Permutations/@allnorm[n],MatchQ[#,{_,x_,_,x_,_,x_,_}]&]],{n,0,6}]

a(n) = Sum_{k=3..n} A276922(n,k). - Alois P. Heinz, Jan 28 2024

a(n) = A000670(n) - A080599(n). - Andrew Howroyd, Jan 28 2024

a(9)-a(21) from Alois P. Heinz, Jan 28 2024

A386576 Number of anti-runs of length n covering an initial interval of positive integers with strictly decreasing multiplicities.

Original entry on oeis.org

1, 1, 0, 1, 0, 1, 10, 4, 14, 84, 1136, 967, 3342, 12823, 101762, 1769580

Offset: 0

Gus Wiseman, Aug 03 2025

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

			The a(7) = 4 anti-runs are:
  (1,2,1,2,1,2,1)
  (1,2,1,2,1,3,1)
  (1,2,1,3,1,2,1)
  (1,3,1,2,1,2,1)

For any multiplicities we have A005649.
For weakly instead of strictly decreasing multiplicities we have A321688.
A003242 and A335452 count anti-runs, ranks A333489.
A005651 counts ordered set partitions with weakly decreasing sizes, strict A007837.
A032020 counts strict anti-run compositions.
A325534 counts separable multisets, ranks A335433.
A325535 counts inseparable multisets, ranks A335448.
A336103 counts normal separable multisets, inseparable A336102.
A386583 counts separable partitions by length, inseparable A386584.
A386585 counts partitions of separable type by length, sums A336106, ranks A335127.
A386586 counts partitions of inseparable type by length, sums A025065, ranks A335126.
A386633 counts separable set partitions, row sums of A386635.
A386634 counts inseparable set partitions, row sums of A386636.
Cf. A000670, A019472, A106351, A238130, A335125, A335516, A386580, A386581.

seps[ptn_,fir_]:=If[Total[ptn]==1,{{fir}},Join@@Table[Prepend[#,fir]&/@seps[MapAt[#-1&,ptn,fir],nex],{nex,Select[DeleteCases[Range[Length[ptn]],fir],ptn[[#]]>0&]}]];
seps[ptn_]:=If[Total[ptn]==0,{{}},Join@@(seps[ptn,#]&/@Range[Length[ptn]])];
Table[Sum[Length[seps[y]],{y,Select[IntegerPartitions[n],UnsameQ@@#&]}],{n,0,10}]

A337506 Triangle read by rows where T(n,k) is the number of length-n sequences covering an initial interval of positive integers with k maximal anti-runs.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 8, 4, 1, 0, 44, 24, 6, 1, 0, 308, 176, 48, 8, 1, 0, 2612, 1540, 440, 80, 10, 1, 0, 25988, 15672, 4620, 880, 120, 12, 1, 0, 296564, 181916, 54852, 10780, 1540, 168, 14, 1, 0, 3816548, 2372512, 727664, 146272, 21560, 2464, 224, 16, 1

Offset: 0

Gus Wiseman, Sep 06 2020

An anti-run is a sequence with no adjacent equal parts. The number of maximal anti-runs is one more than the number of adjacent equal parts.

			Triangle begins:
  1
  0      1
  0      2      1
  0      8      4      1
  0     44     24      6      1
  0    308    176     48      8      1
  0   2612   1540    440     80     10      1
  0  25988  15672   4620    880    120     12      1
  0 296564 181916  54852  10780   1540    168     14      1
Row n = 3 counts the following sequences (empty column indicated by dot):
  .  (1,2,1)  (1,1,2)  (1,1,1)
     (1,2,3)  (1,2,2)
     (1,3,2)  (2,1,1)
     (2,1,2)  (2,2,1)
     (2,1,3)
     (2,3,1)
     (3,1,2)
     (3,2,1)

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

A000670 gives row sums.
A005649 gives column k = 1.
A337507 gives column k = 2.
A337505 gives the diagonal n = 2*k.
A106356 is the version for compositions.
A238130/A238279/A333755 is the version for runs in compositions.
A335461 has the reversed rows (except zeros).
A003242 counts anti-run compositions.
A124762 counts adjacent equal terms in standard compositions.
A124767 counts maximal runs in standard compositions.
A333381 counts maximal anti-runs in standard compositions.
A333382 counts adjacent unequal terms in standard compositions.
A333489 ranks anti-run compositions.
A333769 gives maximal run-lengths in standard compositions.
A337565 gives maximal anti-run lengths in standard compositions.
Cf. A019472, A052841, A060223, A106351, A269134, A325535, A337564.

allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
Table[Length[Select[Join@@Permutations/@allnorm[n],Length[Split[#,UnsameQ]]==k&]],{n,0,5},{k,0,n}]

\\ here b(n) is A005649.
b(n) = {sum(k=0, n, stirling(n,k,2)*(k + 1)!)}
T(n,k)=if(n==0, k==0, b(n-k)*binomial(n-1,k-1)) \\ Andrew Howroyd, Dec 31 2020

T(n,k) = A005649(n-k) * binomial(n-1,k-1) for k > 0. - Andrew Howroyd, Dec 31 2020

Terms a(45) and beyond from Andrew Howroyd, Dec 31 2020

A335487 Number of (1,1)-matching permutations of the prime indices of n.

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 3, 0, 0, 0, 1, 0, 3, 0, 3, 0, 0, 0, 4, 1, 0, 1, 3, 0, 0, 0, 1, 0, 0, 0, 6, 0, 0, 0, 4, 0, 0, 0, 3, 3, 0, 0, 5, 1, 3, 0, 3, 0, 4, 0, 4, 0, 0, 0, 12, 0, 0, 3, 1, 0, 0, 0, 3, 0, 0, 0, 10, 0, 0, 3, 3, 0, 0, 0, 5, 1, 0, 0, 12, 0, 0

Offset: 1

Gus Wiseman, Jun 14 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. 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) permutations for n = 4, 12, 24, 48, 36, 72, 60:
  (11)  (112)  (1112)  (11112)  (1122)  (11122)  (1123)
        (121)  (1121)  (11121)  (1212)  (11212)  (1132)
        (211)  (1211)  (11211)  (1221)  (11221)  (1213)
               (2111)  (12111)  (2112)  (12112)  (1231)
                       (21111)  (2121)  (12121)  (1312)
                                (2211)  (12211)  (1321)
                                        (21112)  (2113)
                                        (21121)  (2131)
                                        (21211)  (2311)
                                        (22111)  (3112)
                                                 (3121)
                                                 (3211)

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

Positions of zeros are A005117 (squarefree numbers).
The case where the match must be contiguous is A333175.
The avoiding version is A335489.
The (1,1,1)-matching case is A335510.
Patterns are counted by A000670.
Permutations of prime indices are counted by A008480.
(1,1)-matching patterns are counted by A019472.
(1,1)-matching compositions are counted by A261982.
STC-numbers of permutations of prime indices are A333221.
Patterns matched by standard compositions are counted by A335454.
Dimensions of downsets of standard compositions are A335465.
(1,1)-matching compositions are ranked by A335488.
Cf. A000961, A056239, A056986, A112798, A181796, A335451, A335452, A335460, A335462.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Table[Length[Select[Permutations[primeMS[n]],!UnsameQ@@#&]],{n,100}]

a(n) = 0 if n is squarefree, otherwise a(n) = A008480(n).

a(n) = A008480(n) - A281188(n) for n != 4.

A337507 Number of length-n sequences covering an initial interval of positive integers with exactly two maximal anti-runs, or with one pair of adjacent equal parts.

Original entry on oeis.org

0, 0, 1, 4, 24, 176, 1540, 15672, 181916, 2372512, 34348932, 546674120, 9486840748, 178285201008, 3607174453844, 78177409231768, 1806934004612220, 44367502983673664, 1153334584544496676, 31643148872573831016

Offset: 0

Gus Wiseman, Sep 06 2020

nonn

An anti-run is a sequence with no adjacent equal parts. For example, the maximal anti-runs in (3,1,1,2,2,2,1) are ((3,1),(1,2),(2),(2,1)). In general, there is one more maximal anti-run than the number of pairs of adjacent equal parts.

			The a(4) = 24 sequences:
  (2,1,2,2)  (2,1,3,3)  (3,1,2,2)
  (2,2,1,2)  (2,3,3,1)  (3,2,2,1)
  (1,2,2,1)  (3,3,1,2)  (1,1,2,3)
  (2,1,1,2)  (3,3,2,1)  (1,1,3,2)
  (1,1,2,1)  (1,2,2,3)  (2,1,1,3)
  (1,2,1,1)  (1,3,2,2)  (2,3,1,1)
  (1,2,3,3)  (2,2,1,3)  (3,1,1,2)
  (1,3,3,2)  (2,2,3,1)  (3,2,1,1)

A002133 is the version for runs in partitions.
A106357 is the version for compositions.
A337506 has this as column k = 2.
A000670 counts patterns.
A005649 counts anti-run patterns.
A003242 counts anti-run compositions.
A106356 counts compositions by number of maximal anti-runs.
A124762 counts adjacent equal terms in standard compositions.
A124767 counts maximal runs in standard compositions.
A238130/A238279/A333755 count maximal runs in compositions.
A333381 counts maximal anti-runs in standard compositions.
A333382 counts adjacent unequal terms in standard compositions.
A333489 ranks anti-run compositions.
A333769 gives maximal run lengths in standard compositions.
A337565 gives maximal anti-run lengths in standard compositions.
Cf. A019472, A052841, A060223, A106351, A269134, A335461, A337505, A337564.

kv=2;
allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
Table[Length[Select[Join@@Permutations/@allnorm[n],Length[Split[#,UnsameQ]]==kv&]],{n,0,6}]

a(n > 0) = (n - 1)*A005649(n - 2).

cp's OEIS Frontend

A335508 Number of patterns of length n matching the pattern (1,1,1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A386576 Number of anti-runs of length n covering an initial interval of positive integers with strictly decreasing multiplicities.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A337506 Triangle read by rows where T(n,k) is the number of length-n sequences covering an initial interval of positive integers with k maximal anti-runs.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A335487 Number of (1,1)-matching permutations of the prime indices of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A337507 Number of length-n sequences covering an initial interval of positive integers with exactly two maximal anti-runs, or with one pair of adjacent equal parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula