A005649 -id:A005649 - cp's OEIS frontend

A351292 Number of patterns of length n with all distinct run-lengths.

1, 1, 1, 5, 5, 9, 57, 61, 109, 161, 1265, 1317, 2469, 3577, 5785, 43901, 47165, 86337, 127665, 204853, 284197, 2280089, 2398505, 4469373, 6543453, 10570993, 14601745, 22502549, 159506453, 171281529, 314077353, 462623821, 742191037, 1031307185, 1580543969, 2141246229

Offset: 0

Gus Wiseman, Feb 10 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.

			The a(1) = 1 through a(5) = 9 patterns:
  (1)  (1,1)  (1,1,1)  (1,1,1,1)  (1,1,1,1,1)
              (1,1,2)  (1,1,1,2)  (1,1,1,1,2)
              (1,2,2)  (1,2,2,2)  (1,1,1,2,2)
              (2,1,1)  (2,1,1,1)  (1,1,2,2,2)
              (2,2,1)  (2,2,2,1)  (1,2,2,2,2)
                                  (2,1,1,1,1)
                                  (2,2,1,1,1)
                                  (2,2,2,1,1)
                                  (2,2,2,2,1)
The a(6) = 57 patterns grouped by sum:
  111111  111112  111122  112221  111223  111233  112333  122333
          111211  111221  122211  111322  111332  113332  133322
          112111  122111  211122  112222  112223  122233  221333
          211111  221111  221112  211222  113222  133222  223331
                                  221113  122222  211333  333122
                                  222112  211133  222133  333221
                                  222211  221222  222331
                                  223111  222113  233311
                                  311122  222122  331222
                                  322111  222221  332221
                                          222311  333112
                                          233111  333211
                                          311222
                                          322211
                                          331112
                                          332111

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

