Math Lab

数学にセンスはいらない。

場合の数の基本〜考えやすいように言い換える〜

場合の数の基本〜考えやすいように言い換える〜

例題

4 桁の整数を作る.その千の位の数を x , 百の位の数を y , 十の位の数を z , 一の位の数を w とする.
(1) x\gt y\gt z\gt w となる整数は全部で何個か.
(2) x+y+z=9 となる整数は全部で何個か.
(3) x\leqq y\leqq z\leqq w となる整数は全部で何個か.


(1) 調べ上げは大変です.
0〜9 の10個の数字から4個選び,大きい方から順に x, y, z, w と並べることを考え
   {}_{10}\mathrm{C}_4\times1=210

(2)調べ上げは大変です.ボールと仕切りで考えると考えやすいです.


9個の〇と2個の|(仕切り) を並べて考える

f:id:mathchem:20170311101748p:plain

左から順に, x,\ y,\ z とし,x\geqq 1 より,左端は 〇 とする.

残りは8個の 〇 と2個の|を並べることになるので,

同じものを含む順列を考え,\dfrac{10!}{8!\cdot2!}通り,

(または,10箇所のうちのどの2箇所(8箇所)が|か(〇か)で {}_{10}\mathrm{C}_{2} 通り.

w は10通りあるから,答えは 45\times10=450


(3) (1)とちょっと違う...
(1)は上手く言い換えられました.(3)は(1)と何が違うでしょうか?
そう等号が含まれているので,考えにくい...じゃあ,等号外しましょうよ.

   1\leqq x\leqq y\leqq z\leqq w\leqq 9

★等号外すために1を足していきます.

   1\leqq x\lt y+1\lt z+2\lt w+3\leqq 12

と同値である.

よって,1〜12から4個選び,小さいほうから順に x,\ y+1,\ z+2,\ w+3 とすればよいから,{}_{12}\mathrm{C}_{4}=495 個.

★簡単に同値変形とかいうなよ...

と思うかもしれませんがこの変形は経験ありき,です.知らないとおそらく解けないです.

実際に値を入れて確認してみましょう.

   1\leqq x\leqq y\leqq z\leqq w\leqq 9

を満たす,x=1, y=4, z=4, w=9

   1\leqq x\lt y+1\lt z+2\lt w+3\leqq 12

に入れてみると,

   1\leqq 1\lt 4+1\lt 4+2\lt 9+3\leqq 12

   1\leqq 1\lt 5\lt 6\lt 12\leqq 12

となり,等号が外れた状態が作れます.

逆に,1\leqq x\lt y+1\lt z+2\lt w+3\leqq 12

で,x=1,\ y+1=5,\ z+2=6,\ w+3=12 とすると

x=1,\ y=4,\ z=4,\ w=9 となるので,同じことを意味してるんですね.