Important Formulae: Permutations & Combinations | CSAT Preparation - UPSC PDF Download

Permutation & Combination

When two tasks are performed in succession (connected by AND), the total number of ways of performing both tasks equals the product of the number of ways of performing each task individually. When only one of several tasks is to be performed (connected by OR), the total number of ways equals the sum of the individual numbers of ways.

Example: In a shop there are d doors and w windows.

• If a thief wants to enter via a door or a window, he can do it in (d + w) ways.
• If a thief enters via a door and leaves via a window, he can do it in (d × w) ways.

Linear arrangement of ‘r’ out of 'n' distinct items (ⁿP_r) 

The first position can be filled in n ways, the second in (n - 1) ways, the third in (n - 2) ways and so on until r positions are filled. Multiplying these counts gives the total number of linear arrangements of r items chosen from n distinct items.

The number of such arrangements is

ⁿP_r = n × (n - 1) × (n - 2) × ... × (n - r + 1)

This can be written using factorials as

ⁿP_r =

Circular arrangement of n distinct items

In circular arrangements where only relative order matters (rotations considered identical), fix one item as reference and arrange the remaining n - 1 items linearly around it. This yields

Circular permutations of n distinct items = (n - 1)! 

EduRev's Tip: For arrangements such as a necklace where reflections (turning over) are considered the same as rotations, the count is

Necklace (rotation + reflection) = for n > 2.

To count selections (order does not matter) of r items from n distinct items, first count ordered selections and then remove the internal orders of the chosen items.

The number of ordered selections is nPr. Each unordered selection of r items corresponds to r! different orderings. Therefore

Derangement (complete mismatch)

A derangement of n distinct objects is a permutation in which none of the objects appears in its original position. The number of derangements is denoted by !n.

The exact formula using the inclusion-exclusion principle is

!n = n! × Σ_k=0ⁿ ((-1)^k / k!)

There is also a useful recurrence:

• !0 = 1, !1 = 0
• !n = (n - 1) [!(n - 1) + !(n - 2)] for n ≥ 2

For large n, !n is well approximated by n! / e, and the nearest integer to n! / e gives !n.

EduRev's Tip: Number of ways of arranging n items in a line when some items are identical (for example, p alike, q alike, r alike, ...) is

Permutations with identical items =

Partitioning (multinomial / labelled group partitions)

If n distinct items are to be partitioned into k labelled groups of sizes n1, n2, ..., nk where Σ ni = n, the number of ways is given by the multinomial coefficient.

Number of partitions into labelled groups = n! / (n1! n2! ... nk!)

Additional formulae and relations

• Relation between permutations and combinations: ⁿP_r = ⁿC_r × r!.
• Factorial definition: n! = n × (n - 1) × (n - 2) × ... × 1, with 0! = 1.
• Approximation for derangements: !n ≈ n! / e; the nearest integer to n!/e is !n for large n.

Final concise formula sheet

• ⁿP_r = n! / (n - r)!
• ⁿC_r = n! / (r! (n - r)!)
• Circular permutations of n distinct items = (n - 1)! 
• Necklace (rotation + reflection) = (n - 1)! / 2 for n > 2
• Derangements: !n = n! × Σ_k=0ⁿ ((-1)^k / k!)
• Permutations with identical items = n! / (p! q! r! ...)
• Partition into labelled groups sizes n1,...,nk: n! / (n1! n2! ... nk!)