A345194 -id:A345194 - cp's OEIS frontend

A351200 Number of patterns of length n with all distinct runs.

1, 1, 3, 11, 53, 305, 2051, 15731, 135697, 1300869, 13726431, 158137851, 1975599321, 26607158781, 384347911211, 5928465081703, 97262304328573, 1691274884085061, 31073791192091251, 601539400910369671, 12238270940611270161, 261071590963047040241

Offset: 0

Gus Wiseman, Feb 09 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(3) = 11 patterns:
  (1)  (1,1)  (1,1,1)
       (1,2)  (1,1,2)
       (2,1)  (1,2,2)
              (1,2,3)
              (1,3,2)
              (2,1,1)
              (2,1,3)
              (2,2,1)
              (2,3,1)
              (3,1,2)
              (3,2,1)
The complement for n = 3 counts the two patterns (1,2,1) and (2,1,2).

Andrew Howroyd, Table of n, a(n) for n = 0..200
Mathematics Stack Exchange, What is a sequence run? (answered 2011-12-01)

The version for run-lengths instead of runs is A351292.
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.
A297770 counts distinct runs in binary expansion.
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.
- A351642 = word structures.
Row sums of A351640.
Cf. A003242, A098504, A098859, A106356, A242882, A325545, A328592, A329740, A351014, A351204, A351291.

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

\\ here LahI is A111596 as row polynomials.
LahI(n,y)={sum(k=1, n, y^k*(-1)^(n-k)*(n!/k!)*binomial(n-1, k-1))}
S(n)={my(p=prod(k=1, n, 1 + y*x^k + O(x*x^n))); 1 + sum(i=1, (sqrtint(8*n+1)-1)\2, polcoef(p,i,y)*LahI(i,y))}
R(q)={[subst(serlaplace(p), y, 1) | p<-Vec(q)]}
seq(n)={my(q=S(n)); concat([1], sum(k=1, n, R(q^k-1)*sum(r=k, n, binomial(r, k)*(-1)^(r-k)) ))} \\ Andrew Howroyd, Feb 12 2022

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

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

Original entry on oeis.org

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

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

A349056 Number of weakly alternating permutations of the multiset of prime factors of n.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 2, 1, 1, 3, 1, 3, 2, 2, 1, 4, 1, 2, 1, 3, 1, 4, 1, 1, 2, 2, 2, 4, 1, 2, 2, 4, 1, 4, 1, 3, 3, 2, 1, 5, 1, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 6, 1, 2, 3, 1, 2, 4, 1, 3, 2, 4, 1, 6, 1, 2, 3, 3, 2, 4, 1, 5, 1, 2, 1, 6, 2, 2, 2

Offset: 1

Gus Wiseman, Dec 02 2021

nonn

We define a sequence to be weakly alternating if it is alternately weakly increasing and weakly decreasing, starting with either. Then a sequence is alternating in the sense of A025047 iff it is a weakly alternating anti-run.

A prime index of n is a number m such that prime(m) divides n. For n > 1, the multiset of prime factors of n is row n of A027746. The prime indices A112798 can also be used.

			The following are the weakly alternating permutations for selected n:
n = 2   6    12    24     48      60     90     120     180
   ----------------------------------------------------------
    2   23   223   2223   22223   2253   2335   22253   22335
        32   232   2232   22232   2325   2533   22325   22533
             322   2322   22322   2523   3253   22523   23253
                   3222   23222   3252   3325   23252   23352
                          32222   3522   3352   25232   25233
                                  5232   3523   32225   25332
                                         5233   32522   32325
                                         5332   35222   32523
                                                52223   33252
                                                52322   33522
                                                        35232
                                                        52323
                                                        53322

