A059615 a(n) is the number of non-parallel lines determined by a pair of vertices (extreme points) in the polytope of real n X n doubly stochastic matrices. The vertices are the n! permutation matrices.

0, 1, 15, 240, 6040, 217365, 10651011, 681667840, 55215038880, 5521504648185, 668102052847735, 96206695728917136, 16258931576714668920, 3186750589054271109325, 717018882536990087693835

Offset

1,3

References

M. Marcus, Hermitian Forms and Eigenvalues, in Survey of Numerical Analysis, J. Todd, ed. McGraw-Hill, New York, 1962.

Links

Table of n, a(n) for n=1..15.

Formula

a(n) = (1/2)*Sum_{k=0...n-2} binomial(n,k)^2 * (n-k)! * d(n-k) for n >= 2, where d(n) is the number of derangements of n elements: permutations of n elements with no fixed points - sequence A000166. Using the formula: d(n) = n!*Sum_{k=0..n} (-1)^k/k!, a(n) = (1/2)*Sum_{k=0..n-2} ((n!/k!)^2 * Sum_{m=0..n-k} (-1)^m/m!).

Example

a(3) = 15 because there are 3! = 6 vertices and C(6,2) lines and in this case all are nonparallel so a(3) = C(6,2) = 15.

Maple

Digits := 200: with(combinat): d := n->n!*sum((-1)^j/j!, j=0..n): a059615 := n->1/2*sum( binomial(n, k)^2 * (n-k)!*d(n-k), k=0..n-2): for n from 1 to 30 do printf(`%d, `, round(evalf(a059615(n)))) od:

Prog

(PARI) a(n) = (1/2)*sum(k=0, n-2, ((n!/k!)^2 * sum(m=0, n-k, (-1)^m/m!))); \\ Michel Marcus, Mar 14 2018

Crossrefs

Cf. A000166, A059760.

Sequence in context: A154806 A133199 A059760 * A215855 A163031 A065920

Adjacent sequences: A059612 A059613 A059614 * A059616 A059617 A059618

Keyword

nonn

Author

Noam Katz (noamkj(AT)hotmail.com), Feb 18 2001

Extensions

More terms from James A. Sellers, Feb 19 2001

Offset corrected by Michel Marcus, Mar 14 2018

Status

approved