Skip to content
GATETECH
Official PYQ · 2015Set 3 · Q5Combinatorics: Counting, Recurrence Relations, Generating FunctionsNAT1 mark

GATE CS 2015 Set 3 Q5 — Combinatorics: Counting, Recurrence Relations, Generating Functions

Explain with AI
The number of 44 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}\{1, 2, 3\} is ________.
View worked solution

Answer: 15

Let the 44-digit number be represented by d1d2d3d4d_1d_2d_3d_4, where each digit diext(fori=1,2,3,4ext)extbelongsto{1,2,3}d_i ext{ (for } i = 1, 2, 3, 4 ext{)} ext{ belongs to } \{1, 2, 3\}.

The digits must be in non-decreasing order from left to right, which gives the condition:

1≤d1≤d2≤d3≤d4≤31 \le d_1 \le d_2 \le d_3 \le d_4 \le 3

This problem is equivalent to selecting 44 digits from the set {1,2,3}\{1, 2, 3\} where repetition is allowed, because once any 44 digits are selected, there is exactly one unique way to arrange them in non-decreasing order.

The number of ways to choose rr items from a set of nn distinct items with repetition allowed is given by the combination with repetition formula:

(n+r−1r)\binom{n + r - 1}{r}

Here, n=3n = 3 (the digits {1,2,3}\{1, 2, 3\}) and r=4r = 4 (the length of the number):

Number of ways=(3+4−14)=(64)=(62)=6×52=15\text{Number of ways} = \binom{3 + 4 - 1}{4} = \binom{6}{4} = \binom{6}{2} = \frac{6 \times 5}{2} = 15

Thus, there are 15 such 44-digit numbers.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Combinatorics: Counting, Recurrence Relations, Generating Functions questions