## Probability, Combinatorics

Theory

### Derangements

If n distinct items are arranged, the number of ways they can be arranged so that they do not occupy their intended spot is $$D = n!$$($$\frac{1}{0!}$$ - $$\frac{1}{1!}$$ + $$\frac{1}{2!}$$ - $$\frac{1}{3!}$$ + .... + $$\frac{(-1)^{n}}{n!}$$)

Theory
• If the probability of an event occurring is p, then the probability that the event will occur r times in n trials is given by = $$^{n}\textrm{C}_{r}p^{r}(1-p)^{n-r}$$
• If p is the probability of an event, then odds in favor of an event are p / (1 – p). Conversely, the odds against are (1-p)/p.
• Say $$E_{1}, E_{2}…. E_{n}$$ are mutually exclusive exhaustive events with probabilities $$p_{1}, p_{2}.... p_{n}$$ and expected values $$e_{1}, e_{2}.... e_{n}$$ then Expected payoff = $$\sum_{i=1}$$ $$^{n}p_{i}e_{i}$$
Formula

### Partitioning:

• Number of ways to partition n identical things in r distinct slots is given by: $$= ^{n+r-1} C_{r-1}$$
• Number of ways to partition n identical things in r distinct slots so that each slot gets at least 1: $$= ^{n-1}C_{r-1}$$
• Number of ways to partition n distinct things in r distinct slots is given by: $$r^{n}$$
• Number of ways to partition n distinct things in r distinct slots where arrangement matters: $$\frac{(n+r-1)!}{(r-1)!}$$
Formula
• Arrangement: n items can be arranged in n! ways
• Permutation: A way of selecting and arranging r objects out of a set of n objects: $$^{n}\textrm{P}_{r}$$ = $$\frac{n!}{(n-r)!}$$
• Combination: A way of selecting r objects out of n (arrangement does not matter)  $$^{n}\textrm{C}_{r}$$ = $$\frac{n!}{r!(n-r)!}$$
• Selecting r objects out of n is same as selecting (n-r) objects out of n $$^{n}C_{r}$$ = $$^{n}C_{n-r}$$
• $$\sum_{k=0}^{n}$$$$^{n}C_{k}=2^{n}$$
Theory

Both of Permutations & Combinations and Probability are extremely important topics in CAT. We have combined both of them together because improving in P&C would help you get better in Probability. After number systems, this is the second most important topic for CAT preparation. Many students find learning P&C and probability a nightmarish experience. Many even skip this topic in frustration. We think under-preparing in P&C and probability is one of the biggest mistakes you could make in CAT prep. This topic can be the most rewarding topic in quant section. Unlike number systems questions, these questions generally take lesser time to solve. Also, they are generally fairly basic in nature. And the best part is- the more questions you solve, the better you will get at this subject. So look through the formula list a few times and understand the formulae. But the best way to tackle this subject is by solving questions. Solve as many as you can- solve so many from this topic that you start to see that all of them are generally variations of the same few themes that are listed in the formula list.

Theory
• Probability of an event: If in n equally likely outcomes an event is said to have occurred m times, then the probability of the event is P(E) = m/n
• Probability of the event not occurring is P (E') = 1-m/n
• Events are said to be mutually exclusive if they can never occur together. They are said to be collectively exhaustive if together they encompass all possible outcomes.
• The sum of probabilities of mutually exclusive and exhaustive events is 1
• Probability of event A or B occurring P (A or B) = P(A) + P(B) – P(A and B)
• Probability of A given B = P(A and B) / P(B)
• Two events are independent of each other if P(A and B ) = P (A)* P(B)
Formula

### Integral Solutions

• Number of positive integral solutions to $$x_{1}+x_{2}+x_{3}+.....+ x_{n}=s$$ where s>=0 is $$^{s-1}\textrm{C}_{n-1}$$
• Number of non-negative integral solutions to $$x_{1}+x_{2}+x_{3}+.....+ x_{n}=s$$ where s>=0 is $$^{n+s-1}\textrm{C}_{n-1}$$
Theory

### Rank of a word:

To get the rank of a word in the alphabetical list of all permutations of the word, start with alphabetically arranging the n letters. If there are x letters higher than the first letter of the word, then there are at least x*(n-1)! Words above our word. After removing the first affixed letter from the set if there are y letters above the second letter then there are y*(n-2)! words more before your word and so on. So rank of word = x*(n-1)! + y*(n-2)! + .. +1

Theory

### Circular arrangement:

• Number of ways of arranging n items around a circle are 1 for n=1,2 and (n-1)! For n>=3s. If its a necklace or bracelet that can be flipped over, the possibilities are 0.5 * (n-1)!.
Theory

### Bayes theorem:

Let $$E_{1}, E_{2}, E_{3}...$$ be mutually exclusive and collectively exhaustive events each with a probability $$p_{1}, p_{2}, p_{3}...$$ of occurring. Let B be another event of non-zero probability such that probability of B given $$E_{1}$$ is $$q_{1}$$, B given $$E_{2}$$ is $$q_{2}$$ etc. By Bayes theorem: $$P(E_{i}/B) = \frac{p_{i}q_{i}}{\sum_{j=1}^{n}p_{j}q_{j}}$$\$

Tip
• Number of diagonals in an n-sided polygon = n(n-3)/2
Formula

### Arrangement with repetitions:

If x items out of n items are repeated, then the number of ways of arranging these n items is $$\frac{n!}{x!}$$ ways. If x items, y items and z items are repeated within n items, they can be arranged in $$\frac{n!}{a!b!c!}$$ ways.