Permutations and Combinations

An equivalence relation divides the given set into disjoint groups, called equivalence classes. Together, these classes form a complete partition of the set.

Here, the set is $ S = \{1, 2, 3, \ldots, 10\} $. So, we must divide it into parts (subsets) such that the total number of elements across all parts is 10.

For an equivalence relation, if one class has $ n_i $ elements, then all possible ordered pairs inside this class are related. Hence, it contributes $ n_i^2 $ related pairs to the relation.

Because the total number of related pairs is given as 42, we need to find positive integers $ n_1, n_2, \ldots, n_k $ satisfying both:

$ n_1 + n_2 + \ldots + n_k = 10 $

and

$ n_1^2 + n_2^2 + \ldots + n_k^2 = 42 $

Now, we search for combinations of squares that add up to 42, while the corresponding numbers add up to 10.

Possible combinations are:

$ 42 = 36 + 4 + 1 + 1 \ \Rightarrow \ \{6, 2, 1, 1\} $

$ 42 = 25 + 16 + 1 \ \Rightarrow \ \{5, 4, 1\} $

Hence, the partitions can be $ \{6, 2, 1, 1\} $ and $ \{5, 4, 1\} $.

Case 1: Partition {5, 4, 1}

First choose 5 elements out of 10 for one class, then choose 4 out of the remaining 5 for the next class, and the last one forms a single-element class. The number of ways is:

$ {^{10}C_5} \times {^{5}C_4} \times {^{1}C_1} = 1260 $

Case 2: Partition {6, 2, 1, 1}

First choose 6 elements out of 10, then 2 from the remaining 4, and the last two each become single-element classes. Since the two single-element groups are identical, we divide by 2! to adjust for overcounting. So the number of ways is:

$ {^{10}C_6} \times {^{4}C_2} \times \frac{{^{2}C_1 \times ^{1}C_1}}{2} = 1260 $

Therefore, the total number of such equivalence relations is the sum of both cases:

$ 1260 + 1260 = 2520 $

We have to distribute 10 identical red pens and 14 identical blue pens among four persons so that each person gets 6 pens in total.

For every possible way of giving out the red pens, the blue pens will automatically be distributed, because the total number of pens each person receives is fixed at 6. Hence, we only need to count the number of ways to distribute the red pens.

Let the number of red pens received by the four persons be $ x_1, x_2, x_3, x_4 $. Then,

$ x_1 + x_2 + x_3 + x_4 = 10 $

and since each person can receive a maximum of 6 pens, $ 0 \leq x_i \leq 6 $.

The number of non-negative integer solutions to the equation $ x_1+x_2+x_3+x_4=10 $ with $ x_i \le 6 $ can be obtained by finding the coefficient of $ x^{10} $ in the expansion of $ (1+x+x^2+\ldots+x^6)^4 $.

We know that:

$ (1+x+x^2+\ldots+x^6) = \frac{1-x^7}{1-x} $

Therefore,

$ (1+x+x^2+\ldots+x^6)^4 = \left( \frac{1-x^7}{1-x} \right)^4 = (1-x^7)^4(1-x)^{-4} $

Now, we need the coefficient of $ x^{10} $ in this expansion. Expanding $ (1-x^7)^4 $, we get:

$ (1-x^7)^4 = 1 - 4x^7 + \ldots $

Thus, the required coefficient of $ x^{10} $ is:

$ \text{Coeff. of } x^{10} \text{ in } (1-x)^{-4} - 4 \times \text{Coeff. of } x^{3} \text{ in } (1-x)^{-4} $

We know that the coefficient of $ x^r $ in $ (1-x)^{-n} $ is $ {^{n+r-1}C_{r}} $. Hence,

$ {^{13}C_3} - 4 \times {^{6}C_3} = 286 - 80 = 206 $

Therefore, the total number of ways = 206.

Problem restated: Let $R$ be a relation on $X = \{a,b,c,d,e,f\}$.

We want $R$ to be reflexive and symmetric, and contain exactly 10 elements.

Let $\mathcal{S} = \{R : R \text{ satisfies this}\}$. Find $|\mathcal{S}|$.

Step 1. Size of the universe

