Number of logic formulas I can create with n uses of certain symbols In the first lesson of a course in logic we defined as a logical formula the following:


*

*propositional variables $p_0,p_1,...$

*if $\phi$ is a formula then $\lnot\phi$ is a formula too

*if $\phi$ and $\psi$ are formulas then $(\phi \lor \psi)$ , $(\phi \land \psi)$ , $(\phi \rightarrow \psi)$ , $(\phi \leftrightarrow \psi)$ are formulas
and nothing else is a formula.
Now by using only one propositional variable $p$,
and $0$ times any of the symbols $\lnot, \lor, \land, \rightarrow, \leftrightarrow$ we can create only $1$ logical formula
and $1$ time any of the symbols $\lnot, \lor, \land, \rightarrow, \leftrightarrow$ we can create $5$ logical formulas: $\lnot p$ and $(p*p)$ ,where $*$ can stand for any of the symbols $\lor, \land, \rightarrow, \leftrightarrow$ (I write it this way to write less)
and $2$ times any of the symbols $\lnot, \lor, \land, \rightarrow, \leftrightarrow$ we can create the following logical formulas: $\lnot\lnot p$, $(\lnot p * p)$, $(p*\lnot p)$, $\lnot (p*p)$, $(p*(p*p))$, $((p*p)*p)$ which are $1+4+4+4+4^2+4^2=45$
My question is how many logical formulas can we create using only one variable and $n$ times any of the symbols $\lnot, \lor, \land, \rightarrow, \leftrightarrow$? I can calculate it(I think) for very small $n$ as above but for larger $n$ the thing gets more complicated.
 A: Every formula with $n$ symbols is an incomplete binary tree.  It has: 


*

*exactly $n$ internal nodes (incl. the root), 

*each internal node having $1$ or $2$ children, 


*

*any internal node having $2$ children being decorated with any of $4$ symbols ($\lor, \land, \rightarrow, \leftrightarrow$), 

*any internal node having $1$ child being decorated with $\lnot$, 


*all the leaves decorated with the variable $p$.
The related problem where every internal node has $2$ children (i.e. complete binary tree), and there are no decorations, has a neat solution, but generalizing it to counting incomplete binary trees probably makes it very hairy, and adding decorations will make it even hairier.  
Anyway here's an alternative: Let $f(n)$ be the number you seek.  


*

*If the root has $1$ child (the formula has a leading $\lnot$), then there are $f(n-1)$ ways to complete the tree.

*If the root has $2$ children, i.e. $2$ subtrees, they can have $a, b$ internal nodes respectively as long as $a+b = n-1$, so there are $f(a)$ ways to make the left subtree and $f(b)$ ways to make the right subtree.  And of course, need to multiply by $4$ for the $4$ binary op symbols.
Therefore:
$$f(n) = f(n-1) + 4 \times \sum_{a=0}^{n-1} f(a) f(n-1-a)$$
I am not sure how to turn this into something better (either closed-form, or at least some summation/product).
UPDATE: Just found this excellent CS.SE answer which suggests there is a way to count these using generating functions.  Sadly, I'm out of my depth.
