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!}$$)

For, example, Derangements of 4 will be D(4) = $$4!\left(1-\dfrac{1}{1!}+\dfrac{1}{2!}-\dfrac{1}{3!}+\dfrac{1}{4!}\right)=24\left(\dfrac{1}{2}-\dfrac{1}{6}+\dfrac{1}{24}\right)=24\left(\dfrac{12-4+1}{24}\right)=9$$

D(1) = 0, D(2) = 1, D(3) = 2, D(4) = 9, D(5) = 44, and D(6) = 265

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)!}$$

• 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}$$

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)!.

• Number of diagonals in an n-sided polygon = n(n-3)/2
• For 'm' non-parallel lines, then the maximum number of regions into which the plane is divided is given by
  [m(m+1)/2]+1

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

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} $$

Arrangement with repetitions:

If x items out of n items are repeated, then the number of ways of arranging these n items is $$\dfrac{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.

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}}$$$