[答901] 組合せと偶数の個数
[答901] 組合せと偶数の個数
0以上の整数nに対して、nC0, nC1, nC2,……,nCn のうち偶数であるものの個数を E(n) とします。
(1) E(0)+E(1)+E(2)+……+E(50)=?
(2) E(n)=901 のとき n=?
[解答]
nC0, nC1, nC2,……,nCn のうち奇数であるものの個数を F(n) とし、
F(m) から F(n) までの和を簡単に ΣF(m,n) と書くことにします。
図はパスカルの三角形において、
奇数を●,偶数を○で表し、右に n の値を2進法で書いたものです。
nCr=n-1Cr-1+n-1Cr だから、奇数●になるのは、両端および斜め上の2数が●と○のときだけです。
以下、奇数●の配置について考察します。
n=3=11(2) の場合、全部が●で 4個並んでいますが、
n=4=100(2) の場合、両端だけが●になるので、
n=4=100(2) ~ n=7=111(2) については n=0=0(2) ~ n=3=11(2) の配置を横に2個並べたものになり、
n=7=111(2) には、全部が●で 8個並びます。
n=8=1000(2) の場合、両端だけが●になるので、
n=8=1000(2) ~ n=15=1111(2) については n=0=0(2) ~ n=7=111(2) の配置を横に2個並べたものになり、
n=15=1111(2) には、全部が●で 16個並びます。
このように、自然数kについて、
n=2k-1 のとき、全部が●で 2k個並び、F(2k-1)=2k 、
その下の n=2k のとき、両端だけが●で、F(2k)=2 です。
また、例えば n=6=110(2) や n=10=1010(2) の行は
n=2=10(2) の行を2個並べたものだから、F(6)=F(10)=2・F(2) です。
一般に、2進法で n を表したとき、上位に 1 がひとつ増えれば、F(n) は2倍になります。
従って、F(0)=1=20 を元にすれば、F(n)=2k ( k は n を2進法で表したときの 1 の個数) となります。
(1) n=0 ~ n=15 は2進法で4桁以下で、1 が k 個の数は 4Ck 個だから、
ΣF(0,15)=20・4C0+21・4C1+22・4C2+23・4C3+24・4C4=(1+2)4=81 、
16=10000(2) より ΣF(16,31)=2・ΣF(0,15) 、32=100000(2) より ΣF(32,47)=2・ΣF(0,15) 、
ΣF(0,2)=1+2+2=5 、48=110000(2) より ΣF(48,50)=22・Σ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+2k=1110000100(2)+10(2)k より
右辺を2進法で計算して 1 の個数が k 個になるのは k=5 のときだけだから、
n=900+25=932 です。
.