A129838 -id:A129838 - cp's OEIS frontend

A025048 Number of up/down (initially ascending) compositions of n.

1, 1, 1, 2, 3, 4, 7, 11, 16, 26, 41, 64, 100, 158, 247, 389, 612, 960, 1509, 2372, 3727, 5858, 9207, 14468, 22738, 35737, 56164, 88268, 138726, 218024, 342652, 538524, 846358, 1330160, 2090522, 3285526, 5163632, 8115323, 12754288, 20045027, 31503382

Offset: 0

David W. Wilson

nonn

Original name was: Ascending wiggly sums: number of sums adding to n in which terms alternately increase and decrease.

A composition is up/down if it is alternately strictly increasing and strictly decreasing, starting with an increase. For example, the partition (3,2,2,2,1) has no up/down permutations, even though it does have the anti-run permutation (2,3,2,1,2). - Gus Wiseman, Jan 15 2022

			From _Gus Wiseman_, Jan 15 2022: (Start)
The a(1) = 1 through a(7) = 11 up/down compositions:
  (1)  (2)  (3)    (4)      (5)      (6)        (7)
            (1,2)  (1,3)    (1,4)    (1,5)      (1,6)
                   (1,2,1)  (2,3)    (2,4)      (2,5)
                            (1,3,1)  (1,3,2)    (3,4)
                                     (1,4,1)    (1,4,2)
                                     (2,3,1)    (1,5,1)
                                     (1,2,1,2)  (2,3,2)
                                                (2,4,1)
                                                (1,2,1,3)
                                                (1,3,1,2)
                                                (1,2,1,2,1)
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Wikipedia, Alternating permutation

The case of permutations is A000111.
The undirected version is A025047, ranked by A345167.
The down/up version is A025049, ranked by A350356.
The strict case is A129838, undirected A349054.
The weak version is A129852, down/up A129853.
The version for patterns is A350354.
These compositions are ranked by A350355.
A001250 counts alternating permutations, complement A348615.
A003242 counts Carlitz compositions, complement A261983.
A011782 counts compositions, unordered A000041.
A325534 counts separable partitions, complement A325535.
A345192 counts non-alternating compositions, ranked by A345168.
A345194 counts alternating patterns, complement A350252.
A349052 counts weakly alternating compositions, complement A349053.
Cf. A008965, A049774, A128761, A344604, A344605, A344614, A344615, A345195, A349057, A349800.

