有两根不同的旗杆和19面旗帜，其中蓝旗有10面，绿旗有9面．现在要将所有旗帜都挂在旗杆上，使得每一根旗杆至少有1面旗帜，且任意两面绿旗不相邻．设这样的排列方法数为 $N$，求 $N$ 除以1000的余数．
【难度】
【出处】
2008年第26届美国数学邀请赛Ⅱ（AIMEⅡ）
【标注】
【答案】
310
【解析】
为了计算方便，我们将两根旗杆分别标为1号杆和2号杆．设 ${{G}_{n}}$ 表示在1号杆上有 $n$ 面绿旗的排列数．若其中一根旗杆挂上了所有的绿旗，则这根旗杆上至少挂了8面蓝旗，另一根旗杆上至少挂了1面蓝旗，剩下一面蓝旗共有 $10+1=11$ 个可选择的位置，故 ${{G}_{0}}={{G}_{9}}=11$．
若 $0n9$，则1号杆上有 $n$ 面绿旗，同时上面至少有 $n-1$ 面蓝旗，2号杆上有 $9-n$ 绿旗，同时至少有 $8-n$ 面蓝旗，那么已经有7面蓝旗是由绿旗锁定了位置，剩下的蓝旗可以在 $\left(n+1 \right)+\left( 10-n \right)=11$ 个位置中任意选择并且可重复，这相当于从13个位置中选取3个，因此放置这三面蓝旗的排列数为 $\text{C}_{\text{13}}^{\text{3}}$，故总的排列数为
$\displaystyle N=\sum\limits_{i=0}^{9}{{{G}_{i}}=2\cdot11+8\text{C}_{13}^{3}=2310}$．
故所求的数为310．
若 $0n9$，则1号杆上有 $n$ 面绿旗，同时上面至少有 $n-1$ 面蓝旗，2号杆上有 $9-n$ 绿旗，同时至少有 $8-n$ 面蓝旗，那么已经有7面蓝旗是由绿旗锁定了位置，剩下的蓝旗可以在 $\left(n+1 \right)+\left( 10-n \right)=11$ 个位置中任意选择并且可重复，这相当于从13个位置中选取3个，因此放置这三面蓝旗的排列数为 $\text{C}_{\text{13}}^{\text{3}}$，故总的排列数为
$\displaystyle N=\sum\limits_{i=0}^{9}{{{G}_{i}}=2\cdot11+8\text{C}_{13}^{3}=2310}$．
故所求的数为310．
答案
解析
备注
