A186997 G.f. satisfies: A(x) = 1 + x*A(x)^3 + x^2*A(x)^4.

1, 1, 4, 19, 104, 614, 3816, 24595, 162896, 1101922, 7580904, 52878654, 373100272, 2658188524, 19096607120, 138182654595, 1006202473888, 7367648586954, 54214472633064, 400698865376842, 2973344993337520, 22142778865313364

Offset: 0

Author

Paul D. Hanna, Mar 01 2011

Keywords

• nonn
• easy

Comments

a(n-1) is the number of rows with the value false in the truth tables of all bracketed implications with n distinct variables. - Volkan Yildiz, Jul 01 2011

From Peter Bala, Aug 02 2016: (Start)

Conjectures (both checked up to n = 100):

2-adic valuation of a(2*n+1) = 2-adic valuation of Catalan(2*n+1) (= 2-adic valuation of Catalan(n));

2-adic valuation of a(2*n) = 3 + 2-adic valuation of Catalan(n-2) for n >= 2, where Catalan(n) = A000108(n). (End)

a(n) is the number of Dyck paths of semi-length n using only steps U_1 = (4,2), U_2 = (9,3) and D = (1,-1). - Michael D. Weiner, Jun 12 2017

Examples

			G.f.: A(x) = 1 + x + 4*x^2 + 19*x^3 + 104*x^4 + 614*x^5 + 3816*x^6 + ...
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..100
• Daniel Birmajer, Juan B. Gil, Peter R. W. McNamara and Michael D. Weiner, Enumeration of colored Dyck paths via partial Bell polynomials, arXiv:1602.03550 [math.CO], 2016.
• P. J. Cameron and V. Yildiz, Counting false entries in truth tables of bracketed formulas connected by implication. Also arXiv:1106.4443 [math.CO], 2011.
• Volkan Yildiz, General combinatorical structure of truth tables of bracketed formulas connected by implication, arXiv preprint arXiv:1205.5595 [math.CO], 2012.
• Volkan Yildiz, Notes on algebraic structure of truth tables of bracketed formulae connected by implications, arXiv:2106.04728 [math.CO], 2021. See S(x) p. 3.

Crossrefs

Cf. A000108.

Programs

Maple

A(x):= 1/x * (-1-sqrt(1-8*x)+sqrt(2+2*sqrt(1-8*x)+8*x))/4 ;
a:= n-> coeff(series(A(x), x, n+2), x, n):
seq(a(n), n=0..20); # Volkan Yildiz, Jul 01 2011

Mathematica

CoefficientList[Series[1/x * (-1-Sqrt[1-8*x]+Sqrt[2+2*Sqrt[1-8*x]+8*x])/4, {x, 0, 20}], x] (* Vaclav Kotesovec, May 31 2014 *)
a[n_] := Sum[Binomial[k, n-k]*Binomial[n+2*k, n+k]/(n+k+1), {k, 1, n}]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Apr 02 2015, after Vladimir Kruchinin *)

Maxima

a(n):=sum((binomial(k,n-k)*binomial(n+2*k,n+k))/(n+k+1),k,1,n); /* Vladimir Kruchinin, May 12 2011 */

PARI

{a(n)=local(A=1+x);for(i=1,n,A=1+x*A^3+x^2*(A+x*O(x^n))^4);polcoeff(A,n)}
for(n=0,25,print1(a(n),", "))

PARI

{a(n)=polcoeff((1/x)*serreverse(x*(1+sqrt(1-4*x-4*x^2 +x^2*O(x^n)))/2),n)}
for(n=0,25,print1(a(n),", "))

PARI

x='x+O('x^66); /* that many terms */
Vec(1/x*serreverse((x*(1+sqrt(1-4*x-4*x^2))/2))) /* show terms */ /* Joerg Arndt, May 13 2011 */

Formula

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

a(n) = Sum_{k=0..n} binomial(k,n-k)*binomial(n+2*k,n+k)/(n+k+1). - Vladimir Kruchinin, May 12 2011

From Volkan Yildiz, Jul 03 2011: (Start)

Let f(n) = Sum_{i=1..n-1} (2^i*C(i-1)-f(i))*f(n-i), with f(0)=0, f(1)=1, and where C are the Catalan numbers A000108. Then a(n)=f(n+1).

G.f.: (1/x) * (-1-sqrt(1-8*x)+sqrt(2+2*sqrt(1-8*x)+8*x))/4.

For large n, a(n) is asymptotically (3-sqrt(3))/3* 2^(3*n)/sqrt(Pi*n^3), corrected by Vaclav Kotesovec, May 31 2014. (End)

O.g.f. satisfies A(x^2) = 1/x * Series_Reversion( x*(1 - x^2)/(1 + x^4) ). - Peter Bala, Aug 02 2016

D-finite with recurrence n*(n+1)*(2*n+1)*a(n) -n*(28*n^2-27*n+8)*a(n-1) +6*(11*n^3-36*n^2+32*n-5)*a(n-2) +8*(2*n-5)*(14*n^2-52*n+51)*a(n-3) +32*(2*n-5)*(2*n-7)*(n-3)*a(n-4)=0. - R. J. Mathar, Nov 22 2024