updoQ[y_]:=And@@Table[If[EvenQ[m],y[[m]]>y[[m+1]],y[[m]]Gus Wiseman, Jan 15 2022 *)

a(n) = 1 + A025047(n) - A025049(n) = Sum_k A059882(n,k). - Henry Bottomley, Feb 05 2001

a(n) ~ c * d^n, where d = 1.571630806607064114100138865739690782401305155950789062725011227781640624..., c = 0.4408955566119650057730070154620695491718230084159159991449729825619... . - Vaclav Kotesovec, Sep 12 2014

Name and offset changed by Gus Wiseman, Jan 15 2022

A025049 Number of down/up (initially descending) compositions of n.

Original entry on oeis.org

1, 1, 1, 2, 2, 4, 6, 9, 14, 23, 35, 55, 87, 136, 214, 337, 528, 830, 1306, 2051, 3223, 5067, 7962, 12512, 19667, 30908, 48574, 76343, 119982, 188565, 296358, 465764, 732006, 1150447, 1808078, 2841627, 4465992, 7018891, 11031101, 17336823, 27247087, 42822355

Offset: 0

David W. Wilson

nonn

Original name was: Descending wiggly sums: number of sums adding to n in which terms alternately decrease and increase.

A composition is down/up if it is alternately strictly decreasing and strictly increasing, starting with a decrease. For example, the partition (3,2,2,2,1) has no down/up permutations, even though it does have the anti-run permutation (2,1,2,3,2). - Gus Wiseman, Jan 28 2022

			From _Gus Wiseman_, Jan 28 2022: (Start)
The a(1) = 1 through a(8) = 14 down/up compositions:
  (1)  (2)  (3)    (4)    (5)      (6)        (7)        (8)
            (2,1)  (3,1)  (3,2)    (4,2)      (4,3)      (5,3)
                          (4,1)    (5,1)      (5,2)      (6,2)
                          (2,1,2)  (2,1,3)    (6,1)      (7,1)
                                   (3,1,2)    (2,1,4)    (2,1,5)
                                   (2,1,2,1)  (3,1,3)    (3,1,4)
                                              (4,1,2)    (3,2,3)
                                              (2,1,3,1)  (4,1,3)
                                              (3,1,2,1)  (5,1,2)
                                                         (2,1,3,2)
                                                         (2,1,4,1)
                                                         (3,1,3,1)
                                                         (4,1,2,1)
                                                         (2,1,2,1,2)
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Mohammed L. Nadji, Moussa Ahmia, Daniel F. Checa, and José L. Ramírez, Arndt Compositions with Restricted Parts, Palindromes, and Colored Variants, J. Int. Seq. (2025) Vol. 28, Issue 3, Article 25.3.6. See p. 12.
Wikipedia, Alternating permutation

The case of permutations is A000111.
The undirected version is A025047, ranked by A345167.
The up/down version is A025048, ranked by A350355.
The strict case is A129838, undirected A349054.
The weak version is A129853, up/down A129852.
The version for patterns is A350354.
These compositions are ranked by A350356.
A001250 counts alternating permutations, complement A348615.
A003242 counts Carlitz compositions, complement A261983.
A011782 counts compositions, unordered A000041.
A325534 counts separable partitions, complement A325535.
A345192 counts non-alternating compositions, ranked by A345168.
A345194 counts alternating patterns, complement A350252.
A349052 counts weakly alternating compositions, complement A349053.
Cf. A008965, A049774, A128761, A344604, A344605, A344614, A344615, A345195, A349057, A349800.

doupQ[y_]:=And@@Table[If[EvenQ[m],y[[m]]y[[m+1]]],{m,1,Length[y]-1}];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],doupQ]],{n,0,15}] (* Gus Wiseman, Jan 28 2022 *)

a(n) = 1 + A025047(n) - A025048(n) = Sum_{k=1..n} A059883(n,k). - Henry Bottomley, Feb 05 2001

a(0)=1 prepended by Alois P. Heinz, Jan 20 2022

Name changed by Gus Wiseman, Jan 28 2022

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

A350355 Numbers k such that the k-th composition in standard order is up/down.

Original entry on oeis.org

0, 1, 2, 4, 6, 8, 12, 13, 16, 20, 24, 25, 32, 40, 41, 48, 49, 50, 54, 64, 72, 80, 81, 82, 96, 97, 98, 102, 108, 109, 128, 144, 145, 160, 161, 162, 166, 192, 193, 194, 196, 198, 204, 205, 216, 217, 256, 272, 288, 289, 290, 320, 321, 322, 324, 326, 332, 333, 384

Offset: 1

Gus Wiseman, Jan 15 2022

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.

			The terms together with the corresponding compositions begin:
   0: ()
   1: (1)
   2: (2)
   4: (3)
   6: (1,2)
   8: (4)
  12: (1,3)
  13: (1,2,1)
  16: (5)
  20: (2,3)
  24: (1,4)
  25: (1,3,1)
  32: (6)
  40: (2,4)
  41: (2,3,1)
  48: (1,5)
  49: (1,4,1)
  50: (1,3,2)
  54: (1,2,1,2)

