cp's OEIS Frontend

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

%I A384907 #13 Jun 23 2025 00:42:37
%S A384907 1,1,1,5,17,97,587,4291,33109,319967,3106433,35554459,419889707,
%T A384907 5632467097,77342295637,1201240551077,18804238105133,328322081898745,
%U A384907 5832312989183807,113154541564902427,2229027473451951265,47899977701182298255,1037672943682453127645
%N A384907 Number of permutations of {1..n} with all distinct lengths of maximal anti-runs (not increasing by 1).
%H A384907 Christian Sievers, <a href="/A384907/b384907.txt">Table of n, a(n) for n = 0..449</a>
%F A384907 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).
%e A384907 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).
%e A384907 The a(0) = 1 through a(4) = 17 permutations:
%e A384907   ()  (1)  (2,1)  (1,3,2)  (1,2,4,3)
%e A384907                   (2,1,3)  (1,3,2,4)
%e A384907                   (2,3,1)  (1,4,2,3)
%e A384907                   (3,1,2)  (1,4,3,2)
%e A384907                   (3,2,1)  (2,1,3,4)
%e A384907                            (2,1,4,3)
%e A384907                            (2,3,1,4)
%e A384907                            (2,4,1,3)
%e A384907                            (2,4,3,1)
%e A384907                            (3,1,4,2)
%e A384907                            (3,2,1,4)
%e A384907                            (3,2,4,1)
%e A384907                            (3,4,2,1)
%e A384907                            (4,1,3,2)
%e A384907                            (4,2,1,3)
%e A384907                            (4,3,1,2)
%e A384907                            (4,3,2,1)
%t A384907 Table[Length[Select[Permutations[Range[n]],UnsameQ@@Length/@Split[#,#2!=#1+1&]&]],{n,0,10}]
%o A384907 (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
%Y A384907 For subsets instead of permutations we have A384177.
%Y A384907 For strict partitions we have A384880, for runs A384178.
%Y A384907 For partitions we have A384885, for runs A384884.
%Y A384907 For runs instead of anti-runs we have A384891.
%Y A384907 A010027 counts permutations by maximal anti-runs, for runs A123513.
%Y A384907 A034839 counts subsets by number of maximal runs, for strict partitions A116674.
%Y A384907 A098859 counts Wilf partitions (distinct multiplicities), complement A336866.
%Y A384907 A384893 counts subsets by number of maximal anti-runs, for partitions A268193, A384905.
%Y A384907 Cf. A000255, A044813, A072574, A242882, A325325, A328592, A329739, A351202, A356606, A384886, A384892.
%K A384907 nonn
%O A384907 0,4
%A A384907 _Gus Wiseman_, Jun 21 2025
%E A384907 a(11) and beyond from _Christian Sievers_, Jun 22 2025