|
| |
|
|
A008302
|
|
Triangle of Mahonian numbers T(n,k): coefficients in expansion of Product_{i=0..n-1} (1 + x + ... + x^i), where k ranges from 0 to A000217(n-1). Also enumerates permutations by their major index.
|
|
114
|
|
|
|
1, 1, 1, 1, 2, 2, 1, 1, 3, 5, 6, 5, 3, 1, 1, 4, 9, 15, 20, 22, 20, 15, 9, 4, 1, 1, 5, 14, 29, 49, 71, 90, 101, 101, 90, 71, 49, 29, 14, 5, 1, 1, 6, 20, 49, 98, 169, 259, 359, 455, 531, 573, 573, 531, 455, 359, 259, 169, 98, 49, 20, 6, 1, 1, 7, 27, 76, 174, 343, 602, 961, 1415, 1940, 2493, 3017, 3450, 3736, 3836, 3736, 3450, 3017, 2493, 1940, 1415, 961, 602, 343, 174, 76, 27, 7, 1, 1, 8, 35, 111, 285, 628, 1230, 2191, 3606, 5545, 8031, 11021, 14395, 17957, 21450, 24584, 27073, 28675, 29228, 28675, 27073, 24584, 21450, 17957, 14395, 11021, 8031, 5545, 3606, 2191, 1230, 628, 285, 111, 35, 8, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,5
|
|
|
COMMENTS
|
T(n,k) is the number of permutations of {1..n} with k inversions.
n-th row gives growth series for symmetric group S_n with respect to transpositions (1,2), (2,3), ..., (n-1,n).
T(n,k) is the number of permutations of (1,2,...,n) having disorder equal to k. The disorder of a permutation p of (1,2,...,n) is defined in the following manner. We scan p from left to right as often as necessary until all its elements are removed in increasing order, scoring one point for each occasion on which an element is passed over and not removed. The disorder of p is the number of points scored by the end of the scanning and removal process. For example, the disorder of (3,5,2,1,4) is 8, since on the first scan, 3,5,2 and 4 are passed over, on the second, 3,5 and 4 and on the third scan, 5 is once again not removed. - Emeric Deutsch, Jun 09 2004
T(n,k) is the number of permutations p=(p(1),...,p(n)) of {1..n} such that Sum_{i: p(i)>p(i+1)} = k (k is called the Major index of p). Example: T(3,0)=1, T(3,1)=2, T(3,2)=2, T(3,3)=1 because the major indices of the permutations (1,2,3), (2,1,3), (3,1,2), (1,3,2), (2,3,1) and (3,2,1) are 0,1,1,2,2 and 3, respectively. - Emeric Deutsch, Aug 17 2004
T(n,k) is the number of 2 X c matrices with column totals 1,2,3,...,n and row totals k and binomial(n+1,2) - k. - Mitch Harris, Jan 13 2006
T(n,k) is the number of permutations p of {1,2,...,n} for which den(p)=k. Here den is the Denert statistic, defined in the following way: let p=p(1)p(2)...p(n) be a permutation of {1,2,...,n}; if p(i)>i, then we say that i is an excedance of p; let i_1 < i_2 < ... < i_k be the excedances of p and let j_1 < j_2 < ... < j_{n-k} be the non-excedances of p; let Exc(p) = p(i_1)p(i_2)...p(i_k), Nexc(p)=p(j_1)p(j_2)...p(j_{n-k}); then, by definition den(p) = i_1 + i_2 + ... + i_k + inv(Exc(p)) + inv(Nexc(p)), where inv denotes "number of inversions". Example: T(4,5)=3 because we have 1342, 3241 and 4321. We show that den(4321)=5: the excedances are 1 and 2; Exc(4321)=43, Nexc(4321)=21; now den(4321) = 1 + 2 + inv(43) + inv(21) = 3+1+1 = 5. - Emeric Deutsch, Oct 29 2008
T(n,k) is the number of size k submultisets of the multiset {1,2,2,3,3,3,...,n-1} (which contains i copies of i for 0 < i < n).
The limit of products of the numbers of fixed necklaces of length n composed of beads of types N(n,b), n --> infinity, is the generating function for inversions (we must exclude one unimportant factor b^n/n!). The error is < (b^n/n!)*O(1/n^(1/2-epsilon)). See Gaichenkov link. - Mikhail Gaichenkov, Aug 27 2012
The number of ways to distribute k-1 indistinguishable balls into n-1 boxes of capacity 1,2,3,...,n-1. - Andrew Woods, Sep 26 2012
The number of permutations of n that require k pair swaps in the bubble sort to sort them into the natural 1,2,...,n order. - R. J. Mathar, May 04 2013
Also series coefficients of q-factorial [n]_q ! -- see Mathematica line. - Wouter Meeussen, Jul 12 2014
Following asymptotic expansions in the Central Limit Theorem developed by Valentin V. Petrov, the cumulative distribution function of these numbers, CDF_N(x), is equal to the CDF of the normal distribution - (0.06/sqrt(2*Pi))*exp(-x^2/2)(x^3-3x)*(6N^3+21N^2+31N+31)/(N(2N+5)^2(N-1)+O(1/N^2).
This can be written as: CDF of the normal distribution -(0.09/(N*sqrt(2*Pi)))*exp(-x^2/2)*He_3(x) + O(1/N^2), N > 1, natural numbers (Gaichenkov, private research).
According to B. H. Margolius, Permutations with inversions, J. Integ. Seqs. Vol. 4 (2001), #01.2.4, "the unimodal behavior of the inversion numbers suggests that the number of inversions in a random permutation may be asymptotically normal". See links.
Moreover, E. Ben-Naim (Theoretical Division and Center for Nonlinear Studies, Los Alamos National Laboratory), "On the Mixing of Diffusing Particles" (13 Oct 2010), states that the Mahonian Distribution becomes a function of a single variable for large numbers of element, i.e., the probability distribution function is normal. See links.
To be more precise the expansion of the distribution is presented for a finite number of elements (or particles in terms of E. Ben-Naim's article). The distribution tends to the normal distribution for an infinite numbers of elements.
(End)
T(n,k) statistic counts (labeled) permutation graphs with n vertices and k edges. - Mikhail Gaichenkov, Aug 20 2019
Number of divisors of A006939(n - 1) or A076954(n - 1) with k prime factors, counted with multiplicity, where A006939(n) = Product_{i = 1..n} prime(i)^(n - i + 1). For example, row n = 4 counts the following divisors:
1 2 4 8 24 72 360
3 6 12 36 120
5 9 18 40 180
10 20 60
15 30 90
45
Crossrefs:
A336420 is the case with distinct prime multiplicities.
A006939 lists superprimorials or Chernoff numbers.
A022915 counts permutations of prime indices of superprimorials.
A317829 counts factorizations of superprimorials.
A336941 counts divisor chains under superprimorials.
(End)
Named after the British mathematician Percy Alexander MacMahon (1854-1929). - Amiram Eldar, Jun 13 2021
Row maxima ~ n!/(sigma * sqrt(2*Pi)), sigma^2 = (2*n^3 + 9*n^2 + 7*n)/72 = variance of group type A_n (see also A161435). - Mikhail Gaichenkov, Feb 08 2023
|
|
|
REFERENCES
|
Miklós Bóna, Combinatorics of permutations, Chapman & Hall/CRC, Boca Raton, Florida, 2004 (p. 52).
Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 240.
Florence Nightingale David, Maurice George Kendall and David Elliot Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 241.
Pierre de la Harpe, Topics in Geometric Group Theory, Univ. Chicago Press, 2000, p. 163, top display.
Eugen Netto, Lehrbuch der Combinatorik. 2nd ed., Teubner, Leipzig, 1927, p. 96.
Valentin V. Petrov, Sums of Independent Random Variables, Springer Berlin Heidelberg, 1975, p. 134.
Richard P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, 1999; see Corollary 1.3.10, p. 21.
|
|
|
LINKS
|
J. Bourget, Des permutations, Nouvelles annales de mathématiques, 2e série, tome 10 (1871), pp. 254-268.
Mariusz Czekała and Agnieszka Bukietyńska, Distribution of Inversions and the Power of the τ-Kendall's Test, in J. Świątek, Z. Wilimowska, L. Borzemski, A. Grzech (eds.), Information Systems Architecture and Technology: Proceedings of 37th International Conference on Information Systems Architecture and Technology - ISAT 2016 - Part III, pp. 175-185.
Yang-Hui He, Cyril Matti and Chuang Sun, The Scattering Variety, arXiv preprint arXiv:1403.6833 [hep-th], 2014.
Juan Miguel Nieto, Tailoring and Hexagon Form Factors, Spinning Strings and Correlation Functions in the AdS/CFT Correspondence, Springer Theses (Recognizing Outstanding Ph.D. Research), Springer, Cham, 2018.
Eric Weisstein's World of Mathematics, Necklace.
|
|
|
FORMULA
|
Bourget, Comtet and Moritz-Williams give recurrences.
Mendes and Stanley give g.f.'s.
G.f.: Product_{j=1..n} (1-x^j)/(1-x) = Sum_{k=0..M} T{n, k} x^k, where M = n*(n-1)/2.
T(1, 0) = 1,
T(n, k) = 0 for n < 0, k < 0 or k > n*(n-1)/2.
T(n, k) = Sum_{j=0..n-1} T(n-1, k-j),
T(n, k) = T(n, k-1) + T(n-1, k) - T(n-1, k-n). (End)
E.g.f. satisfies: A(x,q) = 1 + Integral (A(x,q) - q*A(q*x,q))/(1-q) dx, where A(x,q) = Sum_{n>=0} x^n/n! * Sum_{k=0..n*(n-1)/2} T(n,k)*q^k, when T(0,0) = 1 is included. - Paul D. Hanna, Dec 31 2016
|
|
|
EXAMPLE
|
1; 1+x; (1+x)*(1+x+x^2) = 1+2*x+2*x^2+x^3; etc.
Triangle begins:
n\k| 0 1 2 3 4 5 6 7 8 9 10
---+--------------------------------------------------------------
1 | 1;
2 | 1, 1;
3 | 1, 2, 2, 1;
4 | 1, 3, 5, 6, 5, 3, 1;
5 | 1, 4, 9, 15, 20, 22, 20, 15, 9, 4, 1;
6 | 1, 5, 14, 29, 49, 71, 90, 101, 101, 90, 71, ...
7 | 1, 6, 20, 49, 98, 169, 259, 359, 455, 531, 573, ...
8 | 1, 7, 27, 76, 174, 343, 602, 961, 1415, 1940, 2493, ...
9 | 1, 8, 35, 111, 285, 628, 1230, 2191, 3606, 5545, 8031, ...
10 | 1, 9, 44, 155, 440, 1068, 2298, 4489, 8095, 13640, 21670, ...
Row n = 4 counts the following submultisets of {1,1,1,2,2,3}:
{} {1} {11} {111} {1112} {11122} {111223}
{2} {12} {112} {1122} {11123}
{3} {22} {122} {1113} {11223}
{13} {113} {1123}
{23} {123} {1223}
{223}
(End)
|
|
|
MAPLE
|
g := proc(n, k) option remember; if k=0 then return(1) else if (n=1 and k=1) then return(0) else if (k<0 or k>binomial(n, 2)) then return(0) else g(n-1, k)+g(n, k-1)-g(n-1, k-n) end if end if end if end proc; # Barbara Haas Margolius (margolius(AT)math.csuohio.edu), May 31 2001
BB:=j->1+sum(t^i, i=1..j): for n from 1 to 8 do Z[n]:=sort(expand(simplify(product(BB(j), j=0..n-2)))) od: for n from 1 to 8 do seq(coeff(Z[n], t, j), j=0..(n-1)*(n-2)/2) od; # Zerinvary Lajos, Apr 13 2007
# alternative Maple program:
b:= proc(u, o) option remember; expand(`if`(u+o=0, 1,
add(b(u+j-1, o-j)*x^(u+j-1), j=1..o)+
add(b(u-j, o+j-1)*x^(u-j), j=1..u)))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
|
|
|
MATHEMATICA
|
f[n_] := CoefficientList[ Expand@ Product[ Sum[x^i, {i, 0, j}], {j, n}], x]; Flatten[Array[f, 8, 0]]
(* Second program: *)
T[0, 0] := 1; T[-1, k_] := 0;
T[n_, k_] := T[n, k] = If[0 <= k <= n*(n - 1)/2, T[n, k - 1] + T[n - 1, k] - T[n - 1, k - n], 0]; (* Peter Kagey, Mar 18 2021; corrected the program by Mats Granvik and Roger L. Bagula, Jun 19 2011 *)
alternatively (versions 7 and up):
Table[CoefficientList[Series[QFactorial[n, q], {q, 0, n(n-1)/2}], q], {n, 9}] (* Wouter Meeussen, Jul 12 2014 *)
|
|
|
PROG
|
(Sage)
from sage.combinat.q_analogues import q_factorial
for n in (1..6): print(q_factorial(n).list()) # Peter Luschny, Jul 18 2016
(PARI) {T(n, k) = my(A=1+x); for(i=1, n, A = 1 + intformal(A - q*subst(A, x, q*x +x^2*O(x^n)))/(1-q)); polcoeff(n!*polcoeff(A, n, x), k, q)}
for(n=1, 10, for(k=0, n*(n-1)/2, print1(T(n, k), ", ")); print("")) \\ Paul D. Hanna, Dec 31 2016
(PARI) for(n=1, 10, print(Vec(prod(k=1, n, (1-q^k)/(1-q))))); \\ Joerg Arndt, Apr 13 2019
|
|
|
CROSSREFS
|
A001809 gives total Denert index of all permutations.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
There were some mistaken edits to this entry (inclusion of an initial 1, etc.) which I undid. - N. J. A. Sloane, Nov 30 2009
Added mention of "major index" to definition. - N. J. A. Sloane, Feb 10 2019
|
|
|
STATUS
|
approved
|
| |
|
|
