A337505 Number of sequences of length 2*n covering an initial interval of positive integers and splitting into n maximal anti-runs.

1, 2, 24, 440, 10780, 329112, 12006456, 508903824, 24559486380, 1328964785720, 79670488601704, 5240336913228144, 375167786246499064, 29038998659140223600, 2416268289647552828400, 215068032231876851531040, 20389611819955706893052460, 2051184695261785540782403320

Offset: 0

Author

Gus Wiseman, Sep 05 2020

Keywords

• nonn

Comments

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

Examples

			The a(2) = 24 sequences:
  (2,1,2,2)  (1,2,3,3)  (1,2,2,3)  (1,1,2,3)
  (2,2,1,2)  (1,3,3,2)  (1,3,2,2)  (1,1,3,2)
  (1,2,2,1)  (2,1,3,3)  (2,2,1,3)  (2,1,1,3)
  (2,1,1,2)  (2,3,3,1)  (2,2,3,1)  (2,3,1,1)
  (1,1,2,1)  (3,3,1,2)  (3,1,2,2)  (3,1,1,2)
  (1,2,1,1)  (3,3,2,1)  (3,2,2,1)  (3,2,1,1)
		

Links

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

Crossrefs

A336108 is the version for compositions and runs.

A337504 is the version for compositions.

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

A337564 is the version for runs.

A000670 counts sequences covering an initial interval.

A003242 counts anti-run compositions.

A005649 counts anti-runs covering an initial interval.

A124767 counts maximal runs in standard compositions.

A333381 counts maximal anti-runs in standard compositions.

A333769 gives run-lengths in standard compositions.

A337565 gives anti-run lengths in standard compositions.

Cf. A052841, A106351, A106356, A269134, A325535, A333489, A333627, A333755.

Programs

Mathematica

allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
Table[Length[Select[Join@@Permutations/@allnorm[2*n],Length[Split[#,UnsameQ]]==n&]],{n,0,3}]

PARI

\\ here b(n) is A005649.
b(n) = {sum(k=0, n, stirling(n,k,2)*(k + 1)!)}
a(n) = {b(n)*binomial(2*n-1,n)} \\ Andrew Howroyd, Dec 31 2020

Formula

a(n) = A005649(n)*binomial(2*n-1,n). - Andrew Howroyd, Dec 31 2020

Extensions

Terms a(5) and beyond from Andrew Howroyd, Dec 31 2020