GATE CSE 2015 Set 3 | Question: 5

Question

The number of $4$ digit numbers having their digits in non-decreasing order (from left to right) constructed by using the digits belonging to the set $\{1, 2, 3\}$ is ________.

Comments

@Kanwae Kan This formulae will work for non-decreasing order and non-increasing order . This will not work for increasing and decreasing order.

You can cross check with small set of elements.

---

@Deepak Poonia Sir how will we solve this type of questions if size of set of elements is large. because then brute force will be time consuming!!

---

@abir_banerjee

This question is based on IODB template(Star Bars Problem) of Objects distribution into Boxes. Even if size of set of elements is large, the question is Easily & efficiently solvable.

Watch this lecture: https://youtu.be/0oRBHg1ERtU 

Answer 1

A simple way to think of this is treating as a “combinations with repetition” type problem.

Note that for any 4 digits we pick, we will get a unique ordering.

Example: If we pick ${1,1,2,3}$ we have,  $d_{1}d_{2}d_{3}d_{4}=1123$ as the only number that can be formed.

Here, we are given 3 digits $1,2,3$ out of which we should pick 4 digits.

This boils down to

$x_{1}+x_{2}+x_{3}=4$  (Combinations with repetition)

Therefore the number of ways $=\binom{6}{4}=15$

Answer 2

we  can also solve it directly intutively (distribution of identical into distinct formula n-1+r C r)

X1 be number of 1s in 4 digit number formed.

X2 be number of 2s in 4 digit number formed.

X3 be number of 3s in 4 digit number formed.

Now,

X1+x2+X3=4

There are 15 solution possible for this,and each solution when arranged in sorted order of digit is solution to this problem.

Answer 3

Simplified :

Use IODB template for these kind of problems

Assume X1 ,X2,X3 are the noof 1's,2's,3's in the resultant number .

Then according to question we have to choose a 4 digit number , so the equation becomes

X1+X2+X3=4 ( X1,X2,X3>=0)

noof solutions for that equation can be easily found . (6c4=15)

For every possible solution there is only one possible non decreasing order ( assume X1=2,X2=1,X3=1 ---> so only possible ordering to this soln is 1123).

So noof orderings possible is 15

Answer 4

$\phi$ testing