How to calculate combinations of a set under a certain condition

Question

example: if i have the following set set = [ 14, 3, 5 ]. all possible combinations(subsets) can be deducted easily however i want to deduct the subsets based on a certain rule example of a rule. a subset cannot be descending (e.g: {14,3} the otherway around is acceptable (e.g: {3,14} ) another rule is subsets cannot include two adjacent numbers (e.g {3,14} is not acceptable however {5,14} is acceptable}.

Answer 1

Let $S=\{x_1,x_2,\dots,x_n\}$ be the set. Since $S$ is a set then $\forall i,j\in\mathbb{N}, 1\le i,j\le n$ if $i\ne j\Rightarrow x_i\ne x_j$.

Suppose we have a subset $S'\subset S$ such that $S'$ has not adjacent numbers, then $S'$ has a unique way to "put" its numbers such that $S'=\{y_1,y_2,\dots,y_k\}$ and $y_1<y_2<\cdots<y_k$.

So we have a bijection here, if we have a subset $S'\subset S$ and it hasn't adjacent numbers then we have one valid subset.

All we need is how calculate the subset $S'\subset S$. Then if $|S'|=k$ and $|S|=n$, all we need is to peek $k$ elements from a set of $n$ and any pair of them are adjacent numbers in $S$, then $2k\le n+1$.

Let's do this:
Given a sequence $s$ of $n$ bits then $s$ define a subset $S'\subseteq S$ such that the $i$-th bit define if the $i$-th element of $S$ has been chosen to "take part" in $S'$, if $i$-th bit is turned on $0$ then $x_i\notin S'$ and otherwise $x_i\in S'$. Also, all possible subsequence $s$ of $n$ bits define all possible subset of $S$.
So we have another bijection here, $S'$ hasn't adjacent numbers if and only if $s$ hasn't $2$ adjacent bits turned on $1$.

If we want to find a valid subset $S'$ with $k$ elements then we could do this:
Let define the sequence $s'$ of $n-k$ bits turned on $0$, then we will "put" $k$ bits turned on $1$ in $s'$ and we will take care that $s'$ hasn't $2$ adjacent bits turned on $1$. So $s'$ has $n-k+1$ possible position to "put" a bit turned on $1$, so we have $\binom{n-k+1}{k}$ possible ways to "make" a "new" sequence $s'$ of $n$ bits such that $s'$ hasn't $2$ adjacent bits turned on $1$.

So we will have $\binom{n-k+1}{k},~2k\le n+1$ subsets $S'\subset S$ of length $k$ and $S'$ hasn't $2$ adjacent numbers of the set $S$. If you want to calculate the number $n$ of all possible subset $S'$ then:
$\displaystyle n=\sum^{t}_{k=1}\binom{n-k+1}{k},$ $t=\lfloor\frac{n+1}{2}\rfloor$

Note: If you include the empty subset just take $k$ from $0$ to $t$.