

A301897


Number of permutations b of length n that satisfy the DiaconisGraham 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_{n1} as follows: Take a permutation c in M_{n1} and an integer i in {1,...,n1} 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_{n1} as follows: take a permutation c in M_{n1} 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 3inversion (i.e., it avoids the pattern 321). A 3inversion 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(2n1) = A001519(n) = A000045(2*n1).
In the language of the PetersenTenner 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), 527529.
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), 262268.
P. Hadjicostas and C. Monico, A reexamination of the DiaconisGraham inequality, J. Combin. Math. Combin. Comput. 87 (2013), 275295.
P. Hadjicostas and C. Monico, A new inequality related to the DiaconisGraham inequalities and a new characterisation of the dihedral group, Australasian Journal of Combinatorics, 63(2) (2015), 226245.
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), 145178.


FORMULA

a(n) <= 1 + Sum_{2 <= m <= n} ((m1)!*Sum_{1 <= k <= m1} (2/k)  Sum_{1 <= k <= m1} (k1)!*(mk1)!).
a(n)/n! = O(log(n)/n).
a(n) >= 1 + Sum_{2 <= m <= n} (m1)*Fibonacci(2*m3) = 1 + Sum_{2 <= m <= n} (m1)*A001519(m1). (For a proof of this lower bound, see the links above.)
G.f.: A(x) satisfies 0 = x^2*A(x)^3+(4*x^23*x+1)*A(x)^2+(5*x^23*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..n2} Sum_{j=1..n1k} binomial(n,k1)*binomial(n1,k+j)*binomial(nk+j1,j1)*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..n2} Sum_{j=1..n1k} binomial(n,k1)*binomial(n1,k+j)*binomial(nk+j1,j1)*(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) = 42 = 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



