A384907 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

LINKS

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

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). - Christian Sievers, Jun 22 2025

EXAMPLE

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)

MATHEMATICA

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

PROG

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

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.