不相邻的数

1,...N中取X个两两不相邻的数，有多少种取法？

例如，1,2,3中取2个不相邻的数，只有{1,3}这1种取法。

解法1:
假设这X个不相邻的数中，第一个数之前有a个数，最后一个数之后有k-a个数。这X个不相邻的数形成了X-1个容器，每个容器中至少有一个数。这和把N-k-X个不可分辨的球分入X-1个容器，每个容器中至少有一个球的问题类似。按照前文“分球问题的总结”，这一共有C(N-k-1, X-2)种分法。当然，要使上述问题有意义，必须有N-k-X>=X-1。也就是说k最大可以取N+1-2X。k最小显然可以取0。对于每个固定的k，a可以取0,1,...,k，共(k+1)种取法。从而题目的答案是
\[\sum_{k=0}^{N+1-2X} (k+1)C(N-k-1,X-2)\]

解法2:
假设这X个数为$n_1<n_2<\cdots<n_X$。则不相邻等价于
$n_2-1>n_1$,
$n_3-1>n_2$,
...,
$n_X-1>n_{X-1}$
引入新变量$m_1=n_1$,$ m_2=n_2-1$, $m_3=n_3-2$, ..., $m_X=n_X-(X-1)$，则上述不相邻条件等价于
$m_2>m_1$,
$m_3>m_2$,
...,
$m_X>m_{X-1}$
也就是说，$m_1<m_2<\cdots<m_X$只是普通的X个从小到大的整数，不再有不相邻的限制。由于$n_X$最大可以取到N，从而$m_X$最大可以取$N+1-X$。于是$m_1,m_2,\cdots,m_X$有C(N+1-X,X)种取法。由于$m_1,m_2,\cdots,m_X$和$n_1,n_2,\cdots,n_X$有一一对应关系，从而$n_1,n_2,\cdots,n_X$也有C(N+1-X,X)种取法。

解法3:

把N个数看成N个小球。先取N-X个小球排成一排，然后把X个小球插进去。N-X个小球包括其两端一共有N-X+1个空位，所以答案是C(N-X+1, X)。