離散数学-カウント理論

日常生活では、多くの場合、一連のイベントのすべての可能な結果の数を調べる必要があります。たとえば、6人の男性と4人の女性で構成される審査員団は、50人の男性と38人の女性の中からいくつ選べますか？最初の5文字がアルファベット、次の4文字が数字、最後が再び大文字になるように、いくつの異なる10文字のPAN番号を生成できます。これらの問題を解決するために、カウントの数学的理論が使用されます。 *カウント*には、主に基本的なカウント規則、置換規則、および組み合わせ規則が含まれます。

合計と製品のルール

*Rule of Sum* および *Rule of Product* は、難しいカウント問題を単純な問題に分解するために使用されます。

合計のルール-タスク$ T_1、T_2、\ dots、T_m $のシーケンスをそれぞれ$ w_1、w_2、\ dots w_m $の方法で実行できる場合（条件はタスクを同時に実行できないことです）、これらのタスクの1つを行う方法の数は、$ w_1 + w_2 + \ dots + w_m $です。互いに素な2つのタスクAとBを検討する場合（つまり、 $ A \ cap B = \ emptyset $）、その後数学的に$ | A \ cup B | = | A | + | B | $
製品のルール-一連のタスク$ T_1、T_2、\ dots、T_m $をそれぞれ$ w_1、w_2、\ dots w_m $の方法で実行でき、すべてのタスクが前のタスクの発生後に到着する場合、タスクを実行するには、$ w_1 \ times w_2 \ times \ dots \ times w_m $の方法があります。数学的には、タスクBがタスクAの後に到着した場合、$ | A \ times B | = | A | \ times | B | $

例

質問-Xに住んでいる少年がZの学校に行きたいと思っています。彼は自宅Xから最初にYに到達し、次にYからZに到達する必要があります。彼は3つのバス路線または2つの鉄道路線でXからYに行くことができます。そこから、彼はZに到達するために4つのバス路線または5つの列車路線を選択できます。 XからZに行く方法はいくつありますか？

解決策-XからYまで、彼は$ 3 + 2 = 5 $の方法で進むことができます（Rule of Sum）。その後、彼は$ 4 + 5 = 9 $の方法でYからZに移動できます（合計のルール）。したがって、XからZまで、彼は$ 5 \ times 9 = 45 $の方法で進むことができます（製品の規則）。

順列

順列*は、順序が重要ないくつかの要素の配置です。つまり、順列は要素の順序付けられた組み合わせです。

例

セットS = \ {x、y、z}から、一度に2つを取ることにより、すべての順列は- + $ xy、yx、xz、zx、yz、zy $。
数字のセット$ S = \ lbrace 1、2、3 \ rbrace $から3桁の数字の順列を作成する必要があります。数字を配置すると、異なる3桁の数字が形成されます。順列は、123、132、213、231、312、321になります。

順列の数

一度に「n」個の「n」個をとる順列の数は、$ n _ \ {P _ \ {r}} $で示されます。

n _ \ {P _ \ {r}} = \ frac \ {n！} \ {（n-r）！}

$ n！ = 1.2.3。 \ dots（n-1）.n $

証明-「n」個の異なる要素があるとします。

最初の場所を埋める方法はn通りあります。最初の場所（n-1）を埋めた後、要素の数が残ります。したがって、2番目の場所を埋める（n-1）方法があります。 1番目と2番目の場所を埋めると、（n-2）個の要素が残ります。したがって、3番目の場所を埋める（n-2）方法があります。 [n –（r–1）] = n–r + 1のように、r番目の場所を埋める方法の数を一般化できます。

したがって、合計はありません。最初の場所からr番目の場所まで埋める方法の-

$ n _ \ {P _ \ {r}} = n（n-1）（n-2）….. （n-r + 1）$

$ = [n（n-1）（n-2）… （n-r + 1）] [（n-r）（n-r-1）\ dots 3.2.1]/[（n-r）（n-r-1）\ dots 3.2.1] $

したがって、

$ n _ \ {P _ \ {r}} = n！/（n-r）！$

順列のいくつかの重要な公式

