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,8

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

Links

Table of n, a(n) for n=1..50.

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

Example

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))).

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 *)

Prog

(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

Crossrefs

Cf. A000108.

Sequence in context: A144250 A156367 A193593 * A181853 A008276 A094638

Adjacent sequences: A308613 A308614 A308615 * A308617 A308618 A308619

Keyword

nonn,easy

Author

Zachary T. King, Sep 13 2019

Status

approved