A062866 -id:A062866 - cp's OEIS frontend

A062868 Number of permutations of degree n with barycenter 0.

1, 1, 2, 4, 14, 46, 282, 1394, 12658, 83122, 985730, 8012962, 116597538, 1127575970, 19410377378, 217492266658, 4320408974978, 55023200887938, 1238467679662722, 17665859065690754, 444247724347355554, 7015393325151055906, 194912434760367113570, 3375509056735963889634

Offset: 0

Olivier Gérard, Jun 26 2001

The barycenter or signcenter of a permutation is the sum of the signs of the difference between initial and final positions of the objects.

			(4,1,3,5,2) has difference (3,-1,0,1,-3) and signs (1,-1,0,1,-1) with total 0.

Alois P. Heinz, Table of n, a(n) for n = 0..450 (first 151 terms from Maxwell Jiang)

Column k=0 of A062866 or of A062867.

Cf. A179567, A196687, A196688, A320337.

b:= proc(s, t) option remember; (n-> `if`(abs(t)>n, 0, `if`(n=0, 1,
      add(b(s minus {j}, t+signum(n-j)), j=s))))(nops(s))
    end:
a:= n-> b({$1..n}, 0):
seq(a(n), n=0..14);  # Alois P. Heinz, Jul 31 2018

E1[n_ /; n >= 0, 0] = 1;
E1[n_, k_] /; k < 0 || k > n = 0;
E1[n_, k_] := E1[n, k] = (n-k) E1[n-1, k-1] + (k+1) E1[n-1, k];
b[n_] := Sum[(-1)^(n-k) E1[n+k, n] Binomial[2n, n-k], {k, 0, n}];
a[n_] := Sum[Binomial[n, n-2k] b[k], {k, 0, n/2}];
a /@ Range[0, 150] (* Jean-François Alcover, Oct 29 2020, after Peter Luschny in A320337 *)

a(n) = Sum_{k=0..floor(n/2)} binomial(n, n-2*k)*A320337(k). - Maxwell Jiang, Dec 19 2018 (added by editors)

a(n) ~ sqrt(3) * (1 + exp(-2)*(-1)^n) * n^n / exp(n). - Vaclav Kotesovec, Oct 29 2020

One more term from Vladeta Jovovic, Jun 28 2001
a(11)-a(14) from Hugo Pfoertner, Sep 23 2004
a(15)-a(18) from R. H. Hardin, Jul 18 2010
a(19)-a(22) from Kyle G Hess, Jul 30 2018
a(0)=1 prepended by Alois P. Heinz, Jul 30 2018
Terms a(23) and beyond from Maxwell Jiang, Dec 19 2018

A062869 Triangle read by rows: For n >= 0, k >= 0, T(n,k) is the number of permutations pi of n such that the total distance Sum_i abs(i-pi(i)) = 2k. Equivalently, k = Sum_i max(i-pi(i),0).

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 3, 1, 3, 7, 9, 4, 1, 4, 12, 24, 35, 24, 20, 1, 5, 18, 46, 93, 137, 148, 136, 100, 36, 1, 6, 25, 76, 187, 366, 591, 744, 884, 832, 716, 360, 252, 1, 7, 33, 115, 327, 765, 1523, 2553, 3696, 4852, 5708, 5892, 5452, 4212, 2844, 1764, 576, 1, 8, 42, 164, 524

Offset: 0

Olivier Gérard, Jun 26 2001

Number of possible values is 1,2,3,5,7,10,13,17,21,... = A033638. Maximum distance divided by 2 is the same minus one, i.e., 0,1,2,4,6,9,12,16,20,... = A002620.

T. Kyle Petersen and Bridget Eileen Tenner proved that T(n,k) is also the number of permutations of n for which the sum of descent differences equals k. - Susanne Wienand, Sep 11 2014

			Triangle T(n,k) begins:
  1;
  1;
  1, 1;
  1, 2,  3;
  1, 3,  7,  9,   4;
  1, 4, 12, 24,  35,  24,  20;
  1, 5, 18, 46,  93, 137, 148, 136, 100,  36;
  1, 6, 25, 76, 187, 366, 591, 744, 884, 832, 716, 360, 252;
  ...
