A332836 - OEIS

%I #15 Dec 31 2020 17:00:13

%S 1,1,2,4,7,12,24,40,73,128,230,399,712,1241,2192,3833,6746,11792,

%T 20711,36230,63532,111163,194782,340859,596961,1044748,1829241,

%U 3201427,5604504,9808976,17170112,30051470,52601074,92063629,161140256,282033124,493637137,863982135,1512197655

%N Number of compositions of n whose run-lengths are weakly increasing.

%C A composition of n is a finite sequence of positive integers summing to n.

%C Also compositions whose run-lengths are weakly decreasing.

%H Andrew Howroyd, <a href="/A332836/b332836.txt">Table of n, a(n) for n = 0..1000</a>

%e The a(0) = 1 through a(5) = 12 compositions:

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

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

%e                  (21)   (22)    (23)

%e                  (111)  (31)    (32)

%e                         (121)   (41)

%e                         (211)   (122)

%e                         (1111)  (131)

%e                                 (212)

%e                                 (311)

%e                                 (1211)

%e                                 (2111)

%e                                 (11111)

%e For example, the composition (2,3,2,2,1,1,2,2,2) has run-lengths (1,1,2,2,3) so is counted under a(17).

%t Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],LessEqual@@Length/@Split[#]&]],{n,0,10}]

%o (PARI)

%o step(M, m)={my(n=matsize(M)[1]); for(p=m+1, n, my(v=vector((p-1)\m, i, M[p-i*m,i]), s=vecsum(v)); M[p,]+=vector(#M,i,s-if(i<=#v, v[i]))); M}

%o seq(n)={my(M=matrix(n+1, n, i, j, i==1)); for(m=1, n, M=step(M, m)); M[1,n]=0; vector(n+1, i, vecsum(M[i,]))/(n-1)} \\ _Andrew Howroyd_, Dec 31 2020

%Y The version for the compositions themselves (not run-lengths) is A000041.

%Y The case of partitions is A100883.

%Y The case of unsorted prime signature is A304678, with dual A242031.

%Y Permitting the run-lengths to be weakly decreasing also gives A332835.

%Y The complement is counted by A332871.

%Y Unimodal compositions are A001523.

%Y Compositions that are not unimodal are A115981.

%Y Compositions with equal run-lengths are A329738.

%Y Compositions whose run-lengths are unimodal are A332726.

%Y Cf. A001462, A072704, A072706, A100882, A181819, A329744, A329766, A332641, A332727, A332745, A332833, A332834.

%K nonn

%O 0,3

%A _Gus Wiseman_, Feb 29 2020

%E Terms a(21) and beyond from _Andrew Howroyd_, Dec 30 2020