%I #66 Jun 06 2024 12:29:50
%S 0,1,7,46,326,2556,22212,212976,2239344,25659360,318540960,4261576320,
%T 61148511360,937030429440,15275952518400,264030355814400,
%U 4823280687052800,92865738644582400,1879691760950169600,39905092126771200000,886664974825728000000
%N Total number of transpositions in all permutations of n letters.
%C May also be called the "weight" of the symmetric group S_n.
%C 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
%D N. Hann, Average Weight of a Random Permutation, preprint, 2002. [Apparently unpublished]
%H G. C. Greubel, <a href="/A067318/b067318.txt">Table of n, a(n) for n = 1..445</a> (terms 1..100 from T. D. Noe).
%H Emma Colaric, Ryan DeMuse, Jeremy L. Martin, and Mei Yin, <a href="https://arxiv.org/abs/2006.09321">Interval parking functions</a>, arXiv:2006.09321 [math.CO], 2020.
%H Walter Feit, Roger Lyndon, and Leonard L. Scott, <a href="http://dx.doi.org/10.1016/0097-3165(75)90017-5">A remark on permutations</a>, Journal of Combinatorial Theory (A) 18 234-235 (1975).
%H Loïc Foissy, <a href="https://arxiv.org/abs/2406.01120">The antipode of of [sic] a Com-PreLie Hopf algebra</a>, arXiv:2406.01120 [math.CO], 2024. See p. 9.
%H Briana Foster-Greenwood and Cathy Kriloff, <a href="http://arxiv.org/abs/1502.07392">Spectra of Cayley Graphs of Complex Reflection Groups</a>, arXiv preprint arXiv:1502.07392 [math.CO], 2015. (See remarks following Cor. 4.6.)
%H H. N. Hann, <a href="http://209.196.11.38/hnh.html">Symmetric Canonical Form</a>
%H Roberto Mantaci and Fanja Rakotondrajao, <a href="https://hal-auf.archives-ouvertes.fr/hal-00958950/document">A permutation representation that knows what "Eulerian" means</a>, Discrete Mathematics and Theoretical Computer Science, 4 101-108, (2001).
%F 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)!.
%F 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
%F 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
%F 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
%F a(n) = A062119(n) - A001705(n-1). - _Anton Zakharov_, Sep 22 2016
%e a(3)=7 since the permutations are 1, (12), (13), (23), (12)(13) and (12)(13). There are 7 transpositions.
%e The terms satisfy the series:
%e 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
%p ZL :=[S, {S = Set(Cycle(Z),3 <= card)}, labelled]: seq(combstruct[count](ZL, size=n), n=2..22); # _Zerinvary Lajos_, Mar 25 2008
%t a[n_] := n!*(n - HarmonicNumber[n]); Table[a[n], {n, 1, 21}](* _Jean-François Alcover_, Feb 10 2012 *)
%t 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 *)
%o (PARI) {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 */
%o (Maxima) A067318(n):=n*n! - abs(stirling1(n+1, 2))$
%o makelist(A067318(n),n,1,30); /* _Martin Ettl_, Nov 03 2012 */
%Y Cf. A000254, A001563, A001705, A062119, A067369, A067370, A084938.
%K easy,nice,nonn
%O 1,3
%A H. Nick Hann (nickhann(AT)aol.com), Jan 15 2002