A384907 Number of permutations of {1..n} with all distinct lengths of maximal anti-runs (not increasing by 1).

1, 1, 1, 5, 17, 97, 587, 4291, 33109, 319967, 3106433, 35554459, 419889707, 5632467097, 77342295637, 1201240551077, 18804238105133, 328322081898745, 5832312989183807, 113154541564902427, 2229027473451951265, 47899977701182298255, 1037672943682453127645

Offset: 0

Author

Gus Wiseman, Jun 21 2025

Keywords

• nonn

Examples

			The permutation (1,2,4,3,5,7,8,6,9) has maximal anti-runs ((1),(2,4,3,5,7),(8,6,9)), with lengths (1,5,3), so is counted under a(9).
The a(0) = 1 through a(4) = 17 permutations:
  ()  (1)  (2,1)  (1,3,2)  (1,2,4,3)
                  (2,1,3)  (1,3,2,4)
                  (2,3,1)  (1,4,2,3)
                  (3,1,2)  (1,4,3,2)
                  (3,2,1)  (2,1,3,4)
                           (2,1,4,3)
                           (2,3,1,4)
                           (2,4,1,3)
                           (2,4,3,1)
                           (3,1,4,2)
                           (3,2,1,4)
                           (3,2,4,1)
                           (3,4,2,1)
                           (4,1,3,2)
                           (4,2,1,3)
                           (4,3,1,2)
                           (4,3,2,1)
		

Links

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

Crossrefs

For subsets instead of permutations we have A384177.

For strict partitions we have A384880, for runs A384178.

For partitions we have A384885, for runs A384884.

For runs instead of anti-runs we have A384891.

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, A072574, A242882, A325325, A328592, A329739, A351202, A356606, A384886, A384892.

Programs

Mathematica

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

PARI

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

Formula

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

Extensions

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