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

Links

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

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

Example

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)

Mathematica

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

Prog

(PARI) lista(n)=my(b(n)=sum(i=0, n-1, (-1)^i*(n-i)!*binomial(n-1, i)), d=sqrtint(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

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.

Sequence in context: A157241 A365083 A196430 * A366594 A265878 A389407

Adjacent sequences: A384888 A384889 A384890 * A384892 A384893 A384894

Keyword

nonn

Author

Gus Wiseman, Jun 19 2025

Extensions

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

Status

approved