Counting all permutations of prime factors gives A008480.
The variation counting anti-run permutations is A335452.
The strong case is A345164, with twins A344606.
Compositions of this type are counted by A349052, also A129852 and A129853.
Compositions not of this type are counted by A349053, ranked by A349057.
The version for patterns is A349058, strong A345194.
The version for ordered factorizations is A349059, strong A348610.
Partitions of this type are counted by A349060, complement A349061.
The complement is counted by A349797.
The non-alternating case is A349798.
A001250 counts alternating permutations, complement A348615.
A003242 counts Carlitz (anti-run) compositions.
A025047 counts alternating or wiggly compositions, ranked by A345167.
A056239 adds up prime indices, row sums of A112798, row lengths A001222.
A071321 gives the alternating sum of prime factors, reverse A071322.
A344616 gives the alternating sum of prime indices, reverse A316524.
A345165 counts partitions w/o an alternating permutation, ranked by A345171.
A345170 counts partitions w/ an alternating permutation, ranked by A345172.
A348379 counts factorizations with an alternating permutation.
A349800 counts weakly but not strongly alternating compositions.
Cf. A028234, A051119, A096441, A335433, A335448, A344614, A344652, A344653, A345173, A345192.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
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[Permutations[primeMS[n]],whkQ[#]||whkQ[-#]&]],{n,100}]

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

A069321 Stirling transform of A001563: a(0) = 1 and a(n) = Sum_{k=1..n} Stirling2(n,k)kk! for n >= 1.

Original entry on oeis.org

1, 1, 5, 31, 233, 2071, 21305, 249271, 3270713, 47580151, 760192505, 13234467511, 249383390393, 5057242311031, 109820924003705, 2542685745501751, 62527556173577273, 1627581948113854711, 44708026328035782905, 1292443104462527895991, 39223568601129844839353

Offset: 0

Karol A. Penson, Mar 14 2002

nonn

The number of compatible bipartitions of a set of cardinality n for which at least one subset is not underlined. E.g., for n=2 there are 5 such bipartitions: {1 2}, {1}{2}, {2}{1}, {1}{2}, {2}{1}. A005649 is the number of bipartitions of a set of cardinality n. A000670 is the number of bipartitions of a set of cardinality n with none of the subsets underlined. - Kyle Petersen, Mar 31 2005
a(n) is the cardinality of the image set summed over "all surjections". All surjections means: onto functions f:{1, 2, ..., n} -> {1, 2, ..., k} for every k, 1 <= k <= n.  a(n) = Sum_{k=1..n} A019538(n, k)*k. - Geoffrey Critzer, Nov 12 2012
From Gus Wiseman, Jan 15 2022: (Start)
For n > 1, also the number of finite sequences of length n + 1 covering an initial interval of positive integers with at least two adjacent equal parts, or non-anti-run patterns, ranked by the intersection of A348612 and A333217. The complement is counted by A005649. For example, the a(3) = 31 patterns, grouped by sum, are:
  (1111)  (1222)  (1122)  (1112)  (1233)  (1223)
          (2122)  (1221)  (1121)  (1332)  (1322)
          (2212)  (2112)  (1211)  (2133)  (2213)
          (2221)  (2211)  (2111)  (2331)  (2231)
          (1123)                  (3312)  (3122)
          (1132)                  (3321)  (3221)
          (2113)
          (2311)
          (3112)
          (3211)
Also the number of ordered set partitions of {1,...,n + 1} with two successive vertices together in some block.
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..200
Benoit Cloitre, On the fractal behavior of primes, 2011. [internet archive]
Benoit Cloitre, On the fractal behavior of primes, 2011.
D. Foata and D. Zeilberger, The Graphical Major Index, arXiv:math/9406220 [math.CO], 1994.
D. Foata and D. Zeilberger, Graphical major indices, J. Comput. Appl. Math. 68 (1996), no. 1-2, 79-101.

Cf. A000629, A001563, A232472.
The complement is counted by A005649.
A version for permutations of prime indices is A336107.
A version for factorizations is A348616.
Dominated (n > 1) by A350252, complement A345194, compositions A345192.
A000670 = patterns, ranked by A333217.
A001250 = alternating permutations, complement A348615.
A003242 = anti-run compositions, ranked by A333489.
A019536 = necklace patterns.
A226316 = patterns avoiding (1,2,3), weakly A052709, complement A335515.
A261983 = not-anti-run compositions, ranked by A348612.
A333381 = anti-runs of standard compositions.
Cf. A000110, A008277, A055932, A106356, A238424, A333382, A335456, A336103, A349050, A349055, A350138.

b:= proc(n) option remember; `if`(n=0, 1,
      add(b(n-j)*binomial(n, j), j=1..n))
    end:
a:= n-> `if`(n=0, 2, b(n+1)-b(n))/2:
seq(a(n), n=0..30);  # Alois P. Heinz, Feb 02 2018

max = 20; t = Sum[n^(n - 1)x^n/n!, {n, 1, max}]; Range[0, max]!CoefficientList[Series[D[1/(1 - y(Exp[x] - 1)), y] /. y -> 1, {x, 0, max}], x] (* Geoffrey Critzer, Nov 12 2012 *)
Prepend[Table[Sum[StirlingS2[n, k]*k*k!, {k, n}], {n, 18}], 1] (* Michael De Vlieger, Jan 03 2016 *)
a[n_] := (PolyLog[-n-1, 1/2] - PolyLog[-n, 1/2])/4; a[0] = 1; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Mar 30 2016 *)
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],MemberQ[Differences[#],0]&]],{n,0,8}] (* Gus Wiseman, Jan 15 2022 *)

{a(n)=polcoeff(1+sum(m=1, n, (2*m-1)!/(m-1)!*x^m/prod(k=1, m, 1+(m+k-1)*x+x*O(x^n))), n)} \\ Paul D. Hanna, Oct 28 2013

Representation as an infinite series: a(0) = 1 and a(n) = Sum_{k>=2} (k^n*(k-1)/(2^k))/4 for n >= 1. This is a Dobinski-type summation formula.
E.g.f.: (exp(x) - 1)/((2 - exp(x))^2).
a(n) = (1/2)*(A000670(n+1) - A000670(n)).
O.g.f.: 1 + Sum_{n >= 1} (2*n-1)!/(n-1)! * x^n / (Product_{k=1..n} (1 + (n + k - 1)*x)). - Paul D. Hanna, Oct 28 2013
a(n) = (A000629(n+1) - A000629(n))/4. - Benoit Cloitre, Oct 20 2002
a(n) = A232472(n-1)/2. - Vincenzo Librandi, Jan 03 2016
a(n) ~ n! * n / (4 * (log(2))^(n+2)). - Vaclav Kotesovec, Jul 01 2018
a(n > 0) = A000607(n + 1) - A005649(n). - Gus Wiseman, Jan 15 2022

A349059 Number of weakly alternating ordered factorizations of n.

Original entry on oeis.org

1, 1, 1, 2, 1, 3, 1, 4, 2, 3, 1, 8, 1, 3, 3, 8, 1, 8, 1, 8, 3, 3, 1, 18, 2, 3, 4, 8, 1, 11, 1, 16, 3, 3, 3, 22, 1, 3, 3, 18, 1, 11, 1, 8, 8, 3, 1, 38, 2, 8, 3, 8, 1, 18, 3, 18, 3, 3, 1, 32, 1, 3, 8, 28, 3, 11, 1, 8, 3, 11, 1, 56, 1, 3, 8, 8, 3, 11, 1, 38, 8, 3

Offset: 1

Gus Wiseman, Dec 04 2021

nonn

An ordered factorization of n is a finite sequence of positive integers > 1 with product n.

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

			The ordered factorizations for n = 2, 4, 6, 8, 12, 24, 30:
  (2)  (4)    (6)    (8)      (12)     (24)       (30)
       (2*2)  (2*3)  (2*4)    (2*6)    (3*8)      (5*6)
              (3*2)  (4*2)    (3*4)    (4*6)      (6*5)
                     (2*2*2)  (4*3)    (6*4)      (10*3)
                              (6*2)    (8*3)      (15*2)
                              (2*2*3)  (12*2)     (2*15)
                              (2*3*2)  (2*12)     (3*10)
                              (3*2*2)  (2*2*6)    (2*5*3)
                                       (2*4*3)    (3*2*5)
                                       (2*6*2)    (3*5*2)
                                       (3*2*4)    (5*2*3)
                                       (3*4*2)
                                       (4*2*3)
                                       (6*2*2)
                                       (2*2*2*3)
                                       (2*2*3*2)
                                       (2*3*2*2)
                                       (3*2*2*2)

The strong version for compositions is A025047, also A025048, A025049.
The strong case is A348610, complement A348613.
The version for compositions is A349052, complement A349053.
As compositions these are ranked by the complement of A349057.
A001055 counts factorizations, strict A045778, ordered A074206.
A001250 counts alternating permutations, complement A348615.
A335434 counts separable factorizations, complement A333487.
A345164 counts alternating permutations of prime factors, w/ twins A344606.
A345170 counts partitions with an alternating permutation.
A348379 = factorizations w/ alternating permutation, complement A348380.
A348611 counts anti-run ordered factorizations, complement A348616.
A349060 counts weakly alternating partitions, complement A349061.
A349800 = weakly but not strongly alternating compositions, ranked A349799.
Cf. A003242, A122181, A138364, A339846, A339890, A345165, A345167, A345194, A347050, A347438, A347463, A347706.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&, Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
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/@facs[n], whkQ[#]||whkQ[-#]&]],{n,100}]

a(2^n) = A349052(n).

A349054 Number of alternating strict compositions of n. Number of alternating (up/down or down/up) permutations of strict integer partitions of n.

Original entry on oeis.org

1, 1, 1, 3, 3, 5, 9, 11, 15, 21, 35, 41, 59, 75, 103, 155, 193, 255, 339, 443, 569, 841, 1019, 1365, 1743, 2295, 2879, 3785, 5151, 6417, 8301, 10625, 13567, 17229, 21937, 27509, 37145, 45425, 58345, 73071, 93409, 115797, 147391, 182151, 229553, 297061, 365625

Offset: 0

Gus Wiseman, Dec 21 2021

nonn

A strict composition of n is a finite sequence of distinct positive integers summing to n.
A sequence is alternating if it is alternately strictly increasing and strictly decreasing, starting with either.
The case starting with an increase (or decrease, it doesn't matter in the enumeration) is counted by A129838.

			The a(1) = 1 through a(7) = 11 compositions:
  (1)  (2)  (3)    (4)    (5)    (6)      (7)
            (1,2)  (1,3)  (1,4)  (1,5)    (1,6)
            (2,1)  (3,1)  (2,3)  (2,4)    (2,5)
                          (3,2)  (4,2)    (3,4)
                          (4,1)  (5,1)    (4,3)
                                 (1,3,2)  (5,2)
                                 (2,1,3)  (6,1)
                                 (2,3,1)  (1,4,2)
                                 (3,1,2)  (2,1,4)
                                          (2,4,1)
                                          (4,1,2)

Wikipedia, Alternating permutation

Ranking sequences are put in parentheses below.
This is the strict case of A025047/A025048/A025049 (A345167).
This is the alternating case of A032020 (A233564).
The unordered case (partitions) is A065033.
The directed case is A129838.
A001250 = alternating permutations (A349051), complement A348615 (A350250).
A003242 = Carlitz (anti-run) compositions, complement A261983.
A011782 = compositions, unordered A000041.
A345165 = partitions without an alternating permutation (A345171).
A345170 = partitions with an alternating permutation (A345172).
A345192 = non-alternating compositions (A345168).
A345195 = non-alternating anti-run compositions (A345169).
A349800 = weakly but not strongly alternating compositions (A349799).
A349052 = weakly alternating compositions, complement A349053 (A349057).
Cf. A000111, A008965, A015723, A114901, A128761, A129852, A129853, A218074, A333213, A344614, A345164, A345194, A349060, A349795.

g:= proc(u, o) option remember;
      `if`(u+o=0, 1, add(g(o-1+j, u-j), j=1..u))
    end:
b:= proc(n, k) option remember; `if`(k<0 or n<0, 0,
      `if`(k=0, `if`(n=0, 2, 0), b(n-k, k)+b(n-k, k-1)))
    end:
a:= n-> add(b(n, k)*g(k, 0), k=0..floor((sqrt(8*n+1)-1)/2))-1:
seq(a(n), n=0..46);  # Alois P. Heinz, Dec 22 2021

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

a(n) = 2 * A129838(n) - 1.

G.f.: Sum_{n>0} A001250(n)*x^(n*(n+1)/2)/Product_{k=1..n}(1-x^k).

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

cp's OEIS Frontend

A351200 Number of patterns of length n with all distinct runs.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

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

A349056 Number of weakly alternating permutations of the multiset of prime factors of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A069321 Stirling transform of A001563: a(0) = 1 and a(n) = Sum_{k=1..n} Stirling2(n,k)*k*k! for n >= 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A349059 Number of weakly alternating ordered factorizations of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A069321 Stirling transform of A001563: a(0) = 1 and a(n) = Sum_{k=1..n} Stirling2(n,k)kk! for n >= 1.