A345169 -id:A345169 - cp's OEIS frontend

A025047 Number of alternating compositions, i.e., compositions with alternating increases and decreases, starting with either an increase or a decrease.

1, 1, 1, 3, 4, 7, 12, 19, 29, 48, 75, 118, 186, 293, 460, 725, 1139, 1789, 2814, 4422, 6949, 10924, 17168, 26979, 42404, 66644, 104737, 164610, 258707, 406588, 639009, 1004287, 1578363, 2480606, 3898599, 6127152, 9629623, 15134213, 23785388, 37381849, 58750468

Offset: 0

David W. Wilson

nonn

Original name: Wiggly sums: number of sums adding to n in which terms alternately increase and decrease or vice versa.

			From _Joerg Arndt_, Dec 28 2012: (Start)
There are a(7)=19 such compositions of 7:
[ 1] +  [ 1 2 1 2 1 ]
[ 2] +  [ 1 2 1 3 ]
[ 3] +  [ 1 3 1 2 ]
[ 4] +  [ 1 4 2 ]
[ 5] +  [ 1 5 1 ]
[ 6] +  [ 1 6 ]
[ 7] -  [ 2 1 3 1 ]
[ 8] -  [ 2 1 4 ]
[ 9] +  [ 2 3 2 ]
[10] +  [ 2 4 1 ]
[11] +  [ 2 5 ]
[12] -  [ 3 1 2 1 ]
[13] -  [ 3 1 3 ]
[14] +  [ 3 4 ]
[15] -  [ 4 1 2 ]
[16] -  [ 4 3 ]
[17] -  [ 5 2 ]
[18] -  [ 6 1 ]
[19] 0  [ 7 ]
For A025048(7)-1=10 of these the first two parts are increasing (marked by '+'),
and for A025049(7)-1=8 the first two parts are decreasing (marked by '-').
The composition into one part is counted by both A025048 and A025049.
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..3333
Edward A. Bender and E. Rodney Canfield, Locally Restricted Compositions III. Adjacent-Part Periodic Inequalities, Electronic Journal of Combinatorics 17 (2010), #R145.

Dominated by A003242 (anti-run compositions), complement A261983.
The ascending case is A025048.
The descending case is A025049.
The version allowing pairs (x,x) is A344604.
These compositions are ranked by A345167, permutations A349051.
The complement is counted by A345192, ranked by A345168.
The version for patterns is A345194 (with twins: A344605).
A001250 counts alternating permutations, complement A348615.
A011782 counts compositions.
A032020 counts strict compositions.
A106356 counts compositions by number of maximal anti-runs.
A114901 counts compositions where each part is adjacent to an equal part.
A274174 counts compositions with equal parts contiguous.
A325534 counts separable partitions, ranked by A335433.
A325535 counts inseparable partitions, ranked by A335448.
A345164 counts alternating permutations of prime indices.
A345165 counts partitions w/o alternating permutation, ranked by A345171.
A345170 counts partitions w/ alternating permutation, ranked by A345172.
Cf. A000070, A008965, A238279, A333755, A344606, A344614, A344653, A344740, A345163, A345166, A345169.

b:= proc(n, l, t) option remember; `if`(n=0, 1, add(
      b(n-j, j, 1-t), j=`if`(t=1, 1..min(l-1, n), l+1..n)))
    end:
a:= n-> 1+add(add(b(n-j, j, i), i=0..1), j=1..n-1):
seq(a(n), n=0..40);  # Alois P. Heinz, Jan 31 2024

wigQ[y_]:=Or[Length[y]==0,Length[Split[y]]== Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],wigQ]],{n,0,15}] (* Gus Wiseman, Jun 17 2021 *)

D(n,f)={my(M=matrix(n,n,j,k,k>=j), s=M[,n]); for(b=1, n, f=!f; M=matrix(n,n,j,k,if(k1, M[j-k,k-1]), M[j-k,n]-M[j-k,k] ))); for(k=2, n, M[,k]+=M[,k-1]); s+=M[,n]); s~}
seq(n) = concat([1], D(n,0) + D(n,1) - vector(n,j,1)) \\ Andrew Howroyd, Jan 31 2024

