8
$\begingroup$

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.

$\endgroup$

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.