login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A019589 Number of nondecreasing sequences that are differences of two permutations of 1,2,...,n. 7
1, 1, 2, 5, 16, 59, 246, 1105, 5270, 26231, 135036, 713898, 3857113, 21220020, 118547774, 671074583 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
COMMENTS
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
REFERENCES
Olivier Gérard and Karol Penson, Set partitions, multiset permutations and bi-permutations, in preparation.
LINKS
C. Bebeacua, T. Mansour, A. Postnikov and S. Severini, On the X-rays of permutations, arXiv:math/0506334 [math.CO], 2005.
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
FORMULA
a(n) <= A007747(n) <= A362967(n). - Max Alekseyev, Jun 19 2023
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] (* Jean-Franç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([k - p[k] for k in range(n)])))
return len(s)
print([a019589(n) for n in range(10)])
# Bert Dobbelaere, Jan 19 2019
(PARI) a(n) = my(l=List(), v=[1..n]); for(i=0, n!-1, listput(l, vecsort(v-numtoperm(n, i)))); listsort(l, 1); #l
CROSSREFS
Sequence in context: A000753 A346813 A007878 * A087949 A028333 A007747
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
a(15) from Max Alekseyev, Jun 28 2023
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 16:58 EDT 2024. Contains 371254 sequences. (Running on oeis4.)