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

%I #45 Sep 28 2019 08:37:24

%S 1,0,0,1,1,0,1,3,2,1,6,10,6,10,30,36,29,70,141,147,182,421,658,714,

%T 1183,2346,3192,4027,7404,12672,16633,24508,44462,68641,93588,151866,

%U 260118,381888,557128,934220,1509807,2205216,3414269,5681573,8828612,13179557,21120648,34335784,52494403,80688120

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

%C 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.

%C 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

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

%F From _Andrew Howroyd_, Sep 15 2019: (Start)

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

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

%F 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

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

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

%t nmax = 50; A[_] = 0;

%t Do[A[x_] = x + x^3 (A[x]^2 + A[x]) + O[x]^(nmax+1), {nmax+1}];

%t CoefficientList[A[x]/x, x] (* _Jean-François Alcover_, Sep 28 2019 *)

%o (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

%Y Cf. A000108.

%K nonn,easy

%O 1,8

%A _Zachary T. King_, Sep 13 2019