Fussy's Diary

いつの間にか「立夏」を過ぎていたんですね。すでに蒸し暑い状態が続いているように思います。

「数学問題bot」から二年前に拾った問題です。合ってるかどうか、あまり自信はありません。

-----

n個の1の間すべてに四則演算のいずれかの記号を書いて式を作る（カッコは使用不可）とき、答えが１になるものは何通りあるか。例：n=2なら1×1と1÷1の２通り (DrGojiMoriCun様)。

×と÷は値を変化させないので、どのように並んでいても必ず 1 になります。よって、計算結果が 1 になるかどうかは + と - の数だけで決まり、その数がゼロも含めて等しい場合だけ 1 になります。
n 個の 1 の間には n - 1 個の演算子が入れられるので、その中に + と - を並べる場合の数を、全ての×と÷の並べ方に対して求めれば目的の数が得られます。
+ と - を等しい数だけ並べる場合、その数はゼロから ( n - 1 ) / 2 ( n が奇数のとき ) または ( n - 2 ) / 2 ( n が偶数のとき ) となります。ゼロ個の場合から順番に考えてみます。

+, - がゼロ個なら、×,÷は n - 1 箇所に任意に入れられるので、2^n-1 通りの並べ方があります。
+, - が 1 個ずつなら、n - 1 箇所の中に + は n - 1 通りの入れ方があり、それぞれに対して - は n - 2 通りの入れ方があるので、( n - 1 )( n - 2 ) 通りの並べ方があります。残りの n - 3 箇所に×,÷は任意に入れられるので、それぞれに対しさらに 2^n-3 通りの並べ方があります。よって、2^n-3( n - 1 )( n - 2 ) 通りの入れ方があることになります。
一般化して +, - が k 個ずつなら、n - 1 箇所の中に + は _n-1C_k 通りの入れ方があり、それぞれに対して - は残り n - k - 1 箇所に _n-k-1C_k 通りの入れ方があるので、_n-1C_k・_n-k-1C_k 通りの並べ方があります。残りの n - 2k - 1 箇所に×,÷は任意に入れられるので、それぞれに対しさらに 2^n-2k-1 通りの並べ方があり、2^n-2k-1_n-1C_k・_n-k-1C_k 通りの入れ方があることになります。
これが 0 から ( n - 1 ) / 2 ( n が奇数のとき ) または ( n - 2 ) / 2 ( n が偶数のとき ) まであるので、

Σ_k{0→(n-1)/2}( 2^n-2k-1_n-1C_k・_n-k-1C_k ) ( n が奇数のとき )
Σ_k{0→(n-2)/2}( 2^n-2k-1_n-1C_k・_n-k-1C_k ) ( n が偶数のとき )

が求める解となります。n = 2 のときは、

Σ_k{0→0}( 2^2-2k-1₁C_k・_1-kC_k ) = 2

で、n = 3 のときは

Σ_k{0→1}( 2^2-2k₂C_k・_2-kC_k )
= 2²₂C₀・₂C₀ + 2⁰₂C₁・₁C₁
= 4 + 2 = 6

で、1×1×1, 1×1÷1, 1÷1×1, 1÷1÷1, 1+1-1, 1-1+1 が該当します。さらに n = 4 なら

Σ_k{0→1}( 2^3-2k₃C_k・_3-kC_k )
= 2³₃C₀・₃C₀ + 2¹₃C₁・₂C₁
= 8 + 12 = 20

で、

1×1×1×1, 1×1×1÷1, 1×1÷1×1, 1÷1×1×1, 1×1÷1÷1, 1÷1×1÷1, 1÷1÷1×1, 1÷1÷1÷1,
1×1+1-1, 1×1-1+1, 1÷1+1-1, 1÷1-1+1, 1+1×1-1, 1-1×1+1, 1+1÷1-1, 1-1÷1+1,
1+1-1×1, 1-1+1×1, 1+1-1÷1, 1-1+1÷1

が該当します。