Given a natural number $n$, I'm trying to count the number $f(n)$ of series $a_1+a_2\dots +a_k,$ unique up to reversal (so $a_1+\dots a_i \dots +a_k$ and $a_k+ \dots a_{k-i+1}+\dots a_1$ are considered the same series) such that $a_i \le \min(i,k-i+1)$. So for instance with $n=7$ the (distinct) valid series would be $$1+1+1+1+1+1+1$$$$1+2+1+1+1+1$$$$1+1+2+1+1+1$$$$1+1+3+1+1$$$$1+2+2+1+1$$$$1+2+1+2+1$$

Unless I'm mistaken, this is the same as the number of trees on $n$ nodes such that no node has degree $\gt3$ and all nodes of degree $3$ lie on a single path of length $k$ where $k$ is the diameter of the tree. By "a single path", I mean that they all lie on the same path, not that such a path is necessarily unique.

I'm also interested in related concepts such as $g(k)=$ the number of such series with length $k$, and $h(n)=$the number of such series where reversals are considered distinct, and so on.

I've calculated initial values for all three of these, though I might be mistaken:

$$\begin{array}{|c|c|c|c|}\hline n&f(n)&g(n)&h(n)\\\hline3&1&2&1 \\\hline 4&2&3&2\\ \hline5&2&9&3\\\hline6&4&24&5\\\hline7&6&96&9\\\hline8&11&378&17\\\hline9&16&1890&27\\\hline\end{array}$$

For even $n$, I have $$g(n)=\sum_{i=2}^{n\over 2}\left({{i+1}\choose 2}-1\right)\left(\frac {\frac n 2 !}{i!}\right)^2$$ and for odd $n$ $$g(n)=g(n-1){\frac {n+1}2}$$

but I'm looking for formulas for $f$ and $h$ (especially $f$).

Edit: found OEIS A001224 which is related. It counts the number of such series for $n-2$ with the additional requirement that every term is $1$ or $2$. Of course for the case where reflections are considered distinct, the corresponding sequence is the Fibonacci sequence.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.