A006847 Number of extreme points of the set of n X n symmetric doubly-stochastic matrices. (Formerly M1471)

1, 1, 2, 5, 14, 58, 238, 1516, 9020, 79892, 635984, 7127764, 70757968, 949723600, 11260506056, 175400319992, 2416123951952, 42776273847184, 671238787733920, 13302324582892048, 234257439470319776, 5135062189842955616, 100292619307729965152

Offset

0,3

References

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.24(b).

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..200

M. Katz, On the extreme points of a certain convex polytope, J. Combin. Theory, 8 (1970), 417-423.

R. P. Stanley, Differentiably finite power series, European J. Combin., 1 (1980), 175-188.

Formula

A recurrence for this sequence is a(n) = a(n-1) + (n-1)^2*a(n-2) - ((n-1)*(n-2)/2)*a(n-3) - (n-1)*(n-2)*(n-3)*a(n-4). This is given in Stanley, 1980, p. 180, except that there is a typographical error in Stanley's formula (corrected here). - Jeffrey Shallit, Dec 05 2009

E.g.f.: ((1+x)/(1-x))^(1/4)*exp(1/2*x+1/2*x^2).

a(n) = n!*sum((if r=0 then 1 else sum((1/2)^k*C(k,r-k)/k!, k=1..r))*b(n-r), r=0..n), b(n)=if n=0 then 1 else 1/2+sum(2^m*C(n-1,m-1)*(-1)^(m-1)*((1/4)^m*sum(sum(C(j,m-1-3*k+2*j)*C(k,j)*3^(3*k-m+1-j)*2^(m-1-5*k+3*j)*(-1)^(m-1-3*k), j=0..k)*C(k+m-1,m-1), k=1..m-1))/m, m=2..n). - Vladimir Kruchinin, Sep 09 2010

a(n) ~ n! * 2^(-1/4)*GAMMA(3/4)*exp(1)/(Pi*n^(3/4)). - Vaclav Kotesovec, Aug 13 2013

Example

An example for n = 4:
1 0 0 0
0 0 h h
0 h 0 h
0 h h 0
where h = 1/2.

Maple

A006847:= gfun:-rectoproc({a(n)=a(n-1)+(n-1)^2*a(n-2)-((n-1)*(n-2))*a(n-3)/2-(n-1)*(n-2)*(n-3)*a(n-4), a(0)=1, a(1)=1, a(2)=2, a(3)=5}, a(n), remember):  seq(A006847(n), n=0..30); # Wesley Ivan Hurt, Aug 01 2015

Mathematica

max = 22; f[x_] = ((1+x)/(1-x))^(1/4)*Exp[x/2+x^2/2]; CoefficientList[ Series[ f[x], {x, 0, max}], x]*Range[0, max]! (* Jean-François Alcover, Nov 14 2011, after g.f. *)
RecurrenceTable[{a[0]==a[1]==1, a[2]==2, a[3]==5, a[n]==a[n-1]+(n-1)^2 a[n-2]-((n-1)(n-2))/2 a[n-3]-(n-1)(n-2)(n-3)a[n-4]}, a, {n, 30}] (* Harvey P. Dale, Nov 18 2014 *)

Prog

(Maxima) b(n):=if n=0 then 1 else 1/2+sum(2^m*binomial(n-1, m-1)*(-1)^(m-1)*((1/4)^m*sum(sum(binomial(j, m-1-3*k+2*j)*binomial(k, j)*3^(3*k-m+1-j)*2^(m-1-5*k+3*j)*(-1)^(m-1-3*k), j, 0, k)*binomial(k+m-1, m-1), k, 1, m-1))/m, m, 2, n); a(n):=n!*sum((if r=0 then 1 else sum((1/2)^k*binomial(k, r-k)/k!, k, 1, r))*b(n-r), r, 0, n); /* Vladimir Kruchinin, Sep 09 2010 */
(PARI) Vec(serlaplace(((1+x)/(1-x))^(1/4)*exp(1/2*x+1/2*x^2)) + O(x^33)) \\ Gheorghe Coserea, Aug 03 2015

Crossrefs

Cf. A053553.

Sequence in context: A174795 A243551 A110043 * A008286 A049082 A158095

Adjacent sequences: A006844 A006845 A006846 * A006848 A006849 A006850

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Extensions

Edited by N. J. A. Sloane, May 06 2012

Status

approved