A049774 -id:A049774 - cp's OEIS frontend

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

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

A349058 Number of weakly alternating patterns of length n.

Original entry on oeis.org

1, 1, 3, 11, 43, 203, 1123, 7235, 53171, 439595, 4037371, 40787579, 449500595, 5366500163, 68997666867, 950475759899, 13966170378907, 218043973366091, 3604426485899203, 62894287709616755, 1155219405655975763, 22279674547003283003, 450151092568978825707

Offset: 0

Gus Wiseman, Dec 04 2021

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.

We define a sequence to be weakly alternating if it is alternately weakly increasing and weakly decreasing, starting with either.

			The a(1) = 1 through a(3) = 11 patterns:
  (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)

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

The strict case is A001250, complement A348615.
The strong case of compositions is A025047, ranked by A345167.
The unordered version is A052955.
The strong case is A345194, with twins A344605. Also the directed case.
The version for compositions is A349052, complement A349053.
The version for permutations of prime indices: A349056, complement A349797.
The version for compositions is ranked by A349057.
The version for ordered factorizations is A349059, strong A348610.
The version for partitions is A349060, complement A349061.
A003242 counts Carlitz (anti-run) compositions.
A005649 counts anti-run patterns.
A344604 counts alternating compositions with twins.
A345163 counts normal partitions with an alternating permutation.
A345170 counts partitions w/ an alternating permutation, complement A345165.
A345192 counts non-alternating compositions, ranked by A345168.
A349055 counts multisets w/ an alternating permutation, complement A349050.
Cf. A049774, A096441, A129852, A129853, A336103, A344614, A344615, A344740, A345164, A348613, A349794.

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

R(n,k)={my(v=vector(k,i,1), u=vector(n)); for(r=1, n, if(r%2==0, my(s=v[k]); forstep(i=k, 2, -1, v[i] = s - v[i-1]); v[1] = s); for(i=2, k, v[i] += v[i-1]); u[r]=v[k]); u}
seq(n)= {concat([1], -vector(n,i,1) + 2*sum(k=1, n, R(n, k)*sum(r=k, n, binomial(r, k)*(-1)^(r-k)) ) )} \\ Andrew Howroyd, Jan 13 2024

a(9)-a(18) from Alois P. Heinz, Dec 10 2021

a(19) onwards from Andrew Howroyd, Jan 13 2024

A350252 Number of non-alternating patterns of length n.

Original entry on oeis.org

0, 0, 1, 7, 53, 439, 4121, 43675, 519249, 6867463, 100228877, 1602238783, 27866817297, 524175098299, 10606844137009, 229807953097903, 5308671596791901, 130261745042452855, 3383732450013895721, 92770140175473602755, 2677110186541556215233

Offset: 0

Gus Wiseman, Jan 13 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 sequence is alternating if it is alternately strictly increasing and strictly decreasing, starting with either. For example, the partition (3,2,2,2,1) has no alternating permutations, even though it does have the anti-run permutations (2,3,2,1,2) and (2,1,2,3,2). An alternating pattern is necessarily an anti-run (A005649).
Conjecture: Also the number of non-weakly up/down (or down/up) patterns of length n. For example:
- The a(3) = 7 non-weakly up/down patterns:
  (121), (122), (123), (132), (221), (231), (321)
- The a(3) = 7 non-weakly down/up patterns:
  (112), (123), (211), (212), (213), (312), (321)
- The a(3) = 7 non-alternating patterns (see example for more):
  (111), (112), (122), (123), (211), (221), (321)

			The a(2) = 1 and a(3) = 7 non-alternating patterns:
  (1,1)  (1,1,1)
         (1,1,2)
         (1,2,2)
         (1,2,3)
         (2,1,1)
         (2,2,1)
         (3,2,1)
The a(4) = 53 non-alternating patterns:
  2112   3124   4123   1112   2134   1234   3112   2113   1123
  2211   3214   4213   1211   2314   1243   3123   2123   1213
  2212   3412   4312   1212   2341   1324   3211   2213   1223
         3421   4321   1221   2413   1342   3212   2311   1231
                       1222   2431   1423   3213   2312   1232
                                     1432   3312   2313   1233
                                            3321   2321   1312
                                                   2331   1321
                                                          1322
                                                          1323
                                                          1332

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

