Combination Practice Questions

We are given a set $U$ of $n$ elements, and two subsets $A$ and $B$ such that $|A| = |B| = k$ and $A \cap B = \phi$.
A permutation separates $A$ from $B$ if either all elements of $A$ appear before all elements of $B$, or all elements of $B$ appear before all elements of $A$.
Case 1: All elements of $A$ appear before all elements of $B$.
First, choose $k$ positions for elements of $A$ and $k$ positions for elements of $B$ from the $n$ available positions. This can be done in $\binom{n}{2k}$ ways.
Within these $2k$ chosen positions, the $k$ elements of $A$ must occupy the first $k$ positions, and the $k$ elements of $B$ must occupy the next $k$ positions.
The $k$ elements of $A$ can be arranged in $k!$ ways, and the $k$ elements of $B$ can be arranged in $k!$ ways.
The remaining $n-2k$ elements (from $U \setminus (A \cup B)$) can be arranged in $(n-2k)!$ ways in the remaining $n-2k$ positions.
So, the number of permutations for Case 1 is $\binom{n}{2k} (k!)^2 (n-2k)!$.
Case 2: All elements of $B$ appear before all elements of $A$.
Similarly, the number of permutations for Case 2 is $\binom{n}{2k} (k!)^2 (n-2k)!$.
The total number of permutations that separate $A$ from $B$ is the sum of permutations from Case 1 and Case 2:
Total = $2 \times \binom{n}{2k} (k!)^2 (n-2k)!$.

The problem asks for the number of arrangements of six identical balls in three identical bins.
Since the balls are identical, their specific identities don't matter, only the count in each bin.
Since the bins are identical, the order of the bins doesn't matter. For example, (3, 2, 1) is the same arrangement as (1, 2, 3) or (2, 3, 1).
This is a problem of integer partitions of 6 into 3 parts (or fewer, implicitly, as some bins can be empty).
We need to find distinct ways to sum three non-negative integers to 6, where the order of the integers doesn't matter.
Let the number of balls in the three bins be $n_1, n_2, n_3$ such that $n_1 + n_2 + n_3 = 6$ and $n_1 \ge n_2 \ge n_3 \ge 0$.
The partitions are:

1. $6 + 0 + 0 = 6 \Rightarrow (6, 0, 0)$
2. $5 + 1 + 0 = 6 \Rightarrow (5, 1, 0)$
3. $4 + 2 + 0 = 6 \Rightarrow (4, 2, 0)$
4. $4 + 1 + 1 = 6 \Rightarrow (4, 1, 1)$
5. $3 + 3 + 0 = 6 \Rightarrow (3, 3, 0)$
6. $3 + 2 + 1 = 6 \Rightarrow (3, 2, 1)$
7. $2 + 2 + 2 = 6 \Rightarrow (2, 2, 2)$
   These are all the distinct partitions of 6 into 3 parts (allowing 0 parts).
   There are 7 such arrangements.

Let the three distinct computers be A, B, and C, and the six distinct jobs be $J_1, \dots, J_6$ ordered by difficulty.
The toughest job is assigned to the fastest computer (1 way), and the easiest job to the slowest computer (1 way).
This leaves 4 remaining jobs to be assigned to the 3 computers, with the constraint that every computer gets at least one job.
The total number of ways to assign the 4 remaining jobs to 3 computers is $3^4$.
We subtract cases where computer C gets no jobs, which means the 4 jobs are assigned to A or B, in $2^4$ ways.
The number of ways is $3^4 - 2^4 = 81 - 16 = 65$.

The problem asks for the number of derangements of the letters LILAC, with the two 'L's being indistinguishable. This means no character should be in its original position.

1. Identify the distinct characters and their counts:
   The letters are L, I, L, A, C.
   Distinct characters: L, I, A, C.
   Counts: L (2), I (1), A (1), C (1).
   The total number of positions is 5.

2. Handle the indistinguishable 'L's:
   Since the two 'L's are indistinguishable, we consider the possible positions for the 'L's first. No 'L' can be in position 1 or 3 (their original positions). So, the two 'L's must be placed in any two of the remaining positions (2, 4, 5).

3. Calculate combinations for 'L' positions:
   The number of ways to choose 2 positions for the 'L's from positions {2, 4, 5} is $\binom{3}{2} = 3$.
   These combinations are: (2, 4), (2, 5), and (4, 5).

