問題は、1円, 3円, 5円, 7円, 9円, 11円,... と奇数の額面のコインがたくさんあるとき、合計n円を支払うためのコインの組み合わせの総数を$OP_n$で表す。$OP_5=3$であるとき、$OP_{12}$を求めよ、というものです。

1. 問題の内容

問題は、1円, 3円, 5円, 7円, 9円, 11円,... と奇数の額面のコインがたくさんあるとき、合計n円を支払うためのコインの組み合わせの総数を$OP_n$で表す。$OP_5=3$であるとき、$OP_{12}$を求めよ、というものです。

2. 解き方の手順

$OP_{12}$を求めるには、12円を奇数額面のコインで支払うすべての組み合わせを列挙します。

* 12円コイン1枚： 1通り

* 10円コイン1枚、1円コイン2枚：存在しない（10円コインがないため）

* 9円コイン1枚：

* 9円コイン1枚、1円コイン3枚：1通り

* 7円コイン1枚：

* 7円コイン1枚、5円コイン1枚：1通り

* 7円コイン1枚、3円コイン1枚、1円コイン2枚：1通り

* 7円コイン1枚、1円コイン5枚：1通り

* 5円コイン：

* 5円コイン2枚、1円コイン2枚：1通り

* 5円コイン1枚、7円コイン1枚：上の7円のパターンで考慮済み

* 5円コイン1枚、3円コイン2枚、1円コイン1枚：1通り

* 5円コイン1枚、3円コイン1枚、1円コイン4枚：1通り

* 5円コイン1枚、1円コイン7枚：1通り

* 3円コイン：

* 3円コイン4枚：1通り

* 3円コイン3枚、1円コイン3枚：1通り

* 3円コイン2枚、1円コイン6枚：1通り

* 3円コイン1枚、1円コイン9枚：1通り

* 1円コイン12枚：1通り

上記をまとめると以下のようになります。

* 12円：1通り

* 9円 + 1円 x 3：1通り

* 7円 + 5円：1通り

* 7円 + 3円 + 1円 x 2：1通り

* 7円 + 1円 x 5：1通り

* 5円 x 2 + 1円 x 2：1通り

* 5円 + 3円 x 2 + 1円：1通り

* 5円 + 3円 + 1円 x 4：1通り

* 5円 + 1円 x 7：1通り

* 3円 x 4：1通り

* 3円 x 3 + 1円 x 3：1通り

* 3円 x 2 + 1円 x 6：1通り

* 3円 + 1円 x 9：1通り

* 1円 x 12：1通り

したがって、$OP_{12} = 14$となります。

3. 最終的な答え

$OP_{12} = 14$