이산 수학-계산 이론

일상 생활에서 일련의 이벤트에 대해 가능한 모든 결과의 수를 알아 내야하는 경우가 많습니다. 예를 들어, 남성 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 $ 방식으로 수행 될 수있는 경우 (조건은 동시에 수행 할 수없는 작업 임), 다음 방법의 수 이 작업 중 하나는 $ w_1 + w_2 + \ dots + w_m $입니다. 분리 된 두 작업 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까지 갈 수 있습니다. 거기에서 그는 4 개의 버스 노선 또는 5 개의 기차 노선을 선택하여 Z에 도달 할 수 있습니다. X에서 Z까지가는 방법은 몇 개입니까?

Solution− X에서 Y까지, 그는 $ 3 + 2 = 5 $ 방식으로 갈 수 있습니다 (Rule of Sum). 그 후, 그는 $ 4 + 5 = 9 $ 방법 (Rule of Sum)으로 Y에서 Z까지 갈 수 있습니다. 따라서 X에서 Z까지 그는 $ 5 \ x 9 = 45 $ 방식으로 갈 수 있습니다 (Rule of Product).

순열

ㅏ permutation순서가 중요한 일부 요소의 배열입니다. 즉, 순열은 정렬 된 요소 조합입니다.

예

한 번에 두 개를 취하여 S = {x, y, z} 집합에서 모든 순열은 다음과 같습니다.

$ xy, yx, xz, zx, yz, zy $.
숫자 $ S = \ lbrace 1, 2, 3 \ rbrace $에서 세 자리 숫자의 순열을 형성해야합니다. 숫자를 정렬 할 때 다른 세 자리 숫자가 형성됩니다. 순열은 = 123, 132, 213, 231, 312, 321입니다.

순열 수

한 번에 'r'을 취한 'n'개의 서로 다른 항목의 순열 수는 $ n_ {P_ {r}} $로 표시됩니다.

$$ n_ {P_ {r}} = \ frac {n!} {(n-r)!} $$

$ n! = 1.2.3. \ 도트 (n-1) .n $

Proof − 'n'다른 요소가 있도록합니다.

첫 번째 자리를 채우는 방법은 n 가지가 있습니다. 첫 번째 장소 (n-1)를 채운 후 요소 수가 남습니다. 따라서 2 위를 채우는 방법은 (n-1) 가지가 있습니다. 첫 번째와 두 번째 장소를 채운 후 (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 $는 세 번째 종류와 비슷하고 $ 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 $
n 개의 서로 다른 것의 순환 순열 수 = $ ^ np_ {n} / n $

몇몇 문제들

Problem 1 − 6 개의 다른 카드 묶음에서 얼마나 많은 방법으로 그것을 바꿀 수 있습니까?

Solution− 6 장의 카드 한 벌에서 한 번에 6 장의 카드를 가져 오므로 순열은 $ ^ 6P_ {6} = 6입니다! = 720 달러

Problem 2 − 'READER'라는 단어의 글자는 몇 가지 방법으로 배열 할 수 있습니까?

Solution − 'READER'라는 단어에는 6 개의 글자 (2 E, 1 A, 1D 및 2R.)가 있습니다.

순열은 $ = 6입니다! / \ : [(2!) (1!) (1!) (2!)] = 180. $

Problem 3 -자음이 짝수 위치 만 차지하도록 'ORANGE'라는 단어의 글자를 어떻게 배열 할 수 있습니까?

Solution− 'ORANGE'라는 단어에는 모음 3 개와 자음 3 개가 있습니다. 자음을 배열하는 방법의 수 $ = ^ 3P_ {3} = 3! = 6 $. 나머지 3 개의 빈 자리는 $ ^ 3P_ {3} = 3의 모음 3 개로 채워집니다! = 6 $ 방법. 따라서 총 순열 수는 $ 6 \ times 6 = 36 $입니다.

조합

ㅏ combination 순서가 중요하지 않은 일부 요소를 선택하는 것입니다.

n 개의 모든 조합의 수는 한 번에 r을 취합니다.

$$ ^ nC_ {{r}} = \ frac {n! } {r! (nr)! } $$

Problem 1

요소가 3 개인 $ \ lbrace1, 2, 3, 4, 5, 6 \ rbrace $ 집합의 하위 집합 수를 찾습니다.

Solution

집합의 카디널리티는 6이고 집합에서 3 개의 요소를 선택해야합니다. 여기서 순서는 중요하지 않습니다. 따라서 하위 집합의 수는 $ ^ 6C_ {3} = 20 $가됩니다.

Problem 2

한 방에 6 명의 남자와 5 명의 여자가 있습니다. 방에서 남자 3 명과 여자 2 명을 몇 가지 방법으로 선택할 수 있습니까?

Solution

남성 6 명 중에서 남성 3 명을 선택하는 방법은 $ ^ 6C_ {3} $이고 여성 5 명 중에서 여성 2 명을 선택하는 방법은 $ ^ 5C_ {2} $입니다.

따라서 총 길 수는 − $ ^ 6C_ {3} \ times ^ 5C_ {2} = 20 \ times 10 = 200 $입니다.

Problem 3

총 9 명의 학생 중에서 3 명의 학생으로 구성된 3 개의 개별 그룹을 몇 가지 방법으로 선택할 수 있습니까?

Solution

그룹 번호를 1, 2, 3으로 지정하겠습니다.

^{첫 번째} 그룹에 3 명의 학생을 선택 하는 경우 방법 수 − $ ^ 9C_ {3} $

첫 ^번째 그룹 선택 후 두 ^번째 그룹에 3 명의 학생을 선택하는 방법 수 − $ ^ 6C_ {3} $

3 3 명 학생들이 선택하는 방법의 수 ^번째의 1 선택한 후 그룹을 ^일 및 2 ^차 $ ^ 3C_ {3} $ - 그룹을

따라서 총 방법 수 $ = ^ 9C_ {3} \ times ^ 6C_ {3} \ times ^ 3C_ {3} = 84 \ times 20 \ times 1 = 1680 $

파스칼의 정체성

제 17 파스칼 의해 도출 파스칼의 ID, ^제 세기, n 개의 원소 중에서 k 개의 요소를 선택하는 방법의 수 (N-1) 엘리먼트의 (K-1)의 요소를 선택하는 방법의 수의 합과 동일하다한다고 n-1 요소에서 요소를 선택하는 방법의 수.

수학적으로 모든 양의 정수 k 및 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)! (nk)! } + \ frac {(n-1)! } {k! (nk-1)! } $

