login
Number of alternating compositions, i.e., compositions with alternating increases and decreases, starting with either an increase or a decrease.
157

%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