Weekend Mathematics／コロキウム室／NO.113

皆さん！この配列された数列をよく見ると、何かを思い出します。
それは、多項式：ｘ(ｘ＋１)(ｘ＋２)(ｘ＋３)(ｘ＋４)・・・(ｘ＋ｎ−１)を展開したときの係数です。
さらに、この係数は、第１種スターリング数にもなっています。
また、次のような性質を持っています。
F(n,1)=(n-1)!
F(n,n-1)=1
F(n,0)+F(n,1)+・・・+F(n,n-1)=n!

問題５については、
（�T）最後の札がｎであるとき：このときは、最後に必ず入れ換えをすることになるから、 ｋ回の入れ換えが起きるための条件は、最後のｎの札を除くｎ−１枚について、 ｋ−１回の入れ換えが起きることになる。
（�U）最後の札がｎでないとき：このときは、最後の札で入れ換えは起きないから、 ｋ回の入れ換えが起きるための条件は、
最後の札を除くｎ−１枚について、ｋ回の入れ換えが起きることである。
　よって、　Ｆ（ｎ，ｋ）＝Ｆ（ｎ−１，ｋ−１）＋（ｎ−１）×Ｆ（ｎ−１，ｋ）
実は、この漸化式が、第１種スターリング数の漸化式にもなっています。

問題６：期待値の関係は、漸化式を用いて、Ｅ（ｎ）＝Ｅ（ｎ―１）＋１／ｎがでてきます。
後は、Ｅ（ｎ）＝１／２＋１／３＋１／４＋・・・＋１／ｎ　になることは容易です。
出題の意図は、第１種スターリング数に魅力を感じたからです。

第７４回数学的な応募問題

太郎さんは、ときどき大学入試問題を見ています。 過去の東海大学の入試問題を参考にして出題します。

第１の箱、第２の箱、第３の箱、・・・、第ｎの箱と全部でｎ個の箱があります。 どの箱にもｎ本のくじが入っていて、当たりくじの本数は第ｋ個の箱にはｋ本ある。 （ｋ＝１，２，３，・・・，ｎ）
さて、（１）今、これらｎ個の箱から無作為に１個の箱を選び、 その箱からくじを無作為に１本取り出して、 くじを元の箱のもどしてまた同じ箱でさらに１本くじを引いたとき、

問題１：少なくとも１本当たりくじを引く確率を求めよ。

問題２：箱が無限に多くあったとき、少なくとも１本当たりくじを引く確率の極限値を求めよ。

また、（２）これらｎ個の箱から無作為に２個の箱を選び、 それらの箱から１本ずつくじを引きとき、

問題３：少なくとも１本当たりくじを引く確率を求めよ。

問題４：箱が無限に多くあったとき、少なくとも１本当たりくじを引く確率の極限値を求めよ。

包含と排除の原理

集合Ｓの中の部分集合をＳ（ａ_ｉ）と書き、その要素の個数をＮ（ａ_ｉ）とする。
また、集合Ｓ（ａ_ｉ）の補集合をＳ（ａ_ｉ）と書き、その要素の個数をＮ（ａ_ｉ）とする。
さらに、集合Ｓ（ａ_ｉ）と集合Ｓ（ａ_k）との共通部分をＳ（ａ_ｉａ_k）と書き、 その要素の個数をＮ（ａ_ｉａ_k）とする。
ただし、ｉ，ｋ＝１，２，３，・・・，ｎで、ｉ≠ｋとする。
ここで、ｎ＝１のとき、全体集合Ｓの要素の個数Ｎ（Ｓ）をＮとすると、
Ｎ＝Ｎ（ａ_１）＋Ｎ（ａ_１）より、Ｎ（ａ_１）＝Ｎ−Ｎ（ａ_１）・・・�@

ｎ＝２のときは、
Ｎ＝Ｎ（ａ_１ａ_２）＋Ｎ（ａ_１ａ_２）＋Ｎ（ａ_１ａ_２）＋Ｎ（ａ_１ａ_２）
したがって、

Ｎ（ａ１ａ２）	＝Ｎ−Ｎ（ａ１ａ２）−Ｎ（ａ１ａ２）−Ｎ（ａ１ａ２）
	＝Ｎ−｛Ｎ（ａ１ａ２）＋Ｎ（ａ１ａ２）｝−｛Ｎ（ａ１ａ２）＋Ｎ（ａ１ａ２）｝＋Ｎ（ａ１ａ２）
	＝Ｎ−Ｎ（ａ１）−Ｎ（ａ２）＋Ｎ（ａ１ａ２）・・・�A

さて、ｎ＝３のときは、

Ｎ＝	Ｎ（ａ１ａ２ａ３）＋Ｎ（ａ１ａ２ａ３）＋Ｎ（ａ１ａ２ａ３）＋Ｎ（ａ１ａ２ａ３）
	＋Ｎ（ａ１ａ２ａ３）＋Ｎ（ａ１ａ２ａ３）＋Ｎ（ａ１ａ２ａ３）＋Ｎ（ａ１ａ２ａ３）