$|X| = 6$.

So $X \times X$ has $36$ ordered pairs.

Step 2. Reflexivity

Reflexive means we must include all $(x,x)$ pairs.

So there are 6 forced elements.

So any reflexive relation on $X$ automatically contains:

$ \{(a,a),(b,b),(c,c),(d,d),(e,e),(f,f)\}. $

So our reflexive relation starts with 6 elements.

Step 3. Symmetry

For off-diagonal elements:

If we include $(x,y)$ (for $x \neq y$), we must also include $(y,x)$.

So these off-diagonal pairs come in symmetric pairs (each of size 2).

There are $\binom{6}{2} = 15$ distinct unordered pairs $\{x,y\}$, each would correspond to either including both $(x,y)$ and $(y,x)$, or excluding both. So think of them as independent choices.

Step 4. Required size

Total size should be 10.

We already have 6 diagonal pairs.

So we need 4 more pairs.

But each symmetric pair contributes 2 elements.

So to get 4 additional, we must include exactly 2 symmetric pairs.

Step 5. Counting

Number of unordered pairs = 15.

We must choose 2 of them to include.

So total = $\binom{15}{2} = 105$.

Final Answer:

$ |\mathcal{S}| = \boxed{105} $

$|a-b| \geq 2 \text { or }|b-a|=2$

Total

$\begin{array}{lll} a=1 & b=3,4,5,6 & 8 \\ a=2 & b=4,5,6 & 6 \\ a=3 & b=5,6 & 4 \\ a=4 & b=6 & 2 \\ \text { sum }=20 \end{array}$

$\begin{aligned} & \mathrm{n}(\mathrm{X})={ }^{20} \mathrm{C}_6={ }^{\mathrm{m}} \mathrm{C}_6 \\ & \mathrm{~m}=20 \end{aligned}$

given $|a-b| \geq 2$ so if

i.e. Total elements in X is ${ }^{20} \mathrm{C}_6$

Now for $\mathrm{n}(\mathrm{Y})$, range of R has exactly one element i.e. second elements must be constant in R and since R must have 6 element so it is not possible to satisfy both condition so $\mathrm{n}(\mathrm{Y})=0$.

$\begin{aligned} \text { for } \quad \mathrm{n}(\mathrm{z}) \quad & 1 \rightarrow 3,4,5,6 \\ & 2 \rightarrow 4,5,6 \\ & 3 \rightarrow 1,5,6 \\ & 4 \rightarrow 1,2,6 \\ & 5 \rightarrow 1,2,3 \\ & 6 \rightarrow 1,2,3,4 \end{aligned}$

no. of relation that are function will be

$\begin{aligned} & ={ }^4 \mathrm{C}_1 \times{ }^3 \mathrm{C}_1 \times{ }^3 \mathrm{C}_1 \times{ }^3 \mathrm{C}_1 \times{ }^3 \mathrm{C}_1 \times{ }^4 \mathrm{C}_1 \\ & =(4 \times 3 \times 3)^2=\mathrm{k}^2 \\ & \text { i.e. } \mathrm{k}=36 \end{aligned}$

$\matrix{ x & y & z \cr 2 & 3 & 4 \cr {{{\overline S }_1}} & {{{\overline S }_2}} & {} \cr }$

C-i) When x does not contain S$_1$, but contains S$_2$

$\mathop {{}^7{C_1}}\limits_{for\,x} \times \mathop {{{7!} \over {3!4!}}}\limits_{for\,y,z} = 245$

C-ii) When x does not contain $\mathrm{S}_1, \mathrm{~S}_2$ and y does not contain $\mathrm{S}_2$

i.e. $\mathop {{}^7{C_2}}\limits_{for\,x} \times \mathop {{{6!} \over {3!3!}}}\limits_{for\,y,z} = 420$

so total No. of ways 665

This is a 4-digit integer whose 0th digit called D, 10th digit called C, 100th digit called B and 1000th digit called A.

Given range for possible number is 2022 to 4482.

So, position A can have digits 2, 3 or 4.

0, 6 and 7 can't put in A as number starts with 0, 6 or 7 don't fall in the range between 2022 to 4482.

