|
|
A067318
|
|
Total number of transpositions in all permutations of n letters.
|
|
13
|
|
|
0, 1, 7, 46, 326, 2556, 22212, 212976, 2239344, 25659360, 318540960, 4261576320, 61148511360, 937030429440, 15275952518400, 264030355814400, 4823280687052800, 92865738644582400, 1879691760950169600, 39905092126771200000, 886664974825728000000
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
Walter Feit, Roger Lyndon, and Leonard L. Scott, A remark on permutations, Journal of Combinatorial Theory (A) 18 234-235 (1975).
|
|
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
|
|
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
|
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))$
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nice,nonn
|
|
AUTHOR
|
H. Nick Hann (nickhann(AT)aol.com), Jan 15 2002
|
|
STATUS
|
approved
|
|
|
|