$ = (n-1)! (\ frac {k} {k! (nk)!} + \ frac {nk} {k! (nk)!}) $

$ = (n-1)! \ frac {n} {k! (nk)! } $

$ = \ frac {n! } {k! (nk)! } $

$ = n_ {C_ {k}} $

Pigeonhole 원리

1834 년 독일의 수학자 Peter Gustav Lejeune Dirichlet은 서랍 원리라고 부르는 원리를 발표했습니다. 자, 그것은 pigeonhole 원리로 알려져 있습니다.

Pigeonhole Principle총 비둘기 수보다 비둘기 구멍이 적고 각 비둘기를 비둘기 구멍에 넣는 경우 비둘기 구멍이 하나 이상 있어야하며 비둘기 구멍이 하나 이상 있어야합니다. n> m 인 m 개의 비둘기 구멍에 n 개의 비둘기를 넣으면 둘 이상의 비둘기가있는 구멍이 있습니다.

예

10 명의 남자가 한 방에 있고 그들은 악수를하고있다. 각 사람이 한 번 이상 악수하고 한 사람의 손을 한 번 이상 흔드는 사람이 없으면 두 사람이 같은 수의 악수에 참여한 것입니다.
이름이 같은 알파벳으로 시작하는 30 인 클래스에는 최소 두 사람이 있어야합니다.

포함-제외 원칙

그만큼 Inclusion-exclusion principle여러 비 연속 집합의 합집합의 기본 수를 계산합니다. 두 세트 A와 B의 경우 원칙 상태-

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

세 세트 A, B 및 C의 경우 원칙 상태-

$ | A \ 컵 B \ 컵 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 | $

Problem 1

1에서 50까지의 정수는 2 또는 3의 배수이지만 둘다는 아닙니다.

Solution

1부터 100까지 2의 배수 인 $ 50 / 2 = 25 $ 숫자가 있습니다.

3의 배수 인 $ 50 / 3 = 16 $ 숫자가 있습니다.

2와 3의 배수 인 $ 50 / 6 = 8 $ 숫자가 있습니다.

따라서 $ | A | = 25 $, $ | B | = 16 $ 및 $ | A \ cap B | = 8 $.

$ | A \ 컵 B | = | A | + | B | -| A \ cap B | = 25 + 16-8 = 33 달러

Problem 2

50 명의 학생 그룹에서 24 명은 차가운 음료를 좋아하고 36 명은 뜨거운 음료를 좋아하며 각 학생은 두 가지 음료 중 적어도 하나를 좋아합니다. 얼마나 많은 사람들이 커피와 차를 좋아합니까?

Solution

X는 차가운 음료를 좋아하는 학생들의 집합이고 Y는 뜨거운 음료를 좋아하는 학생들의 집합이라고합시다.