This site is supported by donations to The OEIS Foundation.



Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A301897 Number of permutations b of length n that satisfy the Diaconis-Graham inequality I_n(b) + EX_n(b) <= D_n(b) as equality. 2
1, 2, 6, 23, 103, 511, 2719, 15205, 88197, 526018, 3206206, 19885911, 125107063, 796453594 (list; graph; refs; listen; history; text; internal format)



Let S_n be the symmetric group of order n. For permutation b = (b_1,...,b_n) in S_n, let I_n(b) be the number of inversions in b; EX_n(b) be the smallest number of transpositions needed to transform b into the identity (1,...,n); and D_n(b) = Sum_{1 <= i <= n} |b_i - i|. Cayley (1849) proved that EX_n(b) equals n minus the number of cycles in permutation b. In the references for sequence A062869, the quantity D_n(b) is called the total distance of b or the total displacement of b.

Diaconis and Graham (1977) proved that I_n(b) + EX_n(b) <= D_n(b) <= 2*I_n(b), while Hadjicostas and Monico (2015) proved that D_n(b) <= I_n(b) + EX_n(b) + floor(n/2)*(floor(n/2) - 1). Here, a(n) equals the number of permutations b in S_n that satisfy the equality I_n(b) + EX_n(b) = D_n(b).

Let M_n be the set of all permutations b in S_n that satisfy I_n(b) + EX_n(b) = D_n(b). We describe how to construct M_n recursively. Let M_1 = S_1. For n >= 2, construct set M_{n1} from M_{n-1} as follows: Take a permutation c in M_{n-1} and an integer i in {1,...,n-1} and such that either the number of integers in c to the left of c_i that are greater than c_i is zero or the number of integers in c to the right of c_i that are less than c_i is zero. Replace c_i with n and put c_i at the end to form permutation b in M_{n1}. Construct set M_{n2} from M_{n-1} as follows: take a permutation c in M_{n-1} and attach n at the end to form permutation b in M_{n2}. Finally, define M_n as the union of sets M_{n1} and M_{n2}. See Hadjicostas and Monico (2013) for more details.

Diaconis and Graham (1977) and Hadjicostas and Monico (2013) examined when I_n(b) + EX_n(b) = D_n(b) = 2*I_n(b) (i.e., when both inequalities hold as equalities simultaneously). This happens if and only if I_n(b) = EX_n(b), which in turn happens if and only if permutation b belongs to M_n and has no 3-inversion (i.e., it avoids the pattern 321). A 3-inversion in b is a triple of integers (i,j,k) in {1,...,n} such that i < j < k but b_i > b_j > b_k. The number of permutations in S_n that satisfy both equalities is Fib(2n-1) = A001519(n) = A000045(2*n-1).

In the language of the Petersen-Tenner reference, these are permutations for which the depth is equal to the average of length and reflection length. - Joel B. Lewis, Sep 08 2019


P. Hadjicostas and C. Monico, A re-examination of the Diaconis-Graham inequality, J. Combin. Math. Combin. Comput. 87 (2013), 275-295.


Table of n, a(n) for n=1..14.

A. Cayley, Note on the theory of permutations, Philosophical Mag., 34 (1849), 527-529.

P. Diaconis and R. L. Graham, Spearman's footrule as a measure of disarray, J. R. Stat. Soc. Ser. B Stat. Methodol., 39 (1977), 262-268.

P. Hadjicostas and C. Monico, A new inequality related to the Diaconis-Graham inequalities and a new characterisation of the dihedral group, Australasian Journal of Combinatorics, 63(2) (2015), 226-245.

Petros Hadjicostas, Proof of a lower bound for a(n).

T. Kyle Petersen and Bridget Eileen Tenner, The depth of a permutation, arXiv:1202.4765 [math.CO], 2012.

T. Kyle Petersen and Bridget Eileen Tenner, The depth of a permutation, Journal of Combinatorics 6 (2015), pp. 145--178.


a(n) <= 1 + Sum_{2 <= m <= n} ((m-1)!*Sum_{1 <= k <= m-1} (2/k) - Sum_{1 <= k <= m-1} (k-1)!*(m-k-1)!).

a(n)/n! = O(log(n)/n).

a(n) >= 1 + Sum_{2 <= m <= n} (m-1)*Fib(2*m-3) = 1 + Sum_{2 <= m <= n} (m-1)*A001519(m-1). (For a proof of this lower bound, see the links above.)


For n=4, the only permutation b that does not satisfy I_4(b) + EX_4(b) = D_4(b) is b = 3412. (Here, b = 3412 means b_1 = 3, b_2 = 4, b_3 = 1, b_4 = 2. We do not use cycle notation.) We have I_4(b) = 4, EX_4(b) = 4-2 = 2, and D_4(b) = 8, and hence I_4(b) + EX_4(b) = 6 < D_4(b) = 8.

For n=5, the 5! - a(5) = 17 permutations b that do not satisfy I_5(b) + EX_5(b) = D_5(b) are the following: 14523, 24513, 34125, 34152, 34512, 34521, 35124, 35142, 35412, 41523, 42513, 43512, 45123, 45132, 45213, 45312, 54123.


Cf. A000045, A001519, A062869.

Sequence in context: A174193 A238639 A226995 * A022558 A004040 A216040

Adjacent sequences:  A301894 A301895 A301896 * A301898 A301899 A301900




Petros Hadjicostas, Mar 28 2018



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

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 11 21:00 EST 2019. Contains 329937 sequences. (Running on oeis4.)