探求数列递推公式的若干途径

侯作奎

递推公式是数列的一种重要表示方法.许多计数问题需要探求数列的递推公式.那么如何探求数列递推公式呢？本文试图通过若干具体实例，给出探求数列递推公式的若干途径（方法）.

1 制定规则分类，利用分类计数原理

制定规则，并在这个规则下，将计数对象分类，这样比较容易导出递推关系.

例1 （1993年全国高考题）将数字1，2，3，4填入标号为1，2，3，4的四个格子里，每格填一个数字，则每个格子的标号与所填的数字均不相同的填法有（  ）.

A.9种  B.6种  C.11种  D.23种

解 将问题推广到一般：将1，2，3，…，n填入标号为1，2，3，…，n的n个格子里，每格填一个数字，且每个格子的标号与所填的数字均不相同，称这样的一个填法叫作一个错排.求错排种数.

假设n个自然数1，2，…n的错排种数为an.显然a2=1.

当n≥3时，由于是错排，故n必不在第n号格里，设n在第k号格里（k<n）.

以下对第n号格里的数字分类讨论：

（1）若第n号格里的数字是k，那么除n和k以外还要对余下的（n-2）个数进行错排，则此时共有an-2种排法（如图1）.

图1

（2）若第n号格里不是k，

那么把第n号格视作第k号格.这样就变成1，2，…，n-1个数的错排，此时有an-1种排法.

故当n在第k号格里时，共有an-1+an-2种排法.

因为放置n的k号格可在1，2，…，n-1中选取，有n-1种选法，故共有

an=（n-1）·（an-1+an-2）（n≥3）种不同排法.

原问题解答：因a2=1，a3=2，由上面递推关系得a4=（4-1）（2+1）=9.

评 这里制定规则：将n置于第k（k<n）号格中，讨论第n号格放置的数是否为k.从而将此时的错排分为：第n号格里的数字是k与不是k的两大类.从而较方便的沟通了an与an-1、an-2间的关系.

例2 （1996年爱朋思杯，上海市高中数学竞赛题）已知集合{1，2，3，4，5，6，7，8，9，10}，求该集……