The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. 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 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.

Last modified June 16 04:56 EDT 2021. Contains 345056 sequences. (Running on oeis4.)