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.

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