A374742 Number of integer compositions of n whose leaders of weakly decreasing runs are identical.

1, 1, 2, 3, 5, 8, 13, 21, 34, 54, 87, 138, 220, 349, 556, 881, 1403, 2229, 3551, 5653, 9019, 14387, 22988, 36739, 58785, 94100, 150765, 241658, 387617, 622002, 998658, 1604032, 2577512, 4143243, 6662520, 10716931, 17243904, 27753518, 44680121, 71947123, 115880662

Offset: 0

Author

Gus Wiseman, Jul 25 2024

Keywords

• nonn

Comments

The weakly decreasing run-leaders of a sequence are obtained by splitting into maximal weakly decreasing subsequences and taking the first term of each.

Examples

			The composition (3,1,3,2,1,3,3) has maximal weakly decreasing subsequences ((3,1),(3,2,1),(3,3)), with leaders (3,3,3), so is counted under a(16).
The a(0) = 1 through a(6) = 13 compositions:
  ()  (1)  (2)   (3)    (4)     (5)      (6)
           (11)  (21)   (22)    (32)     (33)
                 (111)  (31)    (41)     (42)
                        (211)   (212)    (51)
                        (1111)  (221)    (222)
                                (311)    (321)
                                (2111)   (411)
                                (11111)  (2112)
                                         (2121)
                                         (2211)
                                         (3111)
                                         (21111)
                                         (111111)
		

Links

• John Tyler Rascoe, Table of n, a(n) for n = 0..200
• Gus Wiseman, Sequences counting and ranking compositions by their leaders (for six types of runs).

Crossrefs

Ranked by A374744 = positions of identical rows in A374740, cf. A374629.

Types of runs (instead of weakly decreasing):

- For leaders of identical runs we have A000005 for n > 0, ranks A272919.

- For leaders of anti-runs we have A374517, ranks A374519.

- For leaders of strictly increasing runs we have A374686, ranks A374685.

- For leaders of weakly increasing runs we have A374631, ranks A374633.

- For leaders of strictly decreasing runs we have A374760, ranks A374759.

Types of run-leaders (instead of identical):

- For strictly decreasing leaders we have A374746.

- For weakly decreasing leaders we have A374747.

- For distinct leaders we have A374743, ranks A374701.

- For weakly increasing leaders we appear to have A188900.

A003242 counts anti-run compositions, ranks A333489.

A011782 counts compositions.

A238130, A238279, A333755 count compositions by number of runs.

A274174 counts contiguous compositions, ranks A374249.

A335456 counts patterns matched by compositions.

A335548 counts non-contiguous compositions, ranks A374253.

A373949 counts compositions by run-compressed sum, opposite A373951.

A374748 counts compositions by sum of leaders of weakly decreasing runs.

Cf. A000009, A106356, A188920, A189076, A238343, A261982, A333213, A374632, A374634, A374635, A374741.

Programs

Mathematica

Table[Length[Select[Join@@Permutations /@ IntegerPartitions[n],SameQ@@First/@Split[#,GreaterEqual]&]],{n,0,15}]

PARI

B(i) = x^i/(1-x^i) * sum(j=1,i-1, x^j*prod(k=1,j, (1-x^k)^(-1)))
A_x(N) = {my(x='x+O('x^N)); Vec(1+sum(i=1,N,-1+(1+x^i/(1-x^i))/(1-B(i))))}
A_x(30) \\ John Tyler Rascoe, Apr 29 2025

Formula

G.f.: 1 + Sum_{i>0} -1 + (1 + x^i/(1 - x^i))/(1 - B(i,x)) where B(i,x) = x^i/(1 - x^i) * Sum_{j=1..i-1} x^j * Product_{k=1..j} (1 - x^k)^(-1). - John Tyler Rascoe, Apr 29 2025

Extensions

a(24)-a(40) from Alois P. Heinz, Jul 26 2024