Combinatorics
Combinatorics is the branch of mathematics that deals with combinations of elements belonging to a finite set in accordance with some constraints.
The principle of addition states if a one task can be one done in m ways and another task which is mutually exclusive of the first task can be done in n ways, then the the number of possible ways in which either can be done is m+n.
The principle of multiplication states that if one task can be done in m ways and another task which is independent of the first task can be done in n ways, after the first task has been performed, then the number of possible ways in which both the tasks can be done is m×n.
Number of ways in which you can select n objects taken r at a time. (Order does not matter.)
nCr = n! / r! (n - r)!
Number of ways you can order n objects taken r at a time. (Order matters.)
nPr = n! / (n - r)!
Theorem one
For any pair of positive integers n and k, the number of k-tuples of positive integers whose sum is n is equal to the number of (k − 1)-element subsets of a set with n − 1 elements.
Let us say that we need to distribute 7 cookies to 4 kids such that they all have at least 1. We can represent it as stars and bars.
***|*|*|**
Here the 4 kids get 3, 1, 1 and 2 cookies respectively. we can say that we can place (k-1) bars between (n-1) spaces between the stars. Thus, the answer is 6C3.
This can be generalised as (n-1)C(k-1).
Theorem two
For any pair of positive integers n and k, the number of k-tuples of non-negative integers whose sum is n is equal to the number of multisets of cardinality k − 1 taken from a set of size n + 1.
Let us say that we need to distribute 7 cookies among 4 kids where each kid may get none or more cookies. We can represent this situation using stars and bars as well.
***||**|**
Here the 4 kids get 3, 0, 2 and 2 cookies respectively. So there are 10 symbols out of which 3 have to be bars. Thus, the answer is 10C3.
This can be generalised as (n+k-1)C(k-1).
