[组合] 一道排列组合题

见附图

这么难……用程序搞一下竟然有90个这么多，看来穷举也不易……

PS、纯文字无公式的题目就不必贴图了吧……

无人问津？

3# hflz01

可能难度大吧，我计数弱，暂时也没什么好办法。

今天太晚了,明天用逐步淘汰原理或递推数列的方法试下,别抱太大希望.

今天太晚了,明天用逐步淘汰原理或递推数列的方法试下,别抱太大希望.
realnumber 发表于 2013-1-7 23:24

递推我昨晚想了好久没想出来
“逐步淘汰原理”第一次听……

“逐步淘汰原理”就是容斥原理啦,百度.

7# realnumber

原来还有这么个别名……容斥我也想过，也无果……

先穷举法完成它,积累些经验
1,2,3,4,5,6排成一列,要求任意两个连续自然数不能相邻,问有几种排法?
考虑到1,6对称,同样对于2,5;3,4
以及1放第一个位置和第6个位置一样多
一.1放1号位置(或6号位置)
      ①2在3号位置,
                 (1)3在5号位置,4只能在2号位置,----2种
              (2)3在6号位置,4只能在4号位置(在2号的话,没法放5,6了)---2种
      ②2在4号位置,
                 (1)3在2号位置,4可以在5或6号位置,----2种
              (2)3在6号位置,4可以在2或3号位置-----2种
      ③2在5号位置,
                (1)3在2号位置,4只能在4号位置,----1种
              (2)3在3号位置,4只能在6号位置-----2种
       ④2在6号位置
              (1)3在第2号位置,----0种
              (2)3在第3号位置,4只能在5号位置-----2种
              (3)3在第4号位置,4只能在2号位置,----1种
这样一来"1放1号位置或6号位置"有28种
            ---每一条数量倒不多,太烦琐,容易出错.暂停下这个办法,如有必要才来继续..
二.1放2号位置(或5号位置)
      ①2在第4号位置,
      ②2在第5号位置,
      ③2在第6号位置
三.1放3号位置(或4号位置)
      ①2在第1号位置,
      ②2在第5号位置,
      ③2在第6号位置,

逐步淘汰原则successive sweep principle:

(9.52 KB)

2013-1-8 14:34

总数    $A_6^6=720$
出现1对   $ 1,2;2,3;3,4;4,5;5,6,$这1对看作一个整体,$5A_2^2A_5^5=1200$
出现2对,  $"123,234,345,456,321,432,543,654"$有$8A_4^4=192$
             或$"12,34;12,45;12,56;23,45;23,56;34,56$有$6A_2^2A_2^2A_4^4=576$
出现3对,$"1234;2345,3456,4321,5432,6543"$有$6A_3^3=36$
           或$123,45;123,56;234,56;345,12;456,12;456,23$有$6\times 2\times 2A_3^3=144$
           或$12;34;56$有$({A_2^2})^3A_3^3=48$
出现4对,$"12345;23456;54321;65432"$有$4A_2^2=8$,还有"123,456;12,3456;1234,56;"有$24$种,合计$8+24=32$
出现5对,$"123456;654321"$有$2$种.
所以本题结果是$720-1200+(192+576)-(36+144+48)+32-2=90$ 和kuing程序做出的$90$一样了.

9# realnumber


作考试的话，时间够么？

恩,我不知道,也许一直的训练的一些牛B选手,也许没问题,我得想递推数列,如果可以,应该是最快的.

9# realnumber

真好耐心啊！

$n$个数据依次为$1,2,3,...,n-1,n$.
记 $ a_n $为$n$个数据没有2个相邻的排列数.比如$a_6=90,a_1=1,a_2=a_3=0,a_4=2$
记 $ b_n $为$n$个数据有且仅有1对相邻的排列数.$b_1=0,b_2=2,b_3=4$
记 $c_n$为$n$个数据中有且仅$n-1,n$相邻的排列数.$c_1=0,c_2=c_3=c_4=2,c_5=6$
记 $d_n$表示有3个数据连在一起的个数,$d_3=2,d_4=4,d_5=10$
那么有如下关系:
$a_{n+1}=(n-1)a_n+b_n-c_n$,第$n+1$个数据插入$n$个互不相邻的有$n-1$个位置,插入有且仅有一个相邻的只有一个位置,或无法插入(因为$n-1,n$相邻了(kuing)).
$c_n=2a_{n-1}+c_{n-1}$
$b_n=2(n-1)a_{n-1}+2b_{n-1}+d_{n-1}$1楼问题其实已经解决,就是递推还不够完善.
$d_n=2(n-2)a_{n-2}+2b_{n-2}+d_{n-2}=?b_{n-1}+?$---就这条了,可能有错,没想明白.$a_5,a_7$可以通过四个递推得到,并得到kuing的程序验证.

楼主公布下答案和出处?--想不到已经过去了3天,也许会写文要引用下.

没答案哦，不知同事从哪搞来的。