counting_chap8

B4 古川勇輔




四面体サイコロの目は底面とする
その目
を、1つの数列と考え、生成関数
をProp8.2より、
とすると、目が、
(1,2,3,4)となる四面体サイコロ2つを投げた場合の
和の生成関数は、
と表される
今、投げる2つの四面体サイコロの目をそれぞれ
,
とすると、その和は
となる
つまり、
=
これより、2つの四面体サイコロの目は(1,2,2,3),(1,3,3,5)
となる。




Ex8.5と同様にして考える
サイコロを投げた時の目は(1,2,3,4,5,6)であるから、
その生成関数は、
と表される
よって、サイコロを6個投げる時を考えると
これの
の係数をで割れば、複雑な場合分け
をしなくても求める確率が分かる

,
をそれぞれ、
,


として
も、条件を満たす
よって、このように問題を書きかえることによって、全
ての数列の要素を自然数にしても、一般性を失わな
い
これにより、全ての数列の要素は自然数であると考え、
生成関数を用いる

A=
,B=
れぞれの生成関数は
となる。このとき、Prop8.2より
とすると、そ

同様に
条件より
＝
であるから
A,Bは異なる数列であるから、
ここで、
因数にもち、
よって、
より、
は
よって
は(x-1)を
を因数にもつ
x=1とすることにより
よって、
となる


普通のコインであれば、表を1、裏を0として、(0,1)に
よる生成関数
を使用すれば良いのだが、こ
のコインは出る確率が違い、2k+1回に1回しか表が
でない
よって、確率も考慮すると、(0,0,…,0,1)という数列を
考え、前に挙げた生成関数の代わりに
をk枚目のコインについての生成関数として考える


このとき、n個のコインを投げる事を考えると、その関
数は
となる
この関数のうち、
る。
が、求める確率であ

まず、f(1)は全ての係数の合計である

次に、f(-1)について考えると、これは、xの次数が奇
数の部分は係数が-1,偶数の部分は係数が1となる。

よって、f(1)-f(-1)によって、次数が奇数の係数の合
計の2倍が出る

以上より、求める確率pとすると



例えば、全ての非負整数からなる数列は条件を満た
さない
―全ての非負整数を一意に表すことができない
例）15=15+2×0+4×0=1+2×1＋4×3＝…
この場合表し方が一意ではない
全ての非負整数を一意に表す為の方法を考える
が二進表現に近い形を持っていること
に注目する

というものを考えると、これは、
を二進数であると考えた時の値と一致し、その値は
0以上7以下の整数である。よって、この3つを合わせ
て8進数の1つの数字と考えてもよい

について、8進数で全ての桁が1ま
たは0であるような数字を小さい順に並べたものを考
える。これが全ての非負整数を一意に表す事を示す


任意の非負整数nは、8進数で表される。これを
と表すとすると、全てのは、
0以上7以下の整数であるから
(
は1又は0)と表せる
つまり、は
を二進表示として見たもの
である
これにより、
とすることができ
によって、
一意に表せる



は、以下の様なもの、ただし8進表現
これらが全てAに属していることは、
が1又は0の
値をとることから明らか。非負整数の二進表現は一意
に定まる為、その二進表現に対する
も
一意に定まる

よって、全ての要素が0または1の8進表示の非負整
数による増加数列は、条件を満たす

は、このような数列の1998番目に小さい数で
あるから、1998の二進表現11111001110を8進数
に読み替えたものが、求める数である。



どういう操作をしたのか、実際に1998を用いてやって
みる
1998の二進表現は11111001110 これを3桁ごと
に切り出して、
を作る
=0101,
=1101,
=1110（8進）
これを二進表現に戻すと例えば
=001001000001のように、8のべき乗の位に
それぞれの数字が入る。後はこれを2倍、4倍して位
をずらし、足している





本当にこれでいいのか？
他に求める条件を満たす増加数列はないのか？
その様な増加数列が他にあれば、他に
が存在
するのではないか？
これ以外に条件を満たすものがあるのか無いのかも
調べなければならない
そうだ、生成関数を使おう！

A＝(
)の生成関数は
となる。同様に
よって、Prop8.2より

条件より、
に表すので、
これをg(x)としておく
は、全ての非負整数を一意
更に、
よって、
であるから、

F(x)

この関数の係数は、xのべき乗の和で表される部分に
しか付かない、その他の部分は0

これは、が8のべき乗の和で表される数の集合であ
ることを示している
α(n)の例：4
4=1+1+1+1=1+1+2=1+2+1=2+1+1=2+2
 Β(n)の例：6
6=4+2=3+3=2+4=2+2+2
この場合、α(4)＝β（6）＝5
 α(n,k)を、
、
を満たす
の個数とすると
1つのの生成関数は
である


α(n,k)=
また、α(n)=α(n,1)+α(n,2)+…
よって、α(n)は次の関数の
部分の係数である

つまり、



Β(n)についても同様にして

よって、

これらより

β(n)において、n=n+2とすればα(n)=β(n+2)となる

Download Report