%I #53 Mar 19 2024 08:31:48
%S 1,1,1,3,4,7,12,19,29,48,75,118,186,293,460,725,1139,1789,2814,4422,
%T 6949,10924,17168,26979,42404,66644,104737,164610,258707,406588,
%U 639009,1004287,1578363,2480606,3898599,6127152,9629623,15134213,23785388,37381849,58750468
%N Number of alternating compositions, i.e., compositions with alternating increases and decreases, starting with either an increase or a decrease.
%C Original name: Wiggly sums: number of sums adding to n in which terms alternately increase and decrease or vice versa.
%H Alois P. Heinz, <a href="/A025047/b025047.txt">Table of n, a(n) for n = 0..3333</a>
%H Edward A. Bender and E. Rodney Canfield, <a href="https://doi.org/10.37236/417">Locally Restricted Compositions III. Adjacent-Part Periodic Inequalities</a>, Electronic Journal of Combinatorics 17 (2010), #R145.
%F 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
%F a(n) ~ c * d^n, where d = 1.571630806607064114100138865739690782401305155950789062725..., c = 0.82222360450823867604750473815253345888526601460811483897... . - _Vaclav Kotesovec_, Sep 12 2014
%F a(n) = A344604(n) + 1 - n mod 2. - _Gus Wiseman_, Jun 17 2021
%e From _Joerg Arndt_, Dec 28 2012: (Start)
%e There are a(7)=19 such compositions of 7:
%e [ 1] + [ 1 2 1 2 1 ]
%e [ 2] + [ 1 2 1 3 ]
%e [ 3] + [ 1 3 1 2 ]
%e [ 4] + [ 1 4 2 ]
%e [ 5] + [ 1 5 1 ]
%e [ 6] + [ 1 6 ]
%e [ 7] - [ 2 1 3 1 ]
%e [ 8] - [ 2 1 4 ]
%e [ 9] + [ 2 3 2 ]
%e [10] + [ 2 4 1 ]
%e [11] + [ 2 5 ]
%e [12] - [ 3 1 2 1 ]
%e [13] - [ 3 1 3 ]
%e [14] + [ 3 4 ]
%e [15] - [ 4 1 2 ]
%e [16] - [ 4 3 ]
%e [17] - [ 5 2 ]
%e [18] - [ 6 1 ]
%e [19] 0 [ 7 ]
%e For A025048(7)-1=10 of these the first two parts are increasing (marked by '+'),
%e and for A025049(7)-1=8 the first two parts are decreasing (marked by '-').
%e The composition into one part is counted by both A025048 and A025049.
%e (End)
%p b:= proc(n, l, t) option remember; `if`(n=0, 1, add(
%p b(n-j, j, 1-t), j=`if`(t=1, 1..min(l-1, n), l+1..n)))
%p end:
%p a:= n-> 1+add(add(b(n-j, j, i), i=0..1), j=1..n-1):
%p seq(a(n), n=0..40); # _Alois P. Heinz_, Jan 31 2024
%t wigQ[y_]:=Or[Length[y]==0,Length[Split[y]]== Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1];
%t Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],wigQ]],{n,0,15}] (* _Gus Wiseman_, Jun 17 2021 *)
%o (PARI)
%o 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~}
%o seq(n) = concat([1], D(n,0) + D(n,1) - vector(n,j,1)) \\ _Andrew Howroyd_, Jan 31 2024
%Y Dominated by A003242 (anti-run compositions), complement A261983.
%Y The ascending case is A025048.
%Y The descending case is A025049.
%Y The version allowing pairs (x,x) is A344604.
%Y These compositions are ranked by A345167, permutations A349051.
%Y The complement is counted by A345192, ranked by A345168.
%Y The version for patterns is A345194 (with twins: A344605).
%Y A001250 counts alternating permutations, complement A348615.
%Y A011782 counts compositions.
%Y A032020 counts strict compositions.
%Y A106356 counts compositions by number of maximal anti-runs.
%Y A114901 counts compositions where each part is adjacent to an equal part.
%Y A274174 counts compositions with equal parts contiguous.
%Y A325534 counts separable partitions, ranked by A335433.
%Y A325535 counts inseparable partitions, ranked by A335448.
%Y A345164 counts alternating permutations of prime indices.
%Y A345165 counts partitions w/o alternating permutation, ranked by A345171.
%Y A345170 counts partitions w/ alternating permutation, ranked by A345172.
%Y Cf. A000070, A008965, A238279, A333755, A344606, A344614, A344653, A344740, A345163, A345166, A345169.
%K nonn
%O 0,4
%A _David W. Wilson_
%E Better name using a comment of _Franklin T. Adams-Watters_ by _Peter Luschny_, Oct 31 2021