# Removing Counting redundancy

For a finite set of n sequential, non-zero integers, such as S={1,2,3,...,60}, and all subsets of d members derived from S, the total number of subset combinations are counted as C(n,d).

How many d-member subsets from C(n,d) have adjacent members? In other words, if d = 5, the following two subsets fit this criterion; {1, 3, 21,22, 47} and {31,32,33, 56,57}? Such d-member combinations, or states, are considered disallowed. And how can I count all disallowed states without counting the same subset more than once (redundant counting of disallowed states)?

(It would help to envision S as n contiguous slots and to count how many ways you can fill the slots with d elements without creating adjacently occupied slots, count such disallowed combinations or states only once, and then remove them from C(n,d). This is not a simple problem and I honestly would like some direction.)

The hint given is useful:

It would help to envision $n$ as a contiguous series of slots and see how you can fill the slots with $d$ elements without creating adjacently occupied slots: and then count such disallowed states only once.

The suggestion here is to count the $d$-element subsets that do not have adjacent members (and of course then to subtract that from the total number of $d$-element subsets, which you know to be $\binom{n}d$). I’ll illustrate the idea with a picture for $d=5$ and some unspecified $n$ large enough to make such a subset possible, but I’ll talk about the picture in general terms.

Let $$\ldots\mid\overset{x}\ldots\mid\overset{x}\ldots\mid\overset{x}\ldots\mid\overset{x}\ldots\mid\ldots$$ schematically represent a $d$-element subset; the vertical bars represent the $d$ elements of the chosen subset, and the ellipses represent the unchosen numbers between them and on either end. (Ignore the $x$s for a moment.) The other $n-d$ integers are distributed amongst those $d+1$ gaps. Each of the $d-1$ gaps marked with an $x$ contains at least one of these $n-d$ integers, since we’re counting the $d$-element sets that do not have adjacent elements, while the end gaps may be empty. Each $d$-element subset without adjacent elements gives rise to a picture like this, and each such picture represents a unique $d$-element subset without adjacent elements. Thus, we need only count the pictures of this type. What, exactly, is this type?

If we represent each unchosen integer by a $*$, we have a string of $n$ symbols, $d$ of which are $\mid$’s and $n-d$ of which are $*$’s, and there is at least one $*$ in each gap between consecutive $\mid$’s. Let’s just glue a $*$ immediately to the right of each of the first $d-1$ $\mid$’s, like this:

$$\ldots\underbrace{\mid*}\ldots\underbrace{\mid*}\ldots\underbrace{\mid*}\ldots\underbrace{\mid*}\ldots\mid\ldots$$

Now treat both the $\underbrace{\mid*}$ bars and the last simple $\mid$ as simple $\mid$’s, so that we have a picture

$$\ldots\mid\ldots\mid\ldots\mid\ldots\mid\ldots\mid\ldots$$

with $d$ $\mid$’s and ${n-d-(d-1)=n-2d+1}$ $*$’s distributed arbitrarily in the gaps; the other $d-1$ $*$’s are now part of the first $d-1$ $\mid$’s. Each picture can therefore be thought of as a string of $d$ $\mid$’s and $n-2d+1$ $*$’s, for a total of $n-d+1$ symbols, and the $d$ $\mid$’s can appear anywhere in that string of $n-d+1$ symbols. Thus, there is one picture (and hence one $d$-element subset without adjacent elements) for each way of choosing $d$ of the $n-d+1$ symbols to be the $\mid$’s.

What you could do is count the number of $d$-member subsets that have no adjacent members. This is given by \begin{pmatrix}n-d+1 \\ d \end{pmatrix} And then subtract it from the number of $d$-element subsets of $S=\{1,2,3,\dots,n\}$.