Finding alternative way of combinatorial counting The question is related to databases:


  There is a relation $R(A_1,A_2,...,A_n)$. Every $(n-2)$ attributes of $R$ forms candidate key. Number of superkeys of $R$ are?


I thought if any one of the $(n-2)$ attribute combinations is chosen then the number of superkeys that can be formed with it will be 4, as there will be $2^2$ combinations of remaining two attributes. So I gave answer $nC_{n-2}\times 2^2$.

But then the answer given was $nC_{n-2} + nC_{n-1}+ nC_{n}$ which is also quite obvious. But then I realized that my solution does not equate to this one and that my solution count certain superkeys more than once. 

However I am not able to form an equation of the count of those duplicate superkeys so that I can subtract it from $nC_{n-2}\times 2^2$ in order to get another expression for the solution (somewhat inclusion-exclusion approach). What is that expression/equation which counts those duplicate superkeys?
The correct answer can be rewritten as $\frac{n(n-1)}{2} + n + 1$.

Let's call the two remaining attributes $A_k$and $A_l$.

You are counting each combination of $nC_{n-2}$ candidate keys four times: (1) when they are alone, (2) when they are with $A_k$, (3) when they are with $A_l$, (4) when they are with both $A_k$ and $A_l$.

Your formula then boils down to the following sum:

$nC_{n-2} + nC_{n-2} + nC_{n-2} + nC_{n-2}$

The problem is that you are counting each combination in case (2) an excessive number of times, because each $A_k$ appears in $n-2$ additional identical combinations, when it is taken as a part of the candidate key. The same is true for case (3).

There is just one singular combination in case (4), the one with all attributes.

The corrected version of you formula is then:

$nC_{n-2} + \frac{nC_{n-2}}{n-1} + \frac{nC_{n-2}}{n-1} + \frac{nC_{n-2}}{nC_{n-2}}=\frac{n(n-1)}{2} + \frac{n}{2} + \frac{n}{2} + 1=\frac{n(n-1)}{2} + n + 1$