不对号入座的公式

不对号入座的公式

an=(n-1)(an-1+an-2)
　由2、3、4、5、6个人不对号入座的结论,我们不难发现这类不对号入座问题的一个递推公式.设n个人不对号入座共有an种方法,则不同人数的坐法数对应于数列{an}.易知a1=0,a2=1,从前面的结论可归纳出:an=(n-1)(an+2+an-1)(n≥3).这一结论仅是一种归纳猜想,如何证明这一结论的正确性呢?
　　在这里,我们将上述不对号入座问题,变换一下问题的背景,以便更透彻地理解这一类问题.
　　例2 现有1,2,3,…,n,n个编了号的小球和n个编了号的箱,一个球放在一个箱里且不对号,有多少种不同的方法?
　　解:设n个球时共有an种放法,则不同个数球的放法数对应于数列{an}.
　　分两步考虑,先放①号球,①号球共n-1种放法. 不妨设将其放入2号箱中,此时剩下的n-1个球和n-1个箱(如图1).
　　再放剩下的n-1个球. ②号球可放入1号箱,也可以放到其它箱中.当②号球放入1号箱中时,余下的n-2个球和n-2个小箱恰好一一对号(如图2),则余下的球共an-2种不同放法.
　　当②号球不放入1号箱时,②号球相当于①号球,那么这时n-1个球和n-1箱共有an-1种不同放法.
　　综上可知,n个球的不对号入座方法为an=(n-1)(an-2+an-1)(n≥3).
　　递推公式表述为:a1=0,a2=1,an=(n-1)(an-2+an-1),n≥3,由a1=0,a2=1,则可得:

什么玩意！？

哈哈

虾米意思