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

Product of first n primorials: a(n) = Product_{i=1..n} A002110(i).

Superprimorials, from primorials by analogy with superfactorials.

Smallest number k with n distinct exponents in its prime factorization, i.e., A071625(k) = n.

Subsequence of A130091. - Reinhard Zumkeller, May 06 2007

Hankel transform of A171448. - Paul Barry, Dec 09 2009

This might be a good place to explain the name "Chernoff sequence" since his name does not appear in the References or Links as of Mar 22 2014. - Jonathan Sondow, Mar 22 2014

Pickover (1992) named this sequence after Paul Chernoff of California, who contributed this sequence to his book. He was possibly referring to American mathematician Paul Robert Chernoff (1942 - 2017), a professor at the University of California. - Amiram Eldar, Jul 27 2020

Product of next n numbers divided by product of first n numbers. E.g., a(4) = (7*8*9*10)/(1*2*3*4)= 210. - Amarnath Murthy, Mar 22 2004

Also the number of labeled loop-graphs with n vertices and n edges. The covering case is A368597. - Gus Wiseman, Jan 25 2024

Sorted list of positive integers with a factorization Product p(i)^e(i) such that (e(1) - e(2)) >= (e(2) - e(3)) >= ... >= (e(k-1) - e(k)) >= e(k), with k = A001221(n), and p(k) = A006530(n) = A000040(k), i.e., the prime factors p(1) .. p(k) must be consecutive primes from 2 onward. - Comment clarified by Antti Karttunen, Apr 28 2022

Subsequence of A025487. A025487(n) belongs to this sequence iff A181815(n) is a member of A025487.

If prime signatures are considered as partitions, these are the members of A025487 whose prime signature is conjugate to the prime signature of a member of A182863. - Matthew Vandermast, May 20 2012

The number of arrangements of 1,2,...,n^2 in an n X n matrix such that each row is increasing. - Ahmed Fares (ahmedfares(AT)my-deja.com), Jul 12 2001

a(n) == 0 (mod n!). In fact (n^2)! == 0 (mod (n!)^n) by elementary combinatorics, a better result is (n^2)! == 0 (mod (n!)^(n+1)). - Amarnath Murthy, Jul 13 2005

a(n) is also the number of lattice paths from {n}^n to {0}^n using steps that decrement one component by 1. a(2) = 6: [(2,2), (1,2), (0,2), (0,1), (0,0)], [(2,2), (1,2), (1,1), (0,1), (0,0)], [(2,2), (1,2), (1,1), (1,0), (0,0)], [(2,2), (2,1), (1,1), (0,1), (0,0)], [(2,2), (2,1), (1,1), (1,0), (0,0)], [(2,2), (2,1), (2,0), (1,0), (0,0)]. - Alois P. Heinz, May 06 2013

Given n^2 distinguishable balls and n distinguishable urns, a(n) = the number of ways to place n balls in the i-th urn for all 1 <= i <= n, where n = n_1 + n_2 + ... + n_n. - Ross La Haye, Dec 28 2013

The n-th row also gives the coefficients of the sigma polynomial of the empty graph \bar K_n. - Eric W. Weisstein, Apr 07 2017

The n-th row also gives the coefficients of the independence polynomial of the (n-1)-triangular honeycomb bishop graph. - Eric W. Weisstein, Apr 03 2018

From Gus Wiseman, Aug 11 2020: (Start)

Conjecture: also the number of divisors of the superprimorial A006939(n - 1) that have 0 <= k <= n distinct prime factors, all appearing with distinct multiplicities. For example, row n = 4 counts the following divisors of 360:

1 2 12 360

3 18

4 20

5 24

8 40

9 45

72

Equivalently, T(n,k) is the number of length-n vectors 0 <= v_i <= i with k nonzero values, all of which are distinct.

Crossrefs:

A006939 lists superprimorials or Chernoff numbers.

A022915 counts permutations of prime indices of superprimorials.

A076954 can be used instead of A006939.

A130091 lists numbers with distinct prime multiplicities.

A181796 counts divisors with distinct prime multiplicities.

A336420 is the version counting all prime factors, not just distinct ones.

Cf. A000005, A027423, A095149, A124010, A317829, A327498, A336419, A336421.

(End)

From Leonidas Liponis, Aug 26 2024: (Start)

It appears that this sequence is related to the combinatorial form of Faà di Bruno's formula. Specifically, the number of terms for the n-th derivative of a composite function y = f(g(x)) matches the number of partitions of n.

For example, consider the case where g(x) = e^x, in which all derivatives of g(x) are equal. The first 5 rows of A008278 appear as the factors of derivatives of f(x), highlighted here in brackets:

dy/dx = [ 1 ] * f'(e^x) * e^x

d^2y/dx^2 = [ 1 ] * f''(e^x) * e^{2x} + [ 1 ] * f'(e^x) * e^x

d^3y/dx^3 = [ 1 ] * f'''(e^x) * e^{3x} + [ 3 ] * f''(e^x) * e^{2x} + [ 1 ] * f'(e^x) * e^x

d^4y/dx^4 = [ 1 ] * f''''(e^x) * e^{4x} + [ 6 ] * f'''(e^x) * e^{3x} + [ 7 ] * f''(e^x) * e^{2x} + [ 1 ] * f'(e^x) * e^x

d^5y/dx^5 = [ 1 ] * f'''''(e^x) * e^{5x} + [ 10 ] * f''''(e^x) * e^{4x} + [ 25 ] * f'''(e^x) * e^{3x} + [ 15 ] * f''(e^x) * e^{2x} + [ 1 ] * f'(e^x) * e^x

This pattern is observed in Mathematica for the first 10 cases, using the code below.

(End)

Number of factorizations of the superprimorial A006939(n) into factors > 1. - Gus Wiseman, Aug 21 2020

A number's prime signature (row n of A124010) is the sequence of positive exponents in its prime factorization, so a number has distinct prime multiplicities iff all the exponents in its prime signature are distinct.

The n-th superprimorial or Chernoff number is A006939(n) = Product_{i = 1..n} prime(i)^(n - i + 1).

T(n,k) is also the number of length-n vectors 0 <= v_i <= i summing to k whose nonzero values are all distinct.

Row sums = A007837.

Sum k! * T(n,k) = A032011.

Sum k * T(n,k) = A131623. - Geoffrey Critzer, Aug 30 2012.

T(n,k) is also the number of words w of length n over a k-ary alphabet {a1,a2,...,ak} with #(w,a1) > #(w,a2) > ... > #(w,ak) > 0, where #(w,x) counts the letters x in word w. T(5,2) = 15: aaaab, aaaba, aaabb, aabaa, aabab, aabba, abaaa, abaab, ababa, abbaa, baaaa, baaab, baaba, babaa, bbaaa. - Alois P. Heinz, Jun 21 2013

A number is a perfect power iff it is 1 or its prime exponents (signature) are not relatively prime.

The n-th superprimorial number is A006939(n) = Product_{i = 1..n} prime(i)^(n - i + 1).