A056986 -id:A056986 - cp's OEIS frontend

A335514 Number of (1,2,3)-matching compositions of n.

0, 0, 0, 0, 0, 0, 1, 4, 14, 42, 114, 292, 714, 1686, 3871, 8696, 19178, 41667, 89386, 189739, 399144, 833290, 1728374, 3565148, 7319212, 14965880, 30496302, 61961380, 125577752, 253971555, 512716564, 1033496947, 2080572090, 4183940550, 8406047907, 16875834728

Offset: 0

Gus Wiseman, Jun 22 2020

nonn

			The a(6) = 1 through a(8) = 14 compositions:
  (1,2,3)  (1,2,4)    (1,2,5)
           (1,1,2,3)  (1,3,4)
           (1,2,1,3)  (1,1,2,4)
           (1,2,3,1)  (1,2,1,4)
                      (1,2,2,3)
                      (1,2,3,2)
                      (1,2,4,1)
                      (2,1,2,3)
                      (1,1,1,2,3)
                      (1,1,2,1,3)
                      (1,1,2,3,1)
                      (1,2,1,1,3)
                      (1,2,1,3,1)
                      (1,2,3,1,1)

Andrew Howroyd, Table of n, a(n) for n = 0..500
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

The version for permutations is A056986.
The avoiding version is A102726.
These compositions are ranked by A335479.
The version for patterns is A335515.
The version for prime indices is A335520.
Permutations are counted by A000142 and ranked by A333218.
Patterns are counted by A000670 and ranked by A333217.
Patterns matched by compositions are counted by A335456.
Cf. A011782, A032020, A106356, A226316, A269134, A333755, A335465, A335521.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],MatchQ[#,{_,x_,_,y_,_,z_,_}/;x

a(n > 0) = 2^(n - 1) - A102726(n).

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

A335462 Number of (1,2,1) and (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, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 1

Gus Wiseman, Jun 20 2020

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.

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) permutations for n = 36, 72, 270, 144, 300:
  (1,2,1,2)  (1,1,2,1,2)  (2,1,2,3,2)  (1,1,1,2,1,2)  (1,2,3,1,3)
  (2,1,2,1)  (1,2,1,1,2)  (2,1,3,2,2)  (1,1,2,1,1,2)  (1,3,1,2,3)
             (1,2,1,2,1)  (2,2,1,3,2)  (1,1,2,1,2,1)  (1,3,1,3,2)
             (2,1,1,2,1)  (2,2,3,1,2)  (1,2,1,1,1,2)  (1,3,2,1,3)
             (2,1,2,1,1)  (2,3,1,2,2)  (1,2,1,1,2,1)  (1,3,2,3,1)
                          (2,3,2,1,2)  (1,2,1,2,1,1)  (2,1,3,1,3)
                                       (2,1,1,1,2,1)  (2,3,1,3,1)
                                       (2,1,1,2,1,1)  (3,1,2,1,3)
                                       (2,1,2,1,1,1)  (3,1,2,3,1)
                                                      (3,1,3,1,2)
                                                      (3,1,3,2,1)
                                                      (3,2,1,3,1)

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

The avoiding version is A333175.
Replacing "and" with "or" gives A335460.
Positions of nonzero terms are A335463.
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.
Patterns matched by standard compositions are counted by A335454.
Dimensions of downsets of standard compositions are A335465.
Cf. A056239, A056986, A112798, A158005, A181796, A335451, A335452.

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_,x_,_,y_,_,x_,_}/;x>y]&]],{n,100}]

A335463 Numbers k such that there exists a permutation of the prime indices of k matching both (1,2,1) and (2,1,2).

Original entry on oeis.org

36, 72, 90, 100, 108, 126, 144, 180, 196, 198, 200, 216, 225, 234, 252, 270, 288, 300, 306, 324, 342, 350, 360, 378, 392, 396, 400, 414, 432, 441, 450, 468, 484, 500, 504, 522, 525, 540, 550, 558, 576, 588, 594, 600, 612, 630, 648, 650, 666, 675, 676, 684, 700

