A337504 Number of compositions of 2*n with n maximal anti-runs.

1, 1, 3, 8, 13, 33, 112, 286, 769, 2288, 6695, 18745, 54654, 160888, 467402, 1362378, 4016517, 11807966, 34708018, 102451390, 302870005, 895207191, 2650590597, 7859253320, 23316653154, 69231883374, 205773157904, 612021943421, 1821435719846, 5424528040529, 16165017705176

Offset: 0

Author

Gus Wiseman, Sep 04 2020

Keywords

• nonn

Comments

An anti-run is a sequence with no adjacent equal parts.

Examples

			The a(0) = 1 through a(4) = 13 compositions:
  ()  (2)  (2,2)    (2,2,2)      (2,2,2,2)
           (1,1,2)  (1,1,1,3)    (1,1,1,1,4)
           (2,1,1)  (1,1,2,2)    (1,1,2,2,2)
                    (2,2,1,1)    (2,2,2,1,1)
                    (3,1,1,1)    (4,1,1,1,1)
                    (1,1,1,2,1)  (1,1,1,1,3,1)
                    (1,1,2,1,1)  (1,1,1,2,2,1)
                    (1,2,1,1,1)  (1,1,1,3,1,1)
                                 (1,1,2,2,1,1)
                                 (1,1,3,1,1,1)
                                 (1,2,2,1,1,1)
                                 (1,3,1,1,1,1)
                                 (2,1,1,1,1,2)
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..200

Crossrefs

A106356 has this as main diagonal n = 2*k.

A336108 is the version for runs.

A337505 is the version for patterns.

A337564 is the version for runs in patterns.

A003242 counts anti-run compositions.

A011782 counts compositions.

A124767 counts runs in standard compositions.

A238343 counts compositions by descents.

A333213 counts compositions by weak ascents.

A333381 counts anti-runs in standard compositions.

A333382 counts adjacent unequal pairs in standard compositions.

A333489 ranks anti-runs.

A333755 counts compositions by number of runs.

A333769 gives run-lengths in standard compositions.

A337565 gives anti-run lengths in standard compositions.

Cf. A106351, A124762, A233564, A235998, A238130, A238279, A333214, A333216.

Programs

Mathematica

Table[Length[Select[Join@@Permutations/@IntegerPartitions[2*n],Length[Split[#,UnsameQ]]==n&]],{n,0,10}]

PARI

a(n)={polcoef(polcoef(1 - y + y*(y-1)/(y - 1 - sum(d=1, 2*n, (y-1)^d*x^d/(1 - x^d) + O(x^(2*n+1)))), 2*n, x), n, y)} \\ Andrew Howroyd, Feb 02 2021

Formula

a(n) = [x^(2*n)*y^n] 1 - y + y*(y-1)/(y - 1 - Sum_{d>=1} (y-1)^d*x^d/(1 - x^d)). - Andrew Howroyd, Feb 02 2021

Extensions

Terms a(11) and beyond from Andrew Howroyd, Feb 02 2021