A345163 -id:A345163 - cp's OEIS frontend

A350252 Number of non-alternating patterns of length n.

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

A349051 Numbers k such that the k-th composition in standard order is an alternating permutation of {1..k} for some k.

Original entry on oeis.org

0, 1, 5, 6, 38, 41, 44, 50, 553, 562, 582, 593, 610, 652, 664, 708, 788, 808, 16966, 17036, 17048, 17172, 17192, 17449, 17458, 17542, 17676, 17712, 17940, 18000, 18513, 18530, 18593, 18626, 18968, 18992, 19496, 19536, 20625, 20676, 20769, 20868, 21256, 22600

Offset: 1

Gus Wiseman, Nov 08 2021

nonn

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.

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).

			The sequence together with the corresponding compositions begins:
        0: ()
        1: (1)
        5: (2,1)
        6: (1,2)
       38: (3,1,2)
       41: (2,3,1)
       44: (2,1,3)
       50: (1,3,2)
      553: (4,2,3,1)
      562: (4,1,3,2)
      582: (3,4,1,2)
      593: (3,2,4,1)
      610: (3,1,4,2)
      652: (2,4,1,3)
      664: (2,3,1,4)
      708: (2,1,4,3)
      788: (1,4,2,3)
      808: (1,3,2,4)
    16966: (5,3,4,1,2)
    17036: (5,2,4,1,3)

Wikipedia, Alternating permutation

These permutations are counted by A001250, complement A348615.
Compositions of this type are counted by A025047, complement A345192.
Subset of A333218, which ranks permutations of initial intervals.
Subset of A345167, which ranks alternating compositions, complement A345168.
A003242 counts Carlitz (anti-run) compositions.
A345163 counts normal partitions with an alternating permutation.
A345164 counts alternating permutations of prime indices.
A345170 counts partitions with an alternating permutation.
Compositions in standard order are the rows of A066099:
- Number of parts is given by A000120, distinct A334028.
- Sum and product of parts are given by A070939 and A124758.
- Maximum and minimum parts are given by A333766 and A333768.
- GCD and LCM are given by A326674 and A333226.
- Maximal runs and anti-runs are counted by A124767 and A333381.
- Heinz number is given by A333219.
- Runs-resistance is given by A333628.
- Partitions and strict partitions are ranked by A114994 and A333256.
- Multisets and sets are ranked by A225620 and A333255.
- Strict and constant compositions are ranked by A233564 and A272919.
- Carlitz (anti-run) compositions are ranked by A333489.
Cf. A025048, A025049, A344604, A344615, A344653, A344742, A348377, A348379, A345165.