この関係式を整理すれば良いのだが、３個の場合は容易ではない。
ｎ＝２のときの包除の原理の関係式�Aを利用して、導くことにする。
�Aの式で、全体集合Ｓの代わりにすでに、集合Ｓ（ａ_３）について同じような関係式を作る。

Ｎ（ａ_１ａ_２ａ_３）＝Ｎ（ａ_３）−Ｎ（ａ_１ａ_３）−Ｎ（ａ_２ａ_３）＋Ｎ（ａ_１ａ_２ａ_３）

したがって、

Ｎ（ａ１ａ２ａ３）	＝Ｎ（ａ１ａ２）−Ｎ（ａ１ａ２ａ３）
	＝｛Ｎ−Ｎ（ａ１）−Ｎ（ａ２）＋Ｎ（ａ１ａ２）｝ 　−｛Ｎ（ａ３）−Ｎ（ａ１ａ３）−Ｎ（ａ２ａ３）＋Ｎ（ａ１ａ２ａ３）｝
	＝Ｎ−Ｎ（ａ１）−Ｎ（ａ２）−Ｎ（ａ３） 　＋Ｎ（ａ１ａ２）＋Ｎ（ａ１ａ３）＋Ｎ（ａ２ａ３）−Ｎ（ａ１ａ２ａ３）・・・�B

次に、ｎ個の集合の場合にも一般化した関係式を考えることができる。
その証明方法は、上に�Aから�Bを導いた同じ変形で、数学的帰納法できる。
では、一般の包除の原理は、

Ｎ（ａ１ａ２・・・ａｎ）	＝	Ｎ−Ｎ（ａ１）−Ｎ（ａ２）−・・・−Ｎ（ａｎ）
		＋Ｎ（ａ１ａ２）＋Ｎ（ａ１ａ３）＋・・・＋Ｎ（ａｎ−１ａｎ）
		・・・・・・＋（−１）ｎＮ（ａ１ａ２・・・ａｎ）
	＝

＜証明＞
自然数ｎに関して、数学的帰納法で証明します。
ｎ＝１のときは、�@より証明済み
ｎ＝ｋのとき、上の関係式が成り立つと仮定する。
すると、全体集合Ｓの中で、ｋ個の部分集合に関して、次の関係式が成立する。

Ｎ（ａ１ａ２・・・ａｋ）	＝	Ｎ−Ｎ（ａ１）−Ｎ（ａ２）−・・・−Ｎ（ａｋ）
		＋Ｎ（ａ１ａ２）＋Ｎ（ａ１ａ３）＋・・・＋Ｎ（ａｋ−１ａｋ）
		・・・・・・＋（−１）ｋＮ（ａ１ａ２・・・ａｋ）・・・�C

ここで、部分集合Ｓ（ａ_ｋ＋１）に対する同じ関係式を作ると

Ｎ（ａ１ａ２・・・ａｋａｋ＋１）	＝	Ｎ（ａｋ＋１）−Ｎ（ａ１ａｋ＋１）−Ｎ（ａ２ａｋ＋１） −・・・−Ｎ（ａｋａｋ＋１）
		＋Ｎ（ａ１ａ２ａｋ＋１）＋Ｎ（ａ１ａ３ａｋ＋１）＋・・・＋Ｎ（ａｋ−１ａｋａｋ＋１）
		・・・・・・＋（−１）ｋＮ（ａ１ａ２・・・ａｋａｋ＋１）・・・�D

そして、Ｎ（ａ_１ａ_２・・・ａ_ｋａ_ｋ＋１）を�C−�Dから作ると、

Ｎ（ａ１ａ２・・・ａｋａｋ＋１）	＝	Ｎ（ａ１ａ２・・・ａｋ） −Ｎ（ａ１ａ２・・・ａｋａｋ＋１）
	＝	Ｎ−Ｎ（ａ１）−Ｎ（ａ２）−・・・−Ｎ（ａｋ）
		＋Ｎ（ａ１ａ２）＋Ｎ（ａ１ａ３）＋・・・＋Ｎ（ａｋ−１ａｋ）
		・・・・・・＋（−１）ｋＮ（ａ１ａ２・・・ａｋ）
		−｛Ｎ（ａｋ＋１）−Ｎ（ａ１ａｋ＋１）−Ｎ（ａ２ａｋ＋１）−・・・−Ｎ（ａｋａｋ＋１）
		＋Ｎ（ａ１ａ２ａｋ＋１）＋Ｎ（ａ１ａ３ａｋ＋１）＋・・・＋Ｎ（ａｋ−１ａｋａｋ＋１）
		・・・・・・＋（−１）ｋＮ（ａ１ａ２・・・ａｋａｋ＋１）｝
	＝	Ｎ−Ｎ（ａ１）−Ｎ（ａ２）−・・・−Ｎ（ａｋ＋１）
		＋Ｎ（ａ１ａ２）＋Ｎ（ａ１ａ３）＋・・・＋Ｎ（ａｋａｋ＋１）
		・・・＋（−１）ｋ＋１Ｎ（ａ１ａ２・・・ａｋａｋ＋１）

