1至9的全排列中,至少有一个奇数在其自然位置上的排列有多少个

Question

1至9的全排列中,至少有一个奇数在其自然位置上的排列有多少个

Answer 1

本题是组合数学中的错排问题的一个变形,可以采用容斥原理来解决.

1、

1~9的全排列中,奇数k排在第k位的排列方式一共有(9-1)!=8!种

1~9中一共有1、3、5、7、9这5个奇数,所以如果不考虑重复的话,一共有C(5,1)*(9-1)=5*8!种排列是至少有一个奇数在其自然位置上.

2、

但是上面的计算中显然重复的包含了有2、3、4、5个奇数同时在其自然位置上的排列.

所以根据容斥原理应该把这部分重复计算的值排除在外.

C(5,1)*(9-1)! -C(5,2)*(9-2)!+C(5,3)*(9-3)!-C(5,4)*(9-4)!+C(5,5)*(9-5)!

=C(5,1)*8! -C(5,2)*7!+C(5,3)*6!-C(5,4)*5!+C(5,5)*4!

= 5*8!-10*7!+10*6!-5*5!+4!

=157824

3、

我写了一个C程序来验证,如下

#include 

#define N 9
int Mark[N] = {0};
int Stack[N];
int count = 0;

void print()
{
\x09int i;
\x09for(i=0;i\x09\x09printf("%d\t",Stack[i]);
\x09printf("\n");
}
void judge()
{
\x09int i;
\x09for(i=0;i\x09{
\x09\x09if(Stack[i]==i+1)
\x09\x09{
\x09\x09\x09count++;
\x09\x09\x09return;
\x09\x09}
\x09}
}
void rank(int m,int n)
{
\x09int i;
\x09if(n==0)
\x09{
\x09\x09judge();
\x09\x09return;
\x09}
\x09for(i=0;i\x09\x09if(Mark[i]==0)
\x09\x09{
\x09\x09\x09Mark[i]=1;
\x09\x09\x09Stack[m]=i+1;
\x09\x09\x09rank(m+1,n-1);
\x09\x09\x09Mark[i]=0;
\x09\x09}
}

void main()
{
\x09rank(0,N);
\x09printf("count=%d\n",count);
}

结果表明数学计算是正确的.