2^(n-1)*n!/((2n)!/2^n)

来源: mondayadvisor 2015-10-22 19:58:01 [] [旧帖] [给我悄悄话] 本文已被阅读: 0 次 (809 bytes)

the total number of ways to pick two ends at a time: (2n)!/2^n = C^2_{2n}*C^2_{2n-2}*....*C^2_{2}

to form one loop, each two ends of one noodle must be the neighbor in a lineup, so we wrap a noodle into a ball to get n-balls. Now, we line up n-balls in one line, the line represents one big loop. There are n! lines from n balls. But each ball has two states in a line up: let a noodle has emds a, b, so we have a-b ball and b-a ball. with this into consideration, we 2^n possiblities for one line up, so the total is 2^n n!. Now we link ends of the line to have a loop of noodles. This noodle can flip upside down and it is the same but the different way in a line up, so we devide it by 2. Now the total ways to form a loop is 2^{n-1}n! (there is brute-force way to get this numer).

请您先登陆,再发跟帖!

发现Adblock插件

如要继续浏览
请支持本站 请务必在本站关闭/移除任何Adblock

关闭Adblock后 请点击

请参考如何关闭Adblock/Adblock plus

安装Adblock plus用户请点击浏览器图标
选择“Disable on www.wenxuecity.com”

安装Adblock用户请点击图标
选择“don't run on pages on this domain”