This site is supported by donations to The OEIS Foundation.



The OEIS is looking to hire part-time people to help edit core sequences, upload scanned documents, process citations, fix broken links, etc. - Neil Sloane, njasloane@gmail.com

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001809 a(n) = n!n(n-1)/4.
(Formerly M4649 N1989)
0, 0, 1, 9, 72, 600, 5400, 52920, 564480, 6531840, 81648000, 1097712000, 15807052800, 242853811200, 3966612249600, 68652904320000, 1255367393280000, 24186745110528000, 489781588488192000, 10400656084955136000, 231125690776780800000 (list; graph; refs; listen; history; text; internal format)



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

Mahonian weight function. - Roger L. Bagula, Oct 05 2006

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

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


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.

S. Altmann and E. L. Ortiz, Editors, Mathematical and Social Utopias in France: Olinde Rodrigues and His Times, Amer. Math. Soc., 2005.

D. M. Bressoud, Proofs and Confirmations, Camb. Univ. Press, 1999; p. 90.

C. Lanczos, Applied Analysis. Prentice-Hall, Englewood Cliffs, NJ, 1956, p. 519.

E. Reingold, J. Nievergelt and N. 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).

M. Stern, Crelle, 18 (1838), p. 100.

O. Terquem, Liouville's Journal, 1838.


T. D. Noe, Table of n, a(n) for n=0..100

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].

Eric Babson and Einar Steingrimsson, Generalized Permutation Patterns and Classification of the Mahonian Statistics, Séminaire Lotharingien de Combinatoire, B44b (2000), 18 pp.

Karl Dienger, Beiträge zur Lehre von den arithmetischen und geometrischen Reihen höherer Ordnung, Jahres-Bericht Ludwig-Wilhelm-Gymnasium Rastatt, Rastatt, 1910. [Annotated scanned copy]

FindStat - Combinatorial Statistic Finder, The Denert index of a permutation

Dominique Foata and Marcel-Paul Schützenberger, Major Index and inversion number of permutations , Math. Nachr. 83 (1978), 143-159

D. J. L. Indong, G. R. Peralta, Inversions of permutations in Symmetric, Alternating, and Dihedral Groups, JIS 11 (2008) 08.4.3

W. P. Johnson, Review of Altmann-Ortiz book, Amer. Math. Monthly, 114 (2007), 752-758.

C. Lanczos, Applied Analysis (Annotated scans of selected pages)

J. Ser, Les Calculs Formels des Séries de Factorielles (Annotated scans of some selected pages)

Thotsaporn Thanatipanonda, Inversions and major index for permutations, Math. Mag., April 2004.

Eric Weisstein's World of Mathematics, Transposition Graph

Index entries for sequences related to Laguerre polynomials


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 (n! first 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(sum(C(k,j)*stirling1(n,k)*stirling2(j,i) *x^(k-j), j=i..k), k=i..n) then a(n)=(-1)^n*f(n,2,-3), (n>=2). - Milan Janjic, Mar 01 2009

a(n) = Sum_k k*A008302(n,k). - N. J. A. Sloane, Jan 20 2014


G.f. = x^2 + 9*x^3 + 72*x^4 + 600*x^5 + 5400*x^6 + 52920*x^7 + ...


A001809 := n->n!*n*(n-1)/4;

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


Table[n! n(n-1)/4, {n, 0, 18}]


(PARI) {a(n) = n! * n * (n-1) / 4};

(Sage) [factorial(m)*binomial(m, 2)/2 for m in xrange (0, 19)] # Zerinvary Lajos, Jul 05 2008

(MAGMA) [Factorial(n)*n*(n-1)/4: n in [0..20]]; // Vincenzo Librandi, Jun 15 2015


Cf. A034968 (the inversion numbers of permutations listed in alphabetic order). See also A053495 and A064038.

Cf. A008302.

Sequence in context: A252702 A033135 A127053 * A006135 A180836 A218126

Adjacent sequences:  A001806 A001807 A001808 * A001810 A001811 A001812




N. J. A. Sloane


More terms and new description from Michael Somos, May 19 2000

Simpler description from Emeric Deutsch, Oct 05 2006



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 26 18:26 EDT 2017. Contains 287129 sequences.