|
%I #60 Jun 30 2023 02:38:36
%S 1,1,2,5,16,59,246,1105,5270,26231,135036,713898,3857113,21220020,
%T 118547774,671074583
%N Number of nondecreasing sequences that are differences of two permutations of 1,2,...,n.
%C 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
%C From _Olivier Gérard_, Sep 18 2007: (Start)
%C 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.
%C 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.
%C 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).
%C 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)
%C 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
%D Olivier Gérard and Karol Penson, Set partitions, multiset permutations and bi-permutations, in preparation.
%H C. Bebeacua, T. Mansour, A. Postnikov and S. Severini, <a href="https://arxiv.org/abs/math/0506334">On the X-rays of permutations</a>, arXiv:math/0506334 [math.CO], 2005.
%H David A. Corneth, <a href="/A019589/a019589.gp.txt">Nondecreasing sequences for a(n) where n = 0..8</a>.
%H J.-P. Davalan, <a href="http://jeux-et-mathematiques.davalan.org/mots/suites/tomo/index.html">Permutations et tomographie - X-rays</a>.
%H James D. Louck, <a href="https://www.emis.de/journals/HOA/IJMMS/Volume22_4/840789.pdf">Power of a determinant with two physical applications</a>, Internat. J. Math. & Math. Sci., Vol. 22, No 4(1999) pp. 745-759 - S 0161-1712(99)22745-7
%F a(n) <= A007747(n) <= A362967(n). - _Max Alekseyev_, Jun 19 2023
%p 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
%t a[n_] := Table[b[i+j], {i, n}, {j, n}] // Permanent // Expand // Length;
%t Array[a, 10, 0] (* _Jean-François Alcover_, May 29 2019, after _Vaclav Kotesovec_ *)
%o (Python)
%o import itertools
%o def a019589(n):
%o s = set()
%o for p in itertools.permutations(range(n)):
%o s.add(tuple(sorted([k - p[k] for k in range(n)])))
%o return len(s)
%o print([a019589(n) for n in range(10)])
%o # _Bert Dobbelaere_, Jan 19 2019
%o (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
%Y Cf. A007747, A019447, A019448, A086647, A175176, A290052, A289971, A362967.
%K nonn,more,nice
%O 0,3
%A Alex Postnikov (apost(AT)math.mit.edu)
%E More terms from _Olivier Gérard_, Sep 18 2007
%E Two more terms from _Vladeta Jovovic_, Oct 04 2007
%E a(0)=1 prepended by _Alois P. Heinz_, Jul 24 2017
%E a(13)-a(14) from _Bert Dobbelaere_, Jan 19 2019
%E a(15) from _Max Alekseyev_, Jun 28 2023
| 