TLDR;
This lecture focuses on advanced concepts in permutation and combination, including selecting one or more objects, dealing with identical items, and circular arrangements. It also covers problems related to chessboards, lines, triangles, diagonals of polygons, and distribution of items with restrictions.
- Combinations with selections and rejections
- Chessboard problems
- Circular arrangements and garland problems
Selecting One or More Objects [1:19]
When selecting one or more objects from n objects, the number of combinations is 2^n - 1. This is because for each object, there are two choices: to select it or not. The -1 accounts for the case where no object is selected, which is not acceptable when you have to select at least one object. If zero or more objects can be selected, then the number of combinations is 2^n.
Selecting from P Identical, Q Identical, and N Distinct Things [6:17]
When selecting one or more items from p identical items, q identical items, and n distinct items, the total number of ways is (p+1)(q+1)2^n - 1. The (p+1) and (q+1) represent the ways to choose from the identical items (including choosing none), and 2^n represents the ways to choose from the distinct items. The -1 excludes the case where nothing is selected.
Team Selection Problem [12:17]
To form a team of three boys and four girls from a pool of seven boys and nine girls, the number of ways to select the team is calculated using combinations. This involves selecting three boys out of seven and four girls out of nine, and then multiplying these two values together.
Selection and Rejection Constraints [14:03]
When selecting 11 players from 20, with two players always rejected, the problem reduces to selecting 11 players from the remaining 18 (18C11). If two players are always selected, then you need to choose only 9 players from the remaining 18 (18C9).
Equal Selection from Multiple Sections [16:57]
To select 30 students from three classes (six, eight, and ten) with equal representation from three sections A, B, and C, you must select 10 students from each section. The problem involves adding the different ways this can be achieved.
Ways to Fail an Exam [18:33]
If a student has to pass six papers to pass an exam, the number of ways a student can fail is calculated by considering all possible combinations of passing and failing each paper, except for the case where all papers are passed.
Chess Board Problems: Counting Squares [20:13]
On a chessboard, the number of squares can be found by summing the squares of natural numbers from 1 to 8 (1^2 + 2^2 + ... + 8^2). The formula for the sum of squares of the first n natural numbers is n(n+1)(2n+1)/6.
Chess Board Problems: Counting Rectangles [23:45]
The number of rectangles on a chessboard is determined by selecting two horizontal and two vertical lines from the grid. For an 8x8 chessboard, there are 9 horizontal and 9 vertical lines. The number of ways to choose two lines from nine is 9C2. Therefore, the total number of rectangles is (9C2) * (9C2).
Squares and Rectangles in a 10x10 Chessboard [25:08]
For a 10x10 chessboard, the number of squares is the sum of squares from 1 to 10, calculated as 385. The number of rectangles is (11C2) * (11C2) = 3025. To find the number of rectangles that are not squares, subtract the number of squares from the total number of rectangles.
Grid-Based Problems: Counting Rectangles in a M x N Grid [27:46]
In an m x n grid, the number of rectangles is (m+1C2) * (n+1C2). If n is greater than m, the number of squares is calculated by summing the product of (m-i) * (n-i) for i from 0 to m-1.
Minimum Distance Path Problem [33:10]
To find the number of ways to go from one end to the other in a grid with minimum distance, where there are 8 horizontal and 10 vertical paths, you need to take 18 steps in total. The number of ways to arrange these steps is given by 18! / (10! * 8!).
Drawing Lines Through Points on Parallel Lines [39:10]
Given eight points, with four on one line and four on another parallel line, the number of distinct lines that can be drawn is found by connecting each point on one line to each point on the other line (4*4 = 16 lines) and adding the two parallel lines themselves, resulting in 18 lines.
Counting Rectangles of a Specific Size [43:09]
To count rectangles of a specific size (e.g., 4x2) in a larger grid (e.g., 10x8), determine how many times the smaller rectangle can fit within the larger one.
Diagonals of a Polygon [48:15]
The number of diagonals in a polygon with n sides is given by n(n-3)/2. This is derived from the fact that each vertex can connect to n-3 other vertices (excluding itself and its two adjacent vertices), and the result is halved to avoid double counting.
Circular Arrangements [52:14]
The number of circular arrangements of n objects is (n-1)!. This is because in a circle, there is no fixed starting point, so one object's position is fixed as a reference, and the remaining objects are arranged relative to it.
Circular Arrangements with Restrictions [56:38]
When seating n children around a circular table such that two specific children (A and B) never sit together, calculate the total arrangements (n-1)! and subtract the arrangements where A and B are together. Treat A and B as a single unit, calculate the arrangements of the combined unit and the remaining children, and then account for A and B switching places within their unit.
Garland Problems [1:00:29]
The number of ways to make a garland with n distinct flowers is (n-1)! / 2. This is because a garland can be viewed from either side (clockwise or anticlockwise), so the arrangements are halved.
Seating Boys and Girls with Restrictions in a Circle [1:04:20]
To seat seven boys and eight girls around a table such that no two girls sit together, first seat the girls. The number of ways to arrange the girls in a circle is (8-1)! = 7!. Then, arrange the seven boys in the eight spaces between the girls.
Multinomial Theorem [1:14:51]
The multinomial theorem provides a way to expand expressions of the form (1 + x)^n. Specific expansions and coefficients can be derived using the theorem.
Selection with Multiple Restrictions [1:16:39]
When selecting r things out of n things, where p are of one kind, q are of another kind, and so on, the number of ways can be found by determining the coefficient of x^r in a specific polynomial.
Distribution of Identical Things Among People [1:21:44]
The number of ways to distribute n identical things among a people, where each person can get zero or more things, is (n + a - 1)C(a - 1). If each person must get at least one thing, the number of ways is (n - 1)C(a - 1).