Offset: 1

Gus Wiseman, Jun 20 2020

nonn

A prime index of k is a number m such that prime(m) divides k. The multiset of prime indices of k is row k 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 sequence of terms together with their prime indices begins:
   36: {1,1,2,2}
   72: {1,1,1,2,2}
   90: {1,2,2,3}
  100: {1,1,3,3}
  108: {1,1,2,2,2}
  126: {1,2,2,4}
  144: {1,1,1,1,2,2}
  180: {1,1,2,2,3}
  196: {1,1,4,4}
  198: {1,2,2,5}
  200: {1,1,1,3,3}
  216: {1,1,1,2,2,2}
  225: {2,2,3,3}
  234: {1,2,2,6}
  252: {1,1,2,2,4}
  270: {1,2,2,2,3}
  288: {1,1,1,1,1,2,2}
  300: {1,1,2,3,3}

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

Replacing "and" with "or" gives A126706.
Positions of nonzero terms in 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.
Patterns matched by standard compositions are counted by A335454.
Cf. A056239, A056986, A112798, A158005, A181796, A333175, A335451, A335452, A335460, A335465.

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

A335489 Number of strict permutations of the prime indices of n.

Original entry on oeis.org

1, 1, 1, 0, 1, 2, 1, 0, 0, 2, 1, 0, 1, 2, 2, 0, 1, 0, 1, 0, 2, 2, 1, 0, 0, 2, 0, 0, 1, 6, 1, 0, 2, 2, 2, 0, 1, 2, 2, 0, 1, 6, 1, 0, 0, 2, 1, 0, 0, 0, 2, 0, 1, 0, 2, 0, 2, 2, 1, 0, 1, 2, 0, 0, 2, 6, 1, 0, 2, 6, 1, 0, 1, 2, 0, 0, 2, 6, 1, 0, 0, 2, 1, 0, 2, 2, 2

Offset: 1

Gus Wiseman, Jun 19 2020

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.

Also the number of (1,1)-avoiding permutations of the prime indices of n.

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

Positions of first appearances are A002110 with 2 replaced by 4.
Permutations of prime indices are counted by A008480.
The contiguous version is A335451.
Anti-run permutations of prime indices are counted by A335452.
(1,1,1)-avoiding permutations of prime indices are counted by A335511.
Cf. A056239, A056986, A106356, A112798, A238279, A281188, A333221, A335456, A335460, A335462, A335465.

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

If n is squarefree, a(n) = A001221(n)!; otherwise a(n) = 0.

a(n != 4) = A281188(n); a(4) = 0.

A344652 Number of permutations of the prime indices of n with no adjacent triples (..., x, y, z, ...) such that x <= y <= z.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 0, 1, 2, 1, 2, 1, 2, 2, 0, 1, 2, 1, 2, 2, 2, 1, 1, 1, 2, 0, 2, 1, 5, 1, 0, 2, 2, 2, 3, 1, 2, 2, 1, 1, 5, 1, 2, 2, 2, 1, 0, 1, 2, 2, 2, 1, 1, 2, 1, 2, 2, 1, 7, 1, 2, 2, 0, 2, 5, 1, 2, 2, 5, 1, 2, 1, 2, 2, 2, 2, 5, 1, 0, 0, 2, 1, 7, 2, 2, 2

Offset: 1

Gus Wiseman, Jun 17 2021

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 permutations for n = 2, 6, 8, 30, 36, 60, 180, 210, 360:
  (1)  (12)  (132)  (1212)  (1213)  (12132)  (1324)  (121213)
       (21)  (213)  (2121)  (1312)  (13212)  (1423)  (121312)
             (231)  (2211)  (1321)  (13221)  (1432)  (121321)
             (312)          (2131)  (21213)  (2143)  (131212)
             (321)          (2311)  (21312)  (2314)  (132121)
                            (3121)  (21321)  (2413)  (132211)
                            (3211)  (22131)  (2431)  (212131)
                                    (23121)  (3142)  (213121)
                                    (23211)  (3214)  (213211)
                                    (31212)  (3241)  (221311)
                                    (32121)  (3412)  (231211)
                                    (32211)  (3421)  (312121)
                                             (4132)  (321211)
                                             (4213)
                                             (4231)
                                             (4312)
                                             (4321)

