|
| |
|
|
A001809
|
|
a(n) = n! * n(n-1)/4.
(Formerly M4649 N1989)
|
|
18
|
|
|
|
0, 0, 1, 9, 72, 600, 5400, 52920, 564480, 6531840, 81648000, 1097712000, 15807052800, 242853811200, 3966612249600, 68652904320000, 1255367393280000, 24186745110528000, 489781588488192000, 10400656084955136000, 231125690776780800000, 5364548928029491200000
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
a(n) = n!*n*(n-1)/4 gives the total number of inversions in all the permutations of [n]. [Stern, Terquem] Proof: For fixed i,j and for fixed I,J (i < j, I > J, 1 <= i,j,I,J <= n), we have (n-2)! permutations p of [n] for which p(i)=I and p(j)=J (permute {1,2,...,n} \ {I,J} in the positions (1,2,...,n) \ {i,j}). There are n*(n-1)/2 choices for the pair (i,j) with i < j and n*(n-1)/2 choices for the pair (I,J) with I > J. Consequently, the total number of inversions in all the permutations of [n] is (n-2)!*(n*(n-1)/2)^2 = n!*n*(n-1)/4. - Emeric Deutsch, Oct 05 2006
To state this another way, a(n) is the number of occurrences of the pattern 12 in all permutations of [n]. - N. J. A. Sloane, Apr 12 2014
Equivalently, this is the total Denert index of all permutations on n letters (cf. A008302). - N. J. A. Sloane, Jan 20 2014
Also coefficients of Laguerre polynomials. a(n)=A021009(n,2), n >= 2.
a(n) is the number of edges in the Cayley graph of the symmetric group S_n with respect to the generating set consisting of transpositions. - Avi Peretz (njk(AT)netvision.net.il), Feb 20 2001
a(n+1) is the sum of the moments over all permutations of n. E.g. a(4) is [1,2,3].[1,2,3] + [1,3,2].[1,2,3] + [2,1,3].[1,2,3] + [2,3,1].[1,2,3] + [3,1,2].[1,2,3] + [3,2,1].[1,2.3] = 14 + 13 + 13 + 11 + 11 + 10 = 72. - Jon Perry, Feb 20 2004
Derivative of the q-factorial [n]!, evaluated at q=1. Example: a(3)=9 because (d/dq)[3]!=(d/dq)((1+q)(1+q+q^2))=2+4q+3q^2 is equal to 9 at q=1. - Emeric Deutsch, Apr 19 2007
Also the number of maximal cliques in the n-transposition graph for n > 1. - Eric W. Weisstein, Dec 01 2017
a(n-1) is the number of trees on [n], rooted at 1, with exactly two leaves. A leaf is a non-root vertex of degree 1. - Nikos Apostolakis, Dec 27 2021
|
|
|
REFERENCES
|
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 799.
Simon Altmann and Eduardo L. Ortiz, Editors, Mathematical and Social Utopias in France: Olinde Rodrigues and His Times, Amer. Math. Soc., 2005.
David M. Bressoud, Proofs and Confirmations, Camb. Univ. Press, 1999; p. 90.
Cornelius Lanczos, Applied Analysis, Prentice-Hall, Englewood Cliffs, NJ, 1956, p. 519.
Edward M. Reingold, Jurg Nievergelt and Narsingh Deo, Combinatorial Algorithms, Prentice-Hall, 1977, section 7.1, p. 287.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Olry Terquem, Liouville's Journal, 1838.
|
|
|
LINKS
|
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
M. Stern, Aufgaben, Journal für die reine und angewandte Mathematik, Vol. 18 (1838), p. 100.
|
|
|
FORMULA
|
E.g.f.: (1/2)*x^2/(1-x)^3.
a(n) = a(n-1)*n^2/(n-2), n > 2; a(2)=1.
a(n) = n*a(n-1) + (n-1)!*n*(n-1)/2, a(1) = 0, a(2) = 1; a(n) = sum (first n! terms of A034968); a(n) = sum of the rises j of permutations (p(j)<p(j+1)). - Claude Lenormand (claude.lenormand(AT)free.fr), Feb 02 2001
If we define f(n,i,x) = Sum_{k=i..n} (Sum_{j=i..k}(C(k,j)*Stirling1(n,k)*Stirling2(j,i)*x^(k-j))) then a(n)=(-1)^n*f(n,2,-3), (n>=2). - Milan Janjic, Mar 01 2009
a(n+2) = n*n!*(n+1)^2 / 4 = A000142(n) * (A000292(n) + A000330(n))/2 = sum of the cumulative sums of all the permutations of numbers from 1 to n, where A000142(n) = n! and sequences A000292(n) and A000330(n) are sequences of minimal and maximal values of cumulative sums of all the permutations of numbers from 1 to n. - Jaroslav Krizek, Sep 13 2014
Sum_{n>=2} 1/a(n) = 12 - 4*e.
Sum_{n>=2} (-1)^n/a(n) = 8*gamma - 4 - 4/e - 8*Ei(-1), where gamma is Euler's constant (A001620) and -Ei(-1) is the negated exponential integral at -1 (A099285). (End)
|
|
|
EXAMPLE
|
G.f. = x^2 + 9*x^3 + 72*x^4 + 600*x^5 + 5400*x^6 + 52920*x^7 + ...
|
|
|
MAPLE
|
with(combstruct):ZL:=[st, {st=Prod(left, right), left=Set(U, card=r), right=Set(U, card<r), U=Sequence(Z, card>=1)}, labeled]: subs(r=1, stack): seq(count(subs(r=2, ZL), size=m), m=0..19); # Zerinvary Lajos, Feb 07 2008
with (combstruct):with (combinat):a:=proc(m) [ZL, {ZL=Set(Cycle(Z, card>=m))}, labeled]; end: ZLL:=a(1):seq(count(ZLL, size=n)*binomial(n, 2)/2, n=0..21); # Zerinvary Lajos, Jun 11 2008
|
|
|
MATHEMATICA
|
Table[n! n (n - 1)/4, {n, 0, 18}]
Coefficient[Table[n! LaguerreL[n, x], {n, 20}], x, 2] (* Eric W. Weisstein, Dec 01 2017 *)
|
|
|
PROG
|
(PARI) {a(n) = n! * n * (n-1) / 4};
(Sage) [factorial(m) * binomial(m, 2) / 2 for m in range(19)] # Zerinvary Lajos, Jul 05 2008
|
|
|
CROSSREFS
|
Cf. A034968 (the inversion numbers of permutations listed in alphabetic order). See also A053495 and A064038.
|
|
|
KEYWORD
|
nonn,easy,nice,eigen
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