すなわち、ｎ＝ｋ＋１の場合にも成立しているを示しているので、数学的帰納法よりすべての自然数ｎについて、この定理は成り立つ。
この式は見た目より記憶しやすくなっていますから、覚え易いです。

【参考】
自然数Ｎ＝(ｐ_１^ｎ１) (ｐ_２^ｎ２)・・・(ｐ_ｒ^ｎｒ)
（ただし、ｐ_１≠ｐ_２≠…≠ｐ_ｒ）と因数分解できたとき、１からＮまでの範囲で、 Ｎと互いに素の数の個数φ（Ｎ）（オイラー関数）は、
φ（Ｎ）＝Ｎ（１−１／ｐ_１）（１−１／ｐ_２）・・・（１−１／ｐ_ｒ）
で表される。この証明に、先ほどの包除の原理が利用できる。

太郎さんのクラスの人数は４０人います。 国語、数学、英語の試験を実施した結果、国語の合格者は８人、 数学の合格者は１２人、英語の合格者は１０人で、３科目とも合格者は５人でした。 このとき、３科目とも不合格者は何人以上いるでしょうか。

実は、いつも悩んでいる問題があります。
５０人のクラスで、男の兄弟がいる人は３３人、姉妹がいる人は２７人である。このとき、次の問に答えよ。

問題１：１人っ子は何人以下である。

問題２：男の兄弟、姉妹ともにいる人は何人以上いる。

問題３：男の兄弟だけがいる人は少なくとも何人、多くて何人までいる。

問題４：姉妹だけいる人は何人以下である。

問題１：１人っ子は何人以下である。

0人以上、16人以下。

問題２：男の兄弟、姉妹ともにいる人は何人以上いる。

10人以上、26人以下。

問題３：男の兄弟だけがいる人は少なくとも何人、多くて何人までいる。

7人以上、23人以下。

問題４：姉妹だけいる人は何人以下である。

1人以上、17人以下。

　LET  XMAX=0
　LET  XMINI=50
　LET  YMAX=0
　LET  YMINI=50
　LET  ZMAX=0
　LET  ZMINI=50
　LET  SMAX=0
　LET  SMINI=50
　FOR X=0 TO 33
 　  FOR Z=0 TO 27
  　    FOR Y=0 TO 27
   　      IF X>0 AND Z>0 THEN
    　        FOR S=0 TO 50
     　          LET  XY=X+Y
      　         IF XY=33 THEN
       　           LET  YZ=Y+Z
        　          IF YZ=27 THEN
         　            LET  T=X+Y+Z+S
          　           IF T=50 THEN
           　             IF XXMAX THEN
               　            LET  XMAX=X
                　        END IF
                 　       IF YYMAX THEN
                     　      LET  YMAX=Y
                      　  END IF
                        　IF ZZMAX THEN
                           　LET  ZMAX=Z
                        EN　D IF
                        IF 　SSMAX THEN
                          　 LET  SMAX=S
                        　END IF
                     　END IF
                  　END IF
               　END IF
            　NEXT S
         　END IF
      　NEXT Y
   　NEXT Z
　NEXT X
　PRINT XMINI;XMAX
　PRINT YMINI;YMAX
　PRINT ZMINI;ZMAX
　PRINT SMINI;SMAX
　END

20人以上、 27人以下。

　LET  HMINI=40
　LET  HMAX=0
　FOR A=0 TO 7
 　  FOR B=0 TO 5
  　    FOR C=0 TO 3
   　      FOR D=0 TO 7
    　        FOR E=0 TO 7
     　          FOR F=0 TO 3
      　            FOR G=5 TO 5
       　              FOR H=0 TO 40
        　                LET  T=A+B+C+D+E+F+G+H
         　               IF T=40 THEN
          　                 LET  MA=A+D+E+G
           　                IF MA=12 THEN
            　                  LET  EN=B+E+F+G
             　                 IF EN=10 THEN
              　                   LET  JA=C+D+F+G
               　                  IF JA=8 THEN
                　                    IF HHMAX THEN
                    　                   LET  HMAX=H
                     　               END IF
                      　           END IF
                       　       END IF
                        　   END IF
                        　END IF
                 　    NEXT H
               　   NEXT G
             　  NEXT F
           　 NEXT E
         　NEXT D
     　 NEXT C
   　NEXT B
　NEXT A
　PRINT HMINI;HMAX
　END

（１）問題１，２
どの箱を選ぶか、確率は1/nです。
k番目の箱を選んだとして、２本ともはずれの確率は、{(n-k)/n}²
従って、求める確率をＰ(ｎ)とすると、

または、区分求積を用いて、

ABCD×4=DCBAとなる４桁の数字がある。この4桁の数字を求めよ。

私が最近悩んでいる問題があります。魔法陣のことです。３×３の魔法陣は論 理的に作れるのに、５×５がどうしても作れません。よそのホームページで作り方を 教えてもらいましたが、どうしてその過程になるのかがわかりません。

E-mail 戻る