So, Position A can be filled with 2, 3 or 4 in ${}^3{C_1} = 3$ ways.

Position B can be filled by one of 0, 2, 3, 4, 6, 7

So, total possible ways for position B = ${}^6{C_1} = 6$ ways

Similarly, Position C can be filled in ${}^6{C_1} = 6$ ways

Position D can be filled in ${}^6{C_1} = 6$ ways

$\therefore$ Total possible integer numbers starting with 2 or 3 or 4

$ = 3 \times 6 \times 6 \times 6 = 3 \times 216 = 648$

Now lets find those numbers which starts with 2 and 4 but don't fall in the range between 2022 to 4482.

Situation 1 :

$\therefore$ Total possible numbers starting with 200 are = 6

Situation 2 :

$\therefore$ Total possible number in this case = 1

Situation 3 :

$\therefore$ Total numbers in this case $ = 2 \times 6 \times 6 = 72$

$\therefore$ Total number that don't fall in the range 2022 to 4482 which starts with 2 or 4 are

$= 6 + 1 + 72 = 79$

$\therefore$ Total numbers falls in the range 2022 to 4482

$=648-79$

$=569$

Given that no two persons sitting adjacent have hats of same colour. Also, hats of different colour cannot be used in 1 + 1 + 3 combination because any three hats cannot be of same colour.

So, only possible combination due to circular arrangement is 2 + 2 + 1.

The given, formed word is of length 10.

It is given that x is the number of words where no letter is repeated.

Also, it is given that y is the number of words where exactly one letter is repeated twice and no other letter is repeated. Therefore,

x = 10!

and y = ¹⁰C₁ $\times$ ¹⁰C₂ $\times$ ⁹C₈ $\times$ 8!

Thus, ${y \over {9x}} = {{{}^{10}{C_1} \times {}^{10}{C_2} \times {}^9{C_8} \times 8!} \over {9 \times 10!}}$

Using ${}^n{C_r} = {{n!} \over {r!(n - r)!}}$, we get

${y \over {9x}} = {{\left[ {{{10!} \over {1!(10 - 1)!}} \times {{10!} \over {2!(10 - 2)!}} \times {{9!} \over {8!(9 - 8)!}} \times 8!} \right]} \over {9 \times 10!}}$

$ = {{10!} \over {9 \times 2!\, \times 8!}} = {{10 \times 9 \times 8!} \over {9 \times 2 \times 8!}} = {{10} \over 2} = 5$ [Using $n! = n(n - 1)(n - 2)......1!$]

Number of blue lines $=n=$ number of sides of polygon so formed.

Number of red lines $={ }^n C_2-n$.

Thus, by joining $n$ points (not more than 2 on a line) there are ${ }^n C_2$ lines formed because for each line two points are required.

Also, red lines come after excluding sides of polygon.

Therefore, $n={ }^n C_2-n$

or ${ }^n C_2=2 n$

$\frac{n(n-1)}{2}=2 n$

or $n-1=4 (\because n \neq 0)$

$\therefore n=5$

Given, the set of eight vectors

$\mathrm{V}=\{a \hat{i}+b \hat{j}+c \hat{k}: a, b, c \in\{-1,1\}\} .$

Now, the eight vectors are $\hat{i}+\hat{j}+\hat{k}, \hat{i}+\hat{j}-\hat{k}$,

$\begin{aligned} & \hat{i}-\hat{j}+\hat{k},-\hat{i}+\hat{j}+\hat{k}, \hat{i}-\hat{j}-\hat{k}, \\ & -\hat{i}+\hat{j}-\hat{k},-\hat{i}-\hat{j}+\hat{k} \text { and }-\hat{i}-\hat{j}-\hat{k} . \end{aligned}$

Here, $\hat{i}+\hat{j}+\hat{k}$ and $-\hat{i}-\hat{j}-\hat{k}, \hat{i}+\hat{j}-\hat{k}$ and $-\hat{i}-\hat{j}+\hat{k}, \hat{i}-\hat{j}+\hat{k}$ and $-\hat{i}+\hat{j}-\hat{k},-\hat{i}+\hat{j}+\hat{k}$ and $\hat{i}-\hat{j}-\hat{k}$ are collinear vectors.

