Counting

Counting problems are part of permutations and combinations. In the recent entrance tests and campus placement tests, good number of question are given.

Solved Example 1:
How  many number of 3's  would be used to type numbers from 1 to 700
Answer: 
Instead of calculating manually, if we use the concepts of permutations this problem can be solved easily

If we take numbers upto 699, Then the hudred's place take digits upto 6. But the digits in tenth and unit places take upto 9 from 0. 

If we fix digit 3 in hundred's place the remaining digits can be filled in 10 ways each.
Total ways are 10 X 10 = 100

If we fix digit 3 in tenth's place then the digit in hundred's place can be filled in 7 ways (0-6), and units place can be filled in 10 ways.
Then the total ways are 7 X 10 = 70

If we fix digit 3 in unit's place then the digit in hundred's place can be filled in 7 ways (0-6), and tenth's place can be filled in 10 ways.
Total number of ways if we fix 3 in units place = 70

Then the number 3 digit can be used to write numbers upto 700 is (100 + 70 + 70) = 240

Solved Example 2:
Find the total number of ways of reaching B from A If only right and up steps are allowed.
Method 1:
There are total 5 right steps denoted by R’s, and 3 Up Steps denoted by U’s
RRRRRUUU.  No number of ways of arranging These letters = 8!/(5! X 3!) = 56

Method 2:
Out of 8 there are 3 up steps.  No of ways of selecting  3 upsteps = $8{C_3}$ = 56

Method 3:
We use node method to solve this problem without using permutations

We need to calculate the number of ways of reaching every node or junction.  Take last node B this can be reached in two ways, which have already values 35 and 21.  We add these two to get node value for B. 


Solved Example 3:
How many different routes are available from P to Q?


Solution:
This porblem can be solved easily using above learnt node method.  Applying node values


Solved Example 4:
How many ways  A boy can reach the top of stairs which contain 10 steps, when he can take either one or two steps every time?

Let the number of ways of reaching top of stairs which has n steps = a(n)
If the boy takes the first step then the remaining (n-1) steps can be covered in = a(n-1) ways.
If the boy takes the first step with 2 steps then the remaining (n-2) steps can be covered in = a(n-2) ways.
So a(n) = a(n-1) + a(n-2)
Now if there is only one step number of ways = a(1) = 1
If there are only two steps number of ways = a(2) = 2
But a(3) = 1+2 = 3
So this is nothing but Fibonacci series : 1, 2,3, 5,8,13, 21, 34, 55, 89.

Solved Example 5:
How many ways 10 houses can be painted with only two colors, white and blue , where two houses consecutively cannot be painted blue.

Let the number of ways of painting the houses= a(n)
The first house we can painted with white remaining houses can be painted in = a(n-1) ways.
But if the first house is painted blue, the next house must be white so remaining (n-2) houses can be covered in = a(n-2) ways.
So a(n) = a(n-1) + a(n-2)

Now if there is only one house number of ways = a(1) = 2
If there are only two houses number of ways = a(2) = ww, wb, bw = 3
But a(3) = 2+3 = 5
So this is nothing but Fibonacci series : 2,3, 5,8,13, 21, 34, 55, 89, 144

Solved Example 6:
How many digit "1"s are being used in writing numbers from 1 to 160 in Binary system

160 in binary is 10100000


Let us calculate the number of zero's upto 127


If we fix 1 in the 7th position:
Now the positions from 1 - 6 can take either 1 or 0.  So total number of ways digit 1 can appear in 7th position = 2 x 2 x 2 x 2 x 2 x 2  = 64

Similarly if we fix 1 in 6th, 5th, 4th, 3rd, 2nd, 1st then total digit 1's upto 127 = 7 x 64 = 448.
Number 128 has one digit 1, and 7 zero's. so it has 1 digit 1
now numbers 129 to 159 are 31 numbers where digits change in 1 to 5 positions.  159 has 5 digit 1s.

Now digit 1 in 8th position remains constant and numbers from 1 to 5 positions change to form numbers from 129 to 159.

If we fix 1 in 5th position, remaining positions 1 to 4 change by 2 x 2 x 2 x 2 = 16 times.
Similary 1 in 4th, 3rd, 2nd and 1st position also changes by 16 times.  So total 1's are 16 x 5 = 80

and in all these 31 numbers 1 in 8th position kept on appearing in all these numbers.  So another 31 digit 1's.
So total digit 1's upto 159 = 448 + 1 + 80 + 31 = 560

Now number 160 has 2 digit 1's. so total 562.

Alternate method:

1 ---------> 1
2, 3 are two digit numbers in binary where their left most digit is 1 and right most digit changes from 0 to 1. so total number of 1's are 2 in left most position and half of the numbers which appear in the remaining digits are 1's.


$ \Rightarrow {\rm{2 + }}\frac{1}{2} \times \left( {{\rm{2}} \times {\rm{1}}} \right){\rm{ = 3}}$

4 to 7 are three digit numbers where digit 1 appears in left most position 4 times and the remaining digits are 4 x 2 = 8 and half of which are digit 1's.


4 to 7 $ \Rightarrow {{\rm{2}}^{\rm{2}}}{\rm{ + }}\displaystyle\frac{{\rm{1}}}{{\rm{2}}} \times \left( {{\rm{4}} \times {\rm{2}}} \right){\rm{ = 8}}$

8 to 15 $ \Rightarrow {{\rm{2}}^4}{\rm{ + }}\displaystyle\frac{{\rm{1}}}{{\rm{2}}} \times \left( {{\rm{8}} \times {\rm{3}}} \right){\rm{ = 20}}$

16 to 31 $ \Rightarrow {{\rm{2}}^4}{\rm{ + }}\displaystyle\frac{{\rm{1}}}{{\rm{2}}} \times \left( {{\rm{16}} \times {\rm{4}}} \right){\rm{ = 48}}$

32 to 63 $ \Rightarrow {{\rm{2}}^5}{\rm{ + }}\displaystyle\frac{{\rm{1}}}{{\rm{2}}} \times \left( {{\rm{32}} \times {\rm{5}}} \right){\rm{ = 112}}$

64 to 127 $ \Rightarrow {{\rm{2}}^6}{\rm{ + }}\displaystyle\frac{{\rm{1}}}{{\rm{2}}} \times \left( {{\rm{64}} \times {\rm{6}}} \right){\rm{ = 256}}$

So total digit 1's upto 127 are 1 + 3 + 8 + 20 + 48 + 112 + 256 = 448

128 contains one digit 1.

and from 129 to 159 there are exactly 31 numbers and the number of digit 1's = 31 digit 1's in 8th position and (1 + 3 + 8 + 20 + 48) = 80 digits in 1 to 6 positions.  So total = 111 digit 1's

160 contains 2 digit 1's

Finally total digit 1's are equal to 448 + 1 + 111 + 2 = 562