[答901] 組合せと偶数の個数

[答901] 組合せと偶数の個数


　0以上の整数nに対して、_nＣ₀， _nＣ₁， _nＣ₂，……，_nＣ_n のうち偶数であるものの個数を E(n) とします。

　(1) E(0)＋E(1)＋E(2)＋……＋E(50)＝？

　(2) E(n)＝901 のとき n＝？


[解答]

　_nＣ₀， _nＣ₁， _nＣ₂，……，_nＣ_n のうち奇数であるものの個数を F(n) とし、

　F(m) から F(n) までの和を簡単に ΣF(m，n) と書くことにします。

　図はパスカルの三角形において、

　奇数を●，偶数を○で表し、右に n の値を２進法で書いたものです。

　_nＣ_r＝_n-1Ｃ_r-1＋_n-1Ｃ_r だから、奇数●になるのは、両端および斜め上の２数が●と○のときだけです。

　以下、奇数●の配置について考察します。

　n＝3＝11₍₂₎ の場合、全部が●で 4個並んでいますが、

　n＝4＝100₍₂₎ の場合、両端だけが●になるので、

　n＝4＝100₍₂₎ ～ n＝7＝111₍₂₎ については n＝0＝0₍₂₎ ～ n＝3＝11₍₂₎ の配置を横に２個並べたものになり、

　n＝7＝111₍₂₎ には、全部が●で 8個並びます。

　n＝8＝1000₍₂₎ の場合、両端だけが●になるので、

　n＝8＝1000₍₂₎ ～ n＝15＝1111₍₂₎ については n＝0＝0₍₂₎ ～ n＝7＝111₍₂₎ の配置を横に２個並べたものになり、

　n＝15＝1111₍₂₎ には、全部が●で 16個並びます。

　このように、自然数kについて、

　n＝2^k－1 のとき、全部が●で 2^k個並び、F(2^k－1)＝2^k 、

　その下の n＝2^k のとき、両端だけが●で、F(2^k)＝2 です。

　また、例えば n＝6＝110₍₂₎ や n＝10＝1010₍₂₎ の行は

　n＝2＝10₍₂₎ の行を２個並べたものだから、F(6)＝F(10)＝2･F(2) です。　

　一般に、２進法で n を表したとき、上位に 1 がひとつ増えれば、F(n) は２倍になります。

　従って、F(0)＝1＝2⁰ を元にすれば、F(n)＝2^k ( k は n を２進法で表したときの 1 の個数) となります。

　(1) n＝0 ～ n＝15 は２進法で４桁以下で、1 が k 個の数は ₄Ｃ_k 個だから、

　 ΣF(0，15)＝2⁰･₄Ｃ₀＋2¹･₄Ｃ₁＋2²･₄Ｃ₂＋2³･₄Ｃ₃＋2⁴･₄Ｃ₄＝(1＋2)⁴＝81 、

　 16＝10000₍₂₎ より ΣF(16，31)＝2･ΣF(0，15) 、32＝100000₍₂₎ より ΣF(32，47)＝2･ΣF(0，15) 、

　 ΣF(0，2)＝1＋2＋2＝5 、48＝110000₍₂₎ より ΣF(48，50)＝2²･ΣF(0，2) 、

　 ΣF(0，50)＝(1＋2＋2)･ΣF(0，15)＋4･ΣF(0，2)＝5･81＋4･5＝425 、奇数は 425個です。

　 奇数偶数を合わせて 1＋2＋3＋……＋51＝51･52/2＝1326 個だから、偶数は 1326－425＝901 個です。

　(2) E(n)＋F(n)＝n＋1 だから n＝E(n)＋F(n)－1 、E(n)＝901 のとき n＝900＋F(n) です。

　 900＋2^k＝1110000100₍₂₎＋10₍₂₎^k より

　 右辺を２進法で計算して 1 の個数が k 個になるのは k＝5 のときだけだから、

　 n＝900＋2⁵＝932 です。

.