

A019589


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


5



1, 1, 2, 5, 16, 59, 246, 1105, 5270, 26231, 135036, 713898, 3857113, 21220020, 118547774
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

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 Xrays but more general): on the matrix representation of a permutation of order n, the sum (i.e., here, number of ones) in the ith 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 2n1. The first or the last antidiagonal can be omitted, reducing the size of parts to 2n2 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 bipermutations. (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


REFERENCES

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


LINKS

Table of n, a(n) for n=0..14.
C. Bebeacua, T. Mansour, A. Postnikov and S. Severini, On the Xrays 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  Xrays.
James D. Louck, Power of a determinant with two physical applications, Internat. J. Math. & Math. Sci., Vol. 22, No 4(1999) pp. 745759  S 01611712(99)227457


MAPLE

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


MATHEMATICA

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


PROG

(Python)
import itertools
def a019589(n):
....s=set()
....for p in itertools.permutations(range(n)):
........s.add(tuple(sorted([kp[k] for k in range(n)])))
....return len(s)
# Bert Dobbelaere, Jan 19 2019
(PARI) a(n) = my(l=List(), v=[1..n]); for(i=0, n!1, listput(l, vecsort(vnumtoperm(n, i)))); listsort(l, 1); #l


CROSSREFS

Cf. A290052, A289971.
Cf. A019447, A019448, A086647.
Sequence in context: A280760 A000753 A007878 * A087949 A028333 A007747
Adjacent sequences: A019586 A019587 A019588 * A019590 A019591 A019592


KEYWORD

nonn,more,nice


AUTHOR

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


EXTENSIONS

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


STATUS

approved