The case of permutations is counted by A000111.
These compositions are counted by A025048, down/up A025049.
The strict case is counted by A129838, undirected A349054.
The weak version is counted by A129852, down/up A129853.
The version for anti-runs is A333489, a superset, complement A348612.
This is the up/down case of A345167, counted by A025047.
Counting patterns of this type gives A350354.
The down/up version is A350356.
A001250 counts alternating permutations, complement A348615.
A003242 counts anti-run compositions.
A011782 counts compositions, unordered A000041.
A345192 counts non-alternating compositions, ranked by A345168.
A349052 counts weakly alternating compositions, complement A349053.
A349057 ranks non-weakly alternating compositions.
Statistics of standard compositions:
- Length is A000120.
- Sum is A070939.
- Heinz number is A333219.
- Number of maximal anti-runs is A333381.
- Number of distinct parts is A334028.
Classes of standard compositions:
- Partitions are A114994, strict A333256.
- Multisets are A225620, strict A333255.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Patterns are A333217.
Cf. A008965, A049774, A095684, A106356, A238279, A344604, A344614, A344615, A345169, A345170, A345172, A349051, A349799.

updoQ[y_]:=And@@Table[If[EvenQ[m],y[[m]]>y[[m+1]],y[[m]]

A345167 = A350355 \/ A350356.

A350356 Numbers k such that the k-th composition in standard order is down/up.

Original entry on oeis.org

0, 1, 2, 4, 5, 8, 9, 16, 17, 18, 22, 32, 33, 34, 38, 44, 45, 64, 65, 66, 68, 70, 76, 77, 88, 89, 128, 129, 130, 132, 134, 140, 141, 148, 152, 153, 176, 177, 178, 182, 256, 257, 258, 260, 262, 264, 268, 269, 276, 280, 281, 296, 297, 304, 305, 306, 310, 352, 353

Offset: 1

Gus Wiseman, Jan 15 2022

nonn

A composition is down/up if it is alternately strictly increasing and strictly decreasing, starting with a decrease. For example, the partition (3,2,2,2,1) has no down/up permutations, even though it does have the anti-run permutation (2,1,2,3,2).

			The terms together with the corresponding compositions begin:
   0: ()
   1: (1)
   2: (2)
   4: (3)
   5: (2,1)
   8: (4)
   9: (3,1)
  16: (5)
  17: (4,1)
  18: (3,2)
  22: (2,1,2)
  32: (6)
  33: (5,1)
  34: (4,2)
  38: (3,1,2)
  44: (2,1,3)
  45: (2,1,2,1)

Gus Wiseman, Statistics, classes, and transformations of standard compositions
Wikipedia, Alternating permutation

The case of permutations is counted by A000111.
These compositions are counted by A025049, up/down A025048.
The strict case is counted by A129838, undirected A349054.
The weak version is counted by A129853, up/down A129852.
The version for anti-runs is A333489, a superset, complement A348612.
This is the down/up case of A345167, counted by A025047.
Counting patterns of this type gives A350354.
The up/down version is A350355.
A001250 counts alternating permutations, complement A348615.
A003242 counts anti-run compositions.
A011782 counts compositions, unordered A000041.
A345192 counts non-alternating compositions, ranked by A345168.
A349052 counts weakly alternating compositions, complement A349053.
A349057 ranks non-weakly alternating compositions.
Statistics of standard compositions:
- Length is A000120.
- Sum is A070939.
- Heinz number is A333219.
- Number of maximal anti-runs is A333381.
- Number of distinct parts is A334028.
Classes of standard compositions:
- Partitions are A114994, strict A333256.
- Multisets are A225620, strict A333255.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Patterns are A333217.
Cf. A008965, A049774, A095684, A106356, A238279, A344604, A344614, A344615, A345169, A345170, A345172, A349051, A349799.

doupQ[y_]:=And@@Table[If[EvenQ[m],y[[m]]y[[m+1]]],{m,1,Length[y]-1}];
stc[n_]:=Differences[Prepend[Join@@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Select[Range[0,100],doupQ[stc[#]]&]

A345167 = A350355 \/ A350356.

cp's OEIS Frontend

A025048 Number of up/down (initially ascending) compositions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A025049 Number of down/up (initially descending) compositions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A350355 Numbers k such that the k-th composition in standard order is up/down.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A350356 Numbers k such that the k-th composition in standard order is down/up.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula