Handshake
Counting
In combinatorics there are two types of counting problems.
For example, in how many ways can balls of different colors be arranged ? Let us consider 3 balls of colors red , blue and green respectively.
Possible different arrangements of 3 balls are :
- RGB
- RBG
- BRG
- BGR
- GBR
- GRB
Total count is 6 and it is given by . Or for balls it's .
Counting number of selections (Combinations)
Let us count the number of ways of selecting items out of distinguishable items :
Counting number of arrangements (Permutations)
Let us count the number of ways of selecting items out of distinguishable items and then arranging them in some order.:
Methods for calculating :
int nCr(int n,int r){
int res = 1 ;
r = min(r,n-r) ; // nCr = nC(n-r)
for(int i=r;i>=1;i--){
res = res * n ;
res /= i ;
n -- ;
}
return res ;
}
// this code works properly for small size input
we can also use following recurrence to build up the dynamic programming for repeated queries.
Related challenge for Counting