Counting
Counting is one of the basic problem of mathematics. After the advent of computer science counting has become more important and developed in an area by itself.
There are some basic counting techniques-
1 Addition rule.
If one thing can be done in m or n ways to collectively it can be done in m+n ways.
2. Multiplicaton rule.
If part of a thing can be done in m ways and another part in n ways. to complete the thing m*n ways are in total.
with n elements; a k-subset of a set is a subset with k elements. The set of the first n
integers, that is {1, 2, 3,...,n} will be denoted by [n].
words: A word over an alphabet X, is an finite sequence of elements of X.
Permutation: A permutation of a set X is a total linear ordering of elements of X.
- The number of permutation of set of n elements is n!
k-permutation: A k-permutation of a set X is total linear ordering of a k-element subset of X.
No of k-permutation of a n-set = n!/(n-k)!
Subsets: No of k subsets of a set of n elements is
(n k) = n!/(n-k)!k!
(n k) is called binomial coffecients.
key recurrence relation for binomial coeffecients = (n k) = (n-1 k)+(n-1 k-1)
take on elements (inlcude it)+(exclude it)
Binomial theorem- (a+b)^n =
interpretation (a+b)*(a+b)*(a+b)*.. (a+b) to make up one term one chooses m a's and k
