login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Number of compositions with alternating parts weakly decreasing (or weakly increasing).
22

%I #16 Mar 25 2021 19:02:03

%S 1,1,2,4,7,12,20,32,51,79,121,182,272,399,582,839,1200,1700,2394,3342,

%T 4640,6397,8771,11955,16217,21878,29386,39285,52301,69334,91570,

%U 120465,157929,206313,268644,348674,451185,582074,748830,960676,1229208,1568716,1997064

%N Number of compositions with alternating parts weakly decreasing (or weakly increasing).

%C These are finite sequences q of positive integers summing to n such that q(i) >= q(i+2) for all possible i.

%C The strict case (alternating parts are strictly decreasing) is A000041. Is there a bijective proof?

%C Yes. Construct a Ferrers diagram by placing odd parts horizontally and even parts vertically in a fishbone pattern. The resulting Ferrers diagram will be for an ordinary partition and the process is reversible. It does not appear that this method can be applied to give a formula for this sequence. - _Andrew Howroyd_, Mar 25 2021

%H Andrew Howroyd, <a href="/A342528/b342528.txt">Table of n, a(n) for n = 0..500</a>

%H Gus Wiseman, <a href="/A069916/a069916.txt">Sequences counting and ranking partitions and compositions by their differences and quotients</a>.

%e The a(1) = 1 through a(6) = 20 compositions:

%e (1) (2) (3) (4) (5) (6)

%e (11) (12) (13) (14) (15)

%e (21) (22) (23) (24)

%e (111) (31) (32) (33)

%e (121) (41) (42)

%e (211) (131) (51)

%e (1111) (212) (141)

%e (221) (222)

%e (311) (231)

%e (1211) (312)

%e (2111) (321)

%e (11111) (411)

%e (1212)

%e (1311)

%e (2121)

%e (2211)

%e (3111)

%e (12111)

%e (21111)

%e (111111)

%t Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],GreaterEqual@@Plus@@@Reverse/@Partition[#,2,1]&]],{n,0,15}]

%o (PARI) seq(n)={my(p=1/prod(k=1, n, 1-y*x^k + O(x*x^n))); Vec(1+sum(k=1, n, polcoef(p,k,y)*(polcoef(p,k-1,y) + polcoef(p,k,y))))} \\ _Andrew Howroyd_, Mar 24 2021

%Y The even-length case is A114921.

%Y The version with alternating parts unequal is A224958 (unordered: A000726).

%Y The version with alternating parts equal is A342527.

%Y A000041 counts weakly increasing (or weakly decreasing) compositions.

%Y A000203 adds up divisors.

%Y A002843 counts compositions with all adjacent parts x <= 2y.

%Y A003242 counts anti-run compositions.

%Y A069916/A342492 = decreasing/increasing first quotients.

%Y A070211/A325546 = weakly decreasing/increasing differences.

%Y A175342/A325545 = constant/distinct differences.

%Y A342495 = constant first quotients (unordered: A342496, strict: A342515, ranking: A342522).

%Y Cf. A001522, A008965, A048004, A059966, A062968, A064410, A064428, A065608, A167606, A325557, A342519.

%K nonn

%O 0,3

%A _Gus Wiseman_, Mar 24 2021

%E Terms a(21) and beyond from _Andrew Howroyd_, Mar 24 2021