yukicoder No.2023 Tiling is Fun - かんプリンの学習記録

問題概要

${xy}$ 平面上の ${A=(1,0),B=(a,0),C=(a,b−1),D=(a−1,b),E=(0,b),F=(0,1)}$ を頂点とする六角形 ${ABCDEF}$ を考えます。
この六角形に次の3種類の図形を敷き詰めます。

これらの図形を回転・反転を許さずに、隙間も重なりもないように敷き詰める方法は何通りありますか。

求めるものを ${f(a,b)}$ とします。
六角形の左下には黄色の図形か青の図形を埋めるしかありません。
黄色の図形を埋めると、以下の様に赤の図形を埋めるしかなくなります。残りは ${f(a,b-1)}$ を求めればよいです。

青の図形を埋めると、以下の様に赤の図形を埋めるしかなくなります。残りは ${f(a-1,b)}$ を求めればよいです。

以上から ${f(a,b)=f(a,b-1)+f(a-1,b)}$ となります。
${f(a,1)=1, f(1,b)=1}$ であることを踏まえると $f(a,b)=\binom{a+b-2}{a-1}$ であることが分かります。

解説と違ったので書いてみました。この問題思いつくのがすごい。