证明在n级排列中,奇排列与偶排列各占一半
来源:学生作业帮助网 编辑:作业帮 时间:2024/05/13 15:26:46
证明在n级排列中,奇排列与偶排列各占一半
证明在n级排列中,奇排列与偶排列各占一半
证明在n级排列中,奇排列与偶排列各占一半
证明相等的一个很重要的方法就是构造一个映射,使得它是双射
设任一个n级排列,a1a2a3……an,我们做映射a1a2a3……an-->a2a1a3……an,
观察这个映射,如果a1a2a3……an是奇排列,那么a2a1a3……an为偶排列,如果a1a2a3……an为偶排列,那么a2a1a3……an是奇排列,而且对于任意a1a2a3……an不等于b1b2b3……bn,那么a2a1a3……an不等于b2b1b3……bn,所以这个映射是一个一一对应
注意到所有的a1a2a3……an是1,2,3,……,n的所有排列,显然所有的a2a1a3……an也是1,2,3,……,n的所有排列,我们把定义域取为所有a1a2a3……an为奇排列,那么a2a1a3……an均为偶排列,所以奇排列数小于等于偶排列数,反过来取定义域为所有的偶排列,可以得到偶排列数小于等于奇排列数,故奇排列数等于偶排列数
(或者由映射是一一映射,所以直接推出奇排列数等于偶排列数)
奇/偶=(2n+1)/2n=1+1/2n
n->∞
做奇排列到偶排列的映射f,定义为交换前2个元素位置,即f(a1a2……an)=a2a1……an
则f是满射,因为任给b1b2……bn是偶排列,它在f下都有原像b2b1……bn
f也是单射,假设两个奇排列(a1a2……an)!=(b1b2……bn),则存在某个i使ai!=bi,若i>2则f(a1a2…ai…an)=a2a1…ai…an!=f(b1b2……bi……bn)=b2b1……b...
全部展开
做奇排列到偶排列的映射f,定义为交换前2个元素位置,即f(a1a2……an)=a2a1……an
则f是满射,因为任给b1b2……bn是偶排列,它在f下都有原像b2b1……bn
f也是单射,假设两个奇排列(a1a2……an)!=(b1b2……bn),则存在某个i使ai!=bi,若i>2则f(a1a2…ai…an)=a2a1…ai…an!=f(b1b2……bi……bn)=b2b1……bi……bn,若i=1或2则对换后还是不等。因此,f是双射
又任意排列是奇排列或排列之一,故奇排列与偶排列各占一半均为n!/2
收起