0
$\begingroup$

I have this question in my combinatorics course. Find the number of subsets of the set $\{1,2,...,n\}$ such that it doesn't contain any two consecutive elements. Using Principle of Inclusion-Exclusion.

I tried doing it by subtracting all subsets that have 2 or more consecutive elements but the solution is not taking care of repetitions and It is very confusing. Can someone suggest a way to do this by PIE?

Attempt: Going by the suggestion given by @Wuestenfux and this thought also crossed my mind that takes $A_i$ to be the set of subsets containing $i$ and $i+1$. But to calculate $$\sum_{I\subseteq[n],I\ne\phi}(-1)^{|I|}|\bigcap_{i\in I}A_i|$$ let for $|I|=k$, where $k$ is an integer in $1,2,...,n$. to calculate $|\bigcap_{i\in I}A_i|$ for this, we have to take cases on the $k$ integers we choose because all will give different values.

Example: If $k=2$, $I$ could be $\{1,2\}$ or $\{1,3\}$ giving $|A_1\bigcap A_2|=2^{n-3}$ whereas ,$|A_1\bigcap A_3|=2^{n-4}$.

So my question now is how to find a general $|\bigcap_{i\in I}A_i|$ if $|I|=k$

$\endgroup$
  • $\begingroup$ PIE will handle the repetitions, for example let $E(z)$ denotes the counting of a consecutive $z$ observed and $n=3$, then $E(\{1,2\})+E(\{2,3\})-E(\{1,2\}\land\{2,3\})$ will appears in PIE and count $\{1,2,3\}$ exactly once($1+1-1=1$). Notice that $E(\{1,2\}\land\{2,3\})=E(\{1,2,3\})$, which is your consideration of "have 2 or more consecutive elements". And my $E(\{1,2\})$ is exactly $|A_1|$ in @Wuestenfux's answer. $\endgroup$ – Postal Model Oct 7 '18 at 7:24
  • $\begingroup$ @MarkoRiedel The question in the link is asking permutations of the e$n+1$ digits, but this question is about the total number of subsets, ie. all digits need not be present in the subset. $\endgroup$ – Krishna Oct 7 '18 at 12:28
0
$\begingroup$

Hint: Take $A=\{1,\ldots,n\}$ and define $A_i$ as the set of subsets of $A$ which contain $i$ and $i+1$, where $1\leq i\leq n-1$. Using inclusion-exclusion, you will find the cardinality of $P(A)\setminus (\bigcup_{i=1}^{n-1} A_i)$.

Added hint: You have to consider the cardinality of $\bigcap_{j\in I} A_j$ for each nonzero index set $I\subseteq\{1,\ldots,n-1\}$.

$\endgroup$
  • $\begingroup$ yes, I was asking exactly that in the question which I further edited. I asked how we could do what you said in the added hint. $\endgroup$ – Krishna Oct 7 '18 at 12:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.