# 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?

• Can you explain what is a superkey? I cannot follow your question. – Yuval Filmus Nov 5 '16 at 21:38
• A superkey is a combination of columns that uniquely identifies any row within a relational database management system (RDBMS) table. A candidate key is a minimal superkey i.e. superkey reduced to the minimum number of columns required to uniquely identify each row. Thus adding any nonkey attribute to candidate key gives us superkey (as it looses its minimality). – anir Nov 6 '16 at 5:32
• ohhh ohhh very sorry I miss-written $\times$ for $+$, now modified – anir Nov 6 '16 at 8:26
• This is just basic combinatorics. Your question is only accidentally related to databases. I suggest that you adjust the tags accordingly. – André Souza Lemos Nov 6 '16 at 14:04
• Rather than just leaving clarifications in the comments, please edit the question to include all relevant information in the question body itself. Comments exist only to help you improve the question and can disappear at any time. We want questions to be self-contained, so people don't have to read the comment thread to understand what you are asking. Thank you! – D.W. Nov 6 '16 at 18:28

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$

• damn this is so beautifully explained... – anir Nov 12 '16 at 19:55