|
| |
|
|
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.
|
|
3
|
|
|
|
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
(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
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
|
|
|
LINKS
|
Christopher R. Cornwell and Nathan McNew, Unknotted cycles, arXiv:2007.04917 [math.CO], 2020. See p. 20.
|
|
|
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)/n! = O(log(n)/n).
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
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
|
|
|
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.
|
|
|
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}]];
|
|
|
PROG
|
(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))
(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]]) >;
(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]
|
|
|
CROSSREFS
|
Column k=0 of A369518 (with different offset).
|
|
|
KEYWORD
|
nonn,changed
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
