|
%I M1471 #45 Aug 03 2015 08:34:43
%S 1,1,2,5,14,58,238,1516,9020,79892,635984,7127764,70757968,949723600,
%T 11260506056,175400319992,2416123951952,42776273847184,
%U 671238787733920,13302324582892048,234257439470319776,5135062189842955616,100292619307729965152
%N Number of extreme points of the set of n X n symmetric doubly-stochastic matrices.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.24(b).
%H Vincenzo Librandi, <a href="/A006847/b006847.txt">Table of n, a(n) for n = 0..200</a>
%H M. Katz, <a href="http://dx.doi.org/10.1016/S0021-9800(70)80034-5">On the extreme points of a certain convex polytope</a>, J. Combin. Theory, 8 (1970), 417-423.
%H R. P. Stanley, <a href="http://dx.doi.org/10.1016/S0195-6698(80)80051-5">Differentiably finite power series</a>, European J. Combin., 1 (1980), 175-188.
%F 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
%F E.g.f.: ((1+x)/(1-x))^(1/4)*exp(1/2*x+1/2*x^2).
%F 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
%F a(n) ~ n! * 2^(-1/4)*GAMMA(3/4)*exp(1)/(Pi*n^(3/4)). - _Vaclav Kotesovec_, Aug 13 2013
%e An example for n = 4:
%e 1 0 0 0
%e 0 0 h h
%e 0 h 0 h
%e 0 h h 0
%e where h = 1/2.
%p 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
%t 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. *)
%t 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 *)
%o (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 */
%o (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
%Y Cf. A053553.
%K nonn,easy,nice
%O 0,3
%A _N. J. A. Sloane_
%E Edited by _N. J. A. Sloane_, May 06 2012
|
