login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006847 Number of extreme points of the set of n X n symmetric doubly-stochastic matrices.
(Formerly M1471)
2
1, 1, 2, 5, 14, 58, 238, 1516, 9020, 79892, 635984, 7127764, 70757968, 949723600, 11260506056, 175400319992, 2416123951952, 42776273847184, 671238787733920, 13302324582892048, 234257439470319776, 5135062189842955616, 100292619307729965152 (list; graph; refs; listen; history; text; internal format)
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

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

License Agreements, Terms of Use, Privacy Policy .

Last modified February 17 14:12 EST 2018. Contains 299296 sequences. (Running on oeis4.)