a(n) = A025048(n) + A025049(n) - 1 = sum_k[A059881(n, k)] = sum_k[S(n, k) + T(n, k)] - 1 where if n>k>0 S(n, k) = sum_j[T(n - k, j)] over j>k and T(n, k) = sum_j[S(n - k, j)] over k>j (note reversal) and if n>0 S(n, n) = T(n, n) = 1; S(n, k) = A059882(n, k), T(n, k) = A059883(n, k). - Henry Bottomley, Feb 05 2001
a(n) ~ c * d^n, where d = 1.571630806607064114100138865739690782401305155950789062725..., c = 0.82222360450823867604750473815253345888526601460811483897... . - Vaclav Kotesovec, Sep 12 2014
a(n) = A344604(n) + 1 - n mod 2. - Gus Wiseman, Jun 17 2021

Better name using a comment of Franklin T. Adams-Watters by Peter Luschny, Oct 31 2021

A345167 Numbers k such that the k-th composition in standard order is alternating.

Original entry on oeis.org

0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 16, 17, 18, 20, 22, 24, 25, 32, 33, 34, 38, 40, 41, 44, 45, 48, 49, 50, 54, 64, 65, 66, 68, 70, 72, 76, 77, 80, 81, 82, 88, 89, 96, 97, 98, 102, 108, 109, 128, 129, 130, 132, 134, 140, 141, 144, 145, 148, 152, 153, 160, 161, 162

Offset: 1

Gus Wiseman, Jun 15 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 terms together with their binary indices begin:
      1: (1)         25: (1,3,1)       66: (5,2)
      2: (2)         32: (6)           68: (4,3)
      4: (3)         33: (5,1)         70: (4,1,2)
      5: (2,1)       34: (4,2)         72: (3,4)
      6: (1,2)       38: (3,1,2)       76: (3,1,3)
      8: (4)         40: (2,4)         77: (3,1,2,1)
      9: (3,1)       41: (2,3,1)       80: (2,5)
     12: (1,3)       44: (2,1,3)       81: (2,4,1)
     13: (1,2,1)     45: (2,1,2,1)     82: (2,3,2)
     16: (5)         48: (1,5)         88: (2,1,4)
     17: (4,1)       49: (1,4,1)       89: (2,1,3,1)
     18: (3,2)       50: (1,3,2)       96: (1,6)
     20: (2,3)       54: (1,2,1,2)     97: (1,5,1)
     22: (2,1,2)     64: (7)           98: (1,4,2)
     24: (1,4)       65: (6,1)        102: (1,3,1,2)

Wikipedia, Alternating permutation

These compositions are counted by A025047, complement A345192.
The complement is A345168.
Partitions with a permutation of this type: A345170, complement A345165.
Factorizations with a permutation of this type: A348379.
A001250 counts alternating permutations, complement A348615.
A003242 counts anti-run compositions.
A345164 counts alternating permutations of prime indices.
A345194 counts alternating patterns, with twins A344605.
Statistics of standard compositions:
- Length is A000120.
- Constant runs are A124767.
- Heinz number is A333219.
- Number of maximal anti-runs is A333381.
- Runs-resistance is A333628.
- Number of distinct parts is A334028.
Classes of standard compositions:
- Weakly decreasing compositions (partitions) are A114994.
- Weakly increasing compositions (multisets) are A225620.
- Anti-runs are A333489.
- Non-alternating anti-runs are A345169.
Cf. A025048, A025049, A059893, A106356, A238279, A335448, A344604, A344615, A344653, A344742, A345163, A348377.

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,100],wigQ@*stc]

A345192 Number of non-alternating compositions of n.

Original entry on oeis.org