The unordered version is A122746.
The version for compositions is A345192, ranked by A345168, weak A349053.
The complement is counted by A345194, weak A349058.
The version for factorizations is A348613, complement A348610, weak A350139.
The strict case (permutations) is A348615, complement A001250.
The weak version for partitions is A349061, complement A349060.
The weak version for perms of prime indices is A349797, complement A349056.
The weak version is A350138.
The version for perms of prime indices is A350251, complement A345164.
A000670 = patterns (ranked by A333217).
A003242 = anti-run compositions, complement A261983, ranked by A333489.
A005649 = anti-run patterns, complement A069321.
A019536 = necklace patterns.
A025047/A129852/A129853 = alternating compositions, ranked by A345167.
A226316 = patterns avoiding (1,2,3), weakly A052709, complement A335515.
A345163 = normal partitions w/ alternating permutation, complement A345162.
A345170 = partitions w/ alternating permutation, complement A345165.
A349055 = normal multisets w/ alternating permutation, complement A349050.
Cf. A049774, A052955, A096441, A128761, A274230, A335456, A335457, A336103, A344605, A344614.

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

a(n) = A000670(n) - A345194(n).

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

A111004 Number of permutations avoiding a consecutive 132 pattern.

Original entry on oeis.org

1, 1, 2, 5, 16, 63, 296, 1623, 10176, 71793, 562848, 4853949, 45664896, 465403791, 5108121216, 60069714207, 753492215808, 10042248398625, 141712039383552, 2110880441637045, 33097631526180864, 544903371859138335, 9398216812334008320, 169463659008217238055

Offset: 0

David Callan, Oct 01 2005

nonn

a(n) is the number of permutations on [n] that avoid the consecutive pattern 132 (pattern entries must occur consecutively in the permutation).
In the Mathematica code below, a[n, k] is the number of such permutations with first entry k and they are counted recursively by the length, say ell, of the longest increasing left factor L. (For ell >= 2 the first entry following L must be < the penultimate entry of L or else a consecutive 132 would occur.) The first sum counts ell = 1, the second ell = 2, the third ell >= 3; m is the penultimate entry of L and j is the first entry in the (reduced) subpermutation following L. Note that j is indexed from 0 to cover the case when L is the entire permutation.
Asymptotically, a(n)/n! ~ c/r^n where r = 1.2755477364172... is the unique positive root of Integrate[exp(-t^2/2), {t,0,r}] = 1 and c = exp(r^2/2)/r = 1.7685063678958....

			The first 3 entries of 2431 form a consecutive 132 pattern.
The 4!-a(4) = 8 permutations on [4] that DO contain a consecutive 132 pattern are 1243, 1324, 1423, 1432, 2143, 2431, 3142, 4132. Also, for example, 1342 contains a scattered 1-3-2 pattern but not a consecutive 132.

Ray Chandler, Table of n, a(n) for n = 0..200
A. Baxter, B. Nakamura, and D. Zeilberger. Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes
Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns, arXiv:math/0505254 [math.CO], 2005.
S. Elizalde and M. Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110-125.
M. E. Jones and J. B. Remmel, Pattern matching in the cycle structures of permutations, Pure Math. Appl. (PU.M.A.) 22 (2011), 173-208.

Cf. A049774, A197365, A324130, A324134.

Row m = 0 of A327722.

Clear[a]; a[0, 0] = a[0] = 1; a[n_, 0]/;n>=1 := 0; a[n_, k_]/;k>n := 0; a[n_, k_]/;1<=k<=n<=2 := 1; a[n_, k_]/;n>=3 := a[n, k] = Sum[a[n-1, j], {j, k-1}] + (n-k)Sum[a[n-2, j], {j, k-1}] + Sum[(n-m) Binomial[m-k-1, ell-3]a[n-ell, j], {ell, 3, n-k+1}, {m, k+ell-2, n-1}, {j, 0, m-ell+1}]; a[n_]/;n>=1 := a[n] = Sum[a[n, k], {k, n}]; Table[a[n], {n, 0, 15}]
(* or, faster *) ExpGfToList[f_, n_, x_] := CoefficientList[Normal[Series[f, {x, 0, n}]] /. x^(pwr_) -> pwr!*x^pwr, x]; ExpGfToList[1/( 1-(Pi/2)^(1/2)*Erf[z/2^(1/2)] ), 25, z]

