A362967 -id:A362967 - 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

A077045 Doubly restricted composition numbers: number of compositions of 1+2+3+...+n = n(n+1)/2 into exactly n positive integers each no more than n.

Original entry on oeis.org

1, 1, 2, 7, 44, 381, 4332, 60691, 1012664, 19610233, 432457640, 10701243741, 293661065788, 8851373201919, 290711372717976, 10334165623697259, 395320344293410544, 16192709833199300337, 707125993042984343136, 32795665902734099555845, 1609908874238209683872480

Offset: 0

Henry Bottomley, Oct 22 2002

			a(3) = 7 since the compositions of 1+2+3=6 into exactly 3 positive integers each no more than 3 are: 1+2+3, 1+3+2, 2+1+3, 2+2+2, 2+3+1, 3+1+2, 3+2+1.

Alois P. Heinz, Table of n, a(n) for n = 0..100
Index entries for sequences related to compositions

Cf. A077042, A077046, A077047, A077048, A362967.

b:= proc(n, h, t) option remember;
      `if`(t*h b(n*(n-1)/2, n-1, n):
seq(a(n), n=0..20);  # Alois P. Heinz, Apr 10 2012

f[n_] := Union[ CoefficientList[ Expand[ Sum[x^j, {j, n}]^n], x]][[-1]]; Join[{1}, Array[f, 18]] (* Robert G. Wilson v, Apr 06 2012 *)
f[n_] := Block[{ip = IntegerPartitions[n (n + 1)/2, {n}, Range@ n], k = 1, s = 0}, len = Length[ip] + 1; While[k < len, s = s + Length@ Permutations[ ip[[k]]]; k++]; s]; Array[f, 11, 0] (* CAUTION, very slow and requires a lot of resources beyond 10, Robert G. Wilson v, Apr 09 2012 *)
b[n_, h_, t_] := b[n, h, t] = If[t*h < n, 0, If[n == 0, 1, Sum[b[n-j, Min[h, n-j], t-1], {j, 0, Min[n, h]}]]]; a[n_] := b[n*(n-1)/2, n-1, n]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Sep 16 2013, after Alois P. Heinz *)
Table[Sum[Binomial[n, k] Binomial[n + Binomial[n, 2] - n k - 1, n - 1] (-1)^k, {k, 0, Floor[(n-1)/2] + If[n == 0, 1, 0]}], {n, 0, 100}] (* Emanuele Munarini, Jul 15 2016 *)

makelist(sum(binomial(n,k)*binomial(n+binomial(n,2)-n*k-1,n-1)*(-1)^k,k,0,floor((n-1)/2)), n, 1, 12); /* for n >= 1; Emanuele Munarini, Jul 15 2016 */

a(n) = if(n<1,n==0,sum(k=0, (n-1)\2, binomial(n,k)*binomial(n + binomial(n,2) - n*k - 1, n-1)*(-1)^k)); \\ Andrew Howroyd, Feb 27 2018

a(n) = A077042(n, n). Roughly n^(n-3/2)*sqrt(6/Pi) by the central limit theorem and something like n^n*sqrt(6/(Pi*(n^3+0.3*n^2-0.91*n+0.3))) seems to be even closer.
From Emanuele Munarini, Jul 15 2016: (Start)
a(n) = [x^binomial(n,2)](1+x+x^2+...+x^(n-1))^n.
a(n) = Sum_{k = 0..floor((n-1)/2)} binomial(n,k)*binomial(n + binomial(n,2) - n*k - 1, n-1)*(-1)^k for n >=1. (End)

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.

A039744 Number of ways n(n-1) can be partitioned into the sum of 2(n-1) integers in the range 0..n.

Original entry on oeis.org

1, 1, 2, 5, 18, 73, 338, 1656, 8512, 45207, 246448, 1371535, 7764392, 44585180, 259140928, 1521967986, 9020077206, 53885028921, 324176252022, 1962530559999, 11947926290396, 73108804084505, 449408984811980, 2774152288318052, 17190155366056138, 106894140685782646

Offset: 0

Bill Daly (bill.daly(AT)tradition.co.uk)

nonn

An upper bound on A007878.

The indices of the odd terms appear to be A118113. - T. D. Noe, Dec 19 2006

Alois P. Heinz, Table of n, a(n) for n = 0..150 (terms n=1..65 from T. D. Noe)

Cf. A007878, A118113, A362967.

b:= proc(n, i, t) option remember; `if`(n=0, 1, `if`(t*i
      n, 0, b(n-i, i, t-1))))
    end:
a:= n-> b(n*(n-1), n, 2*(n-1)):
seq(a(n), n=0..25);  # Alois P. Heinz, May 15 2016

T[0,p_,m_]=1; T[k_,0,m_]=0; T[k_,p_,m_]:=T[k,p,m]=Sum[T[k+i,p-1,-i], {i,-m,-1}]; Table[T[n(n-1),2n-2,n], {n,40}] (* T. D. Noe, Dec 19 2006 *)

a039744(n) = polcoef(matpascal(3*n-1, x)[3*n-1, n+1], n*(n-1)); \\ Max Alekseyev, Jun 16 2023

def a039744(n): return gaussian_binomial(3*n-2, n)[n*(n-1)] # Max Alekseyev, Jun 16 2023

a(n) = T(n(n+1),2n-2,n), where T(k,p,m) is a recursive function that gives the number of partitions of k into p parts of 0..m. It is defined T(k,p,m) = sum_{i=1..m} T(k-i,p-1,i), with the boundary conditions T(0,p,m)=1 and T(k,0,m)=0 for all positive k, p and m. - T. D. Noe, Dec 19 2006
a(n) = coefficient of q^(n*(n-1)) in q-binomial(3*n-2, n). - Max Alekseyev, Jun 16 2023
a(n) ~ 3^(3*n - 3/2) / (Pi * n^2 * 2^(2*n - 1)). - Vaclav Kotesovec, Jun 17 2023

Definition corrected by Jozsef Pelikan (pelikan(AT)cs.elte.hu), Dec 05 2006
More terms from T. D. Noe, Dec 19 2006
a(0)=1 prepended by Alois P. Heinz, May 15 2016

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

A077045 Doubly restricted composition numbers: number of compositions of 1+2+3+...+n = n(n+1)/2 into exactly n positive integers each no more than n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

Formula

A039744 Number of ways n*(n-1) can be partitioned into the sum of 2*(n-1) integers in the range 0..n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

Extensions

A039744 Number of ways n(n-1) can be partitioned into the sum of 2(n-1) integers in the range 0..n.