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

1, 1, 1, 3, 3, 5, 23, 25, 43, 63, 345, 365, 665, 949, 1513, 8175, 9003, 15929, 23399, 36949, 51043, 293715, 314697, 570353, 826817, 1318201, 1810393, 2766099, 14180139, 15600413, 27707879, 40501321, 63981955, 88599903, 134362569, 181491125, 923029217

Offset: 0

Author

Gus Wiseman, Jun 19 2025

Keywords

• nonn

Examples

			The permutation (1,2,6,7,8,9,3,4,5) has maximal runs ((1,2),(6,7,8,9),(3,4,5)), with lengths (2,4,3), so is counted under a(9).
The a(0) = 1 through a(7) = 25 permutations:
  ()  (1)  (12)  (123)  (1234)  (12345)  (123456)  (1234567)
                 (231)  (2341)  (23451)  (123564)  (1234675)
                 (312)  (4123)  (34512)  (123645)  (1234756)
                                (45123)  (124563)  (1245673)
                                (51234)  (126345)  (1273456)
                                         (145623)  (1456723)
                                         (156234)  (1672345)
                                         (231456)  (2314567)
                                         (234156)  (2345167)
                                         (234561)  (2345671)
                                         (312456)  (3124567)
                                         (345126)  (3456127)
                                         (345612)  (3456712)
                                         (412356)  (4567123)
                                         (451236)  (4567231)
                                         (456231)  (4567312)
                                         (456312)  (5123467)
                                         (561234)  (5612347)
                                         (562341)  (5671234)
                                         (564123)  (6712345)
                                         (612345)  (6723451)
                                         (634512)  (6751234)
                                         (645123)  (7123456)
                                                   (7345612)
                                                   (7561234)
		

Links

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

Crossrefs

Counting by number of maximal anti-runs gives A010027, for runs A123513.

For subsets instead of permutations we have A384175, complement A384176.

For partitions we have A384884 (anti-runs A384885), strict A384178 (anti-runs A384880).

For equal instead of distinct lengths we have A384892.

For anti-runs instead of runs we have A384907.

A000041 counts integer partitions, strict A000009.

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

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

A356606 counts strict partitions without a neighborless part, complement A356607.

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

Cf. A000255, A044813, A072574, A242882, A287170, A325324, A325325, A328592, A329739, A351202, A384177, A384886.

Programs

Mathematica

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

PARI

lista(n)=my(b(n)=sum(i=0,n-1,(-1)^i*(n-i)!*binomial(n-1,i)), d=floor(sqrt(2*n)), p=prod(i=1,n,1+x*y^i,1+O(y*y^n)*((1-x^(n+1))/(1-x))+O(x*x^d))); Vec(1+sum(i=1,d,i!*b(i)*polcoef(p,i))) \\ Christian Sievers, Jun 22 2025

Formula

a(n) = Sum_{k=1..n} ( T(n,k) * A000255(k-1) ) for n>=1, where T(n,k) is the number of compositions of n into k distinct parts (cf. A072574). - Christian Sievers, Jun 22 2025

Extensions

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