(3) 2以上の自然数nに対して, 0と1をn 個並べたもの,すなわち各え
1,…….. n に対して of = 0 または as
a ai
"
て得られる (a,…………
(a1,・・・
バイナリーベクトル (a1,・・・・・ ,an)
10m) と
・,an) をn次元バイナリーベクトルとよぶ。 2つのn次元
=1であるようなai を順にn個並べ
・on) に対して、あるに対して
man)と
(b1,......, 6m) は隣接するという。 n次元バイナリーベクトル全体の集合をBで
Js031#
FOR
Q, b; であり,それ以外のうについては aj = b, となるとき, (a1,......
=
そわけか。
表すことにする。 例えば, n=3のときは
B3 = {(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)}
SKLE
$164.
であり,(0,0,0)と (1,0,0) は隣接し, (0,1,1) と (1,0,0) は隣接しない。 B の中
から隣接する2つのn次元バイナリーベクトルを取り出すとき, 取り出し方の組
み合わせの総数を M² と記す。 このとき、以下が成り立つ。ち
立。
(a) M2 ヤである。
= =
SARA
(b) M3= ユヨである。
=
(c)2以上のすべての自然数nに対して, Mn+1
立つ。
30
@=
ラ M + リが成り
n
ER
C
(d) すべての自然数nに対して, Mn+1 = (n+ルレ”である。
OA BA301008 (4)
+BA
(3)(a) B₂= {(0, 0), (0, 1), (1, 0), (1, 1)}
である。これらのうち、隣接する2つは
(00) と (01) (00) (1,0),
(0, 1)
(1, 1), (1, 0) (1, 1)
だけであるから
M2 = 4 →ヤ
(b)(a)と同様に隣接する2つを書き出してもよいが、 先に(d)まで解いてか
らその結果を用いると
M3=3.22=12 →ユヨ
(c) n≧2 とする。
B1 の中の隣接する2つのバイナリーベクトルは
(a1,a2,.., an, 0) と (61, 62, .., bn, 0)
(a1,a2,
..., am, 1)と(b, bz, ..., b, 1)
(a1,a2,.., an, 0) と (b1,b2, ・・・, b , 1)
... 1
......
②
.....③
のいずれかの形である。
9
①の形のとき, (a1,a2, ..., an) と (b1, 62, ..., bm) は B" の中の隣接
するバイナリーベクトルである。 よって, ①の形のものは M個ある。
20 5+)
同様に、②の形のものも M7個ある。
③の形のとき, すべてのi (i=1, ..., n) に対してa= b; である。 各
i (i=1, .... n) に対してα(= b;) の値は0か1の2通りあるから③の
9
形のものは2"個ある。
以上より
Mm+1 = M+M+2"=2M"+2" →ラ, リ
SVE
ありがとうございます!