(4,3,1,2) has distances (3,1,2,2), sum is 8 and there are 3 other permutations of degree 4 with this sum.

D. E. Knuth, The Art of Computer Programming, vol. 3, (1998), page 22 (exercise 28) and page 597 (solution and comments).

Daniel Graf and Alois P. Heinz, Rows n = 0..50, flattened (first 31 rows from Alois P. Heinz)
Max Alekseyev, Proof that T(n,k) is even for k>=n, SeqFan Mailing List, Dec 07 2006
Andreas Bärtschi, Barbara Geissmann, Daniel Graf, Tomas Hruz, Paolo Penna, and Thomas Tschager, On computing the total displacement number via weighted Motzkin paths, arXiv:1606.05538 [cs.DS], 2016. See pp. 1, 3-5, 13. - _Daniel Graf_, Jun 20 2016
P. Diaconis and R. L. Graham, Spearman's Footrule as a Measure of Disarray, J. Royal Stat. Soc. B, 39 (1977), 262-268.
FindStat - Combinatorial Statistic Finder, The depth of a permutation., The sum of the descent differences of a permutations.
Mathieu Guay-Paquet and T. Kyle Petersen, The generating function for total displacement, arXiv:1404.4674 [math.CO], 2014.
Mathieu Guay-Paquet and T. Kyle Petersen, The generating function for total displacement, The Electronic Journal of Combinatorics, 21(3) (2014), #P3.37.
Dirk Liebhold, Gabriele Nebe, and Angeles Vazquez-Castro, Network coding and spherical buildings, arXiv preprint arXiv:1612.07177 [cs.IT], 2016. See p. 4.
T. Kyle Petersen and Bridget Eileen Tenner, The depth of a permutation, arXiv:1202.4765 [math.CO], 2012.
Balázs R. Sziklai, Attila Gere, Károly Héberger, and Jochen Staudacher, rSRD: An R package for the Sum of Ranking Differences statistical procedure, arXiv:2502.03208 [math.ST], 2025. See p. 34.

Cf. A005990, A009006, A062866, A062867, A062870, A072949, A301897.
Row sums give A000142.
T(2n,n) gives A072948.
A357329 is a sub-triangle.

# The following program yields the entries of the specified row n
n := 9: with(combinat): P := permute(n): excsum := proc (p) (1/2)*add(abs(p[i]-i), i = 1 .. nops(p)) end proc: f[n] := sort(add(t^excsum(P[j]), j = 1 .. factorial(n))): seq(coeff(f[n], t, j), j = 0 .. floor((1/4)*n^2)); # Emeric Deutsch, Apr 02 2010
# Maple program using the g.f. given by Guay-Paquey and Petersen:
g:= proc(h, n) local i, j; j:= irem(h, 2, 'i');
       1-`if`(h=n, 0, (i+1)*z*t^(i+j)/g(h+1, n))
    end:
T:= n-> (p-> seq(coeff(p, t, k), k=0..degree(p)))
        (coeff(series(1/g(0, n), z, n+1), z, n)):
seq(T(n), n=0..10);  # Alois P. Heinz, May 02 2014

