cp's OEIS Frontend

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

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

From Mikhail Gaichenkov, Aug 16 2016: (Start)

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

From Gus Wiseman, Aug 12 2020: (Start)

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.

Cf. A000005, A001222, A008278, A022559, A027423, A076954, A181796.

(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

Sum_{i>=0} T(n,i)*k^i = A069777(n,k). - Geoffrey Critzer, Feb 26 2025

The following sequences (allowing offset of first term) all appear to have the same parity: A034953, triangular numbers with prime indices; A054269, length of period of continued fraction for sqrt(p), p prime; A082749, difference between the sum of next prime(n) natural numbers and the sum of next n primes; A006254, numbers n such that 2n-1 is prime; A067076, 2n+3 is a prime. - Jeremy Gardiner, Sep 10 2004

Given a rectangular prism with sides 1, p, p^2 for p = n-th prime (n > 1), the area of the six sides divided by the volume gives a remainder which is 4*a(n). - J. M. Bergot, Sep 12 2011

The infinite sum over the reciprocals is given by 2*A179119. - Wolfdieter Lang, Jul 10 2019

Numbers that are not triangular (nontriangular numbers).

Also definable as follows: a(1)=2; for n>1, a(n) is smallest integer greater than a(n-1) such that the condition "n and a(a(n)) have opposite parities" can always be satisfied. - Benoit Cloitre and Matthew Vandermast, Mar 10 2003

Record values in A256188 that are greater than 1. - Reinhard Zumkeller, Mar 26 2015

From Daniel Forgues, Apr 10 2015: (Start)

With n >= 1, k >= 1:

t(n+k) - k, 1 <= k <= n+k-1, n >= 1;

t(n+k-1) + n, 1 <= n <= n+k-1, k >= 1;

where t(n+k) = t(n+k-1) + (n+k) is the (n+k)-th triangular number, while the number of compositions of n+k into 2 parts is C(n+k-1, 2-1) = n+k-1, the number of nontriangular numbers between t(n+k-1) and t(n+k), just right!

Related to Hilbert's Infinite Hotel:

0) All rooms, numbered through the positive integers, are full;

1) An infinite number of trains, each containing an infinite number of passengers, arrives: i.e., a 2-D lattice of pairs of positive integers;

2) Move occupant of room m, m >= 1, to room t(m) = m*(m+1)/2, where t(m) is the m-th triangular number;

3) Assign n-th passenger from k-th train to room t(n+k-1) + n, 1 <= n <= n+k-1, k >= 1;

4) Everybody has his or her own room, no room is empty, for m >= 1.

If situation 1 happens again, repeat steps 2 and 3, you're back to 4.

(End)

1711 + 2*a(n)*(58 + a(n)) is prime for n<=21. The terms that do not have this property start 29,32,34,43,47,58,59,60,62,63,65,68,70,73,... - Benedict W. J. Irwin, Nov 22 2016

Also numbers k with the property that in the symmetric representation of sigma(k) both Dyck paths have a central peak or both Dyck paths have a central valley. (Cf. A237593.) - Omar E. Pol, Aug 28 2018

Equals (1, 2, 3, 4, ...) convolved with (1, 2, 1, 2, ...). a(4) = 14 = (1, 2, 3, 4) dot (2, 1, 2, 1) = (2 + 2 + 6 + 4). - Gary W. Adamson, May 01 2009

We observe that is the transform of A032766 by the following transform T: T(u_0,u_1,u_2,u_3,...) = (u_0, u_0+u_1, u_0+u_1+u_2, u_0+u_1+u_2+u_3+u_4,...). In other words, v_p = Sum_{k=0..p} u_k and the g.f. phi_v of is given by phi_v = phi_u/(1-z). - Richard Choulet, Jan 28 2010

Equals row sums of a triangle with (1, 4, 7, 10, ...) in every column, shifted down twice for columns > 1. - Gary W. Adamson, Mar 03 2010

Number of pairs (x,y) with x in {0,...,n}, y odd in {0,...,2n}, and x < y. - Clark Kimberling, Jul 02 2012

Also A049451 and positives A000567 interleaved. - Omar E. Pol, Aug 03 2012

Similar to A001082. Members of this family are A093005, A210977, this sequence, A210978, A181995, A210981, A210982. - Omar E. Pol, Aug 09 2012

Staggered diagonal of triangular spiral in A051682, between (0,1,11) spoke and (0,8,25) spoke. - Paul Barry, Mar 15 2003

Number of permutations of n distinct letters (ABCD...) each of which appears thrice with n-2 fixed points. - Zerinvary Lajos, Oct 15 2006

Number of n permutations (n>=2) of 4 objects u, v, z, x with repetition allowed, containing n-2=0 u's. Example: if n=2 then n-2 =zero (0) u, a(1)=9 because we have vv, zz, xx, vx, xv, zx, xz, vz, zv. A027465 formatted as a triangular array: diagonal: 9, 27, 54, 90, 135, 189, 252, 324, ... . - Zerinvary Lajos, Aug 06 2008

