与えられた問題は、次の3つの問いから構成されています。 * 問題2: "BANANA"の6文字から4文字を選んで文字列を作る場合の数を求める。 * 問題4-1: 図1の格子において、点Aから点Bへの最短経路のうち、点Cを通る経路の数を求める。 * 問題4-2: 図1の格子において、点Aから点Bへの最短経路のうち、点Dまたは点Eを通る経路の数を求める。 * 問題4-3: 図2の格子において、点Aから点Bへの最短経路の数を求める。

1. 問題の内容

与えられた問題は、次の3つの問いから構成されています。

* 問題2: "BANANA"の6文字から4文字を選んで文字列を作る場合の数を求める。

* 問題4-1: 図1の格子において、点Aから点Bへの最短経路のうち、点Cを通る経路の数を求める。

* 問題4-2: 図1の格子において、点Aから点Bへの最短経路のうち、点Dまたは点Eを通る経路の数を求める。

* 問題4-3: 図2の格子において、点Aから点Bへの最短経路の数を求める。

2. 解き方の手順

問題2:

BANANAの文字の構成は、Bが1つ、Aが3つ、Nが2つです。4文字の選び方を場合分けして考えます。

* (i) Aを3つ含む場合: AAAA, AAAB, AAANの3種類。

* (ii) Aを2つ含む場合: AANN, AANBの1種類+1種類。

* (iii) Aを1つ含む場合: ABNNの1種類。

* (iv) Aを全く含まない場合: BNのどちらも2つ以上含まないので不可能。

それぞれの文字列の並べ方を計算します。

* AAAA: 1通り

* AAAB: 4!/3! = 4通り

* AAAN: 4!/3! = 4通り

* AANN: 4!/(2!2!) = 6通り

* AANB: 4!/2! = 12通り

* ABNN: 4!/2! = 12通り

したがって、文字列の総数は $1 + 4 + 4 + 6 + 12 + 12 = 39$通り。

問題4-1:

点Aから点Cへの最短経路は、右に1回、下に2回移動するので、${3 \choose 1} = 3$通りです。点Cから点Bへの最短経路は、右に3回、上に1回移動するので、${4 \choose 1} = 4$通りです。したがって、点Aから点Cを経由して点Bへ行く最短経路は $3 \times 4 = 12$通りです。

問題4-2:

点Aから点Dへの最短経路は、右に1回、上に1回移動するので、${2 \choose 1} = 2$通りです。点Dから点Bへの最短経路は、右に3回、下に3回移動するので、${6 \choose 3} = 20$通りです。したがって、点Aから点Dを経由して点Bへ行く最短経路は $2 \times 20 = 40$通りです。

点Aから点Eへの最短経路は、右に2回、下に2回移動するので、${4 \choose 2} = 6$通りです。点Eから点Bへの最短経路は、右に2回、上に2回移動するので、${4 \choose 2} = 6$通りです。したがって、点Aから点Eを経由して点Bへ行く最短経路は $6 \times 6 = 36$通りです。

点Dと点Eの両方を通る経路を考えます。AからDへは2通り。DからEへは、右に1回、下に3回移動するので、${4 \choose 1}=4$通りです。EからBへは6通りなので、$2 \times 4 \times 6 = 48$通りではありません。DからEを通る場合とEからDを通る場合で場合分けすると、経路が重複するため、包含排除の原理を使います。

点Dを通る経路と点Eを通る経路の和から、点DとEの両方を通る経路を引く必要があります。

AからDを通ってBへ行く経路が40通り。

AからEを通ってBへ行く経路が36通り。

AからDへ行く経路は2通り。DからEへ行く経路は、右に1回、下に1回で、2通り。EからBへ行く経路は6通り。よって、$2*2*6 = 24$通り。

DまたはEを通る経路は、$40 + 36 - 24 = 52$通り。

問題4-3:

図2において、AからBへの最短経路は、右に5回、下に4回移動するので、${9 \choose 4} = \frac{9!}{5!4!} = \frac{9 \times 8 \times 7 \times 6}{4 \times 3 \times 2 \times 1} = 126$通りです。

3. 最終的な答え

* 問題2: 39通り

* 問題4-1: 12通り

* 問題4-2: 52通り

* 問題4-3: 126通り