g[h_, n_] := Module[{i, j}, {i, j} = QuotientRemainder[h, 2]; 1 - If[h == n, 0, (i + 1)*z*t^(i + j)/g[h + 1, n]]]; T[n_] := Function[p, Table[ Coefficient[p, t, k], {k, 0, Exponent[p, t]}]][SeriesCoefficient[ 1/g[0, n], {z, 0, n}]]; Table[T[n], {n, 1, 10}] // Flatten (* Jean-François Alcover, Jan 07 2016, after Alois P. Heinz *)
f[i_] := If[i == 1, 1, -(i-1)^2 t^(2i - 3) z^2];
g[i_] := 1 - (2i - 1) t^(i-1) z;
cf = ContinuedFractionK[f[i], g[i], {i, 1, 5}];
CoefficientList[#, t]& /@ CoefficientList[cf + O[z]^10, z] // Rest // Flatten (* Jean-François Alcover, Nov 25 2018, after Mathieu Guay-Paquet *)

# The following Sage program
# yields the entries of the first n rows
# as a list of lists
def get_first_rows(n):
    R, t = PolynomialRing(ZZ, 't').objgen()
    S, z = PowerSeriesRing(R, 'z').objgen()
    gf = S(1).add_bigoh(1)
    for i in srange(n, 0, -1):
        a = (i+1) // 2
        b = i // 2
        gf = 1 / (1 - a * t^b * z * gf)
    return [list(row) for row in gf.shift(-1)]
# Mathieu Guay-Paquet, Apr 30 2014

From Mathieu Guay-Paquet, Apr 30 2014: (Start)
G.f.: 1/(1-z/(1-t*z/(1-2*t*z/(1-2*t^2*z/(1-3*t^2*z/(1-3*t^3*z/(1-4*t^3*z/(1-4*t^4*z/(...
This is a continued fraction where the (2i)th numerator is (i+1)*t^i*z, and the (2i+1)st numerator is (i+1)*t^(i+1)*z for i >= 0. The coefficient of z^n gives row n, n >= 1, and the coefficient of t^k gives column k, k >= 0. (End)
From Alois P. Heinz, Oct 02 2022: (Start)
Sum_{k=0..floor(n^2/4)} k * T(n,k) = A005990(n).
Sum_{k=0..floor(n^2/4)} (-1)^k * T(n,k) = A009006(n). (End).

T(0,0)=1 prepended by Alois P. Heinz, Oct 03 2022

A062867 Triangle read by rows: entries give numbers of permutations of [1..n] by absolute barycenter.

Original entry on oeis.org

1, 1, 2, 4, 2, 14, 8, 2, 46, 62, 10, 2, 282, 292, 132, 12, 2, 1394, 2578, 784, 268, 14, 2, 12658, 15472, 9718, 1920, 534, 16, 2, 83122, 171662, 69318, 33230, 4470, 1058, 18, 2, 985730, 1282604, 964544, 276044, 107660, 10100, 2096, 20, 2, 8012962, 17465978, 8199268, 4851200, 1022824, 337988, 22396, 4160, 22, 2

Offset: 0

Olivier Gérard, Jun 26 2001

The barycenter or signcenter of a permutation is the sum of the signs of the difference between initial and final positions of the objects.

			[1], [2], [4, 2], [14, 8, 2], [46, 62, 10, 2], [282, 292, 132, 12, 2], ...
(1,6,2,3,4,5,7) has difference (0,5,-1,-1,-1,-1,0) and signs (0,1,-1,-1,-1,-1,0) with total -3, absolute value is 3. This is one of 268 such permutations of degree 7.
Triangle T(n,k) begins:
       1;
       1;
       2;
       4,       2;
      14,       8,      2;
      46,      62,     10,      2;
     282,     292,    132,     12,      2;
    1394,    2578,    784,    268,     14,     2;
   12658,   15472,   9718,   1920,    534,    16,    2;
   83122,  171662,  69318,  33230,   4470,  1058,   18,  2;
  985730, 1282604, 964544, 276044, 107660, 10100, 2096, 20, 2;

Alois P. Heinz, Rows n = 0..20, flattened

Column k=0 gives A062868.
Row sums give A000142.
Cf. A062866.

b:= proc(s, t) option remember; (n-> `if`(n=0, x^t,
      add(b(s minus {j}, t+signum(n-j)), j=s)))(nops(s))
    end:
T:= n-> (p-> seq(coeff(p, x, i)*`if`(i=0, 1, 2), i=0..degree(p)))(b({$1..n}, 0)):
seq(T(n), n=0..12);  # Alois P. Heinz, Jul 31 2018

b[s_, t_] := b[s, t] = With[{n = Length[s]}, If[n == 0, x^t, Sum[b[s  ~Complement~ {j}, t + Sign[n - j]], {j, s}]]];
T[n_] := With[{p = b[Range[n], 0]}, Table[Coefficient[p, x, i]*If[i == 0, 1, 2], {i, 0, Exponent[p, x]}]];
Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Jan 25 2021, after Alois P. Heinz *)

T(n,0) = A062868(n) = A062866(n,0), T(n,k) = 2 * A062866(n,k) for k>0. - Alois P. Heinz, Jul 31 2018

More terms from Vladeta Jovovic, Jun 29 2001

A062870 Number of permutations of degree n with greatest sum of distances.

Original entry on oeis.org

1, 1, 1, 3, 4, 20, 36, 252, 576, 5184, 14400, 158400, 518400, 6739200, 25401600, 381024000, 1625702400, 27636940800, 131681894400, 2501955993600, 13168189440000, 276531978240000, 1593350922240000, 36647071211520000, 229442532802560000, 5736063320064000000

Offset: 0

Olivier Gérard, Jun 26 2001

nonn

Number of possible values is 1,2,3,5,7,10,13,17,21,... which I conjecture to be A033638. Maximum distance divided by 2 is the same minus one, i.e., 0,1,2,4,6,9,12,16,20,... which seems to be A002620.

			(4,3,1,2) has distances (3,1,2,2), sum is 8 and there are 3 other permutations of degree 4 {3, 4, 1, 2}, {3, 4, 2, 1}, {4, 3, 2, 1} with this sum which is the maximum possible.

Georg Fischer, Table of n, a(n) for n = 0..506 (first 301 terms from _Alois P. Heinz_)
Max Alekseyev, Proof of conjecture
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), pp. 145--178.

Cf. A002620, A062866, A062867, A062869.

A007590(n) is the greatest sum of distances for a permutation of degree n. - Dmitry Kamenetsky, Nov 14 2017

a:= proc(n) option remember; `if`(n<2, 1+n*(n-1),
      (n*((n-1)^2*(3*n-4)*a(n-2)-4*a(n-1)))/(4*(n-1)*(3*n-7)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Jan 16 2014

a[n_?EvenQ] := (n/2)!^2; a[n_?OddQ] := n*((n-1)/2)!^2; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Apr 15 2015 *)

for(k=0,20,print1((2*k+1)*k!^2","(k+1)!^2",")) \\ Herman Jamke (hermanjamke(AT)fastmail.fm), Dec 27 2007

a(n) = (n/2)!^2 if n is even else n*((n-1)/2)!^2, cf. A092186. - Conjectured by Vladeta Jovovic, Aug 21 2007; proved (see the link) by Max Alekseyev, Aug 21 2007

a(n) = A062869(n,floor(n^2/4)) for n>=1. - Alois P. Heinz, Oct 02 2022

a(10)-a(14) from Hugo Pfoertner, Sep 23 2004

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Dec 27 2007

cp's OEIS Frontend

A062868 Number of permutations of degree n with barycenter 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A062869 Triangle read by rows: For n >= 0, k >= 0, T(n,k) is the number of permutations pi of n such that the total distance Sum_i abs(i-pi(i)) = 2k. Equivalently, k = Sum_i max(i-pi(i),0).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

Extensions

A062867 Triangle read by rows: entries give numbers of permutations of [1..n] by absolute barycenter.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A062870 Number of permutations of degree n with greatest sum of distances.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A169934 Number of permutations of 1..n with the number moved left exceeding the number moved right by 2.

Views

Author

Keywords

Crossrefs

Extensions

A179562 Number of permutations of 1..n with the number moved left exceeding the number moved right by 1.

Views

Author

Keywords

Crossrefs

Extensions

A179564 Number of permutations of 1..n with the number moved left exceeding the number moved right by 3.

Views

Author

Keywords

Crossrefs

Extensions

A179565 Number of permutations of [n] with the number moved left exceeding the number moved right by 4.

Views

Author

Keywords

Crossrefs

Extensions