Finding total unique combinations and Generalisation of the same.

34 Views Asked by At

There are n numbers of k bits, I want to find out how many unique combinations will be if a bit position is set for each of the n numbers. Take an example for n = 4, k=2.

    n   k1   k0

   1.   _    1        The dashed positions can be filled with two possible values 0 or 1. 
   2.   _    1 
   3.   _    1
   4.   _    1

So if the last bit is set, I can generate $2^4$ combinations/values. Same no. of possible value for setting 1st-bit position.

I calculated it for this particular n and k and found out there is only 1 duplicate combination :

k1 k0
1  1
1  1
1  1
1  1

so I can now count the total no. of unique combinations as $2^4$ + $2^4$ - 1.

How can I generalize it for any value of n and k? I tried for n = 8, k = 4 to find any pattern but it's very lengthy to generate this by writing.