Count the number of subsets where no two elements have sum equal to $n + 1$

combinatoricsdiscrete mathematics

I'm given a set of $n$ integers, where the integers are numbered from $1$ to $n$.

For example if $n = 3$, the set would be $\{1, 2, 3\}$.

The question is: how many subsets don't have a pair whose sum = $n + 1$.

If I consider all subsets of $n = 3$, $\{\}$, $\{1\}$, $\{2\}$, $\{3\}$, $\{1, 2\}$, $\{2, 3\}$, $\{1, 3\}$, $\{1, 2, 3\}$.

In this case the number of subsets in the above condition is $6$ because I excluded $\{1, 3\}$, $\{1, 2, 3\}$ and there exists a pair add up to $n + 1$, which is $(1, 3)$. I noticed that the number of pairs whose sum add up to $n + 1$ = $\lfloor{\frac{n}{2}}\rfloor$.

Best Answer

To make such a subset, for each of pair that sums to $n+1$, you have to decide between $3$ options: Include the only lower number, include only the higher number, or not include any of them. This gives a total of $$ 3^{\lfloor n/2\rfloor} $$ options.

When $n$ is odd, you also have the number $\frac{n+1}2$ which is not part of any pair. This one you can freely decide whether to include.

So all in all, we get $$ \text{Number of such subsets} = \cases{3^{n/2} & if $n$ is even\\ 2\cdot 3^{(n-1)/2} & if $n$ is odd} $$

Related Question