ಎಣಿಕೆಯ ಮೂಲಗಳು (Basics of Counting), ಪರ್ಮ್ಯುಟೇಶನ್‌ಗಳು (Permutations) ಮತ್ತು ಪಿಜನ್‌ಹೋಲ್ ಪ್ರಿನ್ಸಿಪಲ್ (Pigeonhole Principle) | Basics of Counting, Permutations and the Pigeonhole Principle
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
- ಅಥವಾ ಎಂದರೆ ಕೂಡಿಸಿ, ಮತ್ತು ನಂತರ ಎಂದರೆ ಗುಣಿಸಿ. | Or means add; and then means multiply.
- ಕ್ರಮ ಮುಖ್ಯವಾದರೆ P(n, r), ಇಲ್ಲದಿದ್ದರೆ C(n, r). | If order matters use P(n, r), otherwise C(n, r).
- ವೃತ್ತಾಕಾರ ಜೋಡಣೆ (n − 1)!. | Circular arrangements: (n − 1)!.
- n ವೇರಿಯೇಬಲ್‌ಗಳ ಬೂಲಿಯನ್ ಫಂಕ್ಷನ್‌ಗಳು 2 ರ ಘಾತ (2 ರ ಘಾತ n). | There are 2 to the power (2 to the power n) Boolean functions of n variables.
- ಖಚಿತತೆಯ ಪ್ರಶ್ನೆಗಳಿಗೆ: ಕೆಟ್ಟ ಸಂದರ್ಭ + 1. | For guarantee questions: worst case plus one.
On this page
ಎರಡು ಮೂಲ ನಿಯಮಗಳು | The two basic rules
- ಸಮ್ ರೂಲ್ (Sum Rule): ಕೆಲಸವನ್ನು m ರೀತಿ ಅಥವಾ n ರೀತಿಯಲ್ಲಿ ಮಾಡಬಹುದು, ಎರಡೂ ಒಟ್ಟಿಗೆ ಅಲ್ಲ: m + n ರೀತಿಗಳು. ಪದ: ಅಥವಾ. | Sum rule: a task done in m ways or in n ways, never both: m + n ways. Key word: or.
- ಪ್ರಾಡಕ್ಟ್ ರೂಲ್ (Product Rule): ಮೊದಲ ಹಂತ m ರೀತಿ, ನಂತರ ಎರಡನೇ ಹಂತ n ರೀತಿ: m × n ರೀತಿಗಳು. ಪದ: ಮತ್ತು ನಂತರ. | Product rule: a first step in m ways and then a second in n ways: m × n ways. Key word: and then.
8 ಬಿಟ್‌ಗಳ ಸ್ಟ್ರಿಂಗ್‌ಗಳು: ಪ್ರತಿ ಸ್ಥಾನಕ್ಕೆ 2 ಆಯ್ಕೆ, 2 ರ ಘಾತ 8 = 256. | Bit strings of length 8: 2 choices per position, 2 to the power 8 = 256.
3 ಅಕ್ಷರಗಳು ನಂತರ 3 ಅಂಕೆಗಳ ವಾಹನ ಸಂಖ್ಯೆ: 26 ಘನ × 10 ಘನ = 17,576,000. | A plate of 3 letters then 3 digits: 26 cubed × 10 cubed = 17,576,000.
ಪರ್ಮ್ಯುಟೇಶನ್ (Permutation) ಮತ್ತು ಕಾಂಬಿನೇಶನ್ (Combination) | Permutations and combinations
| ಪರಿಕಲ್ಪನೆ | Idea | ಸೂತ್ರ | Formula | ಕ್ರಮ ಮುಖ್ಯವೇ | Order matters |
|---|---|---|
| n ವಸ್ತುಗಳಲ್ಲಿ r ಜೋಡಣೆ | Arrange r of n objects | P(n, r) = n! / (n − r)! | P(n, r) = n! / (n − r)! | ಹೌದು | Yes |
| n ವಸ್ತುಗಳಲ್ಲಿ r ಆಯ್ಕೆ | Choose r of n objects | C(n, r) = n! / [r! (n − r)!] | C(n, r) = n! / [r! (n − r)!] | ಇಲ್ಲ | No |
| ಪುನರಾವರ್ತಿತ ಅಕ್ಷರಗಳ ಜೋಡಣೆ | Arrangements with repeated letters | n! / (n1! n2! ...) | n! / (n1! n2! ...) | ಹೌದು | Yes |
| ವೃತ್ತಾಕಾರ ಜೋಡಣೆ | Circular arrangement | (n − 1)! | (n − 1)! | ಹೌದು, ತಿರುಗಿಸಿದ್ದು ಒಂದೇ | Yes, rotations are the same |
C(n, r) = C(n, n − r); P(n, r) = r! × C(n, r). | C(n, r) = C(n, n − r); P(n, r) = r! × C(n, r).
ಫಂಕ್ಷನ್‌ಗಳ ಎಣಿಕೆ | Counting functions
- m ಸದಸ್ಯರ ಸೆಟ್‌ನಿಂದ n ಸದಸ್ಯರ ಸೆಟ್‌ಗೆ ಎಲ್ಲಾ ಫಂಕ್ಷನ್‌ಗಳು: n ರ ಘಾತ m. | All functions from an m-set to an n-set: n to the power m.
- ಒನ್-ಟು-ಒನ್ (One-to-One) ಫಂಕ್ಷನ್‌ಗಳು (m ≤ n): P(n, m). | One-to-one functions (m ≤ n): P(n, m).
- n ವೇರಿಯೇಬಲ್‌ಗಳ ಬೂಲಿಯನ್ ಫಂಕ್ಷನ್‌ಗಳು: ಟ್ರೂತ್ ಟೇಬಲ್‌ನಲ್ಲಿ 2 ರ ಘಾತ n ಸಾಲುಗಳು, ಪ್ರತಿಯೊಂದಕ್ಕೆ 2 ಔಟ್‌ಪುಟ್: 2 ರ ಘಾತ (2 ರ ಘಾತ n). | Boolean functions of n variables: 2 to the power n rows, each with 2 outputs: 2 to the power (2 to the power n).
ಪಿಜನ್‌ಹೋಲ್ ಪ್ರಿನ್ಸಿಪಲ್ (Pigeonhole Principle) | The pigeonhole principle
n + 1 ವಸ್ತುಗಳನ್ನು n ಪೆಟ್ಟಿಗೆಗಳಲ್ಲಿ ಇಟ್ಟರೆ ಕನಿಷ್ಠ ಒಂದು ಪೆಟ್ಟಿಗೆಯಲ್ಲಿ ಎರಡು ಅಥವಾ ಹೆಚ್ಚು. ಸಾಮಾನ್ಯ ರೂಪ: N ವಸ್ತುಗಳು k ಪೆಟ್ಟಿಗೆಗಳಲ್ಲಿ ಇದ್ದರೆ ಯಾವುದಾದರೂ ಒಂದರಲ್ಲಿ ಕನಿಷ್ಠ ಸೀಲಿಂಗ್ (N / k). | If n + 1 objects go into n boxes, some box holds at least two. General form: N objects in k boxes put at least the ceiling of N / k in some box.
ಖಚಿತಪಡಿಸಲು ಬೇಕಾದ ಕನಿಷ್ಠ ಸಂಖ್ಯೆ ಕೇಳಿದಾಗ, ಕೆಟ್ಟ ಸಂದರ್ಭವನ್ನು ಮೊದಲು ನಿರ್ಮಿಸಿ ನಂತರ 1 ಸೇರಿಸಿ. ಮೂರು ಹಾರ್ಟ್ಸ್ (Hearts) ಖಚಿತಪಡಿಸಲು: ಮೊದಲು ಹಾರ್ಟ್ ಅಲ್ಲದ 39 ಕಾರ್ಡ್‌ಗಳು, ನಂತರ 3 ಹಾರ್ಟ್ಸ್: 42. | When asked for the minimum that guarantees something, build the worst case first and then add. To guarantee three hearts: all 39 non-hearts first, then 3 hearts: 42.
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