$ a_1 $が何らかの種類に似ている_n_要素がある場合、$ a_2 $は別の種類に似ています。 $ a_3 $は第3種などで、$ a_r $は$ r ^ \ {th} $種で、$（a_1 + a_2 + … a_r）= n $。 +次に、これらのn個のオブジェクトの順列の数は= $ n！です。/[（a_1！（a_2！）\ dots（a_r！）] $。
一度にn個の要素を取るn個の異なる要素の順列の数= $ n _ \ {P_n} = n！$
一度にr個の要素をとるn個の非類似要素の順列の数。x個の特定のものが常に一定の場所を占める場合= $ n-x _ \ {p _ \ {r-x}} $
r個の指定されたものが常に一緒になったときのn個の異なる要素の順列の数は-$ rです！（n−r + 1）！$
r個の指定されたものが一緒にならない場合のn個の異なる要素の順列の数は、-$ n！– [r！（n−r + 1）！] $
時間でx個の要素をとるn個の異なる要素の循環順列の数= $ ^ np _ \ {x}/x $
n個の異なるものの循環順列の数= $ ^ np _ \ {n}/n $

いくつかの問題

問題1 *-6種類のカードの束から、いくつの方法でそれを変更できますか？

解決策-6枚のカードのデッキから一度に6枚のカードを取っているので、順列は$ ^ 6P _ \ {6} = 6になります！ = 720$

問題2 *-「リーダー」という単語の文字をいくつの方法で配置できますか？

解決策-単語「READER」には6文字の単語（2 E、1 A、1D、および2R）があります。

順列は$ = 6になります！/\：[（2！）（1！）（1！）（2！）] = 180. $

問題3 *-子音が偶数位のみを占めるように、「ORANGE」という単語の文字をどのように配置できますか？

解決策-「ORANGE」という単語には3つの母音と3つの子音があります。子音を互いに配置する方法の数$ = ^ 3P _ \ {3} = 3！ = 6$. 残りの3つの空いている場所は、$ ^ 3P _ \ {3} = 3の3つの母音で埋められます！ = 6 $ウェイ。したがって、順列の総数は$ 6 \ times 6 = 36 $です

組み合わせ

組み合わせ*は、順序が重要ではない特定の要素の選択です。

一度にrを取るn個のすべての組み合わせの数は-

^ nC _ \ {\ {r}} = \ frac \ {n！ } \ {r！（n-r）！ }

問題1 *

3つの要素を持つセット$ \ lbrace1、2、3、4、5、6 \ rbrace $のサブセットの数を見つけます。

溶液

セットの基数は6であり、セットから3つの要素を選択する必要があります。ここでは、順序は関係ありません。したがって、サブセットの数は$ ^ 6C _ \ {3} = 20 $になります。

問題2 *

部屋には6人の男性と5人の女性がいます。部屋から男性3人と女性2人を選択する方法はいくつありますか？

溶液

6人の男性から3人の男性を選択する方法の数は$ ^ 6C _ \ {3} $で、5人の女性から2人の女性を選択する方法の数は$ ^ 5C _ \ {2} $です

したがって、ウェイの総数は− $ ^ 6C _ \ {3} \ times ^ 5C _ \ {2} = 20 \ times 10 = 200 $です。

問題3 *

合計9人の生徒から3人の生徒の3つの異なるグループを選択する方法はいくつありますか？

溶液

グループに1、2、3の番号を付けましょう

1 ^ st ^グループに3人の生徒を選択する場合、ウェイの数-$ ^ 9C _ \ {3} $

1番目のグループを選択した後、2番目のグループの3人の生徒を選択する方法の数-$ ^ 6C _ \ {3} $

1 ^ st ^および2 ^ nd ^グループを選択した後、3 ^ rd ^グループに3人の生徒を選択する方法の数-$ ^ 3C _ \ {3} $

したがって、ウェイの総数$ = ^ 9C _ \ {3} \ times ^ 6C _ \ {3} \ times ^ 3C _ \ {3} = 84 \ times 20 \ times 1 = 1680 $

パスカルのアイデンティティ

