A067318 Total number of transpositions in 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,3

Comments

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

References

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

Links

G. C. Greubel, Table of n, a(n) for n = 1..445 (terms 1..100 from T. D. Noe).

Emma Colaric, Ryan DeMuse, Jeremy L. Martin, and Mei Yin, Interval parking functions, arXiv:2006.09321 [math.CO], 2020.

W. Feit, R. Lyndon and L. L. Scott, A remark on permutations, Journal of Combinatorial Theory (A) 18 234-235 (1975).

B. Foster-Greenwood, C. 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

R. Mantaci and F. Rakotondrajao, A permutation representation that knows what "Eulerian" means, Discrete Mathematics and Theoretical Computer Science, 4 101-108, (2001).

Formula

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

Example

a(3)=7 since the permutations are 1, (12), (13), (23), (12)(13) and (12)(13). There are 7 transpositions.
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

Maple

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

Mathematica

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 *)

Prog

(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 */
(Maxima) A067318(n):=n*n! - abs(stirling1(n+1, 2))$
makelist(A067318(n), n, 1, 30); /* Martin Ettl, Nov 03 2012 */

Crossrefs

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

Sequence in context: A244265 A240722 A365773 * A072948 A332852 A356827

Adjacent sequences: A067315 A067316 A067317 * A067319 A067320 A067321

Keyword

easy,nice,nonn

Author

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

Status

approved