PERMUTATIONS AND COMBINATIONS

What is combinatorics?

Combinatorics is the mathematics of counting and arranging

What are permutations and combinations?

Methods of counting the number of ways in which a certain task can be completed

How are permutations and combinations different?

• Combination: Order in which a task is completed doesn’t matter

• Permutation: Order in which a task is completed does matter

What are the methods of calculating combination questions?

• Combination formula: ⁿC_k = n!/(n-k)! * k!

• Box and fill method:

  • Let each box represent a specific choice that must be made

  • Multiply the numbers in each box and divide by the factorial of the number of boxes

  • For eg: If box 1 has 7 available options, box 2 has 6 available options, and box 3 has 5 available options. The box and fill formula comes out to be (7 × 6 × 5)/3!

What are handshake questions? What is the formula for solving such questions?

Handshake questions ask us to determine the number of ways to connect any 2 members of the group while meeting any restrictions that exist.

For eg:

• How many handshakes if each person shakes hands with 4 people?

• Diagonal connects 2 non adjacent vertices. How many different diagonals can be drawn in an 8 sided octagon

Formula for solving such questions:

Total number of entities: nk/2 (Can be used in situations in which each entity is not connected to all other entities)

• n = Total number of entities

• k = Each entity is connected to k other entities

What is the property of equivalent combinations?

We can use property of equivalent combinations when dealing with large combinations

• ⁿC_k = ⁿC_n-k

• If NCx = NCy, then n = x + y

What is the fundamental counting principle?

If there are m ways to perform task A and n ways to perform task B and both these tasks are independent, then there are m * n ways of performing these tasks together

What are mutually exclusive events?

Events are mutually exclusive if they cannot occur together. If there are x ways to accomplish A and y ways to accomplish B and if A and B are mutually exclusive, then there are x + y ways to accomplish A or B

What are collectively exhaustive events?

Two events are collectively exhaustive, if together, the events represent all of the potential outcomes of a situation

If the events are mutually exclusive and and collectively exhaustive, what is the formula for calculating the total number of ways in which a scenario can occur?

Total number of ways in which the scenario can occur = Number of ways in which A can occur + number of ways in which B can occur

*Comes in handy when x items are excluded from being together in the same subgroup of y items

What are the methods of calculating permutation questions?

• Permutation formula: ⁿP_k = n!/(n-k)!

• Box and fill method:

  • Let each box represent a specific choice that must be made

  • Multiply the numbers in each box. No need to divide by the factorial of the number of boxes in permutation problems

  • For eg: If box 1 has 7 available options, box 2 has 6 available options, and box 3 has 5 available options. The box and fill formula comes out to be (7 × 6 × 5)

How do we take care of the indistinguishable items in permutation problems?

• We have to be careful about indistinguishable items in permutation problems. If we fail to realise that there are identical items in a problem, we will likely overcome the true number of permutations.

• In permutation questions, we have to only count the number of distinguishable permutations

• Permutation formula when there are identical items: P = N!/(r1)! x (r2)! .. x (rn)!

What are path questions and how do you solve such questions?

Questions where we have to find the total number of paths one can take to travel from some starting point to some destination

• 2D paths involving 1 or more checkpoints

  • Identify each checkpoint (including starting point + destination)

  • Determine the number of ways to travel between each pair of successive checkpoints

  • Calculate the product of all results from step 2

• 2D paths involving no checkpoints

  • If points A and B are on a 2D rectangular block which involves traveling j blocks in 1 directions and k blocks in another direction

  • Total paths = (j+k)!/j! *k!

• 3D paths

  • Total paths = (j+k+m)!/j! *k! *m!

What is the circular permutation formula?

K items can be arranged in (k-1)! ways

How to use anchor method to solve arrangement questions?

• Anchor the restricted items into their specific spots in the arrangement

• Handle the additional items that need to be arranged

How do you solve questions where x items in an arrangement of y items must be together?

• When x items must be together in an arrangement of y items, treat the x items together as 1 unit. There are now y - x + 1 items that can be arranged in (y - x + 1)! ways. In addition, the x items can be arranges in x! ways generating a total of (x!)(y-x+1)! ways to arrange the y items

How do you calculate the number of items in a group based on the number of ways a subset of the bigger group can be chosen and ordered?

• When we have to calculate the number of items in a group based on the number of ways a subset of the bigger group can be chosen and ordered, use a variable to represent the number of items from which to choose and solve using box and fill diagram/permutation formula

How do we calculate multi digit questions?

• Analyse the number of choices we have for each digit and then multiply the results using the fundamental counting principle

• Look out for any additional restrictions to consider when determining the number of ways to create a particular number. Sometimes the number of ways to make a certain choice depends on the results of earlier choices

• When using the fundamental counting principle always begin with the most restrictive choice followed by the next most restrictive choice and so on

*Be mindful that the first digit of any integer cannot be 0

What are counting triangle questions?

• Some counting questions will ask us how to count the total number of triangles that can be created by connecting three points with lines

• If no three points are collinear, all groups of 3 points will form valid triangles.

  • If a triangle is formed by choosing any 3 non-collinear points (n = distinct points). Number of ways = {n(n−1)(n−2)}/6

• If some points are collinear (say k of them lie on a straight line), then:

  • Number of invalid triangles (degenerate triangles) = {k(k-1)(k-2)}/6

  • So the total number of triangles: = {n(n−1)(n−2)}/6 − {k(k-1)(k-2)}/6

When are the points collinear?

If 3 or more points can be connected by a straight line, the points are collinear

How to solve counting triangle questions?

• If there are n points on a plane such that no 3 points are collinear, then we can create a triangle with points as vertices in ⁿC₃ ways

How to solve the total number of possible triangles such that three or more points are collinear?

• Connecting three collinear points will not produce a triangle

• If there are n points on a plane such that three or more points are collinear, then the number of possible triangles = ⁿC₃ - (Number of ways to select three collinear points)