How to count permutations with restrictions on how items are grouped I am trying to solve the following problem:

A town contains $4$ people who repair televisions. If $4$ sets break down, what is the probability that exactly $i$ of the repairers are called? Solve the problem for $i=1,2,3,4$.

For $i=1$, there are ${}_4P_1$ ways to assign $1$ person to $4$ televisions, so the probability is $\frac{{}_4P_1}{4^4}=\frac{1}{64}$.
For $i=4$, there are ${}_4P_4$ ways to assign $4$ people to $4$ televisions, so the probability is $\frac{{}_4P_4}{4^4}=\frac{3}{32}$.
I am having trouble with $i=2,3$. How should I go about these cases?
 A: Conditions:


*

*The repairmen and TVs are distinct.

*Every TV owner calls ONLY one repairman, that is, the relationship between the set of TVs, $T$, and a set that contains $i$ of the repairmen, $Ri$, is functional, $f: T -> Ri$. Note that $|T|=4$ and $|Ri|=i$

*Every one of the $i$ repairmen gets at least one call, that is the range of $f$ is $Ri$.


The size of the sample space is $|S| = 4^4 = 256$.
$i = 2$:
There are $\binom{4}{2}=6$ ways to select two repairmen. Due to conditions #2 and #3, each repairman can get 1 OR 2 OR 3 calls, for the other will get the remaining calls; therefore, there are $\binom{4}{1} + \binom{4}{2} + \binom{4}{3} = 14$ ways for each repairman to get calls. 
You can also argue as follows to obtain the same result: To satisfy conditions #1, #2 and #3, the number of calls can be divided between the two repairmen in one of the following ways: 1|3, 2|2, or 3|1; This is the same way we must partition the set of TVs. Using multinomial coefficients, these partitions can be counted in $\binom{4}{1,3}+\binom{4}{2,2}+\binom{4}{3,1}=14$ ways.  
Hence $P\{i=2\} = (6*14)/256 = 84/256$.
$i = 3$:
There are $\binom{4}{3} = 4$ ways to select the repairmen. A repairman can get 1 OR 2 calls, for the other two repairmen will get the remaining calls.  
If a repairman gets 1 (out of 4) call, the second repairman can get either 1 OR 2 (out of remaining 3) calls, and the third repairman gets the remaining calls. This can be counted in$\binom{4}{1}\binom{3}{1} + \binom{4}{1}\binom{3}{2}=24$ number of ways. 
If a repairman gets 2 (out of 4) calls, the second repairman can only get 1 (out of 2) call, and the third repairman gets the remaining call. This can be counted in $\binom{4}{2}\binom{2}{1}=12$ number of ways. 
Therefore, the total number of ways the repairmen are called is $24+12=36$.
The same result can be more succinctly obtained by multinomial coefficients: $\binom{4}{1,1,2}+\binom{4}{1,2,1}+\binom{4}{2,1,1}=36$.
Hence $P\{i=3\} = (4*36)/256 = 36/64$.
A: For $i=2$, there are $\binom{4}{2}$ ways to choose $2$ repairers.
Once $2$ repairers are chosen, you want to partition the set of $4$ televisions into $2$ subsets. This is known as the Stirling number of the second kind, denoted by $S(4,2)$, and there are $7$ ways to do this. Since the order of the subsets does not matter, multiply by $2!$. This is known as counting the number of surjective functions from the set of television sets to the set of repairers.
So, the probability for $i=2$ is $\binom{4}{2}S(4,2)2!/4^4=\frac{21}{64}$.
This reasoning also works for $i=1,3,4$.
Note: technically, there are ${}_4P_i$ ways to assign $4$ televisions to $i$ people, not the converse. However, it helps to think of the problem as assigning people to televisions, not televisions to people.
A: Suppose that $i=2$. There are $\binom42=6$ ways to choose which two repairers are called. Each of the $4$ owners of a broken TV can call either repairer, so there are $2^4=16$ ways for the owners to choose one of the $2$ repairers. However, two of those $16$ aren’t actually possible: the two cases in which all four owners call the same repairer. Thus, there are $14$ ways to assign the $2$ repairers to the $4$ TV sets. That’s a grand total of $6\cdot14=84$ different assignments out of the grand total of $4^4$.
The case $i=3$ can be worked similarly, though the bookkeeping to count only the assignments that actually use all $3$ of the chosen repairers is a little more complicated. You might want to read up on the inclusion-exclusion principle if you get stuck, and I’ll be happy to help if that proves insufficient.
A: *

*Probability that exactly 2 repairers are called.
There are two ways how two repairers are called:


*

*Both gets call for two broken sets each
First repairer $A$ can be anyone. Hence, will have probability $\frac{4}{4}=1$. The same repairer will be called for any one of 2nd, 3rd or 4th broken TV set. [Hence the total possible sequences can be 3 $(AABB,ABAB,ABBA)$.] At that time $A$ can be selected with probability $\frac{1}{4}$, that is, he should be same as first one. The 2nd repairer can be any one apart from $A$, Thus, the first call to 2nd repairer $B$ can happen with probability $\frac{3}{4}$. The 2nd call to $B$ can happen with probability $\frac{1}{4}$. Final probability $\frac{4}{4}\times\frac{3}{4}\times\frac{1}{4}\times\frac{1}{4}\times3$

*One gets call for three broken TV sets, while the other one gets call for 
remaining one broken set, then there are four ways:
$(AAAB,AABA,ABAA,BAAA)$.
Each one will have same probability as first bullet point. Hence final probability: $\frac{4}{4}\times\frac{3}{4}\times\frac{1}{4}\times\frac{1}{4}\times 4$. 
Final probability of 1st and 2nd bullet point combined: $\frac{4}{4}\times\frac{3}{4}\times\frac{1}{4}\times\frac{1}{4}\times 7 =\frac{21}{64}$


*Probability that exactly 3 repairers are called.
Let the three repairmen called be $A,B,C$.
There can be six sequences in which call are made for 1st, 3nd, 3rd and 4th broken TV sets: $(ABCA,ABAC,AABC,ABBC,ABCB,ABCC)$. First repairman can be called with probability $\frac{4}{4}$. Second new repairman can be called with probability $\frac{3}{4}$. Third new repairman can be called with probability $\frac{2}{4}$. Any repairman can be repeated with probability $\frac{1}{4}$. Final probability $=\frac{4}{4}\times\frac{3}{4}\times\frac{2}{4}\times\frac{1}{4}\times 6=\frac{36}{64}$

A: I approached the problem with the help of strings. Let each repairman is assigned a letter: A, B, C, D. We have four broken TV sets, so the string is four letters long. Then all possibilities are $4^4=256$, or in each of the four positions we can have each of our letters: AAAA, AAAB, AAAC, AAAD and so on. So basically we have to find how many possible strings exist where there is one letter only, two letters, three letters and all four letters.
(1) One letter only. This one is easy. Obviously there are only four possibilities - AAAA, BBBB, CCCC and DDDD. So the probability that only one repairman has been called is $4/256 = 1/64$.
(2) Two letters. This one is a bit trickier. We can divide this case in two distinct possibilities.
2.1. Two pairs or $2+2$. For example AABB or CACA. There are six combinations of two letters (AB, AC, AD, BC, BD and CD). For each combination there are six ways the letters can be ordered, for example AABB, ABAB, ABBA (Mamma mia, it is a long answer), BBAA, BABA, BAAB. So the total number of possibilities for two pairs is $6\times 6=36$.
2.2. Triple and single, or $3+1$. For example AAAB. The letter that is repeating three times can be one of four possible. Each triple can be combined with one of three remaining letters. And the single letter can be in any of four positions of the string, like BAAA, ABAA, AABA and AAAB. So $4\times 3\times 4=48$.
$36+48 = 84$, so the probability that two repairmen are called is $84/256$ or $21/64$.
(3) Three letters. This means that there is one repeating letter and the two remaining must be different from it AND different from each other (this one often gets me). The repeating letter can be one of four. The combinations of its two positions in the string are six, for example AA$**$, A$*$A$*$, A$**$A, $*$AA$*$, $*$A$*$A, $**$AA. The first remaining letter can be one of three and the second remaining letter can be one of two. So in total $4\times 6\times 3\times 2 = 144$. The probability that three repairmen are called is $144/256$ or $36/64$.
(4) All four letters. This is easy again $-$ it is just the permutations of four letters, as they all need to be represented exactly once in the four-letter string. Permutations are $4! = 24$. The probability that all four repairmen are called is $24/256$ or $6/64$.
Let's see if all numerators add up to $64$ $-$ $1+21+36+6 = 64$. And wee aaaare done.