All permutations of prime indices are counted by A008480.
The case of permutations is A049774.
Avoiding (3,2,1) also gives A344606.
The wiggly case is A345164.
A001250 counts wiggly permutations.
A025047 counts wiggly compositions (ascend: A025048, descend: A025049).
A056239 adds up prime indices, row sums of A112798.
A325534 counts separable partitions, ranked by A335433.
A325535 counts inseparable partitions, ranked by A335448.
A335452 counts anti-run permutations of prime indices.
A345170 counts partitions with a wiggly permutation, ranked by A345172.
A345192 counts non-wiggly compositions, ranked by A345168.
Counting compositions by patterns:
- A102726 avoiding (1,2,3).
- A128761 avoiding (1,2,3) adjacent.
- A335514 matching (1,2,3).
- A344614 avoiding (1,2,3) and (3,2,1) adjacent.
- A344615 weakly avoiding (1,2,3) adjacent.
Cf. A001222, A003242, A056986, A316524, A333213, A335511, A344604, A344653, A344654, A345167, A345173.

Table[Length[Select[Permutations[Flatten[ ConstantArray@@@FactorInteger[n]]],!MatchQ[#,{_,x_,y_,z_,_}/;x<=y<=z]&]],{n,100}]

A019472 Weak preference orderings of n alternatives, i.e., orderings that have indifference between at least two alternatives.

Original entry on oeis.org

0, 0, 1, 7, 51, 421, 3963, 42253, 505515, 6724381, 98618763, 1582715773, 27612565995, 520631327581, 10554164679243, 228975516609853, 5294731892093355, 130015079601039901, 3379132289551117323, 92679942218919579133, 2675254894236207563115, 81073734056332364441821

Offset: 0

Robert Ware (bware(AT)wam.umd.edu)

From Gus Wiseman, Jun 24 2020: (Start)
Equivalently, a(n) is number of (1,1)-matching sequences of length n that cover an initial interval of positive integers. For example, the a(2) = 1 and a(3) = 7 sequences are:
  (1,1)  (1,1,1)
         (1,1,2)
         (1,2,1)
         (1,2,2)
         (2,1,1)
         (2,1,2)
         (2,2,1)
Missing from this list are:
  (1,2)  (1,2,3)
  (2,1)  (1,3,2)
         (2,1,3)
         (2,3,1)
         (3,1,2)
         (3,2,1)
(End)

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

Cf. A000670, A052875.
(1,1)-avoiding patterns are counted by A000142.
(1,2)-matching patterns are counted by A056823.
(1,1)-matching compositions are counted by A261982.
(1,1)-matching compositions are ranked by A335488.
Patterns matched by patterns are counted by A335517.
Cf. A056986, A333217, A335454, A335456, A335515.

a[n_] := Sum[(-1)^(j-i)*Binomial[j, i]*i^n, {i, 0, n-1}, {j, 0, n-1}]; Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Feb 26 2016, after Peter Luschny *)

def A019472(n):
    return add(add((-1)^(j-i)*binomial(j, i)*i^n for i in range(n)) for j in range(n))
[A019472(n) for n in range(21)] # Peter Luschny, Jul 22 2014

a(n) = A000670(n) - n!. - corrected by Eugene McDonnell, May 12 2000

a(n) = Sum_{j=0..n-1} Sum_{i=0..n-1} (-1)^(j-i)*C(j, i)*i^n. - Peter Luschny, Jul 22 2014

A335451 Number of permutations of the prime indices of n with all equal parts contiguous and none appearing more than twice.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 0, 1, 2, 1, 2, 1, 2, 2, 0, 1, 2, 1, 2, 2, 2, 1, 0, 1, 2, 0, 2, 1, 6, 1, 0, 2, 2, 2, 2, 1, 2, 2, 0, 1, 6, 1, 2, 2, 2, 1, 0, 1, 2, 2, 2, 1, 0, 2, 0, 2, 2, 1, 6, 1, 2, 2, 0, 2, 6, 1, 2, 2, 6, 1, 0, 1, 2, 2, 2, 2, 6, 1, 0, 0, 2, 1, 6, 2, 2, 2

Offset: 1

Gus Wiseman, Jun 21 2020

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 a(90) = 6 permutations are (1,2,2,3), (1,3,2,2), (2,2,1,3), (2,2,3,1), (3,1,2,2), (3,2,2,1).

Wikipedia, Permutation pattern

Separations are counted by A003242 and A335452 and ranked by A333489.
Permutations of prime indices are counted by A008480.
Unsorted prime signature is A124010. Sorted prime signature is A118914.
Permutations of prime indices with equal parts contiguous are A333175.
STC-numbers of permutations of prime indices are A333221.
(1,2,1) and (2,1,2)-avoiding permutations of prime indices are A333175.
Numbers whose prime indices are inseparable are A335448.
(1,2,1) or (2,1,2)-matching permutations of prime indices are A335460.
(1,2,1) and (2,1,2)-matching permutations of prime indices are A335462.
Strict permutations of prime indices are counted by A335489.
Cf. A056239, A056986, A112798, A181796, A335446, A335463.

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

a(n) = A001221(n)! if n is cubefree, otherwise 0.

A335516 Number of normal patterns contiguously matched by the prime indices of n in increasing or decreasing order, counting multiplicity.

Original entry on oeis.org

1, 2, 2, 3, 2, 3, 2, 4, 3, 3, 2, 5, 2, 3, 3, 5, 2, 5, 2, 5, 3, 3, 2, 7, 3, 3, 4, 5, 2, 4, 2, 6, 3, 3, 3, 7, 2, 3, 3, 7, 2, 4, 2, 5, 5, 3, 2, 9, 3, 5, 3, 5, 2, 7, 3, 7, 3, 3, 2, 7, 2, 3, 5, 7, 3, 4, 2, 5, 3, 4, 2, 10, 2, 3, 5, 5, 3, 4, 2, 9, 5, 3, 2, 7, 3, 3, 3

Offset: 1

Gus Wiseman, Jun 26 2020

nonn

First differs from A181796 at a(180) = 9, A181796(180) = 10.
First differs from A335549 at a(90) = 7, A335549(90) = 8.
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 (normal) 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 contiguously match a pattern P if there is a contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) contiguously matches (1,1,2) and (2,1,1) but not (2,1,2), (1,2,1), (1,2,2), or (2,2,1).

			The a(n) patterns for n = 2, 30, 12, 60, 120, 540, 1500:
  ()   ()     ()     ()      ()       ()        ()
  (1)  (1)    (1)    (1)     (1)      (1)       (1)
       (12)   (11)   (11)    (11)     (11)      (11)
       (123)  (12)   (12)    (12)     (12)      (12)
              (112)  (112)   (111)    (111)     (111)
                     (123)   (112)    (112)     (112)
                     (1123)  (123)    (122)     (122)
                             (1112)   (1112)    (123)
                             (1123)   (1122)    (1123)
                             (11123)  (1222)    (1222)
                                      (11222)   (1233)
                                      (12223)   (11233)
                                      (112223)  (12333)
                                                (112333)

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

The version for standard compositions is A335458.
The not necessarily contiguous version is A335549.
Patterns are counted by A000670 and ranked by A333217.
A number's prime indices are given in the rows of A112798.
Contiguous subsequences of standard compositions are A124771.
Contiguous sub-partitions of prime indices are counted by A335519.
Minimal avoided patterns of prime indices are counted by A335550.
Patterns contiguously matched by partitions are counted by A335838.
Cf. A000005, A056239, A056986, A108917, A124770, A181796, A269134, A333224, A334299, A335457, A335837.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
mstype[q_]:=q/.Table[Union[q][[i]]->i,{i,Length[Union[q]]}];
Table[Length[Union[mstype/@ReplaceList[primeMS[n],{_,s___,_}:>{s}]]],{n,100}]

A214152 Number of permutations T(n,k) in S_n containing an increasing subsequence of length k; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

Original entry on oeis.org

1, 2, 1, 6, 5, 1, 24, 23, 10, 1, 120, 119, 78, 17, 1, 720, 719, 588, 207, 26, 1, 5040, 5039, 4611, 2279, 458, 37, 1, 40320, 40319, 38890, 24553, 6996, 891, 50, 1, 362880, 362879, 358018, 268521, 101072, 18043, 1578, 65, 1, 3628800, 3628799, 3612004, 3042210, 1438112, 337210, 40884, 2603, 82, 1

Offset: 1

Alois P. Heinz, Jul 05 2012

			T(3,2) = 5.  All 3! = 6 permutations of {1,2,3} contain an increasing subsequence of length 2 with the exception of 321.
Triangle T(n,k) begins:
     1;
     2,    1;
     6,    5,    1;
    24,   23,   10,    1;
   120,  119,   78,   17,   1;
   720,  719,  588,  207,  26,  1;
  5040, 5039, 4611, 2279, 458, 37,  1;
  ...

Alois P. Heinz, Rows n = 1..55, flattened
Eric Weisstein's World of Mathematics, Permutation Pattern
Wikipedia, Longest increasing subsequence problem
Wikipedia, Young tableau

Columns k=1-10 give: A000142 (for n>0), A033312, A056986, A158005, A158432, A159139, A159175, A217675, A217676, A217677.
Row sums give: A003316.
T(2n,n) gives A269021.
Diagonal and lower diagonals give: A000012, A002522, A217200, A217193.
Cf. A047874, A214015.

h:= proc(l) local n; n:=nops(l); add(i, i=l)! /mul(mul(1+l[i]-j
      +add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n)
    end:
g:= (n, i, l)-> `if`(n=0 or i=1, h([l[], 1$n])^2, `if`(i<1, 0,
                 add(g(n-i*j, i-1, [l[], i$j]), j=0..n/i))):
T:= (n, k)-> n! -g(n, k-1, []):
seq(seq(T(n, k), k=1..n), n=1..12);

h[l_] := With[{n = Length[l]}, Sum[i, {i, l}]! / Product[Product[1 + l[[i]] - j + Sum[If[l[[k]] >= j, 1, 0], {k, i+1, n}], {j, 1, l[[i]]}], {i, 1, n}] ]; g[n_, i_, l_] := If[n == 0 || i === 1, h[Join[l, Array[1&, n]]]^2, If[i < 1, 0, Sum[g[n - i*j, i-1, Join[l, Array[i&, j]]], {j, 0, n/i}]]]; t[n_, k_] := n! - g[n, k-1, {}]; Table[Table[t[n, k], {k, 1, n}], {n, 1, 12}] // Flatten (* Jean-François Alcover, Dec 17 2013, translated from Maple *)

T(n,k) = Sum_{i=k..n} A047874(n,i).

T(n,k) = A000142(n) - A214015(n,k-1).

A226316 Expansion of g.f. 1/2 + 1/(1+sqrt(1-8x+8x^2)).

Original entry on oeis.org

1, 1, 3, 12, 56, 284, 1516, 8384, 47600, 275808, 1624352, 9694912, 58510912, 356467392, 2189331648, 13540880384, 84265071360, 527232146944, 3314742364672, 20930141861888, 132673039491072, 843959152564224, 5385800362473472, 34470606645280768, 221213787774230528, 1423139139514138624

Offset: 0

N. J. A. Sloane, Jun 09 2013

nonn

From Robert A. Proctor, Jul 18 2017: (Start)
a(n) is the number of words of length n on {1,2,...,r} with positive multiplicities as 1 <= r <= n avoiding the pattern 123. [This is easy to see from the next comment.]
a(n) is the number of 123-avoiding ordered set partitions of {1,2,...,n}. [This is Cor. 2.3 of the Chen-Dai-Zhou reference.] (End)

			From _Gus Wiseman_, Jun 25 2020: (Start)
The a(0) = 1 through a(3) = 12 words that are (1,2,3)-avoiding and cover an initial interval:
  ()  (1)  (1,1)  (1,1,1)
           (1,2)  (1,1,2)
           (2,1)  (1,2,1)
                  (1,2,2)
                  (1,3,2)
                  (2,1,1)
                  (2,1,2)
                  (2,1,3)
                  (2,2,1)
                  (2,3,1)
                  (3,1,2)
                  (3,2,1)
(End)

Vincenzo Librandi, Table of n, a(n) for n = 0..100
Daniel Birmajer, Juan B. Gil, David S. Kenepp, and Michael D. Weiner, Restricted generating trees for weak orderings, arXiv:2108.04302 [math.CO], 2021.
W. Y. C. Chen, A. Y. L. Dai and R. D. P. Zhou, Ordered Partitions Avoiding a Permutation of Length 3, arXiv preprint arXiv:1304.3187 [math.CO], 2013.
Anders Claesson, Giulio Cerbai, Dana C. Ernst, and Hannah Golab, Pattern-avoiding Cayley permutations via combinatorial species, arXiv:2407.19583 [math.CO], 2024.
Robert A. Proctor and Matthew J. Willis, Parabolic Catalan numbers count flagged Schur functions and their appearances as type A Demazure characters (key polynomials), arXiv preprint arXiv:1706.04649 [math.CO], 2017.
Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

Cf. A220097.
Sequences covering an initial interval are counted by A000670.
(1,2,3)-matching permutations are counted by A056986.
(1,2,3)-avoiding permutations are counted by A000108.
(1,2,3)-matching compositions are counted by A335514.
(1,2,3)-avoiding compositions are counted by A102726.
(1,2,3)-matching patterns are counted by A335515.
(1,2,3)-avoiding patterns are counted by A226316 (this sequence).
(1,2,3)-matching permutations of prime indices are counted by A335520.
(1,2,3)-avoiding permutations of prime indices are counted by A335521.
(1,2,3)-matching compositions are ranked by A335479.
Cf. A158005, A158009, A333217, A335465.

a:= proc(n) option remember; `if`(n<4, [1$2, 3, 12][n+1],
      ((9*n-3)*a(n-1) -(16*n-20)*a(n-2) +(8*n-16)*a(n-3))/(n+1))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Jun 18 2013

CoefficientList[Series[1/2 + 1 / (1 + Sqrt[1 - 8 x + 8 x^2]), {x, 0, 30}], x] (* Vincenzo Librandi, Jun 18 2013 *)
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_,_,y_,_,z_,_}/;xGus Wiseman, Jun 25 2020 *)

a(n) ~ sqrt((sqrt(2)-1)/Pi)*2^(n-1/2)*(2+sqrt(2))^n/n^(3/2). - Vaclav Kotesovec, Jun 29 2013
Conjecture: (n+1)*a(n) +3*(-3*n+1)*a(n-1) +4*(4*n-5)*a(n-2) +8*(-n+2)*a(n-3)=0. - R. J. Mathar, Apr 02 2015
a(n) = A000670(n) - A335515(n). - Gus Wiseman, Jun 25 2020

cp's OEIS Frontend

A335514 Number of (1,2,3)-matching compositions of n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A335462 Number of (1,2,1) and (2,1,2)-matching permutations of the prime indices of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A335463 Numbers k such that there exists a permutation of the prime indices of k matching both (1,2,1) and (2,1,2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A335489 Number of strict permutations of the prime indices of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A344652 Number of permutations of the prime indices of n with no adjacent triples (..., x, y, z, ...) such that x <= y <= z.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A019472 Weak preference orderings of n alternatives, i.e., orderings that have indifference between at least two alternatives.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Sage

Formula

A335451 Number of permutations of the prime indices of n with all equal parts contiguous and none appearing more than twice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A335516 Number of normal patterns contiguously matched by the prime indices of n in increasing or decreasing order, counting multiplicity.

Views

Author

Keywords

Comments

Examples

Links

A226316 Expansion of g.f. 1/2 + 1/(1+sqrt(1-8x+8x^2)).