Leafy Trees
2020年6月8日13:17
正解数: 1 /
解答数: 1
(正答率: 100%)
ギブアップ不可
問題文
枝と葉からなる $2$ 次元的な植物を考えます。植物は，以下の条件を満たすような枝 $s$ 本と葉 $l$ 枚からなります。
条件
- $s, l$ は $0$ 以上の整数である。
- 枝の両端の点には，枝または葉が $0$ 個以上つながっている。
- すべての枝からたどりつくことができるような，根とよばれる点がただひとつ存在する。
- 枝がループを作るようにつながっていることはない。
この植物の重さ $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$ 行目にそれぞれ半角数字で出力してください。
ヒント1
数列 $\{t_n\}$ は，漸化式
\begin{equation}
t_n=t_{n-1}+\sum_{k=0}^{n-2}t_{k}t_{n-2-k}\quad (n\geq 2)
\end{equation}を満たします。
ヒント2
\begin{equation}
f(x)=\sum_{n=0}^{\infty}t_nx^n
\end{equation}とおくと，$f(x)$ はどんな関係式を満たすでしょうか？
スポンサーリンク
解答提出
この問題は自動ジャッジの問題です。
解答形式が指定されていればそれにしたがって解答してください。
おすすめ問題
この問題を解いた人はこんな問題も解いています
