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,2

Comments

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

Links

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

Formula

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

Example

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)

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}]

Prog

(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

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.

Sequence in context: A003102 A370847 A304318 * A228843 A317662 A334025

Adjacent sequences: A337502 A337503 A337504 * A337506 A337507 A337508

Keyword

nonn

Author

Gus Wiseman, Sep 05 2020

Extensions

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

Status

approved