The version for runs instead of run-lengths is A351200.
A000670 counts patterns, ranked by A333217.
A005649 counts anti-run patterns, complement A069321.
A005811 counts runs in binary expansion.
A032011 counts patterns with distinct multiplicities.
A044813 lists numbers whose binary expansion has distinct run-lengths.
A060223 counts Lyndon patterns, necklaces A019536, aperiodic A296975.
A131689 counts patterns by number of distinct parts.
A238130 and A238279 count compositions by number of runs.
A165413 counts distinct run-lengths in binary expansion, runs A297770.
A345194 counts alternating patterns, up/down A350354.
Counting words with all distinct runs:
- A351013 = compositions, for run-lengths A329739, ranked by A351290.
- A351016 = binary words, for run-lengths A351017.
- A351018 = binary expansions, for run-lengths A032020, ranked by A175413.
- A351202 = permutations of prime factors.
- A351638 = word structures.
Row sums of A350824.
Cf. A003242, A098504, A098859, A106356, A239455, A242882, A325545, A328592, A329740, A351014, A351293.

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],UnsameQ@@Length/@Split[#]&]],{n,0,6}]

P(n) = {Vec(-1 + prod(k=1, n, 1 + y*x^k + O(x*x^n)))}
R(u,k) = {k*[subst(serlaplace(p)/y, y, k-1) | p<-u]}
seq(n)={my(u=P(n), c=poldegree(u[#u])); concat([1], sum(k=1, c, R(u, k)*sum(r=k, c, binomial(r, k)*(-1)^(r-k)) ))} \\ Andrew Howroyd, Feb 11 2022

From Andrew Howroyd, Feb 12 2022: (Start)
a(n) = Sum_{k=1..n} R(n,k)*(Sum_{r=k..n} binomial(r, k)*(-1)^(r-k)), where R(n,k) = Sum_{j=1..floor((sqrt(8*n+1)-1)/2)} k*(k-1)^(j-1) * j! * A008289(n,j).
G.f.: 1 + Sum_{r>=1} Sum_{k=1..r} R(k,x) * binomial(r, k)*(-1)^(r-k), where R(k,x) = Sum_{j>=1} k*(k-1)^(j-1) * j! * [y^j](Product_{k>=1} 1 + y*x^k).
(End)

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

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

A336103 Number of separable multisets of size n covering an initial interval of positive integers.

Original entry on oeis.org

1, 1, 1, 3, 5, 13, 24, 56, 108, 236, 464, 976, 1936, 3984, 7936, 16128, 32192, 64960, 129792, 260864, 521472, 1045760, 2091008, 4188160, 8375296, 16763904, 33525760, 67080192, 134156288, 268374016, 536739840, 1073610752, 2147205120, 4294688768, 8589344768, 17179279360, 34358493184

Offset: 0

Gus Wiseman, Jul 09 2020

A multiset is separable if it has a permutation that is an anti-run, meaning there are no adjacent equal parts.
Alternatively, a multiset is separable if its greatest multiplicity is greater than the sum of its remaining multiplicities plus one. Hence a(n) is the number of compositions of n whose greatest part is at most one more than the sum of its other parts. For example, the a(1) = 1 through a(5) = 13 compositions are:
  (1)  (11)  (12)   (22)    (23)
             (21)   (112)   (32)
             (111)  (121)   (113)
                    (211)   (122)
                    (1111)  (131)
                            (212)
                            (221)
                            (311)
                            (1112)
                            (1121)
                            (1211)
                            (2111)
                            (11111)

			The a(1) = 1 through a(5) = 13 separable multisets:
  {1}  {1,2}  {1,1,2}  {1,1,2,2}  {1,1,1,2,2}
              {1,2,2}  {1,1,2,3}  {1,1,1,2,3}
              {1,2,3}  {1,2,2,3}  {1,1,2,2,2}
                       {1,2,3,3}  {1,1,2,2,3}
                       {1,2,3,4}  {1,1,2,3,3}
                                  {1,1,2,3,4}
                                  {1,2,2,2,3}
                                  {1,2,2,3,3}
                                  {1,2,2,3,4}
                                  {1,2,3,3,3}
                                  {1,2,3,3,4}
                                  {1,2,3,4,4}
                                  {1,2,3,4,5}

Michael De Vlieger, Table of n, a(n) for n = 0..3322
Index entries for linear recurrences with constant coefficients, signature (2,4,-8,-4,8).

The inseparable version is A336102.
The strong (weakly decreasing multiplicities) case is A336106.
Sequences covering an initial interval are A000670.
Anti-run compositions are A003242.
Anti-run patterns are A005649.
Separable partitions are A325534.
Inseparable partitions are A325535.
Inseparable factorizations are A333487.
Anti-run compositions are ranked by A333489.
Heinz numbers of inseparable partitions are A335448.
Cf. A001792, A019472, A025065, A049610, A052841, A106351, A269134, A292884, A335126, A335433, A335452.

allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
sepQ[m_]:=Select[Permutations[m],!MatchQ[#,{_,x_,x_,_}]&]!={};
Table[Length[Select[allnorm[n],sepQ]],{n,0,5}]
(* or *)
Table[Length[Join@@Permutations/@Select[IntegerPartitions[n],With[{mx=Max@@#},mx<=1+Total[DeleteCases[#,mx,{1},1]]]&]],{n,0,15}] (* or *)
CoefficientList[Series[(x - 1) (2 x^5 + 7 x^4 - 5 x^2 + 1)/((2 x - 1) (2 x^2 - 1)^2), {x, 0, 36}], x] (* Michael De Vlieger, Apr 07 2021 *)

a(n) = 2^(n-1) - (floor(n/2)+1) * 2^(floor(n/2)-2) for n >= 2. - David A. Corneth, Jul 09 2020
From Chai Wah Wu, Apr 07 2021: (Start)
a(n) = 2*a(n-1) + 4*a(n-2) - 8*a(n-3) - 4*a(n-4) + 8*a(n-5) for n > 6.
G.f.: (x - 1)*(2*x^5 + 7*x^4 - 5*x^2 + 1)/((2*x - 1)*(2*x^2 - 1)^2). (End)

a(26)-a(36) from David A. Corneth, Jul 09 2020

A345169 Numbers k such that the k-th composition in standard order is a non-alternating anti-run.

Original entry on oeis.org

37, 52, 69, 101, 104, 105, 133, 137, 150, 165, 180, 197, 200, 208, 209, 210, 261, 265, 274, 278, 300, 301, 308, 325, 328, 357, 360, 361, 389, 393, 400, 401, 406, 416, 417, 418, 421, 422, 436, 517, 521, 529, 530, 534, 549, 550, 556, 557, 564, 581, 600, 601, 613

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).
An anti-run (separation or Carlitz composition) is a sequence with no adjacent equal parts.

			The sequence of terms together with their binary indices begins:
     37: (3,2,1)      210: (1,2,3,2)      400: (1,3,5)
     52: (1,2,3)      261: (6,2,1)        401: (1,3,4,1)
     69: (4,2,1)      265: (5,3,1)        406: (1,3,2,1,2)
    101: (1,3,2,1)    274: (4,3,2)        416: (1,2,6)
    104: (1,2,4)      278: (4,2,1,2)      417: (1,2,5,1)
    105: (1,2,3,1)    300: (3,2,1,3)      418: (1,2,4,2)
    133: (5,2,1)      301: (3,2,1,2,1)    421: (1,2,3,2,1)
    137: (4,3,1)      308: (3,1,2,3)      422: (1,2,3,1,2)
    150: (3,2,1,2)    325: (2,4,2,1)      436: (1,2,1,2,3)
    165: (2,3,2,1)    328: (2,3,4)        517: (7,2,1)
    180: (2,1,2,3)    357: (2,1,3,2,1)    521: (6,3,1)
    197: (1,4,2,1)    360: (2,1,2,4)      529: (5,4,1)
    200: (1,3,4)      361: (2,1,2,3,1)    530: (5,3,2)
    208: (1,2,5)      389: (1,5,2,1)      534: (5,2,1,2)
    209: (1,2,4,1)    393: (1,4,3,1)      549: (4,3,2,1)

Wikipedia, Alternating permutation

A version counting partitions is A345166, ranked by A345173.
These compositions are counted by A345195.
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.
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 an alternating permutation, ranked by A345171.
A345170 counts partitions w/ an alternating permutation, ranked by A345172.
A345192 counts non-alternating compositions.
A345194 counts alternating patterns (with twins: A344605).
Statistics of standard compositions:
- Length is A000120.
- Constant runs are A124767.
- Heinz number is A333219.
- Anti-runs are A333381.
- Runs-resistance is A333628.
- Number of distinct parts is A334028.
- Non-anti-runs are A348612.
Classes of standard compositions:
- Weakly decreasing compositions (partitions) are A114994.
- Weakly increasing compositions (multisets) are A225620.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Strictly increasing compositions (sets) are A333255.
- Strictly decreasing compositions (strict partitions) are A333256.
- Anti-runs are A333489.
- Alternating compositions are A345167.
- Non-Alternating compositions are A345168.
Cf. A001222, A008965, A238279, A344614, A344615, A344652, A344653, A344654, A345162, A345163, A345193, A348609, 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];
sepQ[y_]:=!MatchQ[y,{_,x_,x_,_}];
Select[Range[0,1000],sepQ[stc[#]]&&!wigQ[stc[#]]&]

Intersection of A345168 (non-alternating) and A333489 (anti-run).

A336102 Number of inseparable multisets of size n covering an initial interval of positive integers.

Original entry on oeis.org

0, 0, 1, 1, 3, 3, 8, 8, 20, 20, 48, 48, 112, 112, 256, 256, 576, 576, 1280, 1280, 2816, 2816, 6144, 6144, 13312, 13312, 28672, 28672, 61440, 61440, 131072, 131072, 278528, 278528, 589824, 589824, 1245184, 1245184, 2621440, 2621440, 5505024, 5505024, 11534336

Offset: 0

Gus Wiseman, Jul 08 2020

nonn

A multiset is separable if it has a permutation that is an anti-run, meaning there are no adjacent equal parts.
Alternatively, a multiset is separable if its greatest multiplicity is greater than the sum of its remaining multiplicities plus one.
Also the number of compositions of n whose greatest part is greater than the sum of its remaining parts plus one. For example, the a(2) = 1 through a(7) = 8 compositions are:
  (2)  (3)  (4)    (5)    (6)      (7)
            (1,3)  (1,4)  (1,5)    (1,6)
            (3,1)  (4,1)  (2,4)    (2,5)
                          (4,2)    (5,2)
                          (5,1)    (6,1)
                          (1,1,4)  (1,1,5)
                          (1,4,1)  (1,5,1)
                          (4,1,1)  (5,1,1)

			The a(2) = 1 through a(7) = 8 multisets:
  {11}  {111}  {1111}  {11111}  {111111}  {1111111}
               {1112}  {11112}  {111112}  {1111112}
               {1222}  {12222}  {111122}  {1111122}
                                {111123}  {1111123}
                                {112222}  {1122222}
                                {122222}  {1222222}
                                {122223}  {1222223}
                                {123333}  {1233333}

Michael De Vlieger, Table of n, a(n) for n = 0..6625
Index entries for linear recurrences with constant coefficients, signature (0,4,0,-4).

The strong (weakly decreasing multiplicities) case is A025065.
The bisection is A049610.
The separable version is A336103.
Sequences covering an initial interval are A000670.
Anti-run compositions are A003242.
Anti-run patterns are A005649.
Separable partitions are A325534.
Inseparable partitions are A325535.
Inseparable factorizations are A333487.
Anti-run compositions are ranked by A333489.
Heinz numbers of inseparable partitions are A335448.
Cf. A001792, A019472, A052841, A106351, A124767, A269134, A292884, A335433, A335126, A335452, A335548.

Table[Length[Join@@Permutations/@Select[IntegerPartitions[n],With[{mx=Max@@#},mx>1+Total[DeleteCases[#,mx,{1},1]]]&]],{n,0,15}]
(* Second program: *)
CoefficientList[Series[x^2*(1 - x) (x + 1)^2/(2 x^2 - 1)^2, {x, 0, 43}], x] (* Michael De Vlieger, Apr 07 2021 *)

a(2*n) = a(2*n + 1) = A049610(n + 1).
a(n) = 2^(n-1) - A336103(n).
A001792 repeated for n > 1. David A. Corneth, Jul 09 2020
From Chai Wah Wu, Apr 07 2021: (Start)
a(n) = 4*a(n-2) - 4*a(n-4) for n > 5.
G.f.: x^2*(1 - x)*(x + 1)^2/(2*x^2 - 1)^2. (End)

A336106 Number of integer partitions of n whose greatest part is at most one more than the sum of the other parts.

Original entry on oeis.org

1, 1, 1, 2, 3, 5, 7, 11, 15, 23, 30, 44, 58, 82, 105, 146, 186, 252, 318, 423, 530, 695, 863, 1116, 1380, 1763, 2164, 2738, 3345, 4192, 5096, 6334, 7665, 9459, 11395, 13968, 16765, 20425, 24418, 29588, 35251, 42496, 50460, 60547, 71669, 85628

Offset: 0

Gus Wiseman, Jul 09 2020

nonn

Also the number of separable strong multisets of length n covering an initial interval of positive integers. A multiset is separable if it has a permutation that is an anti-run, meaning there are no adjacent equal parts.

			The a(1) = 1 through a(8) = 15 partitions:
  (1)  (11)  (21)   (22)    (32)     (33)      (43)       (44)
             (111)  (211)   (221)    (222)     (322)      (332)
                    (1111)  (311)    (321)     (331)      (422)
                            (2111)   (2211)    (421)      (431)
                            (11111)  (3111)    (2221)     (2222)
                                     (21111)   (3211)     (3221)
                                     (111111)  (4111)     (3311)
                                               (22111)    (4211)
                                               (31111)    (22211)
                                               (211111)   (32111)
                                               (1111111)  (41111)
                                                          (221111)
                                                          (311111)
                                                          (2111111)
                                                          (11111111)

The inseparable version is A025065.
The Heinz numbers of these partitions are A335127.
The non-strong version is A336103.
Sequences covering an initial interval are A000670.
Anti-run compositions are A003242.
Anti-run patterns are A005649.
Separable partitions are A325534.
Inseparable partitions are A325535.
Separable factorizations are A335434.
Heinz numbers of separable partitions are A335433.
Cf. A049610, A106351, A292884, A335126, A335433, A335452, A335548, A336102.

Table[Length[Select[IntegerPartitions[n],2*Max@@#<=1+n&]],{n,0,15}]

A349050 Number of multisets of size n that have no alternating permutations and cover an initial interval of positive integers.

Original entry on oeis.org

0, 0, 1, 1, 3, 4, 8, 12, 20, 32, 48, 80, 112, 192, 256, 448, 576, 1024, 1280, 2304, 2816, 5120, 6144, 11264, 13312, 24576, 28672, 53248, 61440, 114688, 131072, 245760, 278528, 524288, 589824, 1114112, 1245184, 2359296, 2621440, 4980736, 5505024

Offset: 0

Gus Wiseman, Dec 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 does have the anti-run permutations (2,3,2,1,2) and (2,1,2,3,2). Alternating permutations of multisets are a generalization of alternating or up-down permutations of {1..n}.

			The multiset {1,2,2,2,2,3,3} has no alternating permutations, even though it does have the three anti-run permutations (2,1,2,3,2,3,2), (2,3,2,1,2,3,2), (2,3,2,3,2,1,2), so is counted under a(7).
The a(2) = 1 through a(7) = 12 multisets:
  {11}  {111}  {1111}  {11111}  {111111}  {1111111}
               {1112}  {11112}  {111112}  {1111112}
               {1222}  {12222}  {111122}  {1111122}
                       {12223}  {111123}  {1111123}
                                {112222}  {1122222}
                                {122222}  {1122223}
                                {122223}  {1222222}
                                {123333}  {1222223}
                                          {1222233}
                                          {1222234}
                                          {1233333}
                                          {1233334}
As compositions:
  (2)  (3)  (4)    (5)      (6)      (7)
            (1,3)  (1,4)    (1,5)    (1,6)
            (3,1)  (4,1)    (2,4)    (2,5)
                   (1,3,1)  (4,2)    (5,2)
                            (5,1)    (6,1)
                            (1,1,4)  (1,1,5)
                            (1,4,1)  (1,4,2)
                            (4,1,1)  (1,5,1)
                                     (2,4,1)
                                     (5,1,1)
                                     (1,1,4,1)
                                     (1,4,1,1)

Andrew Howroyd, Table of n, a(n) for n = 0..1000
Frankie Mennicucci, On the Number of Strong Dominating Sets in a Graph, Master's Thesis, Montclair State Univ. (2024). See p. 32.
Wikipedia, Alternating permutation

The case of weakly decreasing multiplicities is A025065.
The inseparable case is A336102.
A separable instead of alternating version is A336103.
The version for partitions is A345165.
The version for factorizations is A348380, complement A348379.
The complement (still covering an initial interval) is counted by A349055.
A000670 counts sequences covering an initial interval, anti-run A005649.
A001250 counts alternating permutations, complement A348615.
A003242 counts Carlitz (anti-run) compositions, ranked by A333489.
A025047 = alternating compositions, ranked by A345167, also A025048/A025049.
A049774 counts permutations avoiding the consecutive pattern (1,2,3).
A325534 counts separable partitions, ranked by A335433.
A325535 counts inseparable partitions, ranked by A335448.
A345170 counts partitions w/ an alternating permutation, ranked by A345172.
A344654 counts partitions w/o an alternating permutation, ranked by A344653.
Cf. A019472, A052841, A096441, A106351, A106356, A335125, A335126, A344614, A347050, A347706, A348377, A349054.

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[allnorm[n],Select[Permutations[#],wigQ]=={}&]],{n,0,7}]

a(n) = if(n==0, 0, if(n%2==0, (n+2)*2^(n/2-3), (n-1)*2^((n-1)/2-2))) \\ Andrew Howroyd, Jan 13 2024

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

a(n) = (n+2)*2^(n/2-3) for even n > 0; a(n) = (n-1)*2^((n-5)/2) for odd n. - Andrew Howroyd, Jan 13 2024

Terms a(10) and beyond from Andrew Howroyd, Jan 13 2024

A345195 Number of non-alternating anti-run compositions of n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 2, 4, 10, 23, 49, 96, 192, 368, 692, 1299, 2403, 4400, 8029, 14556, 26253, 47206, 84574, 151066, 269244, 478826, 849921, 1506309, 2665829, 4711971, 8319763, 14675786, 25865400, 45552678, 80171353, 141015313, 247905305, 435614270, 765132824

Offset: 0

Gus Wiseman, Jun 17 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 does have the anti-run permutations (2,3,2,1,2) and (2,1,2,3,2).

An anti-run (separation or Carlitz composition) is a sequence with no adjacent equal parts.

			The a(9) = 23 anti-runs:
  (1,2,6)  (1,2,4,2)  (1,2,1,2,3)
  (1,3,5)  (1,2,5,1)  (1,2,3,1,2)
  (2,3,4)  (1,3,4,1)  (1,2,3,2,1)
  (4,3,2)  (1,4,3,1)  (1,3,2,1,2)
  (5,3,1)  (1,5,2,1)  (2,1,2,3,1)
  (6,2,1)  (2,1,2,4)  (2,1,3,2,1)
           (2,4,2,1)  (3,2,1,2,1)
           (3,1,2,3)
           (3,2,1,3)
           (4,2,1,2)

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

Non-anti-run compositions are counted by A261983.
A version counting partitions is A345166, ranked by A345173.
These compositions are ranked by A345169.
Non-alternating compositions are counted by A345192, ranked by A345168.
A001250 counts alternating permutations, complement A348615.
A003242 counts anti-run compositions, ranked by A333489.
A011782 counts compositions.
A025047 counts alternating or wiggly compositions, ranked by A345167.
A032020 counts strict compositions.
A106356 counts compositions by number of maximal anti-runs.
A325534 counts separable partitions, ranked by A335433.
A325535 counts inseparable partitions, ranked by A335448.
A345164 counts alternating permutations of prime indices, w/ twins A344606.
A345165 counts partitions w/o an alternating permutation, ranked by A345171.
A345170 counts partitions w/ an alternating permutation, ranked by A345172.
A345194 counts alternating patterns (with twins: A344605).
Cf. A005649, A008965, A114901, A178470, A333755, A344604, A344614, A344654, A344740, A345162, A345163, A348380, A348612, A348613.

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

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

a(21) onwards from Andrew Howroyd, Jan 31 2024

A349055 Number of multisets of size n that have an alternating permutation and cover an initial interval of positive integers.

Original entry on oeis.org

1, 1, 1, 3, 5, 12, 24, 52, 108, 224, 464, 944, 1936, 3904, 7936, 15936, 32192, 64512, 129792, 259840, 521472, 1043456, 2091008, 4183040, 8375296, 16752640, 33525760, 67055616, 134156288, 268320768, 536739840, 1073496064, 2147205120, 4294443008, 8589344768

Offset: 0

Gus Wiseman, Dec 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 does have the anti-run permutations (2,3,2,1,2) and (2,1,2,3,2). Alternating permutations of multisets are a generalization of alternating or up-down permutations of {1..n}.

The multisets that have an alternating permutation are those which have no part with multiplicity greater than floor(n/2) except for odd n when either the smallest or largest part can have multiplicity ceiling(n/2). - Andrew Howroyd, Jan 13 2024

			The multiset {1,2,2,3} has alternating permutations (2,1,3,2), (2,3,1,2), so is counted under a(4).
The a(1) = 1 through a(5) = 12 multisets:
  {1}  {1,2}  {1,1,2}  {1,1,2,2}  {1,1,1,2,2}
              {1,2,2}  {1,1,2,3}  {1,1,1,2,3}
              {1,2,3}  {1,2,2,3}  {1,1,2,2,2}
                       {1,2,3,3}  {1,1,2,2,3}
                       {1,2,3,4}  {1,1,2,3,3}
                                  {1,1,2,3,4}
                                  {1,2,2,3,3}
                                  {1,2,2,3,4}
                                  {1,2,3,3,3}
                                  {1,2,3,3,4}
                                  {1,2,3,4,4}
                                  {1,2,3,4,5}
As compositions:
  (1)  (1,1)  (1,2)    (2,2)      (2,3)
              (2,1)    (1,1,2)    (3,2)
              (1,1,1)  (1,2,1)    (1,1,3)
                       (2,1,1)    (1,2,2)
                       (1,1,1,1)  (2,1,2)
                                  (2,2,1)
                                  (3,1,1)
                                  (1,1,1,2)
                                  (1,1,2,1)
                                  (1,2,1,1)
                                  (2,1,1,1)
                                  (1,1,1,1,1)

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

The strong inseparable case is A025065.
A separable instead of alternating version is A336103, complement A336102.
The case of weakly decreasing multiplicities is A336106.
The version for non-twin partitions is A344654, ranked by A344653.
The complement for non-twin partitions is A344740, ranked by A344742.
The complement for partitions is A345165, ranked by A345171.
The version for partitions is A345170, ranked by A345172.
The version for factorizations is A348379, complement A348380.
The complement (still covering an initial interval) is counted by A349050.
A000670 counts sequences covering an initial interval, anti-run A005649.
A001250 counts alternating permutations, complement A348615.
A003242 counts Carlitz (anti-run) compositions, ranked by A333489.
A025047 = alternating compositions, ranked by A345167, also A025048/A025049.
A049774 counts permutations avoiding the consecutive pattern (1,2,3).
A325534 counts separable partitions, ranked by A335433.
A325535 counts inseparable partitions, ranked by A335448.
Cf. A019472, A052841, A096441, A106351, A106356, A335125, A335127, A344614, A347050, A347706, A348610, A348613, A349054.

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[allnorm[n], Select[Permutations[#],wigQ]!={}&]],{n,0,7}]

a(n) = if(n==0, 1, 2^(n-1) - if(n%2==0, (n+2)*2^(n/2-3), (n-1)*2^((n-5)/2))) \\ Andrew Howroyd, Jan 13 2024

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

a(n) = 2^(n-1) - (n+2)*2^(n/2-3) for even n > 0; a(n) = 2^(n-1) - (n-1)*2^((n-5)/2) for odd n. - Andrew Howroyd, Jan 13 2024

Terms a(10) and beyond from Andrew Howroyd, Jan 13 2024

A386583 Triangle read by rows where T(n,k) is the number of length k integer partitions of n having a permutation without any adjacent equal parts (separable).

Original entry on oeis.org

1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 2, 2, 0, 0, 0, 1, 2, 2, 1, 0, 0, 0, 1, 3, 4, 1, 1, 0, 0, 0, 1, 3, 5, 3, 2, 0, 0, 0, 0, 1, 4, 6, 4, 3, 1, 0, 0, 0, 0, 1, 4, 8, 6, 5, 1, 1, 0, 0, 0, 0, 1, 5, 10, 8, 8, 3, 2, 0, 0, 0, 0, 0, 1, 5, 11, 12, 11, 5, 3, 1, 0, 0, 0, 0

Offset: 0

Gus Wiseman, Aug 03 2025

A multiset is separable iff it has a permutation that is an anti-run, meaning there are no adjacent equal parts.
Separable partitions (A325534) are different from partitions of separable type (A386585).
Are the rows all unimodal?
Some rows are not unimodal: T(200, k=26..30) = 149371873744, 153304102463, 152360653274, 152412869411, 147228477998. - Alois P. Heinz, Aug 04 2025

			Row n = 9 counts the following partitions:
  (9)  (5,4)  (4,3,2)  (3,3,2,1)  (3,2,2,1,1)  (2,2,2,1,1,1)
       (6,3)  (4,4,1)  (4,2,2,1)  (3,3,1,1,1)
       (7,2)  (5,2,2)  (4,3,1,1)  (4,2,1,1,1)
       (8,1)  (5,3,1)  (5,2,1,1)
              (6,2,1)
              (7,1,1)
Triangle begins:
  1
  0  1
  0  1  0
  0  1  1  0
  0  1  1  1  0
  0  1  2  2  0  0
  0  1  2  2  1  0  0
  0  1  3  4  1  1  0  0
  0  1  3  5  3  2  0  0  0
  0  1  4  6  4  3  1  0  0  0
  0  1  4  8  6  5  1  1  0  0  0
  0  1  5 10  8  8  3  2  0  0  0  0
  0  1  5 11 12 11  5  3  1  0  0  0  0
  0  1  6 14 14 15  8  6  1  1  0  0  0  0
  0  1  6 16 19 20 11  9  3  2  0  0  0  0  0
  0  1  7 18 23 27 17 14  5  3  1  0  0  0  0  0
  0  1  7 21 29 34 23 20  9  6  1  1  0  0  0  0  0
  0  1  8 24 34 43 32 28 13 10  3  2  0  0  0  0  0  0
  0  1  8 26 42 53 42 38 20 15  5  3  1  0  0  0  0  0  0
  0  1  9 30 48 66 55 52 28 23  9  6  1  1  0  0  0  0  0  0
  0  1  9 33 58 80 70 68 41 33 14 10  3  2  0  0  0  0  0  0  0
  ...

Alois P. Heinz, Rows n = 0..200, flattened

Separable case of A008284.
Row sums are A325534, ranked by A335433.
For inseparable instead separable we have A386584, sums A325535, ranks A335448.
For separable type instead of separable we have A386585, sums A336106, ranks A335127.
For inseparable type instead of separable we have A386586, sums A025065, ranks A335126.
A003242 and A335452 count anti-runs, ranks A333489, patterns A005649.
A124762 gives inseparability of standard compositions, separability A333382.
A239455 counts Look-and-Say partitions, ranks A351294.
A336103 counts normal separable multisets, inseparable A336102.
A351293 counts non-Look-and-Say partitions, ranks A351295.
A386633 counts separable set partitions, row sums of A386635.
A386634 counts inseparable set partitions, row sums of A386636.
Cf. A106351, A111133, A238130, A335434, A386575, A386576, A386580, A386581, A386577.

sepQ[y_]:=Select[Permutations[y],Length[Split[#]]==Length[y]&]!={};
Table[Length[Select[IntegerPartitions[n,{k}],sepQ]],{n,0,15},{k,0,n}]

cp's OEIS Frontend

A351292 Number of patterns of length n with all distinct run-lengths.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A336103 Number of separable multisets of size n covering an initial interval of positive integers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A345169 Numbers k such that the k-th composition in standard order is a non-alternating anti-run.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A336102 Number of inseparable multisets of size n covering an initial interval of positive integers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A336106 Number of integer partitions of n whose greatest part is at most one more than the sum of the other parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A349050 Number of multisets of size n that have no alternating permutations and cover an initial interval of positive integers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI