Permutations and Combinations Comprehensive Study Notes

Fundamental Principles of Permutations and Combinations

In the study of combinatorics, a permutation refers to an arrangement where the specific order of items is important. Conversely, a combination refers to a selection where order is not important. Two fundamental rules govern the calculation of these arrangements and selections based on logic. The first rule states that if the logical connective "And" ($\cap$) is used between events, the operations must be multiplied ($\times$). The second rule states that if the logical connective "Or" ($\cup$) is used, the operations must be added ($+$).

Pathway Problems and Travel Scenarios

A specific case study involves a man traveling from Lucknow to Kanpur. If there are 3 distinct paths available from Lucknow to Kanpur, the total number of paths for a one-way trip is simply $3$. If the man goes to Kanpur and returns back to Lucknow (a round trip), the logic applied is Lucknow to Kanpur "And" Kanpur to Lucknow. This results in $3 \times 3 = 9$ total possible routes. However, if the man travels to Kanpur and returns back but does not follow the same path used initially, the calculation changes to Lucknow to Kanpur ($3$ routes available) and Kanpur to Lucknow ($2$ routes remaining), resulting in $3 \times 2 = 6$ routes.

In a more complex scenario involving a trip from Lucknow to Agra via Kanpur, we assume there are $3$ routes from Lucknow to Kanpur and $5$ routes from Kanpur to Agra. To determine the number of ways to go from Lucknow to Agra, we multiply the paths: $3 \times 5 = 15$ routes. For a complete round trip (Lucknow to Agra and back to Lucknow via Kanpur) using any path, the calculation is $3 \times 5 \times 5 \times 3 = 225$ routes. If the constraint is added that the man does not follow the same path again for any segment of the return trip, the number of ways is calculated as $3 \times 5 \times 4 ​\times 2 = 120$ routes. This is because after using one route from Lucknow to Kanpur, only $2$ remain for the return, and after using one route from Kanpur to Agra, only $4$ remain for the return.

Movie Theatre and Lock Combination Scenarios

Consider a movie theatre with $10$ doors. A "movie experience" is defined as entering the theatre and exiting the theatre. If a man can enter and come out through any door, there are $10 \times 10 = 100$ ways to watch the movie. If he is not allowed to exit through the same door he entered, the ways are reduced to $10 \times 9 = 90$. In a separate case where $10$ doors exist but $4$ of those doors are actually walls (labeled as no exit), leaving only $6$ functional exit doors, the number of ways to watch the movie is $10 \times 6 = 60$.

Regarding digital security, consider a lock requiring a $4$-digit code where each digit can be any value from $0$ to $9$. Since there are $10$ possible digits for each of the four blocks, the total number of possible patterns is $10 \times 10 \times 10 \times 10 = 10^{4} = 10,000$. Because only one of these patterns is the correct code to open the lock, the maximum number of unsuccessful attempts a person could make before finding the correct one is $10,000 - 1 = 9,999$.

Number Formation with Digits 1-9 and 0-9

When forming numbers, the availability of digits and the rules regarding repetition significantly alter the results. If digits available are $1$ through $9$ ($9$ total digits) and we wish to form a $4$-digit number where repetition is allowed, each block has $9$ possibilities, resulting in $9 \times 9 \times 9 \times 9 = 6,561$. If repetition is not allowed, the possibilities decrease for each subsequent block: $9 \times 8 \times 7 \times 6 = 3,024$.

When the digit $0$ is included (making $10$ available digits), we must respect the rule that a $4$-digit number cannot start with $0$. If repetition is allowed, the first block has $9$ possibilities ($1-9$), while the subsequent three blocks each have $10$ possibilities ($0-9$), resulting in $9 \times 10 \times 10 \times 10 = 9,000$. If repetition is not allowed, the first block has $9$ possibilities ($1-9$). The second block also has $9$ possibilities because $0$ is now available but the digit used in the first block is not. Subsequent blocks have $8$ and $7$ possibilities, respectively, leading to $9 \times 9 \times 8 \times 7 = 4,536$.

Odd and Even Number Constraints

