全問題一覧

問題文

枝と葉からなる $2$ 次元的な植物を考えます。植物は，以下の条件を満たすような枝 $s$ 本と葉 $l$ 枚からなります。

条件

1. $s, l$ は $0$ 以上の整数である。
2. 枝の両端の点には，枝または葉が $0$ 個以上つながっている。
3. すべての枝からたどりつくことができるような，根とよばれる点がただひとつ存在する。
4. 枝がループを作るようにつながっていることはない。

この植物の重さ $n$ は $n=2s+l$ で表されます。例えば，重さ $4$ の異なる植物をすべて描いたものは下図のようになります。

ここで，ある点に着目したときに，その点から出ている葉と枝の並びが異なるものは区別することに注意しましょう。

重さ $n$ の植物が $t_n$ 種類あるとき
\begin{equation}
\sum_{n=0}^{\infty}\frac{t_n}{3^n}
\end{equation}の値を求めなさい。ただし，級数が収束することは証明なしに用いてかまいません。

解答形式

答えは正の有理数 $r$ です。

• $r$ が整数ならば，$r$ を半角数字で出力してください。
• $r$ が整数でないならば，互いに素な自然数 $a, b$ を用いて $r=\displaystyle{\frac{a}{b}}$ と表し，$a$ を $1$ 行目に，$b$ を $2$ 行目にそれぞれ半角数字で出力してください。