Another way of counting probability A set $S = \{1, 2, \cdots, k\}$ is given. Two persons independently choose some numbers from this set. I want to count the probability that the cardinality of intersection of the chosen sets by both persons is exactly one.
Each person has to choose at least one number. A person can choose a number which is already chosen by another person. A number is being chosen independently and uniformly at random from the set.
My approach:
Fix one number from $1$ to $k$. Probability of both persons choosing that number is $\frac{1}{k^2}$. Remaining $k-1$ numbers can be chosen by either of both or by none of both. So, probability for that is $\left(1 - \frac{1}{k^2}\right)^{k-1}$. And that fixed number can be selected in ${k \choose 1}$ ways.
So, probability of required event is:
\begin{align}
P(E) = {k \choose 1} \frac{1}{k^2} \left(1 - \frac{1}{k^2}\right)^{k-1}
\end{align}
My questions:


*

*Is this reasoning correct?

*Initially I started with counting all the possible ways of choosing numbers by each person. Can we count the required probability by counting ways technique? Is there any other way of counting the probability?
 A: Your reasoning is not correct.
Let us at first ignore the condition that at least one number has to be chosen (that will get fixed afterwards). Under that condition, as each choice of each possible subset is equally likely (as you say in the comments), and for any given element there are exactly the same number of subsets containing and not containing that element (think of a subset and its complement!), the probability that a person chooses a given number is exactly $1/2$. Thus it's the same problem as if both people throw a coin for each number, and the question is what's the probability that they throw both head for exactly one of the numbers.
This is a fairly standard problem which I guess you can solve. Let's call the obtained probability $p_0$.
Now we have to fix this up for the condition that the empty set is not a valid choice. Fortunately this is easy, since when any party chose the empty set, we know for sure there was no number that was chosen by both (because at least one of them didn't chose a number to begin with).
Since the probability calculated in the previous step is
$$\frac{\text{Number of choices with exactly one shared number}}
{\text{Total number of choices when allowing empty sets}}$$
we have to just fix up the denominator, which we can do by multiplying with
$$\frac{\text{Total number of choices when allowing empty sets}}
{\text{Total number of choices when not allowing empty sets}}.$$
Now the total number of choices when allowing empty sets is $2^{2k}$ since there are $2^k$ subsets, and each person chooses one. When excluding the empty set, each player has one choice less (namely he cannot choose the empty set), and therefore without the empty set, the number of possible choices is $(2^k-1)^2$.
Therefore we have for the requested probability:
$$p = \frac{2^{2k}}{(2^k-1)^2}p_0$$
