counting

Question

how many number are possible of 4 digits whose sum is 12.

Comments

A bit related question

---

@Neal Caffery In the original problem, the first digit can not be 0 and none of the digits can be greater than 9. There are no such restrictions in the problem you have posted in this image. I hope this difference is clear to you.

---

yup i know  thats why "a bit related"  and not identical

Answer 1

The solution can be formulated as : x1+x2+x3+x4 = 12, which has solution 12+4-1C 4-1 = 455(Star and bar problem).

It will also include cases where x1 , x2 , x3 , x4 will take 10 , 11 , 12 values which cannot be the values of any digit.

So we have to remove all those cases.

Now, secondly when 1st digit becomes 0 then the number will not be of 4 digits. So we have to remove those cases.

In that case, put x1 = 0 and find the solution for x2+x3+x4 = 12 => 14C2 = 91(It will also remove all cases where x1 = 0 and x2,x3,x4 >= 0 )

Now we have to remove that case where x1 takes 10 , 11 , 12.

When x1 = 10, x2 +x3+x4 = 2 which gives 4C2 = 6.

When x1 = 11, x2+x3+x4 = 1 which gives 3C2 = 3.

When x1 = 12, x2+x3+x4 = 0 which gives 2C2 = 1.

Now, cases when x2,x3,x4 >= 10  we will count cases for x2 only , same will be applied on x3 and x4 also

x2 = 10 , x1 = 1 , then  x3 + x4 = 1  which gives 2C1 = 2.

x2 = 10 , x1 = 2 , then  x3 + x4 = 0 which gives 1C1 = 1.

x2 = 11 , x1 = 1 , then  x3 + x4 = 0  which gives 1C1 =1.

total ways = 3 * ( 2 + 1 + 1 ) = 12 , same for x3 and x4.

Now total ways :  15C3 - 14C2 -  ( 6 + 3 + 1 ) - 12 =  455 - 91 - 22 = 342.

Comments

@umang_16,when x2=12 then x1=0,why is it so..we can have their sum > 12 also na.we are finding the invalid combo and it is among them.so we will deduct them from the overall soltuion.

---

When x1 = 3,4,5... X2 cannot be greater than 9.... Coz total sum should be less than or equal to 12.

---

alright..i got it.thankyou

Answer 2

The problem can be formulated mathematically as no of non negative integral solutions of:

X1 + X2 + X3 + X4  =  12 

where 1 <= X1 <= 9 , 0 <= X2,X3,X4 <= 9

So it is given by coefficient of x¹² in (x + x².........+ x⁹) . (1 + x + x² ............. + x⁹)³ 

 ==> coefficient of x¹² in  x( 1 + x .........+ x⁸) .(1 + x ........x⁹)³

 ==>  coefficient of x¹¹ in  ( 1 + x .........+ x⁸) .(1 + x ........x⁹)³

 ==>  coefficient of x¹¹ in   (1 - x⁹) . (1 - x¹⁰)³ (1 - x) ^-4          [From sum of G.P. formula]

 ==>  coefficient of x¹¹ in   (1 - x⁹) . ( 1 - 3x¹⁰ + 3x²⁰  -  x³⁰) (1 - x)^-4

So picking up the relevant terms only we need to find coefficient of x¹¹ in  (1 - x)^-4  , -x⁹ (1 - x)^-4 and -3x¹⁰ (1 - x)^-4..We know :

Coefficient of x^r  in (1 - x)^-n   =  ^n-1+r C_r

So for 1st term , putting r = 11 , n = 4 , we have ,

Coefficient of  x¹¹ in  (1 - x)^-4  =   ^4-1+11 C₁₁

                                            =   (14 * 13 * 12) / 6

                                            =   364

Coefficient of  x¹¹ in -x⁹ (1 - x)^-4    =   - (Coefficient of  x²  in   (1 - x)^-4   )

                                                  =   - (^{4 - 1 + 2} C₂ )

                                                  =   - 10

Coefficient of  x¹¹ in  -3x¹⁰ (1 - x)^-4    =   - 12

Hence number of such 4 digit numbers whose sum of digits is 12  =  364 - 10 - 12

                                                                                                =  342

Hence 342 is the correct answer..

Comments

@habib,till now whatever i have read about and understood about generating functions,on the basis of that i still did not get how you write this "So it is given by coefficient of x¹² in (x + x².........+ x⁹) . (1 + x + x² ............. + x⁹)³ ".

if you can explain a bit that how this came into picture,it would be better..

and why did not u consider other terms here -" So picking up the relevant terms only we need to find coefficient of x¹¹ in  (1 - x)^-4  , -x⁹ (1 - x)^-4 and -3x¹⁰ (1 - x)^-4 "

why not 3x¹²(1-x)^-4  and x²⁰(1-x)^-4  ??

THnakyou

---

lets consider 3x¹²(1-x)^-4

Now, all the powers of x in expansion of (1-x)^-4 are positive. So, (x¹²  * some positive power of x) will be have powers >12. But, we want equal to 11. Hence, Habib took onl relevant powers.

---

yes..thanks @sushant..

Answer 3

Make a table of 4 * 12

dp[4][12]  where  dp[i][j] = total numbers formed using only starting i digits which have sum = j.

Over final answer is dp[4][12]

           int n = 4;
           int sum = 12;

     int dp[n + 1][sum + 1];
            memset(dp , 0 , sizeof dp);

             for(int i = 1 ; i <= 9 ; ++i )
             dp[1][i] = 1;

             for(int i = 2 ; i <= n ; ++i ){

               for(int j = 0 ; j < 10 ; ++j ) {              // we can fill our ith place with 0 <= digit <= 9.
                    for(int k = 0 ; j + k <= sum ; ++k )    
                   dp[i][j + k] += dp[i - 1][k];

               }

             }

      dp[n][sum] = 342.

0 1 1 1 1 1 1 1 1 1 0 0 0
0 1 2 3 4 5 6 7 8 9 9 8 7
0 1 3 6 10 15 21 28 36 45 54 61 66
0 1 4 10 20 35 56 84 120 165 219 279 342

Dynamic Programming.

Comments

Yes, this solution includes all the cases and gives a general approach to handle all the other constraints....