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

This problem is same as the number of ways to select 4 numbers from $\{1,2,3\}$ where repetition is allowed. Because, if we select one such sequence of numbers, there will be only 1 way to arrange these numbers in non-decreasing order.
Answer is: C(4+3-1, 3) = C(6, 2) = 15

Comments

Won’t it be C(6,3) according to your formula??

Answer 2

I have got a simple solution, Draw n trees, for n nodes, and the child of the tree is either equal to its parent or greater than the parent. Each node can have maximum n children. Count the no. of leaf nodes. The ith level represents ith position in the number. Here answer is 15.

Comments

bit clumsy but easy approach... thanks for quick response:)

---

Easier approach. But it will become tedious with more no. of digits.

---

@Utsav09 Total no. of leaves are 10?

Answer 3

Four position _ _ _ _

Fill in such a way that numbers are in order i.e. left <= right

Fill all with 3 = 1 choice

Fill last 3 position by 3 = two choice can be their(1,2) = 2 choice 

Fill last 2 position with 3= two place left fill with (22,11,12) but not with 21= 3 choice

Fill last  position with 3= three place left fill with (111, 112, 122,222) but not with 21= 3 choice= 4 choice

finish with 3

now do with 2

Fill all with 2= 1choice

Fill last three position  2= one place left  (1)= 1 choice

Fill last 2 position with 2= two place left fill with (11) but not 12 which is covered above = 1 choice

Fill last  position with 2= three place left fill with (111)= 1 choice

finish with 2

Fill all with 1= 1choice

 

Total choice will be= 1+1+1+3+2+4+1+1+1=15

Answer 4

{1, 1, 1, 1} {1, 1, 1, 2} {1, 1, 1, 3} {1, 1, 2, 2} {1, 1, 2, 3} {1, 1, 3, 3} {1, 2, 2, 2} {1, 2, 2, 3} {1, 2, 3, 3} {1, 3, 3, 3} {2, 2, 2, 2} {2, 2, 2, 3} {2, 2, 3, 3} {2, 3, 3, 3} {3, 3, 3, 3}

so answer is 15