ಇನ್‌ಕ್ಲೂಷನ್-ಎಕ್ಸ್‌ಕ್ಲೂಷನ್ (Inclusion-Exclusion), ಪುನರಾವರ್ತಿತ ಆಯ್ಕೆ ಮತ್ತು ಮ್ಯಾಥಮ್ಯಾಟಿಕಲ್ ಇಂಡಕ್ಷನ್ (Mathematical Induction) | Inclusion-Exclusion, Combinations with Repetition and Mathematical Induction
In the syllabus of UGC NET CS
Saved in this browser only. Sign in to keep your ticks on every device. See all revisions due
Key points
- ಎರಡು ಸೆಟ್: ಕೂಡಿಸಿ, ಸಾಮಾನ್ಯ ಭಾಗ ಕಳೆಯಿರಿ; ಮೂರು ಸೆಟ್: ಮೂರರ ಸಾಮಾನ್ಯ ಭಾಗ ಮತ್ತೆ ಕೂಡಿಸಿ. | Two sets: add, subtract the overlap; three sets: add back the triple overlap.
- n ಒಂದೇ ವಸ್ತುಗಳು k ಪೆಟ್ಟಿಗೆಗಳಿಗೆ: C(n + k − 1, k − 1). | n identical objects into k boxes: C(n + k − 1, k − 1).
- D4 = 9, D5 = 44. | D4 = 9, D5 = 44.
- m ಇಂದ 2 ಕ್ಕೆ ಆನ್ಟು ಫಂಕ್ಷನ್‌ಗಳು: 2 ರ ಘಾತ m ಕಳೆ 2. | Onto functions from an m-set to a 2-set: 2 to the power m minus 2.
- ಇಂಡಕ್ಷನ್‌ಗೆ ಬೇಸ್ ಕೇಸ್ ಮತ್ತು ಇಂಡಕ್ಟಿವ್ ಸ್ಟೆಪ್ ಎರಡೂ ಬೇಕು. | Induction needs both a base case and an inductive step.
On this page
- ಇನ್‌ಕ್ಲೂಷನ್-ಎಕ್ಸ್‌ಕ್ಲೂಷನ್ (Inclusion-Exclusion) | Inclusion-exclusion
- ಪುನರಾವರ್ತನೆಯೊಂದಿಗೆ ಆಯ್ಕೆ: ಸ್ಟಾರ್ಸ್ ಆಂಡ್ ಬಾರ್ಸ್ (Stars and Bars) | Combinations with repetition: stars and bars
- ಡಿರೇಂಜ್‌ಮೆಂಟ್ (Derangement) ಮತ್ತು ಆನ್ಟು (Onto) ಫಂಕ್ಷನ್‌ಗಳು | Derangements and onto functions
- ಬೈನಾಮಿಯಲ್ ಪ್ರಮೇಯ (Binomial Theorem) | The binomial theorem
- ಮ್ಯಾಥಮ್ಯಾಟಿಕಲ್ ಇಂಡಕ್ಷನ್ (Mathematical Induction) | Mathematical induction
ಇನ್‌ಕ್ಲೂಷನ್-ಎಕ್ಸ್‌ಕ್ಲೂಷನ್ (Inclusion-Exclusion) | Inclusion-exclusion
n(A ∪ B) = n(A) + n(B) − n(A ∩ B) | n(A ∪ B) = n(A) + n(B) − n(A ∩ B)
n(A ∪ B ∪ C) = n(A) + n(B) + n(C) − n(A ∩ B) − n(A ∩ C) − n(B ∩ C) + n(A ∩ B ∩ C) | n(A ∪ B ∪ C) = n(A) + n(B) + n(C) − n(A ∩ B) − n(A ∩ C) − n(B ∩ C) + n(A ∩ B ∩ C)
1 ರಿಂದ 100 ರವರೆಗೆ 2 ಅಥವಾ 3 ರಿಂದ ಭಾಗವಾಗುವ ಸಂಖ್ಯೆಗಳು: 50 + 33 − 16 = 67 (16 ಎಂಬುದು 6 ರಿಂದ ಭಾಗವಾಗುವವು). | Numbers from 1 to 100 divisible by 2 or 3: 50 + 33 − 16 = 67, where 16 are divisible by 6.
10 ಬಿಟ್ ಸ್ಟ್ರಿಂಗ್‌ಗಳು 1 ರಿಂದ ಆರಂಭ ಅಥವಾ 00 ರಲ್ಲಿ ಅಂತ್ಯ: 2 ರ ಘಾತ 9 + 2 ರ ಘಾತ 8 − 2 ರ ಘಾತ 7 = 512 + 256 − 128 = 640. | Bit strings of length 10 starting with 1 or ending with 00: 2 to the 9 + 2 to the 8 − 2 to the 7 = 512 + 256 − 128 = 640.
ಪುನರಾವರ್ತನೆಯೊಂದಿಗೆ ಆಯ್ಕೆ: ಸ್ಟಾರ್ಸ್ ಆಂಡ್ ಬಾರ್ಸ್ (Stars and Bars) | Combinations with repetition: stars and bars
- n ಒಂದೇ ತರಹದ ವಸ್ತುಗಳನ್ನು k ಬೇರೆ ಪೆಟ್ಟಿಗೆಗಳಿಗೆ (ಖಾಲಿ ಅನುಮತಿ): C(n + k − 1, k − 1). | n identical objects into k distinct boxes, empty allowed: C(n + k − 1, k − 1).
- x1 + x2 + ... + xk = n ನ ಋಣವಲ್ಲದ ಪೂರ್ಣಾಂಕ ಪರಿಹಾರಗಳು: ಅದೇ C(n + k − 1, k − 1). | Non-negative integer solutions of x1 + x2 + ... + xk = n: the same C(n + k − 1, k − 1).
- ಪ್ರತಿ ಪೆಟ್ಟಿಗೆಯಲ್ಲಿ ಕನಿಷ್ಠ ಒಂದು (ಧನ ಪರಿಹಾರಗಳು): C(n − 1, k − 1). | At least one per box (positive solutions): C(n − 1, k − 1).
ಡಿರೇಂಜ್‌ಮೆಂಟ್ (Derangement) ಮತ್ತು ಆನ್ಟು (Onto) ಫಂಕ್ಷನ್‌ಗಳು | Derangements and onto functions
- ಡಿರೇಂಜ್‌ಮೆಂಟ್: ಯಾವ ವಸ್ತುವೂ ತನ್ನ ಸ್ಥಾನದಲ್ಲಿಲ್ಲ. D1 = 0, D2 = 1, D3 = 2, D4 = 9, D5 = 44. ಸೂತ್ರ: Dn = n! [1 − 1/1! + 1/2! − ... ± 1/n!]. | Derangement: no object in its own place. D1 = 0, D2 = 1, D3 = 2, D4 = 9, D5 = 44. Formula: Dn = n! [1 − 1/1! + 1/2! − ... ± 1/n!].
- m ಸದಸ್ಯರಿಂದ n ಸದಸ್ಯರಿಗೆ ಆನ್ಟು ಫಂಕ್ಷನ್‌ಗಳು: n ರ ಘಾತ m − C(n, 1)(n − 1) ರ ಘಾತ m + C(n, 2)(n − 2) ರ ಘಾತ m − ... | Onto functions from an m-set to an n-set: n to the m − C(n, 1)(n − 1) to the m + C(n, 2)(n − 2) to the m − ...
ಬೈನಾಮಿಯಲ್ ಪ್ರಮೇಯ (Binomial Theorem) | The binomial theorem
(x + y) ರ ಘಾತ n ನಲ್ಲಿ x ರ ಘಾತ (n − k) y ರ ಘಾತ k ಪದದ ಗುಣಾಂಕ C(n, k). x = y = 1 ಇಟ್ಟರೆ ಎಲ್ಲಾ C(n, k) ಗಳ ಮೊತ್ತ 2 ರ ಘಾತ n. | In (x + y) to the power n the coefficient of x to the (n − k) times y to the k is C(n, k). Setting x = y = 1 shows the C(n, k) sum to 2 to the power n.
ಮ್ಯಾಥಮ್ಯಾಟಿಕಲ್ ಇಂಡಕ್ಷನ್ (Mathematical Induction) | Mathematical induction
- ಬೇಸ್ ಕೇಸ್ (Base Case): P(n0) ಸತ್ಯ ಎಂದು ತೋರಿಸಿ. | Base case: show P(n0) is true.
- ಇಂಡಕ್ಟಿವ್ ಸ್ಟೆಪ್ (Inductive Step): P(k) ಸತ್ಯ ಎಂದು ಊಹಿಸಿ (ಇಂಡಕ್ಟಿವ್ ಹೈಪೋಥಿಸಿಸ್), P(k + 1) ಸಾಬೀತುಪಡಿಸಿ. | Inductive step: assume P(k) (the inductive hypothesis) and prove P(k + 1).
- ಸ್ಟ್ರಾಂಗ್ ಇಂಡಕ್ಷನ್ (Strong Induction): P(n0), ..., P(k) ಎಲ್ಲವನ್ನೂ ಊಹಿಸಿ P(k + 1) ಸಾಬೀತುಪಡಿಸಿ. | Strong induction: assume all of P(n0), ..., P(k) and prove P(k + 1).
ಬೇಸ್ ಕೇಸ್ ಸರಿಯಾದ ಆರಂಭಿಕ ಮೌಲ್ಯದಲ್ಲಿರಬೇಕು. 2 ರ ಘಾತ n > n ವರ್ಗ ಎಂಬುದು n = 5 ರಿಂದ ಮಾತ್ರ ಸತ್ಯ (n = 4 ರಲ್ಲಿ 16 = 16). | The base case must sit at the right starting value. 2 to the power n > n squared holds only from n = 5 (at n = 4, 16 = 16).
Practice questions
Answer all, then check. Explanations appear after checking.
Finished this topic? Tick it off.
Saved in this browser only. Sign in to keep your ticks on every device. See all revisions due