MH1812
Discrete Mathematics
Contents
nCr=(nr)=n!r!(n−r)!nCr = \binom{n}{r} = \frac{n!}{r! (n-r)!}
nPr=(nr)⋅r!=n!(n−r)!nPr = \binom{n}{r} \cdot r! = \frac{n!}{(n-r)!}
Number of ways to order n distinct items in a circle =n!n\text{Number of ways to order } n \text{ distinct items in a circle } = \frac{n!}{n}
Arranging n distinct items with r indistinguishable items among them =n!r!\text{Arranging } n \text{ distinct items with } r \text{ indistinguishable items among them } = \frac{n!}{r!}
x1+x2+…+xr=nx_1 + x_2 + \dots + x_r = n
If ∀i,xi>0, then #of ways =(n−1r−1)\text{If } \forall i, x_i > 0, \text{ then \# of ways } = \binom{n-1}{r-1}
If ∀i,xi≥0, then #of ways =(n+r−1r−1)\text{If } \forall i, x_i \ge 0, \text{ then \# of ways } = \binom{n+r-1}{r-1}
*Try to normalise all the xi to be >0.
