login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 85
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

T(n,k) = 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) = 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)=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) = number of 2 x c matrices with column totals 1,2,3,...,n and row totals k and (n+1 choose 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,a), n--> infinity, is the generating function for inversions (we must exclude one unimportant factor a^n/n!). The error is < a^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]

Partial sums of rows give triangle A161169. [András Salamon, Feb 16 2013]

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

REFERENCES

M. Bona, Combinatorics of permutations, Chapman & Hall/CRC, Boca Raton, Florida, 2004 (p. 52).

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 240.

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 241.

P. de la Harpe, Topics in Geometric Group Theory, Univ. Chicago Press, 2000, p. 163, top display.

E. Netto, Lehrbuch der Combinatorik. 2nd ed., Teubner, Leipzig, 1927, p. 96.

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, 1999; see Corollary 1.3.10, p. 21.

LINKS

T. D. Noe, Rows n=0..30 of triangle, flattened

F. Brglez, Of n-dimensional Dice, Combinatorial Optimization, and Reproducible Research: An Introduction, Elektrotehniski Vestnik, 78(4): 181-192, 2011.

L. Carlitz, q-Bernoulli numbers and polynomials, Duke Math. J. Volume 15, Number 4 (1948), 987-1000.

E. Deutsch, Problem 10975: Enumeration of Permutations by Disorder, Amer. Math. Monthly, 111 (2004), 541.

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

D. Foata, Distributions eulériennes et mahoniennes sur le groupe des permutations, pp. 27-49 of M. Aigner, editor, Higher Combinatorics, Reidel, Dordrecht, Holland, 1977.

D. Foata and D. Zeilberger, Denert's permutation statistic is indeed Euler-Mahonian, Studies in Appl. Math., 83(1990),31-59. [From Emeric Deutsch, Oct 29 2008]

Mikhail Gaichenkov, Necklaces and the generating function for inversions

Guo-Niu Han, Une nouvelle bijection pour la statistique de Denert, C. R. Acad. Sci. Paris, Ser. I, 310(1990),493-496.

Y.-H. He, C. Matti, C. Sun, The Scattering Variety, arXiv preprint arXiv:1403.6833, 2014

E. Irurozki, B. Calvo, J. A. Lozano, An R package for permutations, Mallows and Generalized Mallows models, 2014.

J. A. Koziol, Sums of ranking differences and inversion numbers for method discrimination, Journal of Chemometrics, 27 (2013): 165-169. doi: 10.1002/cem.2504

B. H. Margolius, Permutations with inversions, J. Integ. Seqs. Vol. 4 (2001), #01.2.4.

J. L. Martin and J. D. Wagner, On the Spectra of Simplicial Rook Graphs, arXiv preprint arXiv:1209.3493, 2012. - From N. J. A. Sloane, Dec 27 2012

A. Mendes, A note on alternating permutations, Amer. Math. Monthly, 114 (2007), 437-440.

R. H. Moritz and R. C. Williams, A coin-tossing problem and some related combinatorics, Math. Mag., 61 (1988), 24-29.

R. P. Stanley, Binomial posets, Moebius inversion and permutation enumeration, J. Combinat. Theory, A 20 (1976), 336-356.

A. Waksman, On the complexity of inversions, IEEE Trans. Computers, 19 (1970), 1225-1226. See Table II.

Eric W. Weisstein, Mathworld: Necklace

Eric W. Weisstein, Mathworld: Irreducible Polynomial

Thomas Wieder, Comments on A008302

FORMULA

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.

From Andrew Woods, Sep 26 2012: (Begin)

T(1, 1) = 1, T(1, k<>1) = 0,

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)

EXAMPLE

1; 1+x; (1+x)*(1+x+x^2) = 1+2*x+2*x^2+x^3; etc.

Triangle begins:

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

...

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;

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

MATHEMATICA

f[n_] := CoefficientList[ Expand@ Product[ Sum[x^i, {i, 0, j}], {j, n}], x]; Flatten[Array[f, 8, 0]]

nn = 25; T[1, 1] = 1; T[n_, 1] = 0; T[n_, k_] := T[n, k] = Sum[T[n - i, k - 1], {i, 1, k - 1}]; MatrixForm[Table[T[n, k], {n, nn}, {k, nn}]] (* 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 *)

CROSSREFS

Diagonals give A000707, A001892, A001893, A001894, A005283, A005284, A005285, A005286, A005287, A005288, A242656, A242657.

Row-maxima: A000140, truncated table: A060701, row sums: A000142.

A161436 is one of the rows.

A001809 gives total Denert index of all permutations.

Cf. A139365.

Sequence in context: A076037 A215563 A076263 * A131791 A010358 A155865

Adjacent sequences:  A008299 A008300 A008301 * A008303 A008304 A008305

KEYWORD

easy,tabf,nonn,nice,look

AUTHOR

N. J. A. Sloane.

EXTENSIONS

Maple code from Barbara Haas Margolius (margolius(AT)math.csuohio.edu) May 31 2001

There were some mistaken edits to this entry (inclusion of an initial 1, etc.) which I undid. - N. J. A. Sloane, Nov 30 2009

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified November 20 21:20 EST 2014. Contains 249754 sequences.