Number of special ordered set

Question

An ordered set is a set such that the order in which the objects appear in the set is significant.

For example, (1, 2, 3) and (2, 1, 3) are two different ordered sets of integers.

An ordered set of integers is said to be a special set if for every element X of the set, the set does not contain the element X+1.

Determine the number of special sets for number N, whose largest element is not greater than N.

For N = 3, there are 5 special sets that are (1), (2), (3), (1, 3), (3, 1).

I tried my self by counting all the ordered set by taking the difference of elements more than >=2 but at last, I observe that it is getting recounted for some of the subsets of size more than >=2.

could anyone please explain this, how to count it correctly.

Thanks in Advance.

Answer 1

Suppose there are $m$ elements in a special set. It seems clear that $m \le \lfloor (N+1)/2 \rfloor$. A well-known result in combinatorics (see below) is that there are $\binom{N-m+1}{m}$ subsets of ${1,2,3,\dots,N}$ of size $m$ with no adjacent elements. Each such set can be ordered in $m!$ ways. So the total number of special sets is $$\sum_{m=1}^{\lfloor (N+1) / 2 \rfloor} \binom{N-m+1}{m} m!$$ The first few values, for $1 \le N \le 10$, are $1, 2, 5, 10, 23, 50, 121, 290, 755, 1978$. I did a search on OEIS without finding this sequence.

---

For those not familiar with the formula for the number of ways to select k non-adjacent items from n, here is a derivation. Suppose we want to select $k$ non-adjacent integers $a_1, a_2, a_3, \dots ,a_k$ from the set $\{1, 2, 3, \dots ,n\}$. For the choices to be non-adjacent, we must have $1 \le a_1$, $a_1 < a_2-1$, $a_2 < a_3-1$, $a_3 < a_4-1$, ..., $a_{k-1} < a_k -1$, and $a_k \le n$. An equivalent set of inequalities is $$1 \le a_1 < a_2-1 < a_3-2 < a_4-3 < \dots < a_k-k+1 \le n-k+1$$ So we may equivalently pick the values $ a_1 , a_2-1 , a_3-2 , a_4-3 , \dots , a_k-k+1$ from $\{1, 2, 3, \dots ,n-k+1 \}$, and this can be done in $\binom{n-k+1}{k}$ ways.

Answer 2

An iterative method

The number of special sets for $n$ is $1$ less than the sum of the elements in the $n+1$th column of the matrix $M$. For example, for $n=4$ the number of special sets is $4+6=10$.

$$M=\begin{pmatrix}1&1&1&1&1&1&1&1&... \\0&1&2&3&4&5&6&7&...\\0&0&0&2&6&12&20&30&...\\0&0&0&0&0&6&24&60&...\\0&0&0&0&0&0&0&24&...\\..&..&..&..&..&..&..&..&...\end{pmatrix}$$

The matrix is calculated by the formula $$m_{i+1,j+2}=m_{i+1,j+1}+im_{i,j}$$

and is easy to implement on Excel. This relationship is proved as follows.

The element $m_{i+1,j+2}$ counts the number of special sets for $j+1$ of size $i$. Consider these sets according to whether or not they contain $j+1$.

Not containing $j+1$. There are $m_{i+1,j+1}$ of these.

Containing $j+1$. Such a set is one of the $m_{i,j}$ sets for $j-1$ of size $i-1$ with $j+1$ added in one of $j$ possible positions.