0, 0, 1, 1, 4, 9, 20, 45, 99, 208, 437, 906, 1862, 3803, 7732, 15659, 31629, 63747, 128258, 257722, 517339, 1037652, 2079984, 4167325, 8346204, 16710572, 33449695, 66944254, 133959021, 268028868, 536231903, 1072737537, 2145905285, 4292486690, 8586035993, 17173742032, 34350108745, 68704342523, 137415168084

Offset: 0

Gus Wiseman, Jun 17 2021

nonn

First differs from A261983 at a(6) = 20, A261983(6) = 18.

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 a(2) = 1 through a(6) = 20 compositions:
  (11)  (111)  (22)    (113)    (33)
               (112)   (122)    (114)
               (211)   (221)    (123)
               (1111)  (311)    (222)
                       (1112)   (321)
                       (1121)   (411)
                       (1211)   (1113)
                       (2111)   (1122)
                       (11111)  (1131)
                                (1221)
                                (1311)
                                (2112)
                                (2211)
                                (3111)
                                (11112)
                                (11121)
                                (11211)
                                (12111)
                                (21111)
                                (111111)

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

The complement is counted by A025047 (ascend: A025048, descend: A025049).
Dominates A261983 (non-anti-run compositions), ranked by A348612.
These compositions are ranked by A345168, complement A345167.
The case without twins is A348377.
The version for factorizations is A348613.
A001250 counts alternating permutations, complement A348615.
A003242 counts anti-run compositions.
A011782 counts compositions.
A032020 counts strict compositions.
A106356 counts compositions by number of maximal anti-runs.
A114901 counts compositions where each part is adjacent to an equal part.
A274174 counts compositions with equal parts contiguous.
A325534 counts separable partitions, ranked by A335433.
A325535 counts inseparable partitions, ranked by A335448.
A344604 counts alternating compositions with twins.
A344605 counts alternating patterns with twins.
A344654 counts non-twin partitions with no alternating permutation.
A345162 counts normal partitions with no alternating permutation.
A345164 counts alternating permutations of prime indices.
A345170 counts partitions w/ alternating permutation, ranked by A345172.
A345165 counts partitions w/o alternating permutation, ranked by A345171.
Patterns:
- A128761 avoiding (1,2,3) adjacent.
- A344614 avoiding (1,2,3) and (3,2,1) adjacent.
- A344615 weakly avoiding (1,2,3) adjacent.
Cf. A000070, A008965, A178470, A238279, A333755, A335126, A344606, A344653, A344740, A345163, A345166, A345169, A345173, A348380.

