4
$\begingroup$

Problem: Let $A_n=\{ 1,2,...,n \}$. We define the ordered triplet $(A,B,C)$ as good if $A \cup B \cup C = A_n$ and $\operatorname{card}(A \cap B \cap C)=2$ (so the intersection has exactly $2$ elements). Let $p_n$ be the number of such interesting pairs.

Is there a formula for $p_n$, and if so, is the fraction $\frac{p_{n+1}}{p_n}$ constant?

Question: I have created a very simple backtrack algorithm that calculated $p_3=18$, $p_4=216$ and $p_5=2160$. I don't see any obvious formula for this, as it may be an arithmetic progression. It is clear that the number of possbible intersections $A \cap B \cap C$ is $n(n-1)/2$. So the question remains in how many possible ways can we arrange such sets such that they will all include at least once all the elements.

Can someone shed some light on what theoretical notion I am forgetting about, and give a hint for the solution? Any help would be appreciated.

$\endgroup$

1 Answer 1

5
$\begingroup$

The answer is $p_n= 6^{n-2}{n\choose 2}$.

As you noticed, all possible intersections of $A,B,C$ are the possible two-element subsets of $\{1,...,n\}$, which are ${n\choose 2} = n(n-1)/2$.

To distribute the other $n-2$ elements we need to choose whether each of them belongs exclusively to $$ A,B,C, $$ or to $$ A\cap B,A\cap C,B\cap C. $$ These 6 possibilities for each of the remaining $n-2$ elements are all disjoint and cover all possible cases exactly once, yielding the other factor $6^{n-2}$.

$\endgroup$
0

You must log in to answer this question.