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

Tinku Tara June 4, 2023 Permutation and Combination 0 Comments

Facebook Tweet Pin

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.

H o w m a n y 6 d i g i t n u m b e r s e x i s t

w h o s e d i g i t s h a v e e x a c t l y t h e s u m 13 ?

f o r e x a m p l e 120505 i s s u c h a n u m b e r .

Commented by Rasheed.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}

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 by aurpeyz last updated on 11/Jul/20

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

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

Commented by mr 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!

R a s h e e d s i r : i {d o n}^{'} t k n o w m u c h

a b o u t s e t m e t h o d s . c a n y o u g i v e s o m e

e x p l a n a t i o n a n d h o w t o a r r i v e a t t h e

r e s u l t ? t h a n k s!

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

i see, thanks! do you have other ideas?

i s e e, t h a n k s! d o y o u h a v e o t h e r i d e a s ?

Commented by Rasheed.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.

S i r, a c t u a l l y {i t}^{'} s n o t m u c h

h e l p f u l l, I t h i n k n o w . I o n l y

e x t e n d e d t h e s e t {0, 1, 2, \dots, 9} b y

w r i t i n g m a x i m u m p o s s i b l e

o c c u r i g s o f e a c h d i g i t i n t h e

r e q u i r e d n u m b e r s .

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

i got 6027 such numbers.

i g o t 6027 s u c h n u m b e r s .

Commented by Rasheed.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.

S i r I t h o u g h t t o a t t a c k t h e

p r o b l e m a s f o l l o w s :

(i) T o d e t e r m i n e t h e n u m b e r

o f p a r t i o n s (i n a n o r d e r)

o f 13 u s i n g a b o v e^{'} u n i v e r s a l {s e t}^{'}

{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}

(i i) T o d e t e r m i n e n u m b e r o f

^{'} {p e r m u t a t i o n s}^{'} o f e a c h

p a r t i t i o n s .

(i i i) A f t e r t h a n n u m b e r o f

e x c l u d i n g u n w a n t e d n u m b e r s .

I a m n o t c o n f i d e n t o f t h e s e

i d e a s . Y o u c a n d o b e t t e r .

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

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

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

Thanks. I will recheck calculation for both methods.

Thanks . I will recheck calculation

for both methods .

Commented by PRITHWISH 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.

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 \times 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 by mr 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

y e s! t h i s i s t h e b e s t m e t h o d t o s o l v e .

p l e a s e r e c h e c k y o u r f o r m u l a, i t h i n k

i t c o n t a i n s a n e r r o r . i g o t :

C_{5}^{17} - C_{5}^{8} - 5 C_{5}^{7} = 6027

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

big thanks to all for the many ideas!

b i g t h a n k s t o a l l f o r t h e m a n y i d e a s!

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

See Q22040

See Q 22040

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

Q55502

Q 55502

Commented by prakash 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.

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 by PRITHWISH SEN 2 last updated on 11/Jul/20

Thank you sirs

Thank you sirs

Commented by mr 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.

t h e r e i s n o s t a n d a r d w a y f o r s u c h

p r o b l e m s . t h e w a y y o u a r e t r y i n g c a n

r e a c h t h e g o a l, b u t i t c o u l d b e t o u g h .

Commented by Rasheed.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 ....

S i r a n i d e a c o m e s t o m e! I f s u m

o f d i g i t s i s 13 t h a t m e a n s

n u m b e r s w h i c h l e a v e s

r e m a i n d e r 1 w h e n {t h e y}^{'} r e

d i v i d e d b y 3 . T h a t i s 3 k + 1 t y p e

n u m b e r s .

T h e n u m b e r s l e a v e s r e m a i n d e r

4 w h e n {t h e y}^{'} r e d i v i d e d b y 9 .

T h a t i s t h e n u m b e r s o f 9 k + 4

t y p e s \dots . S o m e e x t r a n u m b e r s

\dots .

Commented by PRITHWISH 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

sir but the number

300001 = 3 \times 100000 + 1

but 3 + 0 + 0 + 0 + 0 + 1 \neq 13

and

3 \times 94528 + 1 = 283585 \neq 13

Commented by Rasheed.Sindhi last updated on 11/Jul/20

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

H e l l o s i r P R I T H W I S H S E N!

{Y o u}^{'} r e r i g h t s i r! S o m e e x t r a

n u m b e r s w i l l a l s o i n c l u d e d . S o \dots

Commented by PRITHWISH 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

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 by prakash 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) +..)

First digits 1 to 9

rest all 0 to 9

(x^{1} + \dots . + x^{9}) {(1 + \dots + x^{9})}^{5}

Digits with sum 13 is given by

coefficient of x^{13} in above expression .

\frac{x (1 - x^{9})}{1 - x} \times \frac{{(1 - x^{10})}^{5}}{{(1 - x)}^{5}}

= x (1 - x^{9} - x^{10} + higherpower) {(1 - x)}^{- 6}

= x (1 - x^{9} - 5 x^{10}) (1 + \underset{i = 1}{\sum^{\infty}}^{6 + i - 1} C_{i} x^{i})

= (x - x^{10} - x^{11}) (\dots)

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 - 5 x^{10} + . .)

Commented by mr 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?

y e s s i r! i s o l v e d s i m i l a r q u e s t i o n s

s o m e t i m e s a g o, b u t i {c a n}^{'} t r e m e m b e r

t h e o l d p o s t s . h o w d i d y o u f i n d t h e s e

o l d p o s t s ?

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

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

I searched for generating or just

generat etc . tried 2 - 3 search text .

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

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

t h a n k s s i r! i n t h i s w a y o n e c a n f i n d

s o m e o l d p o s t s, g r e a t!

Commented by PRITHWISH 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

sir prakash jain

i think your 2^{nd} expression will be

{(1 + \dots . + x^{9})}^{5} not 6

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

yes. it is 5.

y e s . i t i s 5 .

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

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

o k . I r e a l i z e n o w . i n p r e v i o u s s t e p

i h a v e w r i t t e n s i x .

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

{l e t}^{'} s l o o k a t t h e g e n e r a l c a s e :

h o w m a n y n d i g i t n u m b e r s e x i s t

w h o s e d i g i t s h a v e e x a c t l y t h e s u m m ?

s a y s u c h a n u m b e r i s

d_{1} d_{2} d_{3} \dots d_{n}

w i t h t h e c o n d i t i o n s :

1 ⩽ d_{1} ⩽ 9

0 ⩽ d_{2}, d_{3}, \dots, d_{n} ⩽ 9

s o t h e q u e s t i o n i s h o w m a n y i n t e g r a l

s o l u t i o n s t h e f o l l o w i n g e q u a t i o n

d_{1} + d_{2} + d_{3} + \dots + d_{n} = m \dots (I)

h a s u n d e r t h e g i v e n c o n d i t i o n s .

w e c a n u s e t h e g e n e r a t i n g f u n c t i o n s

f o r d_{1} : x + x^{2} + x^{3} + \dots + x^{9}

f o r d_{2}, d_{3}, \dots, d_{n} : 1 + x + x^{2} + x^{3} + \dots + x^{9}

f o r d_{1} + d_{2} + d_{3} + \dots + d_{n} i t i s t h e n

(x + x^{2} + x^{3} + \dots + x^{9}) {(1 + x + x^{2} + x^{3} + \dots + x^{9})}^{n - 1}

= \frac{x (1 - x^{9}) {(1 - x^{10})}^{n - 1}}{{(1 - x)}^{n}}

= x (1 - x^{9}) {(1 - x^{10})}^{n - 1} \underset{k = 0}{\sum^{\infty}} C_{n - 1}^{k + n - 1} x^{k}

= x (1 - x^{9}) [\underset{r = 0}{\sum^{n - 1}} {(- 1)}^{r} C_{r}^{n - 1} x^{10 r}] [\underset{k = 0}{\sum^{\infty}} C_{n - 1}^{k + n - 1} x^{k}]

t h e c o e f f i c i e n t o f t h e x^{m} t e r m i n t h i s

g e n e r a t i n g f u n c t i o n r e p r e s e n t s t h e

n u m b e r o f s o l u t i o n s o f e q n . (I) .

e x a m p l e : n = 6, m = 13

G F = x (1 - x^{9}) (1 - 5 x^{10} + \dots) \underset{k = 0}{\sum^{\infty}} C_{5}^{k + 5} x^{k}

= x (1 - x^{9} - 5 x^{10} + \dots) \underset{k = 0}{\sum^{\infty}} C_{5}^{k + 5} x^{k}

c o e f f i c i e n t o f x^{13} t e r m i s

(f o r k = 12, 3, 2)

C_{5}^{17} - C_{5}^{8} - 5 C_{5}^{7} = 6027

Commented by PRITHWISH SEN 2 last updated on 11/Jul/20

Thanks sir

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

x x x x x x x x x x x x x x x x x x (18 x)

Replace any 5 of last 17 x by a bar

count the number of x s between

to bars to get a digit .

Now this will include cases where

where all 5 bars are included in

8 or less continous x s . Meaning digits

has to be ⩽ 9 .

You can't use 'macro parameter character #' in math mode

one digits is 10 = 6 \times^{5} C_{3} +^{7} C_{4} +^{6} C_{4} = 110

one digits is 11 = 5 \times^{4} C_{3} +^{6} C_{4} +^{5} C_{4} = 55

one digits is 12 = 4 \times^{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 ∣ 10 x ∣ 5 x to x 6 x ∣ 10 x

x x ∣ x x x ∣ x x x ∣∣ x x x ∣ x x

233032

x x ∣∣∣∣∣∣ x x x x x x x x x x x

Commented by Rasheed.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!

S i r r e a l l y u s e f u l m e t h o d! I

r e m e m b e r n o w t h a t l o n g a g o I

h a d l e a r n t i t f r o m y o u b u t I

f o r g o t!

Commented by prakash 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.

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 .

Terms of Service
Privacy Policy
Contact: info@tinkutara.com

Facebook Tweet Pin

Leave a Reply Cancel reply