4. Derange the remaining characters for each case:

   • Case 1: L's in positions 2 and 4.
     The remaining characters are I, A, C, and their original positions are 1, 3, 5.
     The available positions for I, A, C are 1, 3, 5.
     I cannot be in position 2 (now occupied by L). A cannot be in position 4 (now occupied by L). C cannot be in position 5.
     However, the problem statement means "original position" based on the input string "LILAC". So, I cannot be in 2nd position, A cannot be in 4th position, C cannot be in 5th position.
     The original positions of I, A, C are 2, 4, 5.
     We need to place I, A, C in positions {1, 3, 5} such that I $\neq$ 2, A $\neq$ 4, C $\neq$ 5.
     If L is in pos 2 and 4, then I, A, C must be placed in 1, 3, 5.
     Original positions of I, A, C are 2, 4, 5 respectively.
     For I, position 1, 3, 5 are available. A for 1, 3, 5. C for 1, 3, 5.
     A derangement is needed for (I, A, C) in (1, 3, 5) with respect to their original positions (2, 4, 5). This is a standard derangement of 3 items, which is $D_3 = 2$.
     Specifically, for (I, A, C) and available positions (1, 3, 5) where 'L's are at 2 and 4:
     Original mapping: L1->1, I->2, L2->3, A->4, C->5.
     If L's are in pos 2 and 4, then L1 is not at 1, L2 is not at 3. This condition is met for these L's.
     The characters to be placed are (I, A, C). Their original positions are (2, 4, 5). The available positions are (1, 3, 5).
     We need to place I, A, C in (1, 3, 5) such that:
     I is not in its original position (2) -- always true as 2 is occupied by L.
     A is not in its original position (4) -- always true as 4 is occupied by L.
     C is not in its original position (5).
     So, we need to arrange I, A, C in (1, 3, 5) such that C is not in position 5.
     Possible arrangements for (I, A, C) in (1, 3, 5):
     (I, A, C) -> (1, 3, 5) : C at 5 (invalid)
     (I, C, A) -> (1, 3, 5) : C not at 5 (valid)
     (A, I, C) -> (1, 3, 5) : C at 5 (invalid)
     (A, C, I) -> (1, 3, 5) : C not at 5 (valid)
     (C, I, A) -> (1, 3, 5) : C not at 5 (valid)
     (C, A, I) -> (1, 3, 5) : C not at 5 (valid)
     There are $3! = 6$ total permutations. Those where C is at 5 are (I,A,C) and (A,I,C). So, $6 - 2 = 4$ valid arrangements.

   • Case 2: L's in positions 2 and 5.
     I, A, C need to be placed in positions {1, 3, 4}.
     Original positions of I, A, C are 2, 4, 5 respectively.
     I is not in 2 (occupied). A is not in 4. C is not in 5 (occupied).
     We need to arrange I, A, C in (1, 3, 4) such that A is not in 4.
     Total arrangements $3! = 6$. Arrangements where A is at 4: (I, A, C) -> (1, 4, 3) (A at 4) and (C, A, I) -> (1, 4, 3) (A at 4).
     So, $6 - 2 = 4$ valid arrangements.

   • Case 3: L's in positions 4 and 5.
     I, A, C need to be placed in positions {1, 2, 3}.
     Original positions of I, A, C are 2, 4, 5 respectively.
     I cannot be in 2. A cannot be in 4 (occupied). C cannot be in 5 (occupied).
     We need to arrange I, A, C in (1, 2, 3) such that I is not in 2.
     Total arrangements $3! = 6$. Arrangements where I is at 2: (A, I, C) -> (1, 2, 3) (I at 2) and (C, I, A) -> (1, 2, 3) (I at 2).
     So, $6 - 2 = 4$ valid arrangements.