17世紀にブレーズパスカルによって最初に導出されたパスカルのアイデンティティは、n個の要素からk個の要素を選択する方法の数は、（n-1）個から（k-1）個の要素を選択する方法の数の合計に等しいと述べています）要素と、n-1個の要素から要素を選択する方法の数。

数学的には、正の整数kおよびnの場合：$ ^ nC _ \ {k} = ^ n \ {^-} ^ 1C _ \ {k-1} + ^ n \ {^-} ^ 1 \ {C_k} $

証明-

^ n \ {^-} ^ 1C _ \ {k-1} + ^ n \ {^-} ^ 1 \ {C_k}

$ = \ frac \ {（n-1）！ } \ {（k-1）！（n-k）！ } + \ frac \ {（n-1）！ } \ {k！（n-k-1）！ }$

$ =（n-1）！（\ frac \ {k} \ {k！（n-k）！ } + \ frac \ {n-k} \ {k！（n-k）！ } )$

$ =（n-1）！ \ frac \ {n} \ {k！（n-k）！ }$

$ = \ frac \ {n！ } \ {k！（n-k）！ }$

$ = n _ \ {C _ \ {k}} $

ピジョンホールの原理

1834年、ドイツの数学者、ピーター・グスタフ・レジューヌ・ディリクレは、引き出し原理と呼ばれる原理を述べました。今、それは鳩の巣の原則として知られています。

*Pigeonhole Principle* は、鳩の総数が鳩の総数よりも少なく、各鳩が鳩の穴に置かれる場合、複数の鳩のいる鳩の穴が少なくとも1つ存在する必要があると述べています。 n個のハトがm個の鳩の穴に入れられ、n> mの場合、複数の鳩のいる穴があります。

例

10人の男性が部屋にいて、握手に参加しています。各人が少なくとも1回握手し、同じ男性の手を2回以上振る人がいない場合、2人の男性が同じ数の握手に参加しました。
30のクラスには、名前が同じアルファベットで始まる人が少なくとも2人必要です。

包含排除の原則

包含/排除の原則*は、複数の非素集合の和集合の基数を計算します。 2つのセットAとBの場合、原理は次のように述べています-

$ | A \ cup B | = | A | + | B | -| A \ cap B | $

3セットA、B、Cの場合、原理は次のように述べています

$ | A \ cup B \ cup C | = | A | + | B | + | C | -| A \ cap B | -| A \ cap C | -| B \ cap C | + | A \ cap B \ cap C | $

一般化された式-

$ | \ bigcup _ \ {i = 1} ^ \ {n} A_i | = \ sum \ limits _ \ {1 \ leq i <j <k \ leq n} | A_i \ cap A_j | + \ sum \ limits _ \ {1 \ leq i <j <k \ leq n} | A_i \ cap A_j \ cap A_k |-\ dots +（-1）^ \ {\ pi-1} | A_1 \ cap \ dots \ cap A_2 | $

問題1 *

1から50までの整数は2または3の倍数ですが、両方ではありませんか？

溶液

1から100までは、2の倍数である$ 50/2 = 25 $の数値があります。

$ 50/3 = 16 $の数字は3の倍数です。

2と3の倍数である50/6 = 8 $の数字があります。

したがって、$ | A | = 25 $、$ | B | = 16 $、および$ | A \ cap B | = 8 $です。

$ | A \ cup B | = | A | + | B | -| A \ cap B | = 25 + 16-8 = 33 $

問題2 *

50人の生徒のグループでは、24人が冷たい飲み物、36人が熱い飲み物を好み、各生徒は2つの飲み物のうち少なくとも1つを好みます。コーヒーと紅茶の両方が好きですか

溶液

Xを冷たい飲み物が好きな学生のセット、Yを熱い飲み物が好きな人のセットとします。

だから、$ | X \ cup Y | = 50 $、$ | X | = 24 $、$ | Y | = 36 $

$ | X \ cap Y | = | X | + | Y | -| X \ cup Y | = 24 + 36-50 = 60-50 = 10 $

したがって、お茶とコーヒーの両方が好きな学生は10人います。

Discrete-mathematics-counting-theory

目次