Question

请教一个排列组合问题

有A B C D四个字母（很多），随机放到n个空位上，应该是有4的n次方种排法。那么在这之中有多少正着念和倒着念一样的情况？
如：ABC=CBA ACBD=DBCA

Answer 1

n=1 0种 4的n次方 4
n=2 6种 4的n次方 16
n=3 24种 4的n次方 64
n=4 120种 4的n次方 256
n=5 480种 4的n次方 1024
n=6 2016种 4的n次方 4096
n=7 8064种 4的n次方 16384
n=8 32640种 4的n次方 65536
可以推知，在n趋近正无穷的情况下，或者说n足够大的情况下，有1/2乘以4的n次方种是重复的。
是小于1/2乘以4的n次方，极限是1/2乘以4的n次方

Answer 2

4个字母排列应该是CN4P44，也就(N*(N-1)*(N-2)*(N-3)/4*3*2*1)*4*3*2*1
=N*(N-1)*(N-2)*(N-3)
也就是说有N(N-1)(N-2)(N-3)种排法
4个字母顺序排列有4*3*2*1＝24种排法，每一种排列都有和他倒着念一样的排列，所以应该是24种

Answer 3

应该是4的n次方减去4，然后除以二，再加上4种~

Answer 4

解答:

本题是回文式(Palindrome)的问题, 分两种情况讨论:

Case 1 : n 为奇数的情况

因为首尾对称，第 ½(n + 1) 个数是中间数，记为M，其余数首尾对称。
前 ½(n - 1) 个数的各种排列数 = 4^[½(n-1)] = 2^(n-1),
后 ½(n - 1) 个数的各种排列已经由前 ½(n - 1) 个数确定，没有选择余地。
中间的M有4种选择，所以，总共的排列数 = 4×2^(n-1) = 2^(n+1)

Case 2 : n 为偶数的情况

因为首尾对称，所以
前 n/2 个数的各种排列数 = 4^(n/2) = 2^n,
后 n/2 个数的各种排列已经由前 n/2 个数确定，没有选择余地。
所以，总共的排列数 = 2^n