题目
100分求通项公式
已知A2=1;A3=3;A4=11
递推:An=(n-1)*A(n-1)+(n-2)*A(n-2)
求{An}通项公式
没有错呀
中文描述就是,第n项=(n-1)乘以第n-1项+(n-2)乘以第n-2项
比如A4=3*A3+2*A2=11
佩服napcat!
其实,我正是在推广错置排列的问题上得到这个递推的,不过我算出来的方法数Bn=(n-1)*A(n-1),也就是说题中的An是一个辅助数列.(因为如果第n个人的帽子戴在i头上,而i的帽子没有戴在n的头上时,方法数应该不是A(n-1))
前面两种思路(特别是第二种)非常好,第三种中间的容斥定理则更是facinating,不知可否劳驾napcat高手稍微具体地说一下用容斥定律计算错置排列的过程.一定再追加100分.
已知A2=1;A3=3;A4=11
递推:An=(n-1)*A(n-1)+(n-2)*A(n-2)
求{An}通项公式
没有错呀
中文描述就是,第n项=(n-1)乘以第n-1项+(n-2)乘以第n-2项
比如A4=3*A3+2*A2=11
佩服napcat!
其实,我正是在推广错置排列的问题上得到这个递推的,不过我算出来的方法数Bn=(n-1)*A(n-1),也就是说题中的An是一个辅助数列.(因为如果第n个人的帽子戴在i头上,而i的帽子没有戴在n的头上时,方法数应该不是A(n-1))
前面两种思路(特别是第二种)非常好,第三种中间的容斥定理则更是facinating,不知可否劳驾napcat高手稍微具体地说一下用容斥定律计算错置排列的过程.一定再追加100分.
提问时间:2020-08-10
答案
答案:An=n!(1-1/1!+1/2!-1/3!+...+(-1)^n*1/n!)
一会儿回来提供三种证明思路
思路一:数学归纳法.这个没什么可说.
思路二:注意到An/A(n-1)大致是n,令 An=n!bn,代入,得
bn-b(n-1)=-(b(n-1)-b(n-2))/n,b1=0,b2=1/2.
所以,bn-b(n-1)=-(b(n-1)-b(n-2))/n=-(-(b(n-2)-b(n-3))/(n-1))/n=...=(-1)^(n-2)(b2-b1)/(n*(n-1)*...*3)=(-1)^n*1/n!,
所以 bn=1-1/1!+1/2!-1/3!+...+(-1)^n*1/n!,An=n!bn等于上式.
思路三:这个公式是错置排列的公式.所谓错置排列,有一个通俗的说法.n 个人,每人有一顶自己的帽子.An 是他们每个人都戴错帽子的戴法数目.显然 A1=0 (一个人不可能戴错),A2=1.对n>2的情况,第 n 个人的帽子必然戴到 某个第 i 人头上,i=1,2,...,n-1,这有两种情况 1)第i个人的帽子戴到第n个人头上,则其余 n-2 个人要互相戴错,共有 A(n-2)种戴法;
2)另外一个人的帽子戴到第n个人头上,此时共有 A(n-1)种戴法.总之,我们有 An=(n-1)(A(n-1)+A(n-2)),n>2.而我们可以用容斥原理算出错置排列的数目如上,所以必然有An等于上面的数.
一会儿回来提供三种证明思路
思路一:数学归纳法.这个没什么可说.
思路二:注意到An/A(n-1)大致是n,令 An=n!bn,代入,得
bn-b(n-1)=-(b(n-1)-b(n-2))/n,b1=0,b2=1/2.
所以,bn-b(n-1)=-(b(n-1)-b(n-2))/n=-(-(b(n-2)-b(n-3))/(n-1))/n=...=(-1)^(n-2)(b2-b1)/(n*(n-1)*...*3)=(-1)^n*1/n!,
所以 bn=1-1/1!+1/2!-1/3!+...+(-1)^n*1/n!,An=n!bn等于上式.
思路三:这个公式是错置排列的公式.所谓错置排列,有一个通俗的说法.n 个人,每人有一顶自己的帽子.An 是他们每个人都戴错帽子的戴法数目.显然 A1=0 (一个人不可能戴错),A2=1.对n>2的情况,第 n 个人的帽子必然戴到 某个第 i 人头上,i=1,2,...,n-1,这有两种情况 1)第i个人的帽子戴到第n个人头上,则其余 n-2 个人要互相戴错,共有 A(n-2)种戴法;
2)另外一个人的帽子戴到第n个人头上,此时共有 A(n-1)种戴法.总之,我们有 An=(n-1)(A(n-1)+A(n-2)),n>2.而我们可以用容斥原理算出错置排列的数目如上,所以必然有An等于上面的数.
举一反三
已知函数f(x)=x,g(x)=alnx,a∈R.若曲线y=f(x)与曲线y=g(x)相交,且在交点处有相同的切线,求a的值和该切线方程.
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
奥巴马演讲不用看稿子.为什么中国领导演讲要看?
想找英语初三上学期的首字母填空练习……
英语翻译
最新试题
- 10.0453亿 怎么改成科学计数法
- 2水果市场里,苹果的价格比梨贵0.7元,是梨价格的1.25倍,苹果和梨的价格分别是多少元?
- 3植物气孔中有叶绿体吗
- 410,9,17,50,下一位是?
- 53a与负a比大小
- 6一金属块挂在弹簧秤上,弹簧秤读数13.5N,将金属块浸没在水中时,弹簧秤读数8.5N此金属块密度是
- 7计算:7/6*26/39-9/17+26/117-0.5/ 17/16
- 8小明的爸爸做了一个无盖的长方形金鱼缸,长50厘米,宽30高40厘米做这个鱼缸要多少平方厘米的玻璃
- 9像什么的直线叫做数轴
- 10修一条路,第一个月修了全长的1/3,第二个月修了15千米,第三个月修了全长的1/4,三个月刚好把这条路修完
热门考点
- 1设方程log3X+X-3=0的根为x1,方程3^x+x-3=0的根为x2,求x1+x2的值
- 2that is the school last year
- 3太阳公公脉诊缓缓的步子登上天空,把光和热献给大地.仿写
- 4而夏呢,总是浸在苦涩的汗水里的理解
- 5平均速度和平均速率的区别
- 6一种物质有多种元素,而这些元素又有多种化合价,应如何确定他们的原子数
- 7吾日三省吾身的日古义是什么,今义是什么
- 8单项选择 May asked me _I thought about each thing a.how b.what c.which
- 9某课外活动小组女生人数占全组的一半,如果再减少3名女生,那么女生的人数占全组的1/3,求这个课外小组
- 10钢板重量计算公式