a(n) is also the least weight of self-conjugate partitions having n different parts such that each part is a multiple of 3. - Augustine O. Munagi, Dec 18 2008

Also sequence found by reading the line from 0, in the direction 0, 9, ..., and the same line from 0, in the direction 0, 27, ..., in the square spiral whose vertices are the generalized hendecagonal numbers A195160. Axis perpendicular to A195147 in the same spiral. - Omar E. Pol, Sep 18 2011

Sum of the numbers from 4*n to 5*n. - Wesley Ivan Hurt, Nov 01 2014

Number of series-reduced planted trees with n+7 nodes and 3 internal nodes.

The trees enumerated with 3 internal nodes are of two types. Those with all internal nodes at different heights are enumerated by the triangular numbers. Those with two internal nodes at the same height are enumerated by the quarter squares. - Michael Somos, May 19 2000

Number of pairs (x,y) with x in {0,...,n}, y even in {0,...,2n}, and x < y. - Clark Kimberling, Jul 02 2012

Old definition was "Integers of the form: 1/6+2/6+3/6+4/6+5/6+...".

1/6 + 2/6 + 3/6 = 1, 1/6 + 2/6 + 3/6 + 4/6 + 5/6 + 6/6 + 7/6 + 8/6 = 6, ...

a(n) is the set of all integers k such that 48k+1 is a perfect square. The square roots of 48*a(n) + 1 = 1, 7, 17, 23, 25, ... = 8*(n-floor(n/4)) + (-1)^n. - Gary Detlefs, Mar 01 2010

Conjecture: A193828 divided by 2. - Omar E. Pol, Aug 19 2011

The above conjecture is correct. - Charles R Greathouse IV, Jan 02 2012

Quasipolynomial of order 4. - Charles R Greathouse IV, Jan 02 2012

It appears that the sequence terms occur as exponents in the expansion Sum_{n >= 0} x^n/Product_{k = 1..2*n} (1 + x^k) = 1 + x - x^6 - x^11 + x^13 + x^20 - x^35 - x^46 + + - - .... Cf. A218171. [added Jan 21 2025: this is correct - see Berndt et al., Theorem 3.2.] - Peter Bala, Feb 04 2021

From Peter Bala, Dec 12 2024 (Start)

The sequence terms occur as exponents in the expansion of F(x)*Product_{n >= 1} (1 - x^n) = Product_{n >= 1} (1 - x^n)*(1 + x^(4*n))^2*(1 + x^(4*n-2))*(1 + x^(8*n-3))*(1 + x^(8*n-5)) = 1 - x - x^6 + x^11 + x^13 - x^20 - x^35 + x^46 + x^50 - - + + ..., where F(x) is the g.f. of A069910.

It appears that the sequence terms occur as exponents in the expansion 1/(1 - x) * ( - x^2 + Sum_{n >= 1} x^floor((3*n+1)/2) * 1/Product_{k = 1..n} (1 + x^k) ) = x^6 + x^11 - x^13 - x^20 + x^35 + x^46 - - + + .... (End)

It appears that the sequence terms occur as exponents in the expansion Sum_{n >= 0} x^(n+1)/Product_{k = 1..2*n+2} (1 + x^k) = x - x^6 - x^11 + x^13 + x^20 - x^35 - x^46 + + - - .... - Peter Bala, Jan 21 2025

Similar to A181388, this occurs as binary encoding of a straight n-omino lying on the y-axis, when the grid points of the first quadrant (N x N, N={0,1,2,...}) are given the weight 2^k, with k=0, 1,2, 3,4,5, ... filled in by antidiagonals.

Numbers k such that the k-th composition in standard order (row k of A066099) is a reversed initial interval. - Gus Wiseman, Apr 02 2020

Conjecture: a(n)>0 for all n>0.

The author has verified this for n up to 10^8, and also guessed the following refinement: If n>6 is not among 20, 104, 272, 464, 1664, then n can be written as p+q with p an even practical number and q a positive triangular number.

Somu and Tran (2024) proved the conjecture that a(n)>0 for n>0. - Duc Van Khanh Tran, Apr 24 2024

Based on a posting by Zhi-Wei Sun to the Number Theory Mailing List, Mar 23 2008, where he conjectures that a(n) > 0 except for n = 216.

Zhi-Wei Sun has offered a monetary reward for settling this conjecture.

No counterexample below 10^10. - D. S. McNeil

Note that A076768 contains 216 and the numbers n whose only representation has 0 instead of a prime; all other integers appear to be the sum of a prime and a triangular number. Except for n=216, there is no other n < 2*10^9 for which a(n)=0.

It is clear that a(t) > 0 for any triangular number t because we always have the representation t = t+0. Triangular numbers tend to have only a few representations. Hence by not plotting a(n) for triangular n, the plot (see link) more clearly shows how a(n) slowly increases as n increases. This is more evidence that 216 is the only exception.

216 is the only exception less than 10^12. Let p(n) be the least prime (or 0 if n is triangular) such that n = p(n) + t(n), where t(n) is a triangular number. For n < 10^12, the largest value of p(n) is only 2297990273, which occurs at n=882560134401. - T. D. Noe, Jan 23 2009