A226316 -id:A226316 - cp's OEIS frontend

A350354 Number of up/down (or down/up) patterns of length n.

1, 1, 1, 3, 11, 51, 281, 1809, 13293, 109899, 1009343, 10196895, 112375149, 1341625041, 17249416717, 237618939975, 3491542594727, 54510993341523, 901106621474801, 15723571927404189, 288804851413993941, 5569918636750820751, 112537773142244706427

Offset: 0

Gus Wiseman, Jan 16 2022

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 patten is up/down if it is alternately strictly increasing and strictly decreasing, starting with an increase.
A pattern is up/down if it is alternately strictly increasing and strictly decreasing, starting with an increase. For example, the partition (3,2,2,2,1) has no up/down permutations, even though it does have the anti-run permutation (2,3,2,1,2).
Conjecture: Also the half the number of weakly up/down patterns of length n.
These are the values of the Euler zig-zag polynomials A205497 evaluated at x = 1/2 and normalized by 2^n. - Peter Luschny, Jun 03 2024

			The a(0) = 1 through a(4) = 11 patterns:
  ()  (1)  (1,2)  (1,2,1)  (1,2,1,2)
                  (1,3,2)  (1,2,1,3)
                  (2,3,1)  (1,3,1,2)
                           (1,3,2,3)
                           (1,3,2,4)
                           (1,4,2,3)
                           (2,3,1,2)
                           (2,3,1,3)
                           (2,3,1,4)
                           (2,4,1,3)
                           (3,4,1,2)

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

The version for permutations is A000111, undirected A001250.
For compositions we have A025048, down/up A025049, undirected A025047.
This is the up/down (or down/up) case of A345194.
A205497 are the Euler zig-zag polynomials.
A000670 counts patterns, ranked by A333217.
A005649 counts anti-run patterns.
A019536 counts necklace patterns.
A226316 counts patterns avoiding (1,2,3), weakly A052709.
A335515 counts patterns matching (1,2,3).
A349058 counts weakly alternating patterns.
A350252 counts non-alternating patterns.
Row sums of A079502.
Cf. A000041, A003242, A049774, A124754, A128761, A335457, A344604, A344605, A344615, A348610.

# Using the recurrence by Kyle Petersen from A205497.
G := proc(n) option remember; local F;
if n = 0 then 1/(1 - q*x) else F := G(n - 1);
simplify((p/(p - q))*(subs({p = q, q = p}, F) - subs(p = q, F))) fi end:
A350354 := n -> 2^n*subs({p = 1, q = 1, x = 1/2}, G(n)*(1 - x)^(n + 1)):
seq(A350354(n), n = 0..22);  # Peter Luschny, Jun 03 2024

