A217615 G.f.: Sum_{n>=0} x^n * Sum_{k=0..n} binomial(n,k)^2 * x^k*(1-x)^(n-k).

1, 1, 1, 3, 5, 7, 15, 29, 49, 95, 187, 345, 659, 1289, 2465, 4739, 9237, 17911, 34715, 67705, 132063, 257477, 503309, 984983, 1927895, 3778017, 7411237, 14544967, 28565661, 56144615, 110406527, 217225533, 427636561, 842256047, 1659600955, 3271579689, 6451913519

Offset: 0

Author

Paul D. Hanna, Oct 09 2012

Keywords

• nonn

Comments

Radius of convergence of g.f. is r = 1/2.

More generally, given

A(x) = Sum_{n>=1} x^n * Sum_{k=0..n} binomial(n,k)^2 * x^k*(t-x)^(n-k),

then A(x) = 1/sqrt( (1 - t*x + 2*x^2)^2 - 4*x^2 )

and the radius of convergence r satisfies: (1-r)^2 = r*(t-r) for t > 0.

a(n) is the number of (2k-1)-element subsets of {1, 2, ..., n+1} whose k-th smallest (i.e., k-th largest) element equals 2k-1. - Darij Grinberg, Oct 09 2019

Examples

			G.f.: A(x) = 1 + x + x^2 + 3*x^3 + 5*x^4 + 7*x^5 + 15*x^6 + 29*x^7 + 49*x^8 + ...
where the g.f. equals the series:
A(x) = 1 +
  x*((1-x) + x) +
  x^2*((1-x)^2 + 2^2*x*(1-x) + x^2) +
  x^3*((1-x)^3 + 3^2*x*(1-x)^2 + 3^2*x^2*(1-x) + x^3) +
  x^4*((1-x)^4 + 4^2*x*(1-x)^3 + 6^2*x^2*(1-x)^2 + 4^2*x^3*(1-x) + x^4) +
  x^5*((1-x)^5 + 5^2*x*(1-x)^4 + 10^2*x^2*(1-x)^3 + 10^2*x^3*(1-x)^2 + 5^2*x^4*(1-x) + x^5) + ...
		

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000

Crossrefs

Cf. A217616, A217617, A217461, A217464, A216604, A217661.

Programs

Maple

a := n -> `if`(n < 4, [1, 1, 1, 3][n+1], hypergeom([1/2, (1-n)/3, (2-n)/3, -n/3], [1, (1-n)/2, -n/2], -27)):
seq(simplify(a(n)), n=0..36); # Peter Luschny, Oct 09 2019

Mathematica

CoefficientList[Series[1/Sqrt[(1-x+2*x^2)^2-4*x^2], {x, 0, 20}], x] (* Vaclav Kotesovec, Sep 16 2013 *)

PARI

{a(n)=polcoeff(sum(m=0, n+1, x^m*sum(k=0, m, binomial(m, k)^2*x^k*(1-x)^(m-k) + x*O(x^n))), n)}
for(n=0,40,print1(a(n),", "))

PARI

a(n)={sum(k=0, n\2, binomial(2*k, k) * binomial(n-2*k, k))} \\ Andrew Howroyd, Oct 09 2019

Formula

G.f.: A(x) = 1 / sqrt( (1 - x + 2*x^2)^2 - 4*x^2 ).

G.f.: A(x) = 1 / sqrt( (1-x)*(1-2*x)*(1+x+2*x^2) ).

G.f. satisfies: A(x) = (1 + 2*x^2*Sum_{n>=0} A000108(n)*(-x*A(x))^(2*n)) / (1-x+2*x^2) where A000108(n) = binomial(2*n,n)/(n+1) forms the Catalan numbers.

a(n) ~ 2^n/sqrt(Pi*n). - Vaclav Kotesovec, Sep 16 2013

a(n) = Sum_{k=0..floor(n/2)} binomial(2*k, k) * binomial(n-2*k, k). - Darij Grinberg, Oct 09 2019

a(n) = hypergeom([1/2,(1-n)/3,(2-n)/3, -n/3], [1, (1-n)/2, -n/2], -27) for n >= 4. - Peter Luschny, Oct 09 2019