A308616 Number of well-formed formulas of length n in a formal propositional language with one unitary operator, one binary operator, and one propositional variable.

1, 0, 0, 1, 1, 0, 1, 3, 2, 1, 6, 10, 6, 10, 30, 36, 29, 70, 141, 147, 182, 421, 658, 714, 1183, 2346, 3192, 4027, 7404, 12672, 16633, 24508, 44462, 68641, 93588, 151866, 260118, 381888, 557128, 934220, 1509807, 2205216, 3414269, 5681573, 8828612, 13179557, 21120648, 34335784, 52494403, 80688120

Offset: 1

Author

Zachary T. King, Sep 13 2019

Keywords

• nonn
• easy

Comments

In a formal propositional language, a single propositional variable (usually represented by a lowercase letter) is a well-formed formula of length 1, if A is a WFF of length L then (-A) is a WFF of length L + 3, and if A and B are WFFs of length L1 and L2 then (A*B) is a WFF of length L1 + L2 + 3.

Equivalently, the number of weighted unary-binary plane trees of weight n with non-leaf nodes having a weight of 3 and leaf nodes having a weight of 1. - Andrew Howroyd, Sep 15 2019

Examples

			For n = 8, there are a(8) = 3 possible well-formed formulas: (-(a*a)),((-a)*a),(a*(-a)).
For n = 12, there are a(12) = 10 possible well-formed formulas: (-((a*a)*a)), ((-(a*a))*a), (((-a)*a)*a), ((a*(-a))*a), ((a*a)*(-a)), (-(a*(a*a))), ((-a)*(a*a)), (a*(-(a*a))), (a*((-a)*a)), (a*(a*(-a))).
		

Crossrefs

Cf. A000108.

Programs

Mathematica

nmax = 50; A[_] = 0;
Do[A[x_] = x + x^3 (A[x]^2 + A[x]) + O[x]^(nmax+1), {nmax+1}];
CoefficientList[A[x]/x, x] (* Jean-François Alcover, Sep 28 2019 *)

PARI

seq(n)={Vec(1 - x^3 - sqrt((1 - x^3)^2 - 4*x*x^3 + O(x^4*x^n)))/2} \\ Andrew Howroyd, Sep 15 2019

Formula

If S is the set of pairs of nonnegative integers for which 4b + 3u + 1 = n, then a(n) = Sum_{(b,u) in S} binomial(2b+u, u)*A000108(b).

From Andrew Howroyd, Sep 15 2019: (Start)

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

G.f.: (1 - x^3 - sqrt((1 - x^3)^2 - 4*x*x^3))/(2*x^3). (End)

a(n) ~ 5^(1/4) * phi^(n+2) / (2*sqrt(Pi)*n^(3/2)), where phi = A001622 = (1+sqrt(5))/2 is the golden ratio. - Vaclav Kotesovec, Sep 28 2019