A047665 Expansion of (1/sqrt(1-6*x+x^2)-1/(1-x))/2.

0, 1, 6, 31, 160, 841, 4494, 24319, 132864, 731281, 4048726, 22523359, 125797984, 704966809, 3961924126, 22321190911, 126027618304, 712917362209, 4039658528934, 22924714957471, 130271906898720, 741188107113961, 4221707080583086, 24070622500965631, 137369104574280960, 784622537295845041

Offset: 0

Author

Don Knuth, N. J. A. Sloane

Keywords

• nonn

Comments

Previous name was: Main diagonal of square array defined in A047662.

a(n) is the total number of weak plateaus in all Schroeder n-paths. A weak plateau is a subpath of the form UFF..FD where there are 0 or more Fs. For example, a(2)=6 counts the following weak plateaus (in parentheses) in the 6 Schroeder 2-paths: (UFD), U(UD)D, FF, (UD)F, F(UD), (UD)(UD). - David Callan, Aug 16 2006

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..200 (corrected by Sean A. Irvine, Jan 18 2019)
• Y. Ding and R. R. X. Du, Counting Humps in Motzkin Paths, arXiv:1109.2661 [math.CO], 2011, Eq. (4.2).
• D. E. Knuth and N. J. A. Sloane, Correspondence, December 1999
• Matthew Roughan, Surreal Birthdays and Their Arithmetic, arXiv:1810.10373 [math.HO], 2018.

Crossrefs

Cf. A001850, A002002 (Schroeder paths interpretation).

Cf. A008288 (Delannoy numbers triangle).

Programs

Maple

seq(add(multinomial(n+k,n-k,k,k)/2,k=1..n),n=1..22); # Zerinvary Lajos, Oct 18 2006
a:=n->add(add(binomial(n,j)*binomial(n,k)*binomial(k,j), j=0..n),k=1..n): seq(a(n)/2, n=1..22); # Zerinvary Lajos, Jun 02 2007

Mathematica

Table[SeriesCoefficient[(1/Sqrt[1-6*x+x^2]-1/(1-x))/2,{x,0,n}],{n,1,20}] (* Vaclav Kotesovec, Oct 08 2012 *)

PARI

x='x+O('x^66); Vec((1/sqrt(1-6*x+x^2)-1/(1-x))/2) \\ Joerg Arndt, May 04 2013

Sage

a = lambda n: (hypergeometric([-n, n+1], [1], -1)-1)/2
[simplify(a(n)) for n in (1..25)] # Peter Luschny, May 19 2015

Formula

2*a(n)+1 = A001850(n).

a(n)-a(n-1) = A002002(n).

a(n) = Sum_{k=0..n} Sum_{j=0..n} A008288(k, j).

a(n) = Sum_{j=1..n} C(2*j-1, j-1)*C(n+j, 2*j). - Stefan Hollos (stefan(AT)exstrom.com), Jul 21 2004

D-finite with recurrence: n*(2*n-3)*a(n) = (2*n-1)*(7*n-10)*a(n-1) - (2*n-3)*(7*n-4)*a(n-2) + (n-2)*(2*n-1)*a(n-3). - Vaclav Kotesovec, Oct 08 2012

a(n) ~ sqrt(8+6*sqrt(2))*(3+2*sqrt(2))^n/(8*sqrt(Pi*n)). - Vaclav Kotesovec, Oct 08 2012

a(n) = (hyper2F1(-n,n+1,1,-1)-1)/2 = (hyper2F1(-n, -n, 1, 2)-1)/2. - Peter Luschny, May 19 2015

a(n) = Sum_{k=1..n} binomial(n,k)^2 * 2^(k-1). - Ilya Gutkovskiy, Nov 15 2021

Extensions

Prepended 0, set offset to 0 and new name using a comment of Emeric Deutsch from Dec 25 2003 by Peter Luschny, May 20 2015