Discrete Structure · Unit 7
Combinatorics and Counting
Exam-focused notes for Combinatorics and Counting (Discrete Structure, BIT152): what the TU syllabus asks and how it has actually been tested, with 8 solved past questions from this unit.
What this unit covers
- Product rule
- Permutations
- Combinations
- Lexicographic ordering
- Pigeonhole principle
- Generalized pigeonhole principle
- Inclusion and exclusion principle
- Binomial coefficients
Generalized pigeonhole principle
State generalized Pigeonhole principle. How many ways can you draw four digits integers without repetition of the digit? [5]
- Digit set: $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ - total 10 digits - Required: four-digit integers, no repetition of digits - Implicit constraint: a genuine 4-digit integer must not begin with 0 Statement: If $N$ objects are placed into $k$ boxes, then there...
Full solved answer →What is generalized pigeonhole principle. If a class has 24 students, what is the maximum number of possible grading that must be done to ensure that there at least two students with the same grade. [5]
- Number of students in class: $24$ - Grading system: standard grades assumed as $\{A, B, C, D, F\}$, so number of grade categories $k = 5$ - Required: number of gradings needed to guarantee at least two students share the same grade Note: The number of dis...
Full solved answer →State generalized Pigeonhole principle. How many ways can we get the 3 digit integers without repeating the digit? [5]
- Digits available: $0,1,2,3,4,5,6,7,8,9$ (10 digits total) - Form: 3-digit integer, no digit repeated - Implicit constraint: leading digit (hundreds place) $\neq 0$ --- Statement: If $N$ objects are placed into $k$ boxes, then there is at least one box con...
Full solved answer →Pigeonhole principle
What is the pigeonhole principle? Show that binomn+1k=binomnk−1+binomnk\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}binomn+1k=binomnk−1+binomnk where nnn and kkk are positive integers with n≥kn \geq kn≥k . [5]
--- Definition: If n + 1 or more objects (pigeons) are placed into n containers (pigeonholes), then at least one container must contain two or more objects. Formal Statement: If a function $f: A \to B$ where $A B$, then $f$ is not injective (not one-to-one)...
Full solved answer →Permutations
What is permutation? What is the next permutation in lexicographic order after 362541? [5]
- Current permutation: 362541 (digits: 3, 6, 2, 5, 4, 1) - Task: find the next permutation in lexicographic (dictionary) order. --- A permutation of a set of elements is an arrangement of those elements in a definite order. For a set of $n$ distinct element...
Full solved answer →Differentiate permutation with combination. What is the next permutation in lexicographic order after 362541? [5]
Basis Permutation Combination --------------------------------- Definition Arrangement of objects where order matters Selection of objects where order does not matter Formula $P(n, r) = \dfrac{n!}{(n - r)!}$ $C(n, r) = \dfrac{n!}{r!\,(n - r)!}$ Example $AB$...
Full solved answer →Inclusion and exclusion principle
Why do we need principle of inclusion and exclusion? How many ways can we express the four character words ending with a digit and beginning three are lowercase alphabets. Be sure that none of the character can be repeated. Using induction, show that $3^n - 1$ is multiple of 2 for $n \geq 1$. [5+5]
- Word length: 4 characters - Positions 1, 2, 3: lowercase alphabets (26 available) - Position 4: a digit (10 available: 0-9) - Constraint: no character repeated - Induction claim: $3^n - 1$ is a multiple of 2 for $n \geq 1$ --- When we count elements in a ...
Full solved answer →Product rule
Explain product rule. How many strings are there of four lowercase letters that have the letter x in them? [5]
- String length: 4 characters - Alphabet: 26 lowercase letters - Condition: the letter 'x' must appear at least once The Product Rule (Multiplication Principle) states: If a procedure consists of a sequence of $k$ tasks, where task 1 can be done in $n1$ way...
Full solved answer →Make Unit 7 stick
Practice BIT152 with flashcards & quizzes