A384892 Number of permutations of {1..n} with all equal lengths of maximal runs (increasing by 1).

1, 1, 2, 4, 13, 54, 314, 2120, 16700, 148333, 1468512, 16019532, 190899736, 2467007774, 34361896102, 513137616840, 8178130784179, 138547156531410, 2486151753462260, 47106033220679060, 939765362754015750, 19690321886243848784, 432292066866187743954

Offset: 0

Author

Gus Wiseman, Jun 19 2025

Keywords

• nonn

Examples

			The permutation (1,2,5,6,3,4,7,8) has maximal runs ((1,2),(5,6),(3,4),(7,8)), with lengths (2,2,2,2), so is counted under a(8).
The a(0) = 1 through a(4) = 13 permutations:
  ()  (1)  (12)  (123)  (1234)
           (21)  (132)  (1324)
                 (213)  (1432)
                 (321)  (2143)
                        (2413)
                        (2431)
                        (3142)
                        (3214)
                        (3241)
                        (3412)
                        (4132)
                        (4213)
                        (4321)
		

Links

• Christian Sievers, Table of n, a(n) for n = 0..450

Crossrefs

For subsets instead of permutations we have A243815, for anti-runs A384889.

For strict partitions and distinct lengths we have A384178, anti-runs A384880.

For integer partitions and distinct lengths we have A384884, anti-runs A384885.

For distinct lengths we have A384891, for anti-runs A384907.

For partitions we have A384904, strict A384886.

A010027 counts permutations by maximal anti-runs, for runs A123513.

A034839 counts subsets by number of maximal runs, for strict partitions A116674.

A098859 counts Wilf partitions (distinct multiplicities), complement A336866.

A384893 counts subsets by number of maximal anti-runs, for partitions A268193, A384905.

Cf. A000255, A044813, A047993, A242882, A325325, A329739, A351202, A384175, A384176, A384177.

Programs

Mathematica

Table[Length[Select[Permutations[Range[n]],SameQ@@Length/@Split[#,#2==#1+1&]&]],{n,0,10}]

PARI

a(n)=if(n,sumdiv(n,d,sum(i=0,d-1,(-1)^i*(d-i)!*binomial(d-1,i))),1) \\ Christian Sievers, Jun 22 2025

Formula

a(n) = Sum_{d|n} A000255(d-1). - Christian Sievers, Jun 22 2025

Extensions

a(11) and beyond from Christian Sievers, Jun 22 2025