0
$\begingroup$

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.)

$\endgroup$
0
$\begingroup$

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.

The term stars-and-bars refers to this kind of combinatorial reasoning; the linked article has more information.

$\endgroup$
0
$\begingroup$

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\}$.

$\endgroup$

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.