stc[n_]:=Differences[Prepend[Join@@Position[ Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
wigQ[y_]:=Or[Length[y]==0,Length[Split[y]]== Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1];
Select[Range[0,1000],Sort[stc[#]]==Range[Length[stc[#]]]&&wigQ[stc[#]]&]

Equals A333218 (permutation) /\ A345167 (alternating).

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.

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

A349801 Number of integer partitions of n into three or more parts or into two equal parts.

Original entry on oeis.org

0, 0, 1, 1, 3, 4, 8, 11, 18, 25, 37, 50, 71, 94, 128, 168, 223, 288, 376, 480, 617, 781, 991, 1243, 1563, 1945, 2423, 2996, 3704, 4550, 5589, 6826, 8333, 10126, 12293, 14865, 17959, 21618, 25996, 31165, 37318, 44562, 53153, 63239, 75153, 89111, 105535, 124730

Offset: 0

Gus Wiseman, Dec 23 2021

nonn

This sequence arose as the following degenerate case. If we define a sequence to be alternating if it is alternately strictly increasing and strictly decreasing, starting with either, then a(n) is the number of non-alternating integer partitions of n. Under this interpretation:
- The non-strict case is A047967, weak A349796, weak complement A349795.
- The complement is counted by A065033(n) = ceiling(n/2) for n > 0.
- These partitions are ranked by A289553 \ {1}, complement A167171 \/ {1}.
- The version for compositions is A345192, ranked by A345168.
- The weak version for compositions is A349053, ranked by A349057.
- The weak version is A349061, complement A349060, ranked by A349794.

			The a(2) = 1 through a(7) = 11 partitions:
  (11)  (111)  (22)    (221)    (33)      (322)
               (211)   (311)    (222)     (331)
               (1111)  (2111)   (321)     (421)
                       (11111)  (411)     (511)
                                (2211)    (2221)
                                (3111)    (3211)
                                (21111)   (4111)
                                (111111)  (22111)
                                          (31111)
                                          (211111)
                                          (1111111)

A000041 counts partitions, ordered A011782.
A001250 counts alternating permutations, complement A348615.
A004250 counts partitions into three or more parts, strict A347548.
A025047/A025048/A025049 count alternating compositions, ranked by A345167.
A096441 counts weakly alternating 0-appended partitions.
A345165 counts partitions w/ no alternating permutation, complement A345170.
Cf. A000070, A001700, A002865, A117298, A117989, A102726, A128761, A345162, A345163, A345166, A349798.

Table[Length[Select[IntegerPartitions[n],MatchQ[#,{x_,x_}|{,,__}]&]],{n,0,10}]

a(1) = 0; a(n > 0) = A000041(n) - ceiling(n/2).

A350250 Numbers k such that the k-th composition in standard order is a non-alternating permutation of an initial interval of positive integers.

Original entry on oeis.org

37, 52, 549, 550, 556, 564, 581, 600, 616, 649, 657, 712, 786, 802, 836, 840, 16933, 16934, 16937, 16940, 16946, 16948, 16965, 16977, 16984, 16994, 17000, 17033, 17041, 17092, 17096, 17170, 17186, 17220, 17224, 17445, 17446, 17452, 17460, 17541, 17569, 17584

Offset: 1

Gus Wiseman, Jan 13 2022

nonn

A sequence is alternating if it is alternately strictly increasing and strictly decreasing, starting with either.

			The terms and corresponding permutations begin:
     37: (3,2,1)
     52: (1,2,3)
    549: (4,3,2,1)
    550: (4,3,1,2)
    556: (4,2,1,3)
    564: (4,1,2,3)
    581: (3,4,2,1)
    600: (3,2,1,4)
    616: (3,1,2,4)
    649: (2,4,3,1)
    657: (2,3,4,1)
    712: (2,1,3,4)
    786: (1,4,3,2)
    802: (1,3,4,2)
    836: (1,2,4,3)
    840: (1,2,3,4)
  16933: (5,4,3,2,1)

This is the non-alternating case of A333218.
This is the restriction of A345168 to permutations, complement A345167.
These partitions are counted by A348615, complement A001250.
A003242 counts anti-run compositions, patterns A005649.
A025047 counts alternating compositions, directed A025048/A025049.
A345192 counts non-alternating compositions.
A345194 counts alternating patterns, complement A350252.
Statistics of standard compositions:
- Length is A000120.
- Sum is A070939.
- Heinz number is A333219.
- Number of maximal anti-runs is A333381.
- Number of distinct parts is A334028.
Classes of standard compositions:
- Weakly decreasing compositions (partitions) are A114994, strict A333256.
- Weakly increasing compositions (multisets) are A225620, strict A333255.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Anti-run compositions are A333489, complement A348612.
Cf. A008965, A059893, A164894, A246534, A333217, A344605, A345162, A350251, A345163, A345171, A345172, A348613.

stc[n_]:=Differences[Prepend[Join@@Position[ Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
wigQ[y_]:=Or[Length[y]==0, Length[Split[y]]==Length[y] &&Length[Split[Sign[Differences[y]]]]==Length[y]-1];
Select[Range[0,1000],(Sort[stc[#]]==Range[Length[stc[#]]]&&!wigQ[stc[#]])&]

cp's OEIS Frontend

A350252 Number of non-alternating patterns of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A349051 Numbers k such that the k-th composition in standard order is an alternating permutation of {1..k} for some k.

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A349801 Number of integer partitions of n into three or more parts or into two equal parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A350250 Numbers k such that the k-th composition in standard order is a non-alternating permutation of an initial interval of positive integers.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica