免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
新浪微博
QQ空间
Facebook
Google+
Plurk
Twitter
Line
返回列表 发帖
wujiemin1981

1# 跳转到 » 倒序看帖
打印
tT
发表于 2019-6-3 09:57 | 只看该作者

[组合] 排列组合问题

某单位停车场内5俩汽车并排停在一起，下班时它们要分别驶离，按规定每次都是两边上的其中一辆车先走，如果中间的某辆先走算抢队，则5辆车先后驶离的过程中，恰有一辆抢队的情况有几种
收藏 分享
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

青青子衿

2#
发表于 2019-6-3 13:21 | 只看该作者
本帖最后由 青青子衿 于 2019-6-3 14:23 编辑

回复 1# wujiemin1981
某单位停车场内五俩汽车并排停在一起，下班时它们要分别驶离，按规定每次都是两边上的其中一辆车先走，如果中间的某辆先走算抢队 ...
wujiemin1981 发表于 2019-6-3 09:57


对五辆车进行标记，从左往右依次标为1、2、3、4、5号车，
则可以得到出车“代序排列”（代表顺序的排列），
于是给出一个满足不抢队的序列：AA={5,1,4,3,2}
AA这个“代序排列”代表的是：
第一步，先出最右侧的5号车，剩下四辆车；
第二步，然后出最左侧的1号车，剩下三辆车；
第三步，然后出最右侧的4号车，剩下两辆车；
第四步，然后出最右侧的3号车，剩下一辆车；
第五步，最后出2号车，结束。
\begin{gather*}
1\qquad2\qquad3\qquad4\qquad5\\
\phantom{\small{5}}\downarrow\small{5}\\
1\qquad2\qquad3\qquad4\qquad{\phantom5}\\
\phantom{\small{1}}\downarrow\small{1}\\
{\phantom1}\qquad2\qquad3\qquad4\qquad{\phantom5}\\
\phantom{\small{4}}\downarrow\small{4}\\
{\phantom1}\qquad2\qquad3\qquad{\phantom4}\qquad{\phantom5}\\
\phantom{\small{3}}\downarrow\small{3}\\
{\phantom1}\qquad2\qquad{\phantom3}\qquad{\phantom4}\qquad{\phantom5}\\
\phantom{\small{2}}\downarrow\small{2}\\
\\
\end{gather*}
于是，一共有 16种 出五辆车的出车顺序满足“不抢队”的条件。
（先在5号车与1号车里二选一，再在剩下的车组里最左最右二选一，
继续在剩下的车组里最左最右二选一，以此类推）
\(\,\,2^4=16\,\,\)
也就是说，出五辆车有零辆车“抢队”，一共有 16种 情况 。
{{1, 2, 3, 4, 5}, {1, 2, 3, 5, 4}, {1, 2, 5, 3, 4}, {1, 2, 5, 4, 3},
{1, 5, 2, 3, 4}, {1, 5, 2, 4, 3}, {1, 5, 4, 2, 3}, {1, 5, 4, 3, 2},
{5, 1, 2, 3, 4}, {5, 1, 2, 4, 3}, {5, 1, 4, 2, 3}, {5, 1, 4, 3, 2},
{5, 4, 1, 2, 3}, {5, 4, 1, 3, 2}, {5, 4, 3, 1, 2}, {5, 4, 3, 2, 1}}

那么，出五辆车恰有一辆车“抢队”，一共有 ？？种 情况 。

【代码一】
  1. f[list_] := Module[
  2.   {k}, k = 0;
  3.   For[
  4.    i = 1, i < Length[list], i++,
  5.    If[
  6.     Min[list[[i + 1 ;; Length[list]]]]
  7.      < list[[i]] <
  8.      Max[list[[i + 1 ;; Length[list]]]],
  9.     k = 1;
  10.     Break[]
  11.     ]
  12.    ];
  13.   k == 0]
  14. Select[Permutations[Range[5]], f]
复制代码
*****  *****  *****  *****  *****  *****
【代码二】
  1. ff[ans_, lis_] := ff[ans, lis] =
  2.    If[Length@lis == 1,
  3.     Flatten@{ans, lis}, {ff[Flatten@{ans, First@lis}, Rest@lis],
  4.      ff[Flatten@{ans, Last@lis}, Most@lis]}];
  5. lis = Range@5;
  6. ff[{}, Sort@lis] // Flatten[#, Length@lis - 2] &
复制代码

TOP

kuing

3#
发表于 2019-6-3 14:22 | 只看该作者
下面用 `01` 序列表示出车过程中的抢队情况，比如 `\{0,1,0,0,0\}` 表示抢队出现在第二次出车时。

对于这个例子，方法数为 `2\times(4-2)\times2\times2\times1`，也就是 `0` 的位置上 `\times2`（除了最后一个），而 `1` 的位置上 `\times(5-p+1-2)`，其中 `p` 为该 `1` 所在的位置。

因为最后两次不会抢队，所以只有一次抢队的序列为 `\{1,0,0,0,0\}`, `\{0,1,0,0,0\}`, `\{0,0,1,0,0\}`，故方法总数为 `(5-2)\times2\times2\times2\times1+2\times(4-2)\times2\times2\times1+2\times2\times(3-2)\times2\times1=2^3\times(3+2+1)=48`。

一般情况，计算 `n` 辆车全部出车共有 `k` 次抢队的方法数也是一样的。

当序列中所有的 `1` 出现的位置为 `\{a_1,a_2,\ldots,a_k\}` 时的方法数为
\[2^{n-k-1}(n-a_1+1-2)(n-a_2+1-2)\cdots(n-a_k+1-2),\]于是，当 `\{a_1,a_2,\ldots,a_k\}` 取遍 `\{1,2,\ldots,n-2\}` 的所有子集时，它们的和就是所求，也就是
\[2^{n-k-1}\sum_{\{a_1,\ldots,a_k\}\subset\{1,\ldots,n-2\}}(n-a_1-1)(n-a_2-1)\cdots(n-a_k-1).\]
这结果不知还能不能化简？
$\href{https://kuingggg.github.io/}{\text{About Me}}$

TOP

realnumber

4#
发表于 2019-6-3 14:23 | 只看该作者
本帖最后由 realnumber 于 2019-6-3 14:27 编辑

由2楼解答，没有抢队，就是左边两边选择，就是$2^4=16$种，
对“一次抢队”的位置进行分类，
第1次抢队  $3\times 2^3$
第2次抢队  $2\times 2^3$
第3次抢队  $2^3$
以上和就是答案48.n辆车,1次抢队似乎也适用
那么问题变为n辆车,m次抢队?其中n远大于m.楼上已经解决了

TOP

返回列表 回复 发帖