E.g.f.: Sum_{n >= 0} a(n) x^n/n! = 1/( 1 - (Pi/2)^(1/2)*Erf(x/2^(1/2)) ).
a(n) = A197365(n,0). - Peter Bala, Oct 14 2011
From Sergei N. Gladkovskii, Nov 28 2011: (Start)
E.g.f.: A(x) = 1/( 1 - (Pi/2)^(1/2)*erf(x/2^(1/2)) ) = (1 + (x^3)/(2*(x-1)*W(0) -(x^2)))/(1 - x) with
W(k) = 2*(k^2) + (5 - 4*(x^2))*k + 3 - 2*(x^2) + 2*(x^2)*(k+1)*((2*k + 3)^2)/W(k+1) (continued fraction). (End)

A349799 Numbers k such that the k-th composition in standard order is weakly alternating but has at least two adjacent equal parts.

Original entry on oeis.org

3, 7, 10, 11, 14, 15, 19, 21, 23, 26, 27, 28, 29, 30, 31, 35, 36, 39, 42, 43, 47, 51, 55, 56, 57, 58, 59, 60, 61, 62, 63, 67, 71, 73, 74, 79, 83, 84, 85, 86, 87, 90, 91, 94, 95, 99, 100, 103, 106, 111, 112, 113, 114, 115, 118, 119, 120, 121, 122, 123, 124, 125

Offset: 1

Gus Wiseman, Dec 15 2021

nonn

We define a sequence to be weakly alternating if it is alternately weakly increasing and weakly decreasing, starting with either.
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.
This sequence ranks compositions that are weakly but not strongly alternating.

			The terms and corresponding compositions begin:
   3: (1,1)
   7: (1,1,1)
  10: (2,2)
  11: (2,1,1)
  14: (1,1,2)
  15: (1,1,1,1)
  19: (3,1,1)
  21: (2,2,1)
  23: (2,1,1,1)
  26: (1,2,2)
  27: (1,2,1,1)
  28: (1,1,3)
  29: (1,1,2,1)
  30: (1,1,1,2)
  31: (1,1,1,1,1)

Wikipedia, Alternating permutation

Partitions of this type are counted by A349795, ranked by A350137.
Permutations of prime indices of this type are counted by A349798.
These compositions are counted by A349800.
A001250 = alternating permutations, ranked by A349051, complement A348615.
A003242 = Carlitz (anti-run) compositions, ranked by A333489.
A025047/A025048/A025049 = alternating compositions, ranked by A345167.
A261983 = non-anti-run compositions, ranked by A348612.
A345164 = alternating permutations of prime indices, with twins A344606.
A345165 = partitions without an alternating permutation, ranked by A345171.
A345170 = partitions with an alternating permutation, ranked by A345172.
A345166 = separable partitions with no alternations, ranked by A345173.
A345192 = non-alternating compositions, ranked by A345168.
A345195 = non-alternating anti-run compositions, ranked by A345169.
A349052/A129852/A129853 = weakly alternating compositions.
A349053 = non-weakly alternating compositions, ranked by A349057.
A349056 = weak alternations of prime indices, complement A349797.
A349060 = weak alternations of partitions, complement A349061.
Cf. A005649, A049774, A096441, A128761, A344615, A345163, A349054, A349058, A349796, A349801, A350140.

