A162326 Let a(0) = a(1) = 1, and n*a(n) = 2*(-7+5*n)*a(n-1) + 9*(2-n)*a(n-2) for n >= 2.

1, 1, 3, 13, 71, 441, 2955, 20805, 151695, 1135345, 8671763, 67320573, 529626839, 4213228969, 33833367963, 273892683573, 2232832964895, 18314495896545, 151037687326755, 1251606057754605, 10416531069771111, 87029307323766681

Offset: 0

Author

Georg Muntingh, Jul 01 2009

Keywords

• nonn

Comments

Let y = y(x) be implicitly defined by g(x,y(x)) = 0, with dg/dy not identically zero. For n >= 1, the sequence a(n) is the number of terms in the expansion of the divided difference [x0,...,xn]y in terms of bivariate divided differences of g.

(1 + 3*x + 13*x^2 + 71*x^3 + ...) = (1 + 4*x + 20*x^2 + 116*x^3 + ...) * 1/(1 + x + 4*x^2 + 20*x^3 + 116*x^4 + ...); where A082298 = (1, 4, 20, 116, 740, ...). - Gary W. Adamson, Nov 17 2011

The shifted sequence 1,3,13,71,... is the binomial transform of A151374. - Georg Muntingh, Jul 19 2012

a(n+1) is the number of Schröder paths of semilength n in which the (2,0)-steps come in 3 colors and with no peaks at level 1. - José Luis Ramírez Ramírez, Mar 31 2013

Define an infinite triangle by T(n,0)=1 and the other cells by T(n,k) = Sum_{c=0..k-1} T(n,c) + Sum_{r=k..n-1} T(r,k), the sum of the cells to the left and above a cell. The column k=1 contains A000079, the column k=2 essentially A001792. Then T(n,n)=a(n) on the diagonal. - J. M. Bergot, May 22 2013

Examples

			Write [0...n]y for [x0,...,xn]y and [0...s,0...t]g for [x0,...,xs;y0,...,yt]g.
For n = 1 one finds 1 term, [01]y = -[01;1]g/[0;01]g.
For n = 2 one finds 3 terms, [012]y = -[012;2]g/[0;02]g + ([01;12]g[12;2]g)/([0;02]g[1;12]g) - ([0;012]g[01;1]g[12;2]g)/([0;02]g[0;01]g[1;12]g).
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..300
• Georg Muntingh, Implicit Divided Differences, Little Schroeder Numbers, and Catalan Numbers, J. Integ. Seqs., Vol. 15 (2012), Article 12.6.5.
• Paveł Szabłowski, Beta distributions whose moment sequences are related to integer sequences listed in the OEIS, Contrib. Disc. Math. (2024) Vol. 19, No. 4, 85-109. See p. 98.

Crossrefs

Cf. A172003, which is a generalization to bivariate implicit functions.

Cf. A003262, which is the analogous sequence for implicit derivatives, and A172004 for its generalization to bivariate implicit functions.

Cf. A082298, A000108, A151374.

Programs

Magma

m:=20; R:=PowerSeriesRing(Rationals(), m); Coefficients(R!( (5-Sqrt((1-9*x)/(1-x)))/4 )); // G. C. Greubel, Feb 07 2019

Magma

a:=[1,3]; for n in [3..21] do Append(~a,(2*(-7+5*n)*a[n-1] + 9*(2-n)*a[n-2]) div n); end for ; [1] cat a; // Marius A. Burtea, Jan 20 2020

Mathematica

CoefficientList[Series[(5-Sqrt[(1-9*x)/(1-x)])/4, {x, 0, 20}], x] (* Vaclav Kotesovec, Oct 20 2012 *)

Maxima

a(n):=if n=0 then 1 else sum(binomial(n,k)*2^(n-k-1)*binomial(2*n-2*k-2,n-k-1),k,0,n)/n; /* Vladimir Kruchinin, Mar 13 2016 */

PARI

a(n) = if(n<2, 1, (2*(-7+5*n)*a(n-1) + 9*(2-n)*a(n-2))/n);
vector(25, n, a(n-1)) \\ Altug Alkan, Oct 06 2015

PARI

my(x='x+O('x^20)); Vec((5-sqrt((1-9*x)/(1-x)))/4) \\ G. C. Greubel, Feb 07 2019

Python

L = [1, 1]
for n in range(2,22):
    L.append( ((-14 + 10*n)*L[-1] + (18-9*n)*L[-2])//n )
print(L)
# Georg Muntingh, Jul 19 2012

Sage

((5-sqrt((1-9*x)/(1-x)))/4).series(x, 20).coefficients(x, sparse=False) # G. C. Greubel, Feb 07 2019

Formula

Let E = N x N \ {(0,0), (0,1)} be a set of pairs of natural numbers. The number of terms a(n) is the coefficient of x^n*y^{n-1} of the generating function 1 - log(1 - Sum_{(s,t) in E} x^s*y^{s+t-1}) = 1 + Sum_{q >= 1} (Sum_{(s,t) in E} x^s*y^{s+t-1})^q / q.

From Georg Muntingh, Jul 19 2012: (Start)

a(n) = 2F1(1/2,1-n;2;-8), where 2F1 is the Gauss hypergeometric series.

G.f.: (5 - sqrt( (1-9*x)/(1-x) ))/4.

Quadratic recurrence relation: a(n) = 1 + 2*Sum_{m=1..n-1} a(m)*a(n-m).

(End)

a(n) ~ 3^(2*n+1)/(16*sqrt(2*Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 20 2012

a(n) = Sum_{k=0..n} (binomial(n,k)*2^(n-k-1)*binomial(2*n-2*k-2,n-k-1))/n, n>0, a(0)=1. - Vladimir Kruchinin, Mar 13 2016

From Peter Bala, Jan 19 2020: (Start)

a(n+1) = Sum_{k = 0..n} 2^k*C(n,k)*Catalan(k).

a(n+1) = (2/Pi) * Integral_{x = -1..1} (1 + 8*x^2)^n*sqrt(1 - x^2) dx.

O.g.f.: 1 + x/(1 - x)*c(2*x/(1-x)), where c(x) is the o.g.f. for A000108. (End)

Conjecture: a(n) = t_n for n > 0 with a(0) = 1 where we start with vector v of fixed length m with elements v_i = 1, then set t = v and for i=1..m-1, for j=i+1..m apply [v_i, v_j] := [v_i + 2*v_j, 2*v_i + v_j] (here square brackets mean that instead of sequentially assigning v_i and then v_j, we reserve their values (for example, as A = v_i, B = v_j) and then assign them in any order) and t_{i+1} := v_{i+1} (after ending each cycle for j). It also looks like that if we change 2*v_i to z*v_i it gives us a(n+1) = Sum_{k=0..n} A090981(n, k)*2^(n-k) for n >= 0. - Mikhail Kurkov, Aug 14 2024

Extensions

Edited by Georg Muntingh, Jan 22 2010