離散数学-カウント理論
日常生活では、多くの場合、一連のイベントのすべての可能な結果の数を見つける必要があります。たとえば、男性50人と女性38人の中から、男性6人と女性4人で構成される審査員団をどのように選ぶことができるでしょうか。最初の5文字が大文字のアルファベット、次の4文字が数字、最後の文字が再び大文字になるように、10文字のPAN番号をいくつ生成できますか。これらの問題を解決するために、カウントの数学的理論が使用されます。Counting 主に、基本的なカウントルール、順列ルール、および組み合わせルールが含まれます。
合計と積の規則
ザ・ Rule of Sum そして Rule of Product 難しいカウントの問題を単純な問題に分解するために使用されます。
The Rule of Sum−タスクのシーケンス$ 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 | $
The Rule of Product−タスクのシーケンス$ 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 | $
例
Question−少年はXに住んでいて、Zの学校に行きたいと思っています。自宅のXから、最初にYに到達し、次にYからZに到達する必要があります。3つのバスルートまたは2つの電車ルートのいずれかでXからYに移動できます。そこから、彼はZに到達するために4つのバスルートまたは5つの電車ルートを選択できます。XからZに行くにはいくつの方法がありますか？
Solution− XからYまで、彼は$ 3 + 2 = 5 $の方法で進むことができます（数え上げの和則）。その後、彼はYからZに$ 4 + 5 = 9 $の方法で行くことができます（数え上げの和則）。したがって、XからZまで、彼は$ 5 \ times 9 = 45 $の方法で進むことができます（製品のルール）。
順列
A permutation順序が重要ないくつかの要素の配置です。言い換えれば、順列は要素の順序付けられた組み合わせです。
例
一度に2つを取ることによる集合S = {x、y、z}から、すべての順列は−です。
$ xy、yx、xz、zx、yz、zy $。
数字のセット$ S = \ lbrace 1、2、3 \ rbrace $から3桁の数字の順列を形成する必要があります。数字を並べると、異なる3桁の数字が形成されます。順列は= 123、132、213、231、312、321になります
順列の数
一度に「r」が取られる「n」個の異なるものの順列の数は、$ n_ {P_ {r}} $で表されます。
$$ n_ {P_ {r}} = \ frac {n！} {（n --r）！} $$
ここで$ n！= 1.2.3。\ dots（n-1）.n $
Proof −「n」個の異なる要素があるとします。
そもそも埋める方法はn通りあります。最初の場所（n-1）を埋めた後、要素の数が残ります。したがって、2位を埋める方法は（n-1）あります。1位と2位を埋めた後、（n-2）個の要素が残ります。したがって、3位を埋めるには（n-2）の方法があります。これで、r番目の場所を埋める方法の数を[n –（r–1）] = n–r +1として一般化できます。
だから、合計はありません。1位からr位まで埋める方法の例−
$ n_ {P_ {r}} = n（n-1）（n-2）.....（nr + 1）$
$ = [n（n-1）（n-2）...（nr + 1）] [（nr）（nr-1）\ dots 3.2.1] / [（nr）（nr-1）\ dots 3.2.1] $
したがって、
$ n_ {P_ {r}} = n！/（nr）！$
順列のいくつかの重要な式
$ 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！$
x個の特定のものが常に一定の場所を占める場合に一度にr個の要素をとるn個の異なる要素の順列の数= $ n-x_ {p_ {rx}} $
r個の指定されたものが常に一緒になるときのn個の異なる要素の順列の数は-$ r！（n−r + 1）！$
r個の指定されたものが決して一緒にならないときのn個の異なる要素の順列の数は-$ n！– [r！（n−r + 1）！] $
時間にx個の要素を取得したn個の異なる要素の循環順列の数= $ ^ np_ {x} / x $
The number of circular permutations of n different things = $^np_{n}/n$
Some Problems
Problem 1 − From a bunch of 6 different cards, how many ways we can permute it?
Solution − As we are taking 6 cards at a time from a deck of 6 cards, the permutation will be $^6P_{6} = 6! = 720$
Problem 2 − In how many ways can the letters of the word 'READER' be arranged?
Solution − There are 6 letters word (2 E, 1 A, 1D and 2R.) in the word 'READER'.
The permutation will be $= 6! /\: [(2!) (1!)(1!)(2!)] = 180.$
Problem 3 − In how ways can the letters of the word 'ORANGE' be arranged so that the consonants occupy only the even positions?
Solution − There are 3 vowels and 3 consonants in the word 'ORANGE'. Number of ways of arranging the consonants among themselves $= ^3P_{3} = 3! = 6$. The remaining 3 vacant places will be filled up by 3 vowels in $^3P_{3} = 3! = 6$ ways. Hence, the total number of permutation is $6 \times 6 = 36$
Combinations
A combination is selection of some given elements in which order does not matter.
The number of all combinations of n things, taken r at a time is −
$$^nC_{ { r } } = \frac { n! } { r!(n-r)! }$$
Problem 1
Find the number of subsets of the set $\lbrace1, 2, 3, 4, 5, 6\rbrace$ having 3 elements.
Solution
The cardinality of the set is 6 and we have to choose 3 elements from the set. Here, the ordering does not matter. Hence, the number of subsets will be $^6C_{3} = 20$.
Problem 2
There are 6 men and 5 women in a room. In how many ways we can choose 3 men and 2 women from the room?
Solution
The number of ways to choose 3 men from 6 men is $^6C_{3}$ and the number of ways to choose 2 women from 5 women is $^5C_{2}$
Hence, the total number of ways is − $^6C_{3} \times ^5C_{2} = 20 \times 10 = 200$
Problem 3
How many ways can you choose 3 distinct groups of 3 students from total 9 students?
Solution
Let us number the groups as 1, 2 and 3
For choosing 3 students for 1st group, the number of ways − $^9C_{3}$
The number of ways for choosing 3 students for 2nd group after choosing 1st group − $^6C_{3}$
The number of ways for choosing 3 students for 3rd group after choosing 1st and 2nd group − $^3C_{3}$
Hence, the total number of ways $= ^9C_{3} \times ^6C_{3} \times ^3C_{3} = 84 \times 20 \times 1 = 1680$
Pascal's Identity
Pascal's identity, first derived by Blaise Pascal in 17th century, states that the number of ways to choose k elements from n elements is equal to the summation of number of ways to choose (k-1) elements from (n-1) elements and the number of ways to choose elements from n-1 elements.
Mathematically, for any positive integers k and n: $^nC_{k} = ^n{^-}^1C_{k-1} + ^n{^-}^1{C_k}$
Proof −
$$^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 } }$
Pigeonhole Principle
In 1834, German mathematician, Peter Gustav Lejeune Dirichlet, stated a principle which he called the drawer principle. Now, it is known as the pigeonhole principle.
Pigeonhole Principle states that if there are fewer pigeon holes than total number of pigeons and each pigeon is put in a pigeon hole, then there must be at least one pigeon hole with more than one pigeon. If n pigeons are put into m pigeonholes where n > m, there's a hole with more than one pigeon.
Examples
Ten men are in a room and they are taking part in handshakes. If each person shakes hands at least once and no man shakes the same man’s hand more than once then two men took part in the same number of handshakes.
There must be at least two people in a class of 30 whose names start with the same alphabet.
The Inclusion-Exclusion principle
The Inclusion-exclusion principle computes the cardinal number of the union of multiple non-disjoint sets. For two sets A and B, the principle states −
$|A \cup B| = |A| + |B| - |A \cap B|$
For three sets A, B and C, the principle states −
$|A \cup B \cup C | = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C |$
The generalized formula -
$|\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|$
Problem 1
How many integers from 1 to 50 are multiples of 2 or 3 but not both?
Solution
From 1 to 100, there are $50/2 = 25$ numbers which are multiples of 2.
There are $50/3 = 16$ numbers which are multiples of 3.
There are $50/6 = 8$ numbers which are multiples of both 2 and 3.
So, $|A|=25$, $|B|=16$ and $|A \cap B|= 8$.
$|A \cup B| = |A| + |B| - |A \cap B| = 25 + 16 - 8 = 33$
Problem 2
In a group of 50 students 24 like cold drinks and 36 like hot drinks and each student likes at least one of the two drinks. How many like both coffee and tea?
Solution
Let X be the set of students who like cold drinks and Y be the set of people who like hot drinks.
So, $| X \cup Y | = 50$, $|X| = 24$, $|Y| = 36$
$|X \cap Y| = |X| + |Y| - |X \cup Y| = 24 + 36 - 50 = 60 - 50 = 10$
Hence, there are 10 students who like both tea and coffee.