wigQ[y_]:=Or[Length[y]==0,Length[Split[y]]== Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!wigQ[#]&]],{n,0,15}]

a(n) = A011782(n) - A025047(n).

A344654 Number of integer partitions of n of which every permutation has a consecutive monotone triple, i.e., a triple (..., x, y, z, ...) such that either x <= y <= z or x >= y >= z.

Original entry on oeis.org

0, 0, 0, 1, 1, 2, 4, 5, 7, 11, 16, 20, 28, 37, 50, 65, 84, 106, 140, 175, 222, 277, 350, 432, 539, 663, 819, 999, 1225, 1489, 1816, 2192, 2653, 3191, 3846, 4603, 5516, 6578, 7852, 9327, 11083, 13120, 15532, 18328, 21620, 25430, 29904, 35071, 41110, 48080

Offset: 0

Gus Wiseman, Jun 12 2021

nonn

Such a permutation is characterized by being neither a twin (x,x) nor wiggly (A025047, A345192). A sequence is wiggly if it is alternately strictly increasing and strictly decreasing, starting with either. For example, the partition (3,3,2,2,2,2,1) has no wiggly permutations, even though it has the anti-run permutations (2,3,2,3,2,1,2), (2,3,2,1,2,3,2), and (2,1,2,3,2,3,2).

			The a(3) = 1 through a(9) = 11 partitions:
  (111)  (1111)  (2111)   (222)     (2221)     (2222)      (333)
                 (11111)  (3111)    (4111)     (5111)      (3222)
                          (21111)   (31111)    (41111)     (6111)
                          (111111)  (211111)   (221111)    (22221)
                                    (1111111)  (311111)    (51111)
                                               (2111111)   (321111)
                                               (11111111)  (411111)
                                                           (2211111)
                                                           (3111111)
                                                           (21111111)
                                                           (111111111)

Joseph Likar, Table of n, a(n) for n = 0..1000

The Heinz numbers of these partitions are A344653, complement A344742.
The complement is counted by A344740.
The normal case starts 0, 0, 0, then becomes A345162, complement A345163.
Allowing twins (x,x) gives A345165, ranked by A345171.
A001250 counts wiggly permutations.
A003242 counts anti-run compositions.
A025047 counts wiggly compositions (ascend: A025048, descend: A025049).
A325534 counts separable partitions, ranked by A335433.
A325535 counts inseparable partitions, ranked by A335448.
A344604 counts wiggly compositions with twins.
A344605 counts wiggly patterns with twins.
A344606 counts wiggly permutations of prime indices with twins.
A344614 counts compositions with no consecutive strictly monotone triple.
A345164 counts wiggly permutations of prime indices.
A345170 counts partitions with a wiggly permutation, ranked by A345172.
A345192 counts non-wiggly compositions.
Cf. A000041, A000070, A102726, A103919, A333489, A335126, A344607, A344615, A345166, A345168, A345169.

Table[Length[Select[IntegerPartitions[n],Select[Permutations[#],!MatchQ[#,{_,x_,y_,z_,_}/;x<=y<=z||x>=y>=z]&]=={}&]],{n,15}]

a(26)-a(32) from Robert Price, Jun 22 2021

a(33) onwards from Joseph Likar, Sep 06 2023

A345165 Number of integer partitions of n without an alternating permutation.

Original entry on oeis.org

0, 0, 1, 1, 2, 2, 5, 5, 8, 11, 17, 20, 29, 37, 51, 65, 85, 106, 141, 175, 223, 277, 351, 432, 540, 663, 820, 999, 1226, 1489, 1817, 2192, 2654, 3191, 3847, 4603, 5517, 6578, 7853, 9327, 11084, 13120, 15533, 18328, 21621, 25430, 29905, 35071, 41111, 48080, 56206, 65554, 76420, 88918

Offset: 0

Gus Wiseman, Jun 12 2021

nonn

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 has the anti-run permutations (2,3,2,1,2) and (2,1,2,3,2).

			The a(2) = 1 through a(9) = 11 partitions:
  (11)  (111)  (22)    (2111)   (33)      (2221)     (44)        (333)
               (1111)  (11111)  (222)     (4111)     (2222)      (3222)
                                (3111)    (31111)    (5111)      (6111)
                                (21111)   (211111)   (41111)     (22221)
                                (111111)  (1111111)  (221111)    (51111)
                                                     (311111)    (321111)
                                                     (2111111)   (411111)
                                                     (11111111)  (2211111)
                                                                 (3111111)
                                                                 (21111111)
                                                                 (111111111)

Joseph Likar, Table of n, a(n) for n = 0..1000
Joseph Likar, Java Implementation using QBinomials

Excluding twins (x,x) gives A344654, complement A344740.
The normal case is A345162, complement A345163.
The complement is counted by A345170, ranked by A345172.
The Heinz numbers of these partitions are A345171.
The version for factorizations is A348380, complement A348379.
A version for ordered factorizations is A348613, complement A348610.
A000041 counts integer partitions.
A001250 counts alternating permutations, complement A348615.
A003242 counts anti-run compositions.
A005649 counts anti-run patterns.
A025047 counts alternating or wiggly compositions.
A325534 counts separable partitions, ranked by A335433.
A325535 counts inseparable partitions, ranked by A335448.
A344604 counts alternating compositions with twins.
A345164 counts alternating permutations of prime indices, w/ twins A344606.
A345192 counts non-alternating compositions, without twins A348377.
Cf. A000070, A025048, A025049, A103919, A335126, A344605, A344607, A344615, A344653, A345166, A345167, A345168, A345169, A347706, A348609.

wigQ[y_]:=Or[Length[y]==0,Length[Split[y]]== Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1];
Table[Length[Select[IntegerPartitions[n],Select[Permutations[#],wigQ]=={}&]],{n,0,15}]

a(26) onwards by Joseph Likar, Aug 21 2023

A345168 Numbers k such that the k-th composition in standard order is not alternating.

Original entry on oeis.org

3, 7, 10, 11, 14, 15, 19, 21, 23, 26, 27, 28, 29, 30, 31, 35, 36, 37, 39, 42, 43, 46, 47, 51, 52, 53, 55, 56, 57, 58, 59, 60, 61, 62, 63, 67, 69, 71, 73, 74, 75, 78, 79, 83, 84, 85, 86, 87, 90, 91, 92, 93, 94, 95, 99, 100, 101, 103, 104, 105, 106, 107, 110

Offset: 1

Gus Wiseman, Jun 15 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 of terms together with their binary indices begins:
     3: (1,1)          35: (4,1,1)        59: (1,1,2,1,1)
     7: (1,1,1)        36: (3,3)          60: (1,1,1,3)
    10: (2,2)          37: (3,2,1)        61: (1,1,1,2,1)
    11: (2,1,1)        39: (3,1,1,1)      62: (1,1,1,1,2)
    14: (1,1,2)        42: (2,2,2)        63: (1,1,1,1,1,1)
    15: (1,1,1,1)      43: (2,2,1,1)      67: (5,1,1)
    19: (3,1,1)        46: (2,1,1,2)      69: (4,2,1)
    21: (2,2,1)        47: (2,1,1,1,1)    71: (4,1,1,1)
    23: (2,1,1,1)      51: (1,3,1,1)      73: (3,3,1)
    26: (1,2,2)        52: (1,2,3)        74: (3,2,2)
    27: (1,2,1,1)      53: (1,2,2,1)      75: (3,2,1,1)
    28: (1,1,3)        55: (1,2,1,1,1)    78: (3,1,1,2)
    29: (1,1,2,1)      56: (1,1,4)        79: (3,1,1,1,1)
    30: (1,1,1,2)      57: (1,1,3,1)      83: (2,3,1,1)
    31: (1,1,1,1,1)    58: (1,1,2,2)      84: (2,2,3)

Wikipedia, Alternating permutation

The complement is A345167.
These compositions are counted by A345192.
A001250 counts alternating permutations, complement A348615.
A003242 counts anti-run compositions.
A025047 counts alternating or wiggly compositions, directed A025048, A025049.
A344604 counts alternating compositions with twins.
A345194 counts alternating patterns (with twins: A344605).
A345164 counts alternating permutations of prime indices (with twins: A344606).
A345165 counts partitions without a alternating permutation, ranked by A345171.
A345170 counts partitions with a alternating permutation, ranked by A345172.
A348610 counts alternating ordered factorizations, complement A348613.
Statistics of standard compositions:
- Length is A000120.
- Constant runs are A124767.
- Heinz number is A333219.
- Number of maximal anti-runs is A333381.
- Runs-resistance is A333628.
- Number of distinct parts is A334028.
Classes of standard compositions:
- Weakly decreasing compositions (partitions) are A114994.
- Weakly increasing compositions (multisets) are A225620.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Anti-run compositions are A333489.
- Non-anti-run compositions are A348612.
Cf. A001222, A005649, A008965, A059893, A106356, A238279, A344615, A345162, A345163, A345166, A345169, A348377, A348380.

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,100],Not@*wigQ@*stc]

A344740 Number of integer partitions of n with a permutation that has no consecutive monotone triple, i.e., no triple (..., x, y, z, ...) such that either x <= y <= z or x >= y >= z.

Original entry on oeis.org

1, 1, 2, 2, 4, 5, 7, 10, 15, 19, 26, 36, 49, 64, 85, 111, 147, 191, 245, 315, 405, 515, 652, 823, 1036, 1295, 1617, 2011, 2493, 3076, 3788, 4650, 5696, 6952, 8464, 10280, 12461, 15059, 18163, 21858, 26255, 31463, 37642, 44933, 53555, 63704, 75654, 89683, 106163, 125445, 148021

Offset: 0

Gus Wiseman, Jun 12 2021

nonn

These partitions are characterized by either being a twin (x,x) or having a wiggly permutation. A sequence is wiggly if it is alternately strictly increasing and strictly decreasing, starting with either. For example, the partition (3,2,2,2,1) has no wiggly permutations, even though it has anti-run permutations (2,3,2,1,2) and (2,1,2,3,2).

			The a(1) = 1 through a(8) = 15 partitions:
  (1)  (2)    (3)    (4)      (5)      (6)        (7)          (8)
       (1,1)  (2,1)  (2,2)    (3,2)    (3,3)      (4,3)        (4,4)
                     (3,1)    (4,1)    (4,2)      (5,2)        (5,3)
                     (2,1,1)  (2,2,1)  (5,1)      (6,1)        (6,2)
                              (3,1,1)  (3,2,1)    (3,2,2)      (7,1)
                                       (4,1,1)    (3,3,1)      (3,3,2)
                                       (2,2,1,1)  (4,2,1)      (4,2,2)
                                                  (5,1,1)      (4,3,1)
                                                  (3,2,1,1)    (5,2,1)
                                                  (2,2,1,1,1)  (6,1,1)
                                                               (3,2,2,1)
                                                               (3,3,1,1)
                                                               (4,2,1,1)
                                                               (2,2,2,1,1)
                                                               (3,2,1,1,1)
For example, the partition (3,2,2,1) has the two wiggly permutations (2,3,1,2) and (2,1,3,2), so is counted under a(8).

Joseph Likar, Table of n, a(n) for n = 0..1000

The complement is counted by A344654.
The Heinz numbers of these partitions are A344742, complement A344653.
The normal case starts 1, 1, 1, then becomes A345163, complement A345162.
Not counting twins (x,x) gives A345170, ranked by A345172.
A001250 counts wiggly permutations.
A003242 counts anti-run compositions.
A025047 counts wiggly compositions (ascend: A025048, descend: A025049).
A325534 counts separable partitions, ranked by A335433.
A325535 counts inseparable partitions, ranked by A335448.
A344604 counts wiggly compositions with twins.
A344605 counts wiggly patterns with twins.
A344606 counts wiggly permutations of prime indices with twins.
A344614 counts compositions with no consecutive strictly monotone triple.
A345164 counts wiggly permutations of prime indices.
A345165 counts partitions without a wiggly permutation, ranked by A345171.
A345192 counts non-wiggly compositions.
Cf. A000041, A000070, A102726, A103919, A333489, A344607, A344612, A344615, A345166, A345168, A345169.

Table[Length[Select[IntegerPartitions[n],Select[Permutations[#],!MatchQ[#,{_,x_,y_,z_,_}/;x<=y<=z||x>=y>=z]&]!={}&]],{n,0,15}]

a(n) = A345170(n) for n odd; a(n) = A345170(n) + 1 for n even.

a(26)-a(32) from Robert Price, Jun 22 2021

a(33) onwards from Joseph Likar, Sep 05 2023

A348612 Numbers k such that the k-th composition in standard order is not an anti-run, i.e., has 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, 46, 47, 51, 53, 55, 56, 57, 58, 59, 60, 61, 62, 63, 67, 71, 73, 74, 75, 78, 79, 83, 84, 85, 86, 87, 90, 91, 92, 93, 94, 95, 99, 100, 103, 106, 107, 110, 111, 112, 113, 114, 115, 116

Offset: 1

Gus Wiseman, Nov 03 2021

nonn

First differs from A345168 in lacking 37, corresponding to the composition (3,2,1).

A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (row k of 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.

			The terms and corresponding standard compositions begin:
     3: (1,1)          35: (4,1,1)        61: (1,1,1,2,1)
     7: (1,1,1)        36: (3,3)          62: (1,1,1,1,2)
    10: (2,2)          39: (3,1,1,1)      63: (1,1,1,1,1,1)
    11: (2,1,1)        42: (2,2,2)        67: (5,1,1)
    14: (1,1,2)        43: (2,2,1,1)      71: (4,1,1,1)
    15: (1,1,1,1)      46: (2,1,1,2)      73: (3,3,1)
    19: (3,1,1)        47: (2,1,1,1,1)    74: (3,2,2)
    21: (2,2,1)        51: (1,3,1,1)      75: (3,2,1,1)
    23: (2,1,1,1)      53: (1,2,2,1)      78: (3,1,1,2)
    26: (1,2,2)        55: (1,2,1,1,1)    79: (3,1,1,1,1)
    27: (1,2,1,1)      56: (1,1,4)        83: (2,3,1,1)
    28: (1,1,3)        57: (1,1,3,1)      84: (2,2,3)
    29: (1,1,2,1)      58: (1,1,2,2)      85: (2,2,2,1)
    30: (1,1,1,2)      59: (1,1,2,1,1)    86: (2,2,1,2)
    31: (1,1,1,1,1)    60: (1,1,1,3)      87: (2,2,1,1,1)

Constant run compositions are counted by A000005, ranked by A272919.
Counting these compositions by sum and length gives A131044.
These compositions are counted by A261983.
The complement is A333489, counted by A003242.
The non-alternating case is A345168, complement A345167.
A011782 counts compositions, strict A032020.
A238279 counts compositions by sum and number of maximal runs.
A274174 counts compositions with equal parts contiguous.
A336107 counts non-anti-run permutations of prime factors.
A345195 counts non-alternating anti-runs, ranked by A345169.
For compositions in standard order (rows of A066099):
- Length is A000120.
- Sum is A070939
- Maximal runs are counted by A124767.
- Strict compositions are ranked by A233564.
- Maximal anti-runs are counted by A333381.
- Runs-resistance is A333628.
Cf. A029931, A048793, A106356, A114901, A167606, A178470, A228351, A244164, A262046, A335452, A335464.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Select[Range[100],MatchQ[stc[#],{_,x_,x_,_}]&]

A349057 Numbers k such that the k-th composition in standard order is not weakly alternating.

Original entry on oeis.org

37, 46, 52, 53, 69, 75, 78, 92, 93, 101, 104, 105, 107, 110, 116, 117, 133, 137, 139, 142, 150, 151, 156, 157, 165, 174, 180, 181, 184, 185, 186, 187, 190, 197, 200, 201, 203, 206, 208, 209, 210, 211, 214, 215, 220, 221, 229, 232, 233, 235, 238, 244, 245, 261

Offset: 1

Gus Wiseman, Dec 04 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.

			The terms and corresponding compositions begin:
   37: (3,2,1)
   46: (2,1,1,2)
   52: (1,2,3)
   53: (1,2,2,1)
   69: (4,2,1)
   75: (3,2,1,1)
   78: (3,1,1,2)
   92: (2,1,1,3)
   93: (2,1,1,2,1)
  101: (1,3,2,1)
  104: (1,2,4)
  105: (1,2,3,1)
  107: (1,2,2,1,1)
  110: (1,2,1,1,2)
  116: (1,1,2,3)
  117: (1,1,2,2,1)

The strong case is A345168, complement A345167, counted by A345192.
The strong anti-run case is A345169, counted by A345195.
Including all non-anti-runs gives A348612, complement A333489.
These compositions are counted by A349053, complement A349052.
The directed cases are counted by A129852 (incr.) and A129853 (decr.).
The complement for patterns is A349058, strong A345194.
The complement for ordered factorizations is A349059, strong A348610.
Partitions of this type are counted by A349061, complement A349060.
Partitions of this type are ranked by A349794.
Non-strict partitions of this type are counted by A349796.
Permutations of prime indices of this type are counted by A349797.
A001250 counts alternating permutations, complement A348615.
A003242 counts Carlitz (anti-run) compositions, complement A261983.
A011782 counts compositions.
A025047 counts alternating/wiggly compositions, directed A025048, A025049.
A345164 counts alternating permutations of prime indices, weak A349056.
A345165 counts partitions w/o an alternating permutation, ranked by A345171.
A345170 counts partitions w/ an alternating permutation, ranked by A345172.
A349054 counts strict alternating compositions.
Cf. A001700, A096441, A128761, A344615, A344654, A345173, A348613, A349051, A349794, A349795, A349799.

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[#]]&]

A345166 Number of separable integer partitions of n without an alternating permutation.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 3, 5, 6, 7, 10, 14, 18, 21, 27, 35, 42, 54, 65, 78, 95, 117, 140, 170, 202, 239, 286, 343, 401, 476, 562, 660, 775, 910, 1056, 1241, 1444, 1678, 1948, 2267, 2615, 3031, 3502, 4036, 4647, 5356, 6143, 7068, 8101, 9274, 10613, 12151, 13856

Offset: 0

Gus Wiseman, Jun 13 2021

nonn

A partition is separable if it has an anti-run permutation (no adjacent parts equal).
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 has the anti-run permutations (2,3,2,1,2) and (2,1,2,3,2).
The partitions counted by this sequence are those with 2m-1 parts with m being the multiplicity of a part which is neither the smallest or largest part. For example, 4322221 is such a partition since the multiplicity of 2 is 4, the total number of parts is 7, and 2 is neither the smallest or largest part. - Andrew Howroyd, Jan 15 2024

			The a(10) = 1 through a(16) = 6 partitions:
    32221  42221  52221  62221    43331    43332    53332
                         3222211  72221    53331    63331
                                  4222211  82221    92221
                                           3322221  4322221
                                           5222211  6222211
                                                    322222111

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

Allowing alternating permutations gives A325534, ranked by A335433.
Not requiring separability gives A345165, ranked by A345171.
Permutations of this type are ranked by A345169.
The Heinz numbers of these partitions are A345173.
Numbers with a factorization of this type are A348609.
A000041 counts integer partitions.
A001250 counts alternating permutations, complement A348615.
A003242 counts anti-run compositions.
A005649 counts anti-run patterns.
A025047 counts alternating or wiggly compositions, also A025048, A025049.
A325535 counts inseparable partitions, ranked by A335448.
A344654 counts non-twin partitions w/o alt permutation, rank A344653.
A345162 counts normal partitions w/o alt permutation, complement A345163.
A345170 counts partitions w/ alt permutation, ranked by A345172.
Cf. A000070, A103919, A335126, A344604, A344607, A344615, A344740, A344742, A345164, A345166, A345168, A345192, A348379.

wigQ[y_]:=Or[Length[y]==0,Length[Split[y]]== Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1];
Table[Length[Select[IntegerPartitions[n],Select[Permutations[#],!MatchQ[#,{_,x_,x_,_}]&]!={}&&Select[Permutations[#],wigQ]=={}&]],{n,0,15}]

The Heinz numbers of these partitions are A345173 = A345171 /\ A335433.

a(n) = A325534(n) - A345170(n). - Andrew Howroyd, Jan 15 2024

a(26) onwards from Andrew Howroyd, Jan 15 2024

cp's OEIS Frontend

A025047 Number of alternating compositions, i.e., compositions with alternating increases and decreases, starting with either an increase or a decrease.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A345167 Numbers k such that the k-th composition in standard order is alternating.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A345192 Number of non-alternating compositions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A344654 Number of integer partitions of n of which every permutation has a consecutive monotone triple, i.e., a triple (..., x, y, z, ...) such that either x <= y <= z or x >= y >= z.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A345165 Number of integer partitions of n without an alternating permutation.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A345168 Numbers k such that the k-th composition in standard order is not alternating.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A344740 Number of integer partitions of n with a permutation that has no consecutive monotone triple, i.e., no triple (..., x, y, z, ...) such that either x <= y <= z or x >= y >= z.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions