A067370 -id:A067370 - cp's OEIS frontend

A067318 Sum of the reflection lengths of all permutations of n letters.

0, 1, 7, 46, 326, 2556, 22212, 212976, 2239344, 25659360, 318540960, 4261576320, 61148511360, 937030429440, 15275952518400, 264030355814400, 4823280687052800, 92865738644582400, 1879691760950169600, 39905092126771200000, 886664974825728000000

Offset: 1

H. Nick Hann (nickhann(AT)aol.com), Jan 15 2002

The reflection length of a permutation is the minimum number of transpositions needed to express the permutation.
May also be called the "weight" of the symmetric group S_n.
a(n) is the number of n+1-permutations that have at least 3 cycles. a(n) = Sum_{k=3..n+1} A132393(n+1,k). Cf. A001563 (n-permutations with at least 2 cycles). - Geoffrey Critzer, Dec 01 2013
The number of covering relations in the middle order on S_n. - Bridget Tenner, Jul 11 2025

			a(3)=7 since the permutations are 1, (12), (13), (23), (12)(13) and (13)(12). The sum of reflection lengths of all elements in S_3 is 0+1+1+1+2+2=7.
The terms satisfy the series: x/(1-x) = x/((1+x)*(1+2*x)*(1+3*x)) + 7*x^2/((1+x)*(1+2*x)*(1+3*x)*(1+4*x)) + 46*x^3/((1+x)*(1+2*x)*(1+3*x)*(1+4*x)*(1+5*x)) + 326*x^4/((1+x)*(1+2*x)*(1+3*x)*(1+4*x)*(1+5*x)*(1+6*x)) + ... - _Paul D. Hanna_, Aug 28 2012

N. Hann, Average Weight of a Random Permutation, preprint, 2002. [Apparently unpublished]

G. C. Greubel, Table of n, a(n) for n = 1..445 (terms 1..100 from T. D. Noe).
Mathilde Bouvel, Luca Ferrari, and Bridget Eileen Tenner, Between weak and Bruhat: the middle order on permutations, Graphs and Combin., 41 (2025), #34.
Emma Colaric, Ryan DeMuse, Jeremy L. Martin, and Mei Yin, Interval parking functions, arXiv:2006.09321 [math.CO], 2020.
Walter Feit, Roger Lyndon, and Leonard L. Scott, A remark on permutations, Journal of Combinatorial Theory (A) 18 234-235 (1975).
Loïc Foissy, The antipode of of [sic] a Com-PreLie Hopf algebra, arXiv:2406.01120 [math.CO], 2024. See p. 9.
Briana Foster-Greenwood and Cathy Kriloff, Spectra of Cayley Graphs of Complex Reflection Groups, arXiv preprint arXiv:1502.07392 [math.CO], 2015. (See remarks following Cor. 4.6.)
H. N. Hann, Symmetric Canonical Form [broken link]
Roberto Mantaci and Fanja Rakotondrajao, A permutation representation that knows what "Eulerian" means, Discrete Mathematics and Theoretical Computer Science, 4 101-108, (2001).

Cf. A000254, A001563, A001705, A062119, A067369, A067370, A084938.

ZL :=[S, {S = Set(Cycle(Z),3 <= card)}, labelled]: seq(combstruct[count](ZL, size=n), n=2..22); # Zerinvary Lajos, Mar 25 2008

a[n_] := n!*(n - HarmonicNumber[n]); Table[a[n], {n, 1, 21}](* Jean-François Alcover, Feb 10 2012 *)
nn=22;Drop[Range[0,nn]!CoefficientList[Series[1/(1-x)-1-Log[1/(1-x)]-Log[1/(1-x)]^2/2!,{x,0,nn}],x],2] (* Geoffrey Critzer, Dec 01 2013 *)

A067318(n):=n*n! - abs(stirling1(n+1, 2))$
makelist(A067318(n),n,1,30); /* Martin Ettl, Nov 03 2012 */

{a(n)=if(n==0,0,if(n==1, 1, 1-polcoeff(sum(k=1, n-1, a(k)*x^k/prod(j=1, k+2, (1+j*x+x*O(x^n)) ) ), n)))} /* Paul D. Hanna, Aug 28 2012 */

a(n) = n!*(0/1+1/2+...+(n-1)/n) = n!*(n - H_n), where H_n = Sum_{k=1..n} 1/k; a(1) = 0, a(2) = 1, a(n) = n*a(n-1) + (n-1)*(n-1)!.
a(n) = n*n! - abs(stirling1(n+1, 2)) (cf. A000254). E.g.f.: (x+(1-x)*log(1-x))/(1-x)^2. - Vladeta Jovovic, Feb 01 2003
a(n) = T(n, n-1) for the triangle read by rows: [0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, ...] DELTA [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, ...] where DELTA is the operator defined in A084938. - Philippe Deléham, Nov 30 2003
G.f.: x/(1-x) = Sum_{n>=1} a(n)*x^n/Product_{k=1..n+2} (1+k*x). - Paul D. Hanna, Aug 28 2012
a(n) = A062119(n) - A001705(n-1). - Anton Zakharov, Sep 22 2016

Definition and example edited by Bridget Tenner, Jul 11 2025

A067369 Weight of the alternating group (A_n) in transpositions.

Original entry on oeis.org

0, 0, 4, 22, 166, 1266, 11166, 106128, 1122192, 12809520, 159451920, 2128973760, 30594214080, 468275713920, 7641089769600, 131971588761600, 2412294180710400, 46422407927347200, 940023724189132800, 19949344876532736000, 443393309963068416000, 10288553164881868800000

Offset: 1

Nick Hann (nickhann(AT)aol.com), Jan 20 2002

Sequences A067369, A067370 and A067318 are related: A067318 = A067369 + A067370. A067318 counts transpositions in the symmetric group, denoted S_n. One can think of the transpositions in S_n as being split between the alternating group A_n and its complement, which we call the periphery and denote P_N. For n >= 3, A067369 v(P_N) and A067370 v(A_n) always differ by (n-2)!. When n is odd, v(A_n) is larger; when n is even, v(P_N) is larger. This gives new meaning to the name alternating group. The average weight of permutation in A_n converges with the average weight for a permutation in P_N at infinity.

Charlie Neder and Muniru A Asiru, Table of n, a(n) for n = 1..445

Cf. A067370, A067318.

Concatenation([0],List([2..25],n->(1/2)*((-1)^(n+1)*Factorial(n-2)+n*Factorial(n)-AbsInt(Stirling1(n+1,2))))); # Muniru A Asiru, Dec 15 2018

seq(coeff(series(factorial(n)*(1/2)*(-(1+x)*log(1+x)+x+x/(1-x)^2+log(1-x)/(1-x)+2),x,n+1), x, n), n = 1 .. 25); # Muniru A Asiru, Dec 15 2018

a[n_] := 1/2*((-1)^(n+1)*(n-2)!+n*n!-Abs[StirlingS1[n+1, 2]]); a[1]=0; Table[a[n], {n, 1, 20}] (* Jean-François Alcover, Jan 12 2015, after Vladeta Jovovic *)

a(n)={if(n < 2, 0, 1/2*((-1)^(n+1)*(n-2)!+n*n!-abs(stirling(n+1, 2, 1))))} \\ Andrew Howroyd, Dec 14 2018

a(n) = a(n-1) + [(n-1)!/2]*[vbar(P_N-1)+1]*[n-1)] where vbar(P_N) is the average weight of a permutation in P_N, the periphery of A_n. vbar(P_N-1) is p(n-1)/(n-1)!2 where p(n) is from sequence A067370.
From Vladeta Jovovic, Feb 02 2003: (Start)
a(n) = (1/2)*((-1)^(n+1)*(n-2)! + n*n! - abs(Stirling1(n+1, 2))), n > 1.
E.g.f.: (1/2)*(-(1+x)*log(1+x) + x + x/(1-x)^2 + log(1-x)/(1-x) + 2). (End)

More terms from Vladeta Jovovic, Feb 02 2003

a(20)-a(22) from Charlie Neder, Dec 14 2018

cp's OEIS Frontend

A067318 Sum of the reflection lengths of all permutations of n letters.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Formula

Extensions