将 $10$ 把一字排成一圈，从中选出若干把椅子，若选出的椅子中至少有三把相邻，求不同选法的种数。
【难度】
【出处】
2014年第32届美国数学邀请赛Ⅱ（AIMEⅡ）
【标注】
【答案】
581
【解析】
$3$ 元素子集中，有 $10$ 个是由三把连续的椅子构成的。 $4$ 元素子集中，四把椅子都相邻的有 $10$ 个，恰有三把相邻的有 $10*5\text{=}50$ 个，共 $60$ 个。 $5$ 元素子集中，五把椅子都相邻的有 $10$ 个，恰有四把相邻的有 $10*4\text{=}40$，恰有三把相邻的有 $10*\left(\begin{matrix}
5 \\
2 \\
\end{matrix}\right)\text{=}100$，共 $150$ 个。 $6$ 元素子集中，六把椅子都相邻的有 $10$ 个，恰有五把相邻的有 $10*3\text{=}30$，恰有四把相邻的有 $10*\left(\begin{matrix}4 \\
2 \\
\end{matrix}\right)\text{=}60$，有两组三把相邻的有 $\frac{10*3}{2}\text{=}15$，恰有一组三把相邻的有 $10*\left(\left( \begin{matrix}5 \\
2 \\
\end{matrix}\right)-3 \right)\text{=}70$，共 $185$ 个。元素数大于 $6$ 的子集必然包含三把相邻的椅子，故一共有 $\left( \begin{matrix}10 \\
10 \\
\end{matrix} \right)+\left( \begin{matrix}10 \\
9 \\
\end{matrix} \right)+\left( \begin{matrix}10 \\
8 \\
\end{matrix} \right)+\left( \begin{matrix}10 \\
7 \\
\end{matrix} \right)+185+150+60+10\text{=}581$ 个满足条件的子集。
5 \\
2 \\
\end{matrix}\right)\text{=}100$，共 $150$ 个。 $6$ 元素子集中，六把椅子都相邻的有 $10$ 个，恰有五把相邻的有 $10*3\text{=}30$，恰有四把相邻的有 $10*\left(\begin{matrix}4 \\
2 \\
\end{matrix}\right)\text{=}60$，有两组三把相邻的有 $\frac{10*3}{2}\text{=}15$，恰有一组三把相邻的有 $10*\left(\left( \begin{matrix}5 \\
2 \\
\end{matrix}\right)-3 \right)\text{=}70$，共 $185$ 个。元素数大于 $6$ 的子集必然包含三把相邻的椅子，故一共有 $\left( \begin{matrix}10 \\
10 \\
\end{matrix} \right)+\left( \begin{matrix}10 \\
9 \\
\end{matrix} \right)+\left( \begin{matrix}10 \\
8 \\
\end{matrix} \right)+\left( \begin{matrix}10 \\
7 \\
\end{matrix} \right)+185+150+60+10\text{=}581$ 个满足条件的子集。
答案
解析
备注
