yukicoder No.1127 変形パスカルの三角形 - かんプリンの学習記録

悩まなかったけど公式解説が出てなかったので書きました.

問題概要

パスカルの三角形で(一番上を0段目として)1段目の数を ${a}$ , ${b}$ とし, 各段の一番左の数を ${a}$ ,一番右の数を ${b}$ とする. このときの ${n}$ 段目,左から ${k}$ 番目の数を求めよ. また, ${n}$ 段目の各数の2乗和も求めよ.

通常のパスカルの三角形のように ${a}$ と ${b}$ が何回足されるかを考える.

通常のパスカルの三角形と同じように考えると ${(n,k)}$ ( ${n}$ 段目左から ${k}$ 番目の数)は以下の式で表されることがわかる.

${(n,k)={}_{n-1}\rm{C}_{\textit{k}-1}×\textit{a}+{}_{\textit{n}-1}\rm{C}_{\textit{k}-2}×\textit{b}}$

これは, 階乗の逆元を求めたり直接求めたりして解ける. ただし, ${k=1}$ や ${k=n+1}$ のときはそれぞれ ${a,b}$ とする.

${n}$ 段目の数の2乗和も同じように求められる.

$a^2+b^2+\sum_{k=2}^{n}({}_{n-1}\rm{C}_{\textit{k}-1}×\textit{a}+{}_{\textit{n}-1}\rm{C}_{\textit{k}-2}×\textit{b})^2$

よくあるかんじのやつ.