A175176 -id:A175176 - cp's OEIS frontend

A019589 Number of nondecreasing sequences that are differences of two permutations of 1,2,...,n.

1, 1, 2, 5, 16, 59, 246, 1105, 5270, 26231, 135036, 713898, 3857113, 21220020, 118547774, 671074583

Offset: 0

Alex Postnikov (apost(AT)math.mit.edu)

Also, number of nondecreasing sequences that are sums of two permutations of order n. If nondecreasing requirement is dropped, the sequence becomes A175176. - Max Alekseyev, Jun 19 2023
From Olivier Gérard, Sep 18 2007: (Start)
Number of classes of permutations arrays giving the same partition by the following transformation (equivalent in this case to X-rays but more general): on the matrix representation of a permutation of order n, the sum (i.e., here, number of ones) in the i-th antidiagonal is the number of copies of i in the partition.
This gives an injection of permutations of n into partitions with parts at most 2n-1. The first or the last antidiagonal can be omitted, reducing the size of parts to 2n-2 without changing the number of classes.
This sequence is called Lambda_{n,1} in Louck's paper and appears explicitly on p. 758. Terms up to 10 were computed by Myron Stein (arXiv).
This is similar to the number of Schur functions studied by Di Francesco et al. (A007747) related to the powers of the Vandermonde determinant. Also number of classes of straight (monotonic) crossing bi-permutations. (End)
Also number of monomials in expansion of permanent of an n X n Hankel matrix [t(i+j)] in terms of its entries (cf. A019448). - Vaclav Kotesovec, Mar 29 2019

Olivier Gérard and Karol Penson, Set partitions, multiset permutations and bi-permutations, in preparation.

C. Bebeacua, T. Mansour, A. Postnikov and S. Severini, On the X-rays of permutations, arXiv:math/0506334 [math.CO], 2005.
David A. Corneth, Nondecreasing sequences for a(n) where n = 0..8.
J.-P. Davalan, Permutations et tomographie - X-rays.
James D. Louck, Power of a determinant with two physical applications, Internat. J. Math. & Math. Sci., Vol. 22, No 4(1999) pp. 745-759 - S 0161-1712(99)22745-7

Cf. A007747, A019447, A019448, A086647, A175176, A290052, A289971, A362967.

with(LinearAlgebra): f:=n->nops([coeffs(Permanent(Matrix(n, (i, j) -> a[i+j])))]): [seq(f(n), n=1..10)]; # Vaclav Kotesovec, Mar 29 2019

a[n_] := Table[b[i+j], {i, n}, {j, n}] // Permanent // Expand // Length;
Array[a, 10, 0] (* Jean-François Alcover, May 29 2019, after Vaclav Kotesovec *)

a(n) = my(l=List(), v=[1..n]);for(i=0, n!-1, listput(l, vecsort(v-numtoperm(n,i)))); listsort(l, 1); #l

import itertools
def a019589(n):
    s = set()
    for p in itertools.permutations(range(n)):
        s.add(tuple(sorted([k - p[k] for k in range(n)])))
    return len(s)
print([a019589(n) for n in range(10)])
# Bert Dobbelaere, Jan 19 2019

a(n) <= A007747(n) <= A362967(n). - Max Alekseyev, Jun 19 2023

More terms from Olivier Gérard, Sep 18 2007
Two more terms from Vladeta Jovovic, Oct 04 2007
a(0)=1 prepended by Alois P. Heinz, Jul 24 2017
a(13)-a(14) from Bert Dobbelaere, Jan 19 2019
a(15) from Max Alekseyev, Jun 28 2023

A362968 Number of integral points in 2 * permutohedron of order n.

Original entry on oeis.org

1, 3, 19, 201, 3081, 62683, 1598955, 49180113, 1773405649, 73410669171, 3432267261699, 178922825114905, 10291053760222041, 647436905815864011, 44229766376059342171, 3260749830852693615777, 258039101519624535653025

Offset: 1

Max Alekseyev, Jun 17 2023

nonn

Every vectorial sum of two permutations represents an integral point in 2*permutohedron, however the converse does not hold. Hence, a(n) >= A175176(n) for all n, where the equality holds only for n <= 5.

Number of points up to their components order is given by A007747.

C. Bebeacua, T. Mansour, A. Postnikov, and S. Severini. On the X-rays of permutations, arXiv:math/0506334 [math.CO], 2005.
Wikipedia, Permutohedron.

Cf. A007747, A138464, A175176, A362967.

