login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(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)
OFFSET

1,2

COMMENTS

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 Fibonacci(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

LINKS

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

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

Christopher R. Cornwell and Nathan McNew, Unknotted cycles, arXiv:2007.04917 [math.CO], 2020. See p. 20.

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 re-examination of the Diaconis-Graham inequality, J. Combin. Math. Combin. Comput. 87 (2013), 275-295.

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), 145-178.

FORMULA

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

G.f.: A(x) satisfies 0 = x^2*A(x)^3+(4*x^2-3*x+1)*A(x)^2+(5*x^2-3*x)*A(x)+2*x^2 (conjectured). - Michael D. Weiner, Jun 29 2020

a(n) = binomial(2*n,n)*1/(n+1) + Sum_{k=1..n-2} Sum_{j=1..n-1-k} binomial(n,k-1)*binomial(n-1,k+j)*binomial(n-k+j-1,j-1)*1/j (conjectured). - Michael D. Weiner, Jun 30 2020

If in the above conjectured formula for a(n) by Michael D. Weiner, we replace 1/j with (-1)^j/j, then apparently we get the Motzkin numbers A001006. That is, it seems that A001006(n) = binomial(2*n,n)*1/(n+1) + Sum_{k=1..n-2} Sum_{j=1..n-1-k} binomial(n,k-1)*binomial(n-1,k+j)*binomial(n-k+j-1,j-1)*(-1)^j/j for n >= 1. - Petros Hadjicostas, Jul 01 2020

EXAMPLE

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.

CROSSREFS

Cf. A000045, A001006, A001519, A062869.

Sequence in context: A174193 A238639 A226995 * A022558 A004040 A216040

Adjacent sequences:  A301894 A301895 A301896 * A301898 A301899 A301900

KEYWORD

nonn,more

AUTHOR

Petros Hadjicostas, Mar 28 2018

STATUS

approved

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 June 16 04:56 EDT 2021. Contains 345056 sequences. (Running on oeis4.)