|
%I M4649 N1989 #119 Jan 18 2024 04:13:22
%S 0,0,1,9,72,600,5400,52920,564480,6531840,81648000,1097712000,
%T 15807052800,242853811200,3966612249600,68652904320000,
%U 1255367393280000,24186745110528000,489781588488192000,10400656084955136000,231125690776780800000,5364548928029491200000
%N a(n) = n! * n(n-1)/4.
%C 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
%C 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
%C Equivalently, this is the total Denert index of all permutations on n letters (cf. A008302). - _N. J. A. Sloane_, Jan 20 2014
%C Also coefficients of Laguerre polynomials. a(n)=A021009(n,2), n >= 2.
%C 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
%C 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
%C 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
%C Also the number of maximal cliques in the n-transposition graph for n > 1. - _Eric W. Weisstein_, Dec 01 2017
%C 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
%D 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.
%D Simon Altmann and Eduardo L. Ortiz, Editors, Mathematical and Social Utopias in France: Olinde Rodrigues and His Times, Amer. Math. Soc., 2005.
%D David M. Bressoud, Proofs and Confirmations, Camb. Univ. Press, 1999; p. 90.
%D Cornelius Lanczos, Applied Analysis, Prentice-Hall, Englewood Cliffs, NJ, 1956, p. 519.
%D Edward M. Reingold, Jurg Nievergelt and Narsingh Deo, Combinatorial Algorithms, Prentice-Hall, 1977, section 7.1, p. 287.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D Olry Terquem, Liouville's Journal, 1838.
%H T. D. Noe, <a href="/A001809/b001809.txt">Table of n, a(n) for n=0..100</a>
%H M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
%H Eric Babson and Einar Steingrimsson, <a href="http://radon.mat.univie.ac.at/~slc/s/s44stein.html">Generalized Permutation Patterns and Classification of the Mahonian Statistics</a>, Séminaire Lotharingien de Combinatoire, B44b (2000), 18 pp.
%H Geoffrey Critzer, <a href="https://esirc.emporia.edu/handle/123456789/3595">Combinatorics of Vector Spaces over Finite Fields</a>, Master's thesis, Emporia State University, 2018.
%H Karl Dienger, <a href="/A000217/a000217.pdf">Beiträge zur Lehre von den arithmetischen und geometrischen Reihen höherer Ordnung</a>, Jahres-Bericht Ludwig-Wilhelm-Gymnasium Rastatt, Rastatt, 1910. [Annotated scanned copy]
%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/St000156/">The Denert index of a permutation</a>
%H Dominique Foata and Marcel-Paul Schützenberger, <a href="http://dx.doi.org/10.1002/mana.19780830111">Major Index and inversion number of permutations </a>, Math. Nachr. 83 (1978), 143-159
%H Dexter Jane L. Indong and Gilbert R. Peralta, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL11/Peralta/peralta6.html">Inversions of permutations in Symmetric, Alternating, and Dihedral Groups</a>, JIS, Vol. 11 (2008), Article 08.4.3.
%H Warren P. Johnson, <a href="http://www.jstor.org/stable/27642326">Review of Altmann-Ortiz book</a>, Amer. Math. Monthly, Vol. 114, No. 8 (2007), pp. 752-758.
%H Cornelius Lanczos, <a href="/A002457/a002457.pdf">Applied Analysis</a>. (Annotated scans of selected pages)
%H J. Ser, <a href="/A002720/a002720_4.pdf">Les Calculs Formels des Séries de Factorielles</a>, Gauthier-Villars, Paris, 1933 [Local copy].
%H J. Ser, <a href="/A002720/a002720.pdf">Les Calculs Formels des Séries de Factorielles</a>. (Annotated scans of some selected pages)
%H M. Stern, <a href="http://www.digizeitschriften.de/dms/resolveppn/?PID=GDZPPN002141558">Aufgaben</a>, Journal für die reine und angewandte Mathematik, Vol. 18 (1838), p. 100.
%H Thotsaporn Thanatipanonda, <a href="http://www.jstor.org/stable/3219103">Inversions and major index for permutations</a>, Math. Mag., Vol. 77, No. 2 (April 2004), pp. 136-140.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximalClique.html">Maximal Clique</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Transposition Graph.html">Transposition Graph</a>.
%H <a href="/index/La#Laguerre">Index entries for sequences related to Laguerre polynomials</a>.
%F E.g.f.: (1/2)*x^2/(1-x)^3.
%F a(n) = a(n-1)*n^2/(n-2), n > 2; a(2)=1.
%F 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
%F 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
%F a(n) = Sum_k k*A008302(n,k). - _N. J. A. Sloane_, Jan 20 2014
%F 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
%F From _Amiram Eldar_, Feb 15 2022: (Start)
%F Sum_{n>=2} 1/a(n) = 12 - 4*e.
%F 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)
%e G.f. = x^2 + 9*x^3 + 72*x^4 + 600*x^5 + 5400*x^6 + 52920*x^7 + ...
%p A001809 := n->n!*n*(n-1)/4;
%p 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
%p 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
%t Table[n! n (n - 1)/4, {n, 0, 18}]
%t Table[n! Binomial[n, 2]/2, {n, 0, 20}] (* _Eric W. Weisstein_, Dec 01 2017 *)
%t Coefficient[Table[n! LaguerreL[n, x], {n, 20}], x, 2] (* _Eric W. Weisstein_, Dec 01 2017 *)
%o (PARI) {a(n) = n! * n * (n-1) / 4};
%o (Sage) [factorial(m) * binomial(m, 2) / 2 for m in range(19)] # _Zerinvary Lajos_, Jul 05 2008
%o (Magma) [Factorial(n)*n*(n-1)/4: n in [0..20]]; // _Vincenzo Librandi_, Jun 15 2015
%Y Cf. A034968 (the inversion numbers of permutations listed in alphabetic order). See also A053495 and A064038.
%Y Cf. A001620, A008302, A099285.
%K nonn,easy,nice,eigen
%O 0,4
%A _N. J. A. Sloane_
%E More terms and new description from _Michael Somos_, May 19 2000
%E Simpler description from _Emeric Deutsch_, Oct 05 2006
|
