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,4

Comments

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

Links

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.

Formula

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

Example

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)

Maple

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

Mathematica

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

Prog

(PARI)
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(k<j, if(f, if(k>1, 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

Crossrefs

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.

Sequence in context: A310007 A158237 A117950 * A050342 A293642 A214286

Adjacent sequences: A025044 A025045 A025046 * A025048 A025049 A025050

Keyword

nonn

Author

David W. Wilson

Extensions

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

Status

approved