Question Number 102816 by mr W last updated on 11/Jul/20

How many 6 digit numbers exist  whose digits have exactly the sum 13?    for example 120505 is such a number.

Commented byRasheed.Sindhi last updated on 11/Jul/20

Universal Set  {0,0,0,0,1,1,1,1,1,2,2,2,2,2,3,3,3,3,                                  4,4,4,5,5,6,6,7,8,9}

Commented byaurpeyz last updated on 11/Jul/20

660100 508000 309000...it will be much o. how should this be[done?

Commented bymr W last updated on 11/Jul/20

Rasheed sir: i don′t know much  about set methods. can you give some  explanation and how to arrive at the  result? thanks!

Commented bymr W last updated on 11/Jul/20

i see, thanks! do you have other ideas?

Commented byRasheed.Sindhi last updated on 11/Jul/20

Sir, actually it′s not much  helpfull,I think now.I only    extended the set{0,1,2,...,9} by  writing maximum possible   occurigs of each digit in the   required numbers.

Commented bymr W last updated on 11/Jul/20

i got 6027 such numbers.

Commented byRasheed.Sindhi last updated on 11/Jul/20

Sir I thought to attack the  problem as follows:  (i) To determine the number  of partions(in an order)  of 13 using above ′universal set′  {0,0,0,0,1,1,1,1,1,2,2,2,2,2,3,3,3,3,           4,4,4,5,5,6,6,7,8,9}  (ii)To determine number of  ′permutations′ of each  partitions.  (iii)After than number of  excluding unwanted numbers.       I am not confident of these  ideas.You can do better.

Commented byprakash jain last updated on 11/Jul/20

This method i think is known as generating function method, used in problem involving coins etc.

Commented byprakash jain last updated on 11/Jul/20

Thanks. I will recheck calculation  for both methods.

Commented byPRITHWISH SEN 2 last updated on 11/Jul/20

Sir itis really hard . But I might find a different  way.  For instance let find the 3 digits numbers in between  100 and 200 whose digit sum is 12   Sum of digits         Numbers  1 −−−−100  2−−−−101−−−−110  3−−−−102−−−−111−−−−120  4−−−−103−−−−112−−−−121−−−−130  5−−−−104−−−−113−−−−122−−−−131  6−−−−105−−−−114−−−−123−−−−132  7−−−−106−−−−115−−−−124−−−−133  8−−−−107−−−−116−−−−125−−−−134  9−−−−108−−−−117−−−−126−−−−135  10−−− 109−−−−118−−−− 127−−−−136  11−−−−−−−−−119−−−−128−−−−137  12−−−−−−−−−−−−−−−129−−−−138  and so on..  so the first number is 129 and the last number   is 129+9×n<200  n=7  ∴ no. of 3 digits number whose sum is 12 is  = 7+1=8  sir is it can be helpful for such problems ?  Sir Rasheed and Mr.Wsir please share your  comments.

Commented bymr W last updated on 11/Jul/20

yes! this is the best method to solve.  please recheck your formula, i think  it contains an error. i got:  C_5 ^(17) −C_5 ^8 −5C_5 ^7 =6027

Commented bymr W last updated on 11/Jul/20

big thanks to all for the many ideas!

Commented byprakash jain last updated on 11/Jul/20

See Q22040

Commented byprakash jain last updated on 11/Jul/20

Q55502

Commented byprakash jain last updated on 11/Jul/20

Several other questions answered  by mr W only using method.  mr W, is the same method not  applicable here.  I did remember some previous   questions so searched.

Commented byPRITHWISH SEN 2 last updated on 11/Jul/20

Thank you sirs

Commented bymr W last updated on 11/Jul/20

there is no standard way for such  problems. the way you are trying can  reach the goal, but it could be tough.

Commented byRasheed.Sindhi last updated on 11/Jul/20

Sir an idea comes to me! If sum  of digits is 13 that means  numbers which leaves  remainder 1 when they′re  divided by 3. That is 3k+1 type  numbers.   The numbers leaves remainder  4 when they′re divided by 9.  That is the numbers of 9k+4  types....Some extra numbers  ....

Commented byPRITHWISH SEN 2 last updated on 11/Jul/20

sir but the number  300001 =3×100000+1  but 3+0+0+0+0+1≠13  and  3×94528+1=283585≠13

Commented byRasheed.Sindhi last updated on 11/Jul/20

Hello sir PRITHWISH SEN!  You′re right sir! Some extra  numbers will also included.So...

Commented byPRITHWISH SEN 2 last updated on 11/Jul/20

Please check this   1^(st)  Digit             No. of numbers      9                 The coefficient of 4 in                          (a^0 +a^1 +a^2 +a^3 +a^4 +a^5 +a^6 +a^7 +a^8 +a^9 )^5      8                The coeffi. of 5 in                          (a^0 +a^1 +a^2 +a^3 +a^4 +a^5 +a^6 +a^7 +a^8 +a^9 )^5      7                   The coeffi. of  6 in                           (a^0 +a^1 +a^2 +a^3 +a^4 +a^5 +a^6 +a^7 +a^8 +a^9 )^5      6                  The coeffi. of  7 in                           (a^0 +a^1 +a^2 +a^3 +a^4 +a^5 +a^6 +a^7 +a^8 +a^9 )^5      5                  The coeffi. of  8 in                           (a^0 +a^1 +a^2 +a^3 +a^4 +a^5 +a^6 +a^7 +a^8 +a^9 )^5      4                   The coeffi. of  9 in                           (a^0 +a^1 +a^2 +a^3 +a^4 +a^5 +a^6 +a^7 +a^8 +a^9 )^5      3                  The coeffi. of  10 in                           (a^0 +a^1 +a^2 +a^3 +a^4 +a^5 +a^6 +a^7 +a^8 +a^9 )^5      2                  The coeffi. of  11 in                           (a^0 +a^1 +a^2 +a^3 +a^4 +a^5 +a^6 +a^7 +a^8 +a^9 )^5      1                  The coeffi. of  12 in                           (a^0 +a^1 +a^2 +a^3 +a^4 +a^5 +a^6 +a^7 +a^8 +a^9 )^5

Commented byprakash jain last updated on 11/Jul/20

First digits 1 to 9  rest all 0 to 9  (x^1 +....+x^9 )(1+...+x^9 )^5   Digits with sum 13 is given by  coefficient of x^(13)  in above expression.  ((x(1−x^9 ))/(1−x))×(((1−x^(10) )^5 )/((1−x)^5 ))  =x(1−x^9 −x^(10) +higherpower)(1−x)^(−6)   =x(1−x^9 −5x^(10) )(1+Σ_(i=1) ^∞  ^(6+i−1) C_i x^i )  =(x−x^(10) −x^(11) )(...)  Terms in ()that will given x^(13 )    x^(12) ,x^3 ,x^2     ^(17) C_5 −^8 C_3 −5 ^7 C_2   (correction (1−x^(10) )^5  was  earlier written (1−x^(10) +..)  it should be (1−5x^(10) +..)

Commented bymr W last updated on 11/Jul/20

yes sir! i solved similar questions  sometimes ago, but i can′t remember  the old posts. how did you find these  old posts?

Commented byprakash jain last updated on 11/Jul/20

I searched for generating or just  generat etc. tried 2−3 search text.

Commented bymr W last updated on 11/Jul/20

thanks sir! in this way one can find  some old posts, great!

Commented byPRITHWISH SEN 2 last updated on 11/Jul/20

sir prakash jain  i think your 2^(nd) expression will be  (1+....+x^9 )^5  not 6

Commented byprakash jain last updated on 11/Jul/20

yes. it is 5.

Commented byprakash jain last updated on 11/Jul/20

ok. I realize now. in previous step  i have written six.

Answered by mr W last updated on 11/Jul/20

let′s look at the general case:  how many n digit numbers exist  whose digits have exactly the sum m?  say such a number is  d_1 d_2 d_3 ...d_n   with the conditions:  1≤d_1 ≤9  0≤d_2 ,d_3 ,...,d_n ≤9  so the question is how many integral  solutions the following equation  d_1 +d_2 +d_3 +...+d_n =m   ...(I)  has under the given conditions.  we can use the generating functions  for d_1 : x+x^2 +x^3 +...+x^9   for d_2 ,d_3 ,...,d_n : 1+x+x^2 +x^3 +...+x^9   for d_1 +d_2 +d_3 +...+d_n  it is then  (x+x^2 +x^3 +...+x^9 )(1+x+x^2 +x^3 +...+x^9 )^(n−1)   =((x(1−x^9 )(1−x^(10) )^(n−1) )/((1−x)^n ))  =x(1−x^9 )(1−x^(10) )^(n−1) Σ_(k=0) ^∞ C_(n−1) ^(k+n−1) x^k   =x(1−x^9 )[Σ_(r=0) ^(n−1) (−1)^r C_r ^(n−1) x^(10r) ][Σ_(k=0) ^∞ C_(n−1) ^(k+n−1) x^k ]  the coefficient of the x^m  term in this  generating function represents the  number of solutions of eqn. (I).    example: n=6, m=13  GF=x(1−x^9 )(1−5x^(10) +...)Σ_(k=0) ^∞ C_5 ^(k+5) x^k   =x(1−x^9 −5x^(10) +...)Σ_(k=0) ^∞ C_5 ^(k+5) x^k   coefficient of x^(13)  term is  (for k=12, 3, 2)  C_5 ^(17) −C_5 ^8 −5C_5 ^7 =6027

Commented byPRITHWISH SEN 2 last updated on 11/Jul/20

Thanks sir

Answered by prakash jain last updated on 11/Jul/20

xxxxxxxxxxxxxxxxxx (18x)  Replace any 5 of last 17 x by a bar  count the number of xs between  to bars to get a digit.  Now this will include cases where  where all 5 bars are included in  8 or less continous xs. Meaning digits  has to be ≤9.  # of ways to place 5 bars= ^(17) C_5   one digits is 10=6× ^5 C_3 + ^7 C_4 + ^6 C_4 =110  one digits is 11=5× ^4 C_3 + ^6 C_4 + ^5 C_4 =55  one digits is 12=4× ^3 C_3 + ^5 C_4 +^4 C_4 =10  one digits is 13=1  valid outcomes  =^(17) C_5 −161=6188−161=6027  count the number of x between  2 bars to get the digit.  x∣10x∣5x to x6x∣10x  xx∣xxx∣xxx∣∣xxx∣xx  233032  xx∣∣∣∣∣∣xxxxxxxxxxx

Commented byRasheed.Sindhi last updated on 11/Jul/20

Sir really useful method! I  remember now that long ago I  had learnt it from you but I  forgot!

Commented byprakash jain last updated on 11/Jul/20

This method is commonly known  as stars and bars.  Very useful for dividing n items  in m boxes.  The above is a special cases where  first box is not empty and other  boxes can be empty but cannot  contain more than 9 items.