$\begin{aligned} \text{Let} \quad & \mathrm{S}_1=\{\hat{i}+\hat{j}+\hat{k},-\hat{i}-\hat{j}-\hat{k}\}, \\ & \mathrm{S}_2=\{\hat{i}+\hat{j}-\hat{k},-\hat{i}-\hat{j}+\hat{k}\}, \\ & \mathrm{S}_3=\{\hat{i}-\hat{j}+\hat{k},-\hat{i}+\hat{j}-\hat{k}\} \text { and } \\ & \mathrm{S}_4=\{-\hat{i}+\hat{j}+\hat{k}, \hat{i}-\hat{j}-\hat{k}\} \end{aligned}$

For the set of three non - coplanar vector, we have to select three set out of $\mathrm{S}_1, \mathrm{~S}_2, \mathrm{~S}_3, \mathrm{~S}_4$ and select one vector in every selected set of $\mathrm{S_1, S_2}, \mathrm{S}_3, \mathrm{~S}_4$

$\begin{aligned} & \Rightarrow{ }^4 C_3 \cdot{ }^2 C_1 \cdot{ }^2 C_1{ }^2 C_1=2^p \\ & \Rightarrow \quad 4.2 .2 .2=2^p \\ & \Rightarrow \quad 2^5=2^p \\ & \Rightarrow \quad p=5 \\ \end{aligned}$

Hints :

Recall that $\hat{i}+\hat{j}+\hat{k}$ and $-\hat{i}-\hat{j}-\hat{k}, \hat{i}+\hat{j}-\hat{k}$ and $-\hat{i}-\hat{j}+\hat{k}, \hat{i}-\hat{j}+\hat{k}$ and $-\hat{i}+\hat{j}-\hat{k},-\hat{i}+\hat{j}+\hat{k}$ and $\hat{i}-\hat{j}-\hat{k}$ are collinear vectors.

To solve this problem, we need to find the integer points $\left( {x,\,y,\,z} \right)$ that satisfy the given system of homogeneous equations:

$\matrix{ {3x - y - z = 0} \cr { - 3x + z = 0} \cr { - 3x + 2y + z = 0} \cr }$

Firstly, let’s solve for $z$ in terms of $x$ from the second equation:

$ - 3x + z = 0 \Rightarrow z = 3x $

Next, substitute $z = 3x$ into the first equation:

$ 3x - y - 3x = 0 \Rightarrow -y = 0 \Rightarrow y = 0 $

With $y = 0$ and $z = 3x$, the third equation also should be satisfied. Let's substitute $y$ and $z$ back into the third equation to verify:

$ - 3x + 2y + z = 0 \Rightarrow - 3x + 2(0) + 3x = 0 $

This equation holds true, confirming that the solutions for $y$ and $z$ remain consistent. Therefore, the points that satisfy the given system are of the form:

$\left( x,\,0,\,3x \right)$

Additionally, we need $x^2 + y^2 + z^2 \le 100$. Substituting $y = 0$ and $z = 3x$, we get:

$ x^2 + 0^2 + (3x)^2 \le 100 $

This further simplifies to:

$ x^2 + 9x^2 \le 100 $

$ 10x^2 \le 100 $

$ x^2 \le 10 $

Hence, $ -\sqrt{10} \le x \le \sqrt{10} $

Since $x$ must be an integer, we evaluate acceptable values for $x$:

$x \in \{-3,\,-2,\,-1,\,0,\,1,\,2,\,3\}$

For each of these values, let’s determine the corresponding points $\left( x,\,0,\,3x \right)$:

• $( -3,\,0,\,-9 )$
• $( -2,\,0,\,-6 )$
• $( -1,\,0,\,-3 )$
• $( 0,\,0,\,0 )$
• $( 1,\,0,\,3 )$
• $( 2,\,0,\,6 )$
• $( 3,\,0,\,9 )$

Thus, there are a total of 7 such points.

Therefore, the number of integer-coordinate points $\left( x,\,y,\,z \right)$ satisfying the given system of equations and the condition $x^2 + y^2 + z^2 \le 100$ is 7.