For problems involving odd numbers, it is essential to start filling the unit place first. To be odd, the unit place must contain one of the following: $1, 3, 5, 7,$ or $9$. If digits $1-9$ are available for a $4$-digit odd number with repetition allowed, the unit place has $5$ choices and the other three places have $9$ choices each: $9 \times 9 \times 9 \times 5 = 3,645$. If repetition is not allowed, the unit place has $5$ choices, the first block has $8$ remaining choices, the second has $7$, and the third has $6$, leading to $8 \times 7 \times 6 \times 5 = 1,680$.

With digits $0-9$, a $4$-digit odd number with repetition allowed gives the unit place $5$ choices, the first digit $9$ choices (excluding $0$), and middle digits $10$ choices each: $9 \times 10 \times 10 \times 5 = 4,500$. If repetition is not allowed for odd numbers using $0-9$, we fill the unit place first ($5$ choices). The first digit then has $8$ choices (it cannot be $0$ and it cannot be the odd digit used at the end). The second and third slots have $8$ and $7$ remaining choices respectively: $8 \times 8 \times 7 \times 5 = 2,240$.

For even numbers using digits $0-9$ where repetition is not allowed, the logic must be split into two cases because the digit $0$ affects the restriction on the first block. Case 1 involves numbers ending in $0$: the unit place has $1$ choice ($0$), and the remaining three blocks have $9$, $8$, and $7$ choices ($9 \times 8 \times 7 \times 1 = 504$). Case 2 involves numbers ending in other even digits ($2, 4, 6, 8$): the unit place has $4$ choices, the first block has $8$ choices (cannot be $0$ or the unit digit), and subsequent blocks have $8$ and $7$ choices ($8 \times 8 \times 7 \times 4 = 1,792$). The total is the sum of both cases: $504 + 1,792 = 2,296$.

Divisibility Rules in Combinatorics

Divisibility by $5$ requires the unit digit to be either $0$ or $5$. Using digits $0-9$ without repetition, we again split the logic. If the number ends in $0$, there are $9 \times 8 \times 7 \times 1 = 504$ ways. If the number ends in $5$, the first digit has $8$ choices (excluding $0$ and $5$), resulting in $8 \times 8 \times 7 \times 1 = 448$ ways. The total for a $4$-digit number divisible by $5$ is $504 + 448 = 952$.

Divisibility by $4$ requires that the last two digits of the number be divisible by $4$. For a $5$-digit number using digits $1, 2, 3, 4, 5$ without repetition, the valid pairs for the last two digits are $\{12, 24, 32, 52\}$. For each pair, there are $3!$ ways to arrange the remaining three digits. Total ways: $3 \times 2 \times 1 \times 4 = 24$. When digits $0, 1, 2, 3, 4, 5$ are used, possible pairs are $\{04, 12, 20, 24, 32, 40, 52\}$. We split this into pairs containing $0$ ($\{04, 20, 40\}$) and pairs without $0$ ($\{12, 24, 32, 52\}$). For pairs with $0$, the remaining slots are $4 \times 3 \times 2 \times 3 = 72$. For pairs without $0$, the first digit cannot be $0$, giving $3 \times 3 \times 2 \times 4 = 72$. Total ways: $72 + 72 = 144$.

Inequality and Magnitude Constraints

To find integers greater than $5,000$ using digits $\{3, 4, 5, 6, 7\}$ without repetition, we consider both $4$-digit and $5$-digit numbers. For $4$-digit numbers, the first digit must be $5, 6,$ or $7$ ($3$ choices), while the remaining digits have $4, 3,$ and $2$ choices: $3 \times 4 \times 3 \times 2 = 72$. Every $5$-digit number formed with these digits is inherently greater than $5,000$, totaling $5 \times 4 \times 3 \times 2 ​\times 1 = 120$. The combined total is $72 + 120 = 192$.

If the constraint is numbers greater than $5,600$ using the same digits, we analyze $4$-digit numbers starting with $5$ and those starting with $6$ or $7$. For those starting with $5$, the second digit must be $6$ or $7$ ($2$ choices), totaling $1 \times 2 \times 3 \times 2 = 12$. For those starting with $6$ or $7$ ($2$ choices), there are $2 \times 4 \times 3 \times 2 = 48$ ways. Adding the $120$ possible $5$-digit numbers, the grand total is $12 + 48 + 120 = 180$.