login
Number of compositions of n whose run-lengths are weakly increasing.
13

%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