What is the number of trees possible with $n$ nodes where the $i$th and $(i+1)$th node are not adjacent to each other for $i \in \left[0,n-1\right)$ and $$i/2 = (i+1)/2.$$
(integer division) (nodes are labelled from $0$ to $n-1$) so $\left( 0,1 \right) , \left(2,3\right), \ldots$ pairs can't be adjacent. Usually the number of trees possible with $n$ nodes is $n^{n-2}$ (Cayley's Formula) but under the given conditions how can we approach the problem?
Let $p(n)$ be your number. You can write it recursively as:
$p(n) = n^{n-2} - \sum_{k=1}^{(n/2)} {n/2 \choose k} \times p(n - 2k)$ where $p(0)=0$
What this formula states is that the total number of such trees is equal to total number of trees minus the number of times in which only one of your constraints is violated minus the total number of times in which only two of the constrains are violated etc. here $n/2 \choose k$ is the number of ways you can choose $k$ constraints to violate! Once you've chosen $k$ constraints to violate, you construct a tree that violates no constraint from $n-2k$ remaining nodes.