stc[n_]:=Differences[Prepend[Join@@Position[ Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
whkQ[y_]:=And@@Table[If[EvenQ[m],y[[m]]<=y[[m+1]],y[[m]]>=y[[m+1]]],{m,1,Length[y]-1}];
Select[Range[0,100],(whkQ[stc[#]]||whkQ[-stc[#]])&&MatchQ[stc[#],{_,x_,x_,_}]&]

Equals A345168 \ A349057 = A348612 \ A349057.

A177533 Number of permutations of 1..n avoiding adjacent step pattern up, up, up, up, up.

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 719, 5027, 40168, 361080, 3606480, 39623760, 474915803, 6166512899, 86227808578, 1291868401830, 20645144452320, 350547210173280, 6302294420371031, 119600213982762899, 2389140113204434900, 50111866901959213980, 1101140993932295832120

Offset: 0

R. H. Hardin, May 10 2010

nonn

a(n) is the number of permutations of length n that avoid the consecutive pattern 123456 (or equivalently 654321).

Alois P. Heinz, Table of n, a(n) for n = 0..450 (terms n = 1..30 from Ray Chandler)
R. E. L. Aldred, M. D. Atkinson, D. J. McCaughan, Avoiding consecutive patterns in permutations Adv. in Appl. Math., 45(3), 449-461, 2010.
A. Baxter, B. Nakamura, and D. Zeilberger, Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes
Ira M. Gessel, Yan Zhuang, Counting permutations by alternating descents , arXiv:1408.1886 [math.CO], 2014. See displayed equation before Eq. (3), and set m=6. - _N. J. A. Sloane_, Aug 11 2014
Mingjia Yang, Doron Zeilberger, Increasing Consecutive Patterns in Words, arXiv:1805.06077 [math.CO], 2018.

Cf. A049774, A117158, A177523.

Column k=31 of A242784.

b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
      `if`(t<4, add(b(u+j-1, o-j, t+1), j=1..o), 0)+
      add(b(u-j, o+j-1, 0), j=1..u))
    end:
a:= n-> b(n, 0, 0):
seq(a(n), n=0..30);  # Alois P. Heinz, Oct 07 2013

Table[n!*SeriesCoefficient[1/(Sum[x^(6*k)/(6*k)!-x^(6*k+1)/(6*k+1)!,{k,0,n}]),{x,0,n}],{n,1,20}] (* Vaclav Kotesovec, Dec 11 2013 *)
Rest[CoefficientList[Series[3/(E^(x/2) * Cos[x*Sqrt[3]/2+Pi/3] + Sqrt[3] * E^(-x/2) * Cos[x*Sqrt[3]/2+Pi/6] + E^(-x)),{x,0,20}],x] * Range[0,20]!] (* Vaclav Kotesovec, Aug 23 2014 *)

a(n)/n! ~ 1.005827831279392186... * (1/r)^n, where r = 1.0011988273240623031887... is the root of the equation Sum_{n>=0} (r^(6*n)/(6*n)! - r^(6*n+1)/(6*n+1)!) = 0. - Vaclav Kotesovec, Dec 11 2013
Equivalently, a(n)/n! ~ c * (1/r)^n, where r = 1.00119882732406230318870210972855430833421618931012450844128... is the root of the equation 2 + exp(r/2) * (3 + exp(r)) * cos(sqrt(3)*r/2) = 2 * sqrt(3) * exp(r) * cosh(r/2) * sin(sqrt(3)*r/2), c = sqrt(3) / (2 * r * cosh(r/2) * sin(sqrt(3)*r/2)) = 1.0058278312793921866941324506580803251270892126827302878865925027445... . - Vaclav Kotesovec, Aug 23 2014
E.g.f. (Aldred, Atkinson, McCaughan, 2010): 3/(exp(x/2) * cos(x*sqrt(3)/2+Pi/3) + sqrt(3) * exp(-x/2) * cos(x*sqrt(3)/2+Pi/6) + exp(-x)). - Vaclav Kotesovec, Aug 23 2014

More terms from Ray Chandler, Dec 06 2011
Minor edits by Vaclav Kotesovec, Aug 29 2014
a(0)=1 prepended by Alois P. Heinz, Aug 08 2018

A350138 Number of non-weakly alternating patterns of length n.

Original entry on oeis.org

0, 0, 0, 2, 32, 338, 3560, 40058, 492664, 6647666, 98210192, 1581844994, 27642067000, 521491848218, 10572345303576, 229332715217954, 5301688511602448, 130152723055769810, 3381930236770946120, 92738693031618794378, 2676532576838728227352

Offset: 0

Gus Wiseman, Dec 24 2021

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.
We define a sequence to be weakly alternating if it is alternately weakly increasing and weakly decreasing, starting with either.
Conjecture: The directed cases, which count non-weakly up/down or non-weakly down/up patterns, are both equal to the strong case: A350252.

			The a(4) = 32 patterns:
  (1,1,2,3)  (2,1,1,2)  (3,1,1,2)  (4,1,2,3)
  (1,2,2,1)  (2,1,1,3)  (3,1,2,3)  (4,2,1,3)
  (1,2,3,1)  (2,1,2,3)  (3,1,2,4)  (4,3,1,2)
  (1,2,3,2)  (2,1,3,4)  (3,2,1,1)  (4,3,2,1)
  (1,2,3,3)  (2,3,2,1)  (3,2,1,2)
  (1,2,3,4)  (2,3,3,1)  (3,2,1,3)
  (1,2,4,3)  (2,3,4,1)  (3,2,1,4)
  (1,3,2,1)  (2,4,3,1)  (3,3,2,1)
  (1,3,3,2)             (3,4,2,1)
  (1,3,4,2)
  (1,4,3,2)

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

The unordered version is A274230, complement A052955.
The strong case of compositions is A345192, ranked by A345168.
The strict case is A348615, complement A001250.
For compositions we have A349053, complement A349052, ranked by A349057.
The complement is counted by A349058.
The version for partitions is A349061, complement A349060.
The version for permutations of prime indices: A349797, complement A349056.
The version for ordered factorizations is A350139, complement A349059.
The strong case is A350252, complement A345194. Also the directed case?
A003242 = Carlitz compositions, complement A261983, ranked by A333489.
A005649 = anti-run patterns, complement A069321.
A025047/A129852/A129853 = alternating compositions, ranked by A345167.
A345163 = normal partitions w/ alternating permutation, complement A345162.
A345170 = partitions w/ alternating permutation, complement A345165.
A349055 = normal multisets w/ alternating permutation, complement A349050.
Cf. A049774, A096441, A336103, A344605, A344614, A344615, A344740, A348610, A349794.

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

R(n,k)={my(v=vector(k,i,1), u=vector(n)); for(r=1, n, if(r%2==0, my(s=v[k]); forstep(i=k, 2, -1, v[i] = s - v[i-1]); v[1] = s); for(i=2, k, v[i] += v[i-1]); u[r]=v[k]); u}
seq(n)= {concat([0], vector(n,i,1) + sum(k=1, n, (vector(n,i,k^i) - 2*R(n, k))*sum(r=k, n, binomial(r, k)*(-1)^(r-k)) ) )} \\ Andrew Howroyd, Jan 13 2024

a(n) = A000670(n) - A349058(n).

a(9) onwards from Andrew Howroyd, Jan 13 2024

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

Original entry on oeis.org

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

A206817 Sum_{0

Original entry on oeis.org

1, 10, 73, 520, 3967, 33334, 309661, 3166468, 35416555, 430546642, 5655609529, 79856902816, 1206424711303, 19419937594990, 331860183278677, 6000534640290364, 114462875817046051, 2297294297649673738, 48394006967070653425

Offset: 2

Clark Kimberling, Feb 12 2012

nonn

In the following guide to related sequences,

c(n) = Sum_{0

t(n) = Sum_{0

s(k).................c(n)........t(n)

k....................A000217.....A000292

k^2..................A016061.....A004320

k^3..................A206808.....A206809

k^4..................A206810.....A206811

k!...................A206816.....A206817

prime(k).............A152535.....A062020

prime(k+1)...........A185382.....A206803

2^(k-1)..............A000337.....A045618

k(k+1)/2.............A007290.....A034827

k-th quarter-square..A049774.....A206806

			a(3) = (2-1) + (6-1) + (6-2) = 10.

Danny Rorabaugh, Table of n, a(n) for n = 2..400

Cf. A000142, A206816.

s[k_] := k!; t[1] = 0;
p[n_] := Sum[s[k], {k, 1, n}];
c[n_] := n*s[n] - p[n];
t[n_] := t[n - 1] + (n - 1) s[n] - p[n - 1];
Table[c[n], {n, 2, 32}]          (* A206816 *)
Flatten[Table[t[n], {n, 2, 20}]] (* A206817 *)

a(n)=sum(j=1,n,j!*(2*j-n-1)) \\ Charles R Greathouse IV, Oct 11 2015

a(n)=my(t=1); sum(j=1,n,t*=j; t*(2*j-n-1)) \\ Charles R Greathouse IV, Oct 11 2015

[sum([sum([factorial(k)-factorial(j) for j in range(1,k)]) for k in range(2,n+1)]) for n in range(2,21)] # Danny Rorabaugh, Apr 18 2015

a(n) = a(n-1)+(n-1)s(n)-p(n-1), where s(n) = n! and p(k) = 1!+2!+...+k!.

a(n) = Sum_{k=2..n} A206816(k).

A230051 Number of permutations of [n] avoiding adjacent step pattern {up}^7.

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 720, 5040, 40319, 362863, 3628550, 39913170, 478947480, 6226179960, 87164597520, 1307440134000, 20918580896069, 355608034188517, 6400803479701178, 121612584595293870, 2432198062707745560, 51075033128533094520, 1123625953230764250960

Offset: 0

Alois P. Heinz, Oct 07 2013

nonn

			a(8) = 40319 = 8!-1: only permutation 12345678 does not avoid {up}^7.

R. E. L. Aldred, M. D. Atkinson, D. J. McCaughan, Avoiding consecutive patterns in permutations. Adv. in Appl. Math., 45(3), 449-461, 2010.

Alois P. Heinz, Table of n, a(n) for n = 0..450
Alin Bostan, Andrew Elvey Price, Anthony John Guttmann, Jean-Marie Maillard, Stieltjes moment sequences for pattern-avoiding permutations, arXiv:2001.00393 [math.CO], 2020.
Mingjia Yang, Doron Zeilberger, Increasing Consecutive Patterns in Words, arXiv:1805.06077 [math.CO], 2018.

Cf. A049774, A117158, A177523, A177533, A177553.

Column k=127 of A242784.

b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
      `if`(t<6, add(b(u+j-1, o-j, t+1), j=1..o), 0)+
      add(b(u-j, o+j-1, 0), j=1..u))
    end:
a:= n-> b(n, 0, 0):
seq(a(n), n=0..30);

nn=20;r=7;a=Apply[Plus,Table[Normal[Series[y x^(r+1)/(1-Sum[y x^i,{i,1,r}]),{x,0,nn}]][[n]]/(n+r)!,{n,1,nn-r}]]/.y->-1;Range[0,nn]! CoefficientList[Series[1/(1-x-a),{x,0,nn}],x] (* Geoffrey Critzer, Feb 25 2014 *)
CoefficientList[Series[4/(E^(-x) + Cos[x] - Sin[x] + 2*Cos[x/Sqrt[2]] * Cosh[x/Sqrt[2]] - Sqrt[2] * Cos[x/Sqrt[2]] * Sinh[x/Sqrt[2]] - Sqrt[2] * Cosh[x/Sqrt[2]] * Sin[x/Sqrt[2]]),{x,0,20}],x] * Range[0,20]! (* Vaclav Kotesovec, Aug 23 2014 *)

E.g.f.: 1 / Sum_{n>=0} (8*n+1-x)*x^(8*n)/(8*n+1)!.
E.g.f. (Aldred, Atkinson, McCaughan, 2010): 4/(exp(-x) + cos(x) - sin(x) + 2*cos(x/sqrt(2))*cosh(x/sqrt(2)) - sqrt(2)*cos(x/sqrt(2))*sinh(x/sqrt(2)) - sqrt(2)*cosh(x/sqrt(2))*sin(x/sqrt(2))). - Vaclav Kotesovec, Aug 23 2014
a(n)/n! ~ c / r^n, where r = 1.0000220496837836995332841475679738951237308817759821845322... is the root of the equation exp(-r) + cos(r) - sin(r) + 2*cos(r/sqrt(2)) * cosh(r/sqrt(2)) - sqrt(2)*cos(r/sqrt(2)) * sinh(r/sqrt(2)) - sqrt(2) * cosh(r/sqrt(2)) * sin(r/sqrt(2)) = 0, c = 2*sqrt(2) / (r*sqrt(2 + cosh(sqrt(2)*r) - cos(2*r) + 2*cosh(r/sqrt(2)) * (2*sqrt(2)*sin(r) * sin(r/sqrt(2)) - cos(sqrt(2)*r) * cosh(r/sqrt(2))))) = 1.0001516144914746839400607922657094772985420791612537... . - Vaclav Kotesovec, Aug 23 2014, updated Feb 01 2015

Previous Showing 21-30 of 57 results. Next

cp's OEIS Frontend

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

A349058 Number of weakly alternating patterns of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A350252 Number of non-alternating patterns of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A111004 Number of permutations avoiding a consecutive 132 pattern.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A349799 Numbers k such that the k-th composition in standard order is weakly alternating but has at least two adjacent equal parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A177533 Number of permutations of 1..n avoiding adjacent step pattern up, up, up, up, up.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A350138 Number of non-weakly alternating patterns of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula