Let $(X, Y ) \in P(\{1, ..., n\})^2$, then I need to find the number of couple : $(X, Y)$ such that : $$\mid X \cap Y \mid = 1 $$
I don't know how to find a general formula. The case $n =2$ gives me $6$ couples, and for $n=3$ I get $27$ couples, yet how to get a general formula from this ?
I tried todraw diagrams and test litlle cases but it doesn't seem to work at.
There are $\binom{n}{k}$ subsets $Z$ of $E=\{1,\dots,n\}$ with $k$ elements. And $\binom{n-k}{l-k}$ subsets $X$ with $l$ elements so that $Z\subset X$. Then, to have $X\cap Y =Z$ , we must have $Z\subset Y \subset Z\cup \overline{X}$ where $\overline{X} = E\setminus X$ so there are $2^{n-l}$ possible $Y$. Thus, the number of possible couples $(X,Y)$ so that $X\cap Y=Z$ is: $$ \sum_{l=k}^n \binom{n-k}{l-k}2^{n-l} = (1+2)^{n-k} = 3^{n-k} $$ So the answer to your question is $n3^{n-1}$ (because there are $n$ possible $Z$) but we may go a little further and notice that: $$ \sum_{X,Y\subset E} |X\cap Y| = \sum_{k=0}^n k\binom{n}{k}3^{n-k}=n4^{n-1} $$