|
%I #118 Apr 21 2024 22:26:05
%S 1,2,6,23,103,511,2719,15205,88197,526018,3206206,19885911,125107063,
%T 796453594,5121305414,33213428285,216998830397,1426936199824,
%U 9436710005524,62723077297135,418784925848463,2807458708620337,18889686239933521,127520180043751313,863473397167656913,5863055250124397156
%N Number of permutations b of length n that satisfy the Diaconis-Graham inequality I_n(b) + EX_n(b) <= D_n(b) with equality.
%C 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.
%C 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).
%C 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.
%C 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).
%C 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
%C 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
%H G. C. Greubel, <a href="/A301897/b301897.txt">Table of n, a(n) for n = 1..1000</a>
%H A. Cayley, <a href="https://doi.org/10.1080/14786444908646287">Note on the theory of permutations</a>, Philosophical Mag., 34 (1849), 527-529.
%H Christopher R. Cornwell and Nathan McNew, <a href="https://arxiv.org/abs/2007.04917">Unknotted cycles</a>, arXiv:2007.04917 [math.CO], 2020. See p. 20.
%H P. Diaconis and R. L. Graham, <a href="http://www.jstor.org/stable/2984804">Spearman's footrule as a measure of disarray</a>, J. R. Stat. Soc. Ser. B Stat. Methodol., 39 (1977), 262-268.
%H P. Hadjicostas and C. Monico, <a href="/A301897/a301897_1.pdf">A re-examination of the Diaconis-Graham inequality</a>, J. Combin. Math. Combin. Comput. 87 (2013), 275-295.
%H P. Hadjicostas and C. Monico, <a href="https://ajc.maths.uq.edu.au/pdf/63/ajc_v63_p226.pdf">A new inequality related to the Diaconis-Graham inequalities and a new characterisation of the dihedral group</a>, Australasian Journal of Combinatorics, 63(2) (2015), 226-245.
%H Petros Hadjicostas, <a href="/A301897/a301897.pdf">Proof of a lower bound for a(n)</a>.
%H T. Kyle Petersen and Bridget Eileen Tenner, <a href="http://arxiv.org/abs/1202.4765">The depth of a permutation</a>, arXiv:1202.4765 [math.CO], 2012.
%H T. Kyle Petersen and Bridget Eileen Tenner, <a href="http://dx.doi.org/10.4310/JOC.2015.v6.n1.a9">The depth of a permutation</a>, Journal of Combinatorics 6 (2015), 145-178.
%H Terence Tao, <a href="https://mathoverflow.net/a/449471/231922">Elegant recursion for A301897</a>, answer to question on MathOverflow. (2023)
%H Alexander Woo, <a href="https://arxiv.org/abs/2201.12949">The shallow permutations are the unlinked permutations</a>, arXiv:2201.12949 [math.CO], 2022. See Corollary 1.2 p. 2.
%F 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)!).
%F a(n)/n! = O(log(n)/n).
%F 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.)
%F 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
%F 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
%F 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
%F From _G. C. Greubel_, Feb 20 2022: (Start)
%F 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.
%F 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)
%F 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
%e 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.
%e 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.
%t 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}]];
%t Table[a[n], {n, 40}] (* _G. C. Greubel_, Feb 20 2022 *)
%o (Sage)
%o @CachedFunction
%o def a(n):
%o if (n<2): return n
%o 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))
%o [a(n) for n in (1..40)] # _G. C. Greubel_, Feb 20 2022
%o (Magma)
%o 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]]) >;
%o [A301897(n): n in [1..40]]; // _G. C. Greubel_, Feb 21 2022
%o (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 [verification needed]
%Y Cf. A000045, A001006, A001519, A062869.
%Y Column k=0 of A369518 (with different offset).
%K nonn,changed
%O 1,2
%A _Petros Hadjicostas_, Mar 28 2018
%E Terms a(15) onward added by _G. C. Greubel_, Feb 20 2022
|