allnorm[n_]:=If[n<=0,{{}},Function[s, Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
updoQ[y_]:=And@@Table[If[EvenQ[m],y[[m]]>y[[m+1]],y[[m]]

F(p,x) = {sum(k=0, p, (-1)^((k+1)\2)*binomial((p+k)\2, k)*x^k)}
R(n,k) = {Vec(if(k==1, 0, F(k-2,-x)/F(k-1,x)-1) + x + O(x*x^n))}
seq(n)= {concat([1], sum(k=1, n, R(n, k)*sum(r=k, n, binomial(r, k)*(-1)^(r-k)) ))} \\ Andrew Howroyd, Feb 04 2022

a(n > 2) = A344605(n)/2.

a(n > 1) = A345194(n)/2.

Terms a(10) and beyond from Andrew Howroyd, Feb 04 2022

A240800 Total number of occurrences of the pattern 1<2<3 in all preferential arrangements (or ordered partitions) of n elements.

Original entry on oeis.org

0, 0, 1, 28, 570, 10700, 200235, 3857672, 77620788, 1641549000, 36576771165, 859032716740, 21251178078702, 553095031003060, 15122143306215855, 433634860865610320, 13020228528050054760, 408687299328542444880, 13389274565474007735009, 457150279686453405468780

Offset: 1

N. J. A. Sloane, Apr 13 2014

nonn

There are A000670(n) preferential arrangements of n elements - see A000670, A240763.

The number that avoid the pattern 1<2<3 is given in A226316.

Alois P. Heinz, Table of n, a(n) for n = 1..120

Cf. A000670, A240763, A240796-A240800, A226316.

b:= proc(n, t, h) option remember; `if`(n=0, [1, 0], add((p-> p+
      [0, p[1]*j*h/6])(b(n-j, t+j, h+j*t))*binomial(n, j), j=1..n))
    end:
a:= n-> b(n, 0$2)[2]:
seq(a(n), n=1..25);  # Alois P. Heinz, Dec 08 2014

b[n_, t_, h_] := b[n, t, h] = If[n == 0, {1, 0}, Sum[Function[{p}, p + {0, p[[1]]*j*h/6}][b[n - j, t + j, h + j*t]]*Binomial[n, j], {j, 1, n}]]; a[n_] := b[n, 0, 0][[2]]; Table[a[n], {n, 1, 25}] (* Jean-François Alcover, Jun 08 2015, after Alois P. Heinz *)

a(n) ~ n! * n^3 / (72 * (log(2))^(n+1)). - Vaclav Kotesovec, May 03 2015

a(8)-a(20) from Alois P. Heinz, Dec 08 2014

A335521 Number of (1,2,3)-avoiding permutations of the prime indices of n.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 2, 1, 1, 3, 1, 3, 2, 2, 1, 4, 1, 2, 1, 3, 1, 5, 1, 1, 2, 2, 2, 6, 1, 2, 2, 4, 1, 5, 1, 3, 3, 2, 1, 5, 1, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 9, 1, 2, 3, 1, 2, 5, 1, 3, 2, 5, 1, 10, 1, 2, 3, 3, 2, 5, 1, 5, 1, 2, 1, 9, 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.

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 = 1, 6, 12, 24, 30, 36, 60, 72, 120:
  ()  (12)  (112)  (1112)  (132)  (1122)  (1132)  (11122)  (11132)
      (21)  (121)  (1121)  (213)  (1212)  (1312)  (11212)  (11312)
            (211)  (1211)  (231)  (1221)  (1321)  (11221)  (11321)
                   (2111)  (312)  (2112)  (2113)  (12112)  (13112)
                           (321)  (2121)  (2131)  (12121)  (13121)
                                  (2211)  (2311)  (12211)  (13211)
                                          (3112)  (21112)  (21113)
                                          (3121)  (21121)  (21131)
                                          (3211)  (21211)  (21311)
                                                  (22111)  (23111)
                                                           (31112)
                                                           (31121)
                                                           (31211)
                                                           (32111)

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

These compositions are counted by A102726.
Patterns avoiding this pattern are counted by A226316.
The complement A335520 is the matching version.
Permutations of prime indices are counted by A008480.
Patterns are counted by A000670 and ranked by A333217.
Anti-run permutations of prime indices are counted by A335452.
Cf. A056239, A056986, A112798, A238279, A281188, A333221, A333755, A335456, A335460, A335462, 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_,_,z_,_}/;x

For n > 0, a(n) + A335520(n) = A008480(n).

A335793 Number of hare pop-stack sortable Cayley permutations.

Original entry on oeis.org

1, 1, 3, 11, 41, 151, 553, 2023, 7401

Offset: 0

Michael De Vlieger, Jun 23 2020

Also, the set of Cayley permutations avoiding 231, 312, and 2121.

Giulio Cerbai, Sorting Cayley permutations with pattern-avoiding machines, arXiv:2003.02536 [math.CO], 2020. See p. 16.

Cf. A000670, A226316.

Conjectures from Colin Barker, Jun 24 2020: (Start)
G.f.: (1 - 4*x + 4*x^2 - 2*x^3) / (1 - 5*x + 6*x^2 - 4*x^3).
a(n) = 5*a(n-1) - 6*a(n-2) + 4*a(n-3) for n>3.
(End)

a(7)-a(8) from Giulio Cerbai via Michael De Vlieger, Jun 24 2020

cp's OEIS Frontend

A350354 Number of up/down (or down/up) patterns of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A240800 Total number of occurrences of the pattern 1<2<3 in all preferential arrangements (or ordered partitions) of n elements.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A335521 Number of (1,2,3)-avoiding permutations of the prime indices of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A335793 Number of hare pop-stack sortable Cayley permutations.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions