A059882 -id:A059882 - 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

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

Original entry on oeis.org

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

A059883 As upper right triangle: descending wiggly sums to n where first term is k (sums in which terms alternately decrease and increase; zagzig partitions).

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 2, 1, 1, 1, 1, 0, 2, 2, 2, 1, 1, 1, 0, 4, 3, 2, 2, 1, 1, 1, 0, 6, 6, 3, 3, 2, 1, 1, 1, 0, 9, 9, 6, 3, 3, 2, 1, 1, 1, 0, 14, 13, 10, 6, 4, 3, 2, 1, 1, 1, 0, 23, 21, 15, 10, 6, 4, 3, 2, 1, 1, 1, 0, 35, 33, 24, 15, 10, 7, 4, 3, 2, 1, 1, 1, 0, 55, 52, 38, 25, 15, 10, 7, 4, 3, 2, 1, 1, 1

Offset: 1

Henry Bottomley, Feb 05 2001

			Rows start (1,0,0,0,0,...), (1,1,0,1,...), (1,1,1,...) etc. T(10,4)=6 since 10 can be written as 4+2+4, 4+2+3+1, 4+1+5, 4+1+4+1, 4+1+3+2, or 4+1+2+1+2.

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

Column sums are A025049. Cf. A025047, A025048, A059881, A059882.

If n>k>0 T(n, k)=sum_j[S(n-k, j)] over k>j and if n>0 T(n, n)=1; where S(n, k)=A059882(n, k) and if n>k>0, S(n, k)=sum_j[T(n-k, j)] over j>k (note reversal) and if n>0 S(n, n)=1.

A059881 As upper right triangle: wiggly sums to n where first term is k (sums in which terms alternately increase and decrease or vice versa; zigzag and zagzig partitions).

Original entry on oeis.org

1, 0, 1, 1, 1, 1, 2, 0, 1, 1, 2, 2, 1, 1, 1, 4, 4, 1, 1, 1, 1, 6, 5, 3, 2, 1, 1, 1, 9, 8, 5, 2, 2, 1, 1, 1, 14, 13, 9, 4, 3, 2, 1, 1, 1, 23, 19, 14, 8, 3, 3, 2, 1, 1, 1, 35, 31, 20, 13, 7, 4, 3, 2, 1, 1, 1, 55, 49, 32, 20, 12, 6, 4, 3, 2, 1, 1, 1, 87, 76, 50, 32, 18, 11, 7, 4, 3, 2, 1, 1, 1, 136

Offset: 1

Henry Bottomley, Feb 05 2001

			Rows start (1,0,1,2,2,...), (1,1,0,2,...), (1,1,1,...) etc. T(10,4)=8 since 10 can be written as 4+6, 4+5+1, 4+2+4, 4+2+3+1, 4+1+5, 4+1+4+1, 4+1+3+2, or 4+1+2+1+2.

Column sums are A025047. Cf. A025048, A025049, A059882, A059883.

T(n, k) =A059882(n, k)+A059883(n, k) if n>k>0; T(n, n)=1 if n>0.

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A059883 As upper right triangle: descending wiggly sums to n where first term is k (sums in which terms alternately decrease and increase; zagzig partitions).

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A059881 As upper right triangle: wiggly sums to n where first term is k (sums in which terms alternately increase and decrease or vice versa; zigzag and zagzig partitions).

Views

Author

Keywords

Examples

Crossrefs

Formula