w := LambertW(-2*x): egf := exp(-w * (2 + w) / 4): ser := series(egf, x, 20):
seq(n! * coeff(ser, x, n), n = 1..17); # Peter Luschny, Jun 19 2023

a362968(n) = my(x=y+O(y^(n+1))); n! * polcoef( exp(-lambertw(-2*x)/2 - lambertw(-2*x)^2/4), n );

a(n) = Sum_{k=0..n-1} A138464(n,k) * 2^k, which is the value of the Ehrhart polynomial of permutohedron at t = 2.

E.g.f.: exp(-W(-2*x)/2 - W(-2*x)^2/4), where W() is the Lambert function.

A381244 Number of regions in the arrangement of hyperplanes corresponding to the nonzero differences of two permutations of order n.

Original entry on oeis.org

1, 1, 2, 12, 3696

Offset: 0

Max Alekseyev, Feb 17 2025

The number of distinct hyperplanes is given by A381243.

Cf. A019589, A175176, A362968, A381243.

def a381244(n): return HyperplaneArrangements(QQ,tuple(f'x{i}' for i in range(n)))([[list(r),0] for p in Permutations(n) for r in Permutations([p[i]-i-1 for i in range(n)]) if vector(r)>0]).n_regions()

A381243 Number of hyperplanes defined by the nonzero differences of two permutations of order n.

Original entry on oeis.org

0, 0, 1, 6, 85, 1370, 30481, 778610, 24409645, 881325366, 36635553601, 1713454403210, 89415912126223, 5143372266050837, 323667807885619744, 22112062644980805684

Offset: 0

Max Alekseyev, Feb 17 2025

Each of A175176(n) - 1 nonzero differences between two permutations (viewed as vectors) defines a hyperplane in the n-dimensional space. a(n) gives the number of pairwise distinct hyperplanes among them.

Cf. A019589, A175176, A362968, A381244, A381339.

A381339 Number of vector differences between two permutations of order n, up to multiplication by nonzero rational numbers and permutations of the components.

Original entry on oeis.org

1, 1, 2, 3, 9, 28, 128, 539, 2651, 13000, 67466, 355381, 1926343, 10590537, 59234734, 335302599

Offset: 0

Max Alekseyev, Feb 20 2025

Nonzero difference vectors are associated with their images in the projective space, and in addition we do not distinguish vectors that can be permuted one into the other. In the affine space, their number (including zero vector) is given by A019589, implying that a(n) <= A019589(n). Nonzero difference vectors in the projective space are counted by A381243.

			For n = 3, there are A019589(3) = 5 difference vectors up to permutation of components: (-2, 0, 2), (-2, 1, 1), (-1, -1, 2), (-1, 0, 1), and (0, 0, 0). However, (-2, 0, 2) and (-1, 0, 1) are the same up to a factor 2, and (-2, 1, 1) and (-1, -1, 2) are the same up to negation and reversing the order. Hence, a(3) = 3.

Cf. A019589, A175176, A362968, A381243, A381244.

A384035 Number of vector differences between two permutations of order n, up to multiplication by positive rational numbers and permutations of the components.

Original entry on oeis.org

1, 1, 2, 4, 13, 49, 228, 1034, 5133, 25710, 133872, 708976, 3846150, 21170077, 118429072, 670537495

Offset: 0

Max Alekseyev, May 17 2025

			For n = 3, there are A019589(3) = 5 difference vectors up to permutation of components: (-2, 0, 2), (-2, 1, 1), (-1, -1, 2), (-1, 0, 1), and (0, 0, 0). However, (-2, 0, 2) and (-1, 0, 1) are the same up to a factor 2. Hence, a(3) = 4.

Cf. A019589, A175176, A362968, A381243, A381244, A381339.

cp's OEIS Frontend

A019589 Number of nondecreasing sequences that are differences of two permutations of 1,2,...,n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A362968 Number of integral points in 2 * permutohedron of order n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

Formula

A381244 Number of regions in the arrangement of hyperplanes corresponding to the nonzero differences of two permutations of order n.

Views

Author

Keywords

Comments

Crossrefs

Programs

Sage

A381243 Number of hyperplanes defined by the nonzero differences of two permutations of order n.

Views

Author

Keywords

Comments

Crossrefs

A381339 Number of vector differences between two permutations of order n, up to multiplication by nonzero rational numbers and permutations of the components.

Views

Author

Keywords

Comments

Examples

Crossrefs

A384035 Number of vector differences between two permutations of order n, up to multiplication by positive rational numbers and permutations of the components.

Views

Author

Keywords

Examples

Crossrefs