A301897 Number of permutations b of length n that satisfy the Diaconis-Graham inequality I_n(b) + EX_n(b) <= D_n(b) with equality.

1, 2, 6, 23, 103, 511, 2719, 15205, 88197, 526018, 3206206, 19885911, 125107063, 796453594, 5121305414, 33213428285, 216998830397, 1426936199824, 9436710005524, 62723077297135, 418784925848463, 2807458708620337, 18889686239933521, 127520180043751313, 863473397167656913, 5863055250124397156

Offset: 1

Author

Petros Hadjicostas, Mar 28 2018

Keywords

• nonn

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

Weiner's g.f. (A(x)), see formula section, follows from either Theorem 6.5 of Cornwell and McNew (G(x)) or Corollary 1.2 of Woo (G(x)) by setting A(x) = G(x) - 1. - G. C. Greubel, Feb 17 2022

Examples

			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.
		

Links

• G. C. Greubel, Table of n, a(n) for n = 1..1000
• 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.
• Christopher Cornwell and Nathan McNew, Links and the Diaconis-Graham Inequality, arXiv:2404.16755 [math.CO], 2024.
• 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.
• Terence Tao, Elegant recursion for A301897, answer to question on MathOverflow. (2023)
• Alexander Woo, The shallow permutations are the unlinked permutations, arXiv:2201.12949 [math.CO], 2022. See Corollary 1.2 p. 2.

Crossrefs

Cf. A000045, A001006, A001519, A062869.

Column k=0 of A369518 (with different offset).

Programs

Magma

A301897:= func< n | n lt 3 select Factorial(n) else  Catalan(n) + (&+[ (&+[ Binomial(n,k-1)*Binomial(n-1,k+j)*Binomial(n-k+j-1,j-1)/j: j in [1..n-k-1]]): k in [1..n-2]]) >;
[A301897(n): n in [1..40]]; // G. C. Greubel, Feb 21 2022

Mathematica

a[n_]:= a[n]= If[n<2, n, 2*a[n-1] + Sum[a[k+2]*a[n-k-1] + (Sum[a[k+1-j]*a[j], {j, 0, k}] - 3*a[k+2] + 4*a[k+1])*a[n-k-2], {k, 0, n-3}]];
Table[a[n], {n, 40}] (* G. C. Greubel, Feb 20 2022 *)

PARI

upto(n)=my(v1); v1=vector(n+1, i, 0); v1[2]=1; for(i=2, n, v1[i+1]=2*v1[i] + sum(k=0, i-3, v1[k+3]*v1[i-k] + v1[i-k-1]*(4*v1[k+2] - 3*v1[k+3] + sum(j=0, k, v1[j+1]*v1[k-j+2])))); v1=vector(n, i, v1[i+1]) \\ Mikhail Kurkov, Aug 01 2023

Sage

@CachedFunction
def a(n):
    if (n<2): return n
    else: return 2*a(n-1) + sum(a(k+2)*a(n-k-1) + (sum(a(j)*a(k-j-1) for j in (0..k)) - 3*(k+2) + 4*a(k+1))*a(n-k-2) for k in (0..n-3))
[a(n) for n in (1..40)] # G. C. Greubel, Feb 20 2022

Formula

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

a(n) >= 1 + Sum_{m=2..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. - Michael D. Weiner, Jun 29 2020

a(n) = binomial(2*n,n)/(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). - Michael D. Weiner, Jun 30 2020

If, in Weiner's formula for a(n), we replace 1/j with (-1)^j/j, then we get the Motzkin numbers A001006. That is 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

From G. C. Greubel, Feb 20 2022: (Start)

a(n) = 2*a(n-1) + Sum_{k=0..n-3} ( a(k+2)*a(n-k-1) + ((Sum_{j=0..k} a(j)*a(k-j+1)) - 3*a(k+2) + 4*a(k+1))*a(n-k-2) ), with a(0) = 0, a(1) = 1.

a(n) = 1 + Sum_{k=1..n-1} ((-2)^(n-k-1)/(n-k))*binomial(n, k-1)*JacobiP(n-k-1, 2*k -2*n+1, k; 0), where JacobiP(n, a, b; x) is the Jacobi polynomial. (End)

D-finite with recurrence 3*(n+2)*(n-1)*a(n) +6*(10*n+9)*(n-2)*a(n-1) +(-421*n^2+1259*n-348)*a(n-2) +18*(72*n^2-334*n+369)*a(n-3) +(-1801*n^2+11339*n-17940)*a(n-4) -30*(n-5)*(10*n-51)*a(n-5) +25*(n-5)*(n-6)*a(n-6)=0. - R. J. Mathar, Jun 25 2023

a(n) ~ sqrt((1 + s)*(-3*s + 2*r*(2 + 3*s + s^2)) / (1 - 3*r + r^2*(4 + 3*s))) / (2*sqrt(Pi)*n^(3/2)*r^(n - 1/2)), where r = 0.13826667124150045791560993482... and s = 0.23874607068542101537529085629... are positive real roots of the system of equations s^2 + r^2*(1 + s)^2*(2 + s) = 3*r*s*(1 + s), 2*s + r^2*(5 + 8*s + 3*s^2) = 3*r*(1 + 2*s). - Vaclav Kotesovec, Jul 05 2024

Extensions

Terms a(15) onward added by G. C. Greubel, Feb 20 2022