login
The OEIS is supported by the many generous donors 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
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
KEYWORD
nonn,easy,nice
AUTHOR
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:56 EDT 2024. Contains 370952 sequences. (Running on oeis4.)