A337507 Number of length-n sequences covering an initial interval of positive integers with exactly two maximal anti-runs, or with one pair of adjacent equal parts.

0, 0, 1, 4, 24, 176, 1540, 15672, 181916, 2372512, 34348932, 546674120, 9486840748, 178285201008, 3607174453844, 78177409231768, 1806934004612220, 44367502983673664, 1153334584544496676, 31643148872573831016

Offset: 0

Author

Gus Wiseman, Sep 06 2020

Keywords

• nonn

Comments

An anti-run is a sequence with no adjacent equal parts. For example, the maximal anti-runs in (3,1,1,2,2,2,1) are ((3,1),(1,2),(2),(2,1)). In general, there is one more maximal anti-run than the number of pairs of adjacent equal parts.

Examples

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

Crossrefs

A002133 is the version for runs in partitions.

A106357 is the version for compositions.

A337506 has this as column k = 2.

A000670 counts patterns.

A005649 counts anti-run patterns.

A003242 counts anti-run compositions.

A106356 counts compositions by number of maximal anti-runs.

A124762 counts adjacent equal terms in standard compositions.

A124767 counts maximal runs in standard compositions.

A238130/A238279/A333755 count maximal runs in compositions.

A333381 counts maximal anti-runs in standard compositions.

A333382 counts adjacent unequal terms in standard compositions.

A333489 ranks anti-run compositions.

A333769 gives maximal run lengths in standard compositions.

A337565 gives maximal anti-run lengths in standard compositions.

Cf. A019472, A052841, A060223, A106351, A269134, A335461, A337505, A337564.

Programs

Mathematica

kv=2;
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[n],Length[Split[#,UnsameQ]]==kv&]],{n,0,6}]

Formula

a(n > 0) = (n - 1)*A005649(n - 2).