What is concept of separator in Combination Problems

[s.pratibha14]

Please help me to solve the below question.

How many positive integers less than 10,000 are there in which sum of digits equals 5?
(a) 31
(b) 51
(c) 56
(d) 62
(e) 93.


How to approach these types of questions? Detailed explanation would be appreciated.


Thanx in advance.

[tim]

Before we help with this question, we need you to show some effort of your own. What did you try on this question? Where did you get stuck?

[s.pratibha14]

Hi Tim,

Yes, I tried this question.. I tried it manually, But during this manual count i missed some of the numbers. After that I searched the solution of this problem and I saw the concept of separator in GMATClub forum. But I wanted to know when and why we need to use this separator concept.


Plz help..

[tim]

interesting. i think the "stars and bars" method is probably what they're getting at. this will be a 1, 2, 3, or 4 digit number, so we'll consider the cases separately:

1 digit
can only be 5

2 digits
can be 14, 23, 32, 41, or 50. we can get this result by considering a string of five stars that represent adding up to 5, and by putting a separator (a bar) somewhere to distinguish the first digit from the second. Thus our 2-digit numbers can look like this
*|**** = 14
**|*** = 23
***|** = 32
****|* = 41
*****| = 50
Note that we can't start with a bar because that would mean the first digit is 0 (note that ending with a bar, as in the case of 50, means the final digit is 0). Once we set the first position to be a star, we have 4 stars and 1 bar to put in any order in the remaining 5 positions. This gives us 5!/(4!1!)=5, which corresponds to what we generated manually.

For three digit numbers, we have 5 stars and 2 bars, some examples of which include
**|*|** = 212
*||**** = 104
Again, the first position must be a star, but the remaining 6 will consist of 4 stars and 2 bars, giving us 6!/(4!2!)=15.

For four digit numbers, we have 5 stars and 3 bars. First position is again a star leaving 7 positions to arrange 4 stars and 3 bars, giving us 7!/(4!3!)=35.

Adding these up we get 1+5+15+35=56.