5. Total permutations:
   Total permutations = (Number of ways to place L's) $\times$ (Number of ways to derange remaining letters for each case)
   Total = $3 \times 4 = 12$.

The provided solution gives a more direct approach by considering placing L's and then deranging I, A, C.
"First L's can be arranged in 3 positions 2, 3, or 5 in $\binom{3}{2} = 3$ ways as follows:
_ L _ L _
_ L _ _ L
_ _ _ L L
Now the letters I, A, C can be deranged in 2 $\times$ 2! ways. Example in _ L _ L _. C cannot occupy 5th position, so only 2 ways. Remaining I and A can be arranged in remaining 2 position in 2! ways = 2 ways. So answer is 3 $\times$ 2 $\times$ 2! = 12."

Let's re-interpret the solution's logic. It seems to count derangements differently.
Consider the positions 1, 2, 3, 4, 5. Original characters are L1, I, L2, A, C.
If L's are in positions 2 and 4, the pattern is X L X L X.
The original positions of L's are 1 and 3. So, L1 is not in 1, L2 is not in 3. This condition is met if L's are in (2,4), (2,5), or (4,5).
For the remaining characters I, A, C, their original positions are 2, 4, 5. The available positions are 1, 3, 5.
We need to assign I, A, C to (1, 3, 5) such that:
I $\neq$ 2 (original pos).
A $\neq$ 4 (original pos).
C $\neq$ 5 (original pos).

Let's use the solution's method:
Total positions: 5.
Original arrangement: LILAC (pos: 1 2 3 4 5)
L's cannot be at position 1 or 3.
There are 3 choices for the positions of the two L's (which are indistinguishable): (2,4), (2,5), (4,5).

Case 1: L's are in positions 2 and 4. (Pattern: X L X L X)
The characters to be placed are I, A, C in positions 1, 3, 5.
Original positions of I, A, C are 2, 4, 5 respectively.
We need: I $\neq$ 2, A $\neq$ 4, C $\neq$ 5.
Since L's are in 2 and 4, I $\neq$ 2 and A $\neq$ 4 are automatically satisfied as 2 and 4 are filled by Ls.
So, we only need to ensure C $\neq$ 5.
Permutations of {I, A, C} in {1, 3, 5}:
Total $3! = 6$.
Those where C is in position 5 (invalid):
(I, A, C) -> (1, 3, 5)
(A, I, C) -> (1, 3, 5)
Number of invalid = $2! = 2$.
Valid = $6 - 2 = 4$.

Case 2: L's are in positions 2 and 5. (Pattern: X L X X L)
The characters to be placed are I, A, C in positions 1, 3, 4.
Original positions of I, A, C are 2, 4, 5 respectively.
We need: I $\neq$ 2, A $\neq$ 4, C $\neq$ 5.
I $\neq$ 2 and C $\neq$ 5 are automatically satisfied.
So, we only need to ensure A $\neq$ 4.
Permutations of {I, A, C} in {1, 3, 4}:
Total $3! = 6$.
Those where A is in position 4 (invalid):
(I, C, A) -> (1, 3, 4)
(C, I, A) -> (1, 3, 4)
Number of invalid = $2! = 2$.
Valid = $6 - 2 = 4$.

Case 3: L's are in positions 4 and 5. (Pattern: X X X L L)
The characters to be placed are I, A, C in positions 1, 2, 3.
Original positions of I, A, C are 2, 4, 5 respectively.
We need: I $\neq$ 2, A $\neq$ 4, C $\neq$ 5.
A $\neq$ 4 and C $\neq$ 5 are automatically satisfied.
So, we only need to ensure I $\neq$ 2.
Permutations of {I, A, C} in {1, 2, 3}:
Total $3! = 6$.
Those where I is in position 2 (invalid):
(A, I, C) -> (1, 2, 3)
(C, I, A) -> (1, 2, 3)
Number of invalid = $2! = 2$.
Valid = $6 - 2 = 4$.

Summing up the valid arrangements from all three cases: $4 + 4 + 4 = 12$.

The solution's reasoning "Now the letters I, A, C can be deranged in 2 $\times$ 2! ways. Example in _ L _ L _. C cannot occupy 5th position, so only 2 ways. Remaining I and A can be arranged in remaining 2 position in 2! ways = 2 ways. So answer is 3 $\times$ 2 $\times$ 2! = 12."
This part is a bit condensed. Let's break it down for the first case: L's in positions 2 and 4.
Available positions for (I, A, C) are (1, 3, 5). Original positions for (I, A, C) are (2

This problem requires the Principle of Inclusion-Exclusion for three sets. We want to find the number of integers from 1 to 500 divisible by 3, 5, or 7.
Let $N_k$ be the count of numbers divisible by $k$. The formula is:
$|D_3 \cup D_5 \cup D_7| = N_3 + N_5 + N_7 - (N_{15} + N_{21} + N_{35}) + N_{105}$

Calculating each term using floor division:
$N_3 = \lfloor 500/3 \rfloor = 166$
$N_5 = \lfloor 500/5 \rfloor = 100$
$N_7 = \lfloor 500/7 \rfloor = 71$
$N_{15}=33, N_{21}=23, N_{35}=14, N_{105}=4$

The total is $(166+100+71) - (33+23+14) + 4 = 337 - 70 + 4 = 271$.

To find the number of divisors of 2100, we first determine its prime factorization.
$2100 = 21 \times 100 = (3 \times 7) \times (10^2) = 3^1 \times 7^1 \times (2 \times 5)^2$
This gives the prime factorization as $2^2 \times 3^1 \times 5^2 \times 7^1$.
The total number of divisors is found by adding 1 to each exponent and multiplying the results:
Number of divisors = $(2+1)(1+1)(2+1)(1+1) = 3 \times 2 \times 3 \times 2 = 36$.

This problem is equivalent to finding the number of ways to choose 4 digits from the set {1, 2, 3} with repetition allowed. Since the digits must be in non-decreasing order, the selection of any 4 digits uniquely determines the number. This is a combination with repetition problem. Using the stars and bars formula, $\binom{n+k-1}{k}$, where $n$ is the number of items to choose from (3) and $k$ is the number of choices (4).
$\binom{3+4-1}{4} = \binom{6}{4} = \frac{6!}{4!2!} = \frac{6 \times 5}{2} = 15$

To find the number of distinct positive integral factors of 2014, we first need to find its prime factorization.
$2014 = 2 \times 1007$
Now, we need to factorize 1007. We can test prime numbers:
$1007 \div 7 \approx 143.8$
$1007 \div 11 \approx 91.5$
$1007 \div 13 \approx 77.4$
$1007 \div 17 \approx 59.2$
$1007 \div 19 = 53$
Both 19 and 53 are prime numbers.
So, the prime factorization of 2014 is $2^1 \times 19^1 \times 53^1$.
For a number expressed as $p_1^{a_1} \times p_2^{a_2} \times \dots \times p_k^{a_k}$, the number of distinct positive factors is given by $(a_1+1)(a_2+1)\dots(a_k+1)$.
In this case, the exponents are 1, 1, and 1.
Thus, the number of factors is $(1+1)(1+1)(1+1) = 2 \times 2 \times 2 = 8$.

[CORRECT_OPTION: 8]

Let the weights of coins from bags 1 to 5 be $w_1, w_2, w_3, w_4, w_5$ respectively, where each $w_i \in \{10, 11\}$ gm.
The total weight is given by the sum of (number of coins from bag $i$) $\times$ ($w_i$).
So, the equation for the total weight is $1 \cdot w_1 + 2 \cdot w_2 + 4 \cdot w_3 + 8 \cdot w_4 + 16 \cdot w_5 = 323$.
Since all terms $2w_2, 4w_3, 8w_4, 16w_5$ are even, for the sum to be odd (323), $1w_1$ must be odd. This implies $w_1 = 11$.
Subtracting $1 \cdot 11 = 11$ from 323 gives $323 - 11 = 312$.
The remaining equation is $2w_2 + 4w_3 + 8w_4 + 16w_5 = 312$. Dividing by 2, we get $w_2 + 2w_3 + 4w_4 + 8w_5 = 156$.
Again, for the sum to be even (156), $w_2$ must be even, implying $w_2 = 10$.
Subtracting $1 \cdot 10 = 10$ from 156 gives $156 - 10 = 146$.
The remaining equation is $2w_3 + 4w_4 + 8w_5 = 146$. Dividing by 2, we get $w_3 + 2w_4 + 4w_5 = 73$.
For the sum to be odd (73), $w_3$ must be odd, implying $w_3 = 11$.
Subtracting $1 \cdot 11 = 11$ from 73 gives $73 - 11 = 62$.
The remaining equation is $2w_4 + 4w_5 = 62$. Dividing by 2, we get $w_4 + 2w_5 = 31$.
For the sum to be odd (31), $w_4$ must be odd, implying $w_4 = 11$.
Subtracting $1 \cdot 11 = 11$ from 31 gives $31 - 11 = 20$.
The remaining equation is $2w_5 = 20$, which implies $w_5 = 10$.
So, the bags with 11 gm coins are labelled 1, 3, and 4.
The product of their labels is $1 \times 3 \times 4 = 12$.

[CORRECT_OPTION: N/A]

Let $P_n$ be the number of $n$-pennants.
An $n$-pennant can either start with 1 or 2.
If it starts with 1, the remaining sum is $n-1$, which can be formed in $P_{n-1}$ ways.
If it starts with 2, the remaining sum is $n-2$, which can be formed in $P_{n-2}$ ways.
Thus, $P_n = P_{n-1} + P_{n-2}$. This is the Fibonacci sequence.
Given $P_1 = 1$ ({(1)}) and $P_2 = 2$ ({(2), (1,1)}).
Calculating terms: $P_3 = P_2 + P_1 = 2 + 1 = 3$. $P_4 = P_3 + P_2 = 3 + 2 = 5$. $P_5 = 5+3=8$. $P_6 = 8+5=13$. $P_7 = 13+8=21$. $P_8 = 21+13=34$. $P_9 = 34+21=55$. $P_{10} = 55+34=89$.

[CORRECT_OPTION: N/A]