悠闲数学娱乐论坛(第2版) » 初等数学讨论 » 排列组合（不相邻且至多2个空位）

lrh2006 发表于 2019-2-5 23:24

排列组合（不相邻且至多2个空位）

某电影院一排有10个座位，现有4名观众就坐，若他们每两人都不能相邻，且要求每人左右两边至多只有2个空位，则不同的坐法种数共有几种？
请各位高手指点，谢谢！

色k 发表于 2019-2-5 23:45

记四人从左到右为 A、B、C、D，用 O 表示空座。
由于不能相邻，先在前三人的右边各捆绑一个 O，即：AO、BO、CO、D。
剩下三个 O，有五个位置可以插入，而由于不能出现 OOO，故前后的可放两个，中间的只可放一个，然后你可以分类列举一下。
我就懒得列了，直接展开 `(1+x+x^2)^2(1+x)^3` 可知有一项是 `18x^3`，所以结果就是 18。

业余的业余 发表于 2019-2-6 06:41

用笨办法。

只考察ABCD按照这个顺序从左到右的坐法。假定这样得到的坐法为 $n$ 种, 那么显然总坐法为 $4!n=24n$ 种。

先在每两个人之间放一个空位，这样就保证满足两两不相邻的限制了。这样还有3个空位。边上有点讨厌，我们把最左/右边有两个空位的情形分开处理，显然这种情形下的安排座位的方法(这里是安排空位)为 $2\times C_4^1=8$ （乘2，因为两个空位可以顺在最左，也可顺在最右，之后，4个人中间的三个位置和剩下的一个最左或最右的位置中选一个安放剩下的一个空位)

然后剩下从4个人中间及最边上共5个位置上选三个来安放剩下三个空位， $C_5^3=C_5^2=10$

综上，总坐法有 $24\times (8+10)=432$ 种

色k 发表于 2019-2-6 09:28

好吧，看来我忘了乘以4!，只顾着插，忘了轮{:mad:}

lrh2006 发表于 2019-2-6 10:17

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=29715&ptid=5872]3#[/url] [i]业余的业余[/i] [/b]

嗯嗯，明白了，谢谢谢谢！

lrh2006 发表于 2019-2-6 10:21

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=29710&ptid=5872]2#[/url] [i]色k[/i] [/b]


    kk，你呀。咦，你今天怎么这么早就在线了

kuing 发表于 2019-2-6 12:42

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=29719&ptid=5872]6#[/url] [i]lrh2006[/i] [/b]

这只是个意外{:tongue:}
PS、修改了标题

realnumber 发表于 2019-2-6 16:23

X表示人O表示空位,基本先排好XOXOXOX
XOOXOOXOOX(余下三O在中间,1种)
OXOOXOOXOX（余下三O，2个在中间，一个在一侧,6种）
OXOOXOXOOX
OXOXOOXOOX
XOOXOOXOXO
XOOXOXOOXO
XOXOOXOOXO
OXOOXOXOXO（余下三O，1个在中间，2个在2侧，9种）
OXOXOOXOXO
OXOXOXOOXO
OOXOOXOXOX
OOXOXOOXOX
OOXOXOXOOX
XOOXOXOXOO
XOXOOXOXOO
XOXOXOOXOO
OXOXOXOXOO（余下三O，3个在2侧，2种）
OOXOXOXOXO
一共18种，再$18\times4!$
进一步简化:
基本排好后XOXOXOX，分2类：
1.为5个位置各插一个O$C_5^3$.
2.左或右放2个O，余下4个位置再插一个O,$2C_4^1$.
总数10+8.发现就是3楼的办法.

lrh2006 发表于 2019-2-6 17:34

嗯嗯,明白了.这个论坛真好,谢谢大家

业余的业余 发表于 2019-2-7 04:56

@色k 老兄的是比较高级的办法，我不会。俄国人的一本数学分析习题集一开篇就是一堆这类问题，好像是堆垒数论还是丢番图啥的。有什么简单点的书可以推荐下吗？

kuing 发表于 2019-2-8 00:17

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=29741&ptid=5872]10#[/url] [i]业余的业余[/i] [/b]

你说的“堆垒数论还是丢番图啥的”我一点都不懂……
我用那个展开的道理其实很简单，完全不需要什么高级理论。
展开 `(1+x+x^2)(1+x)(1+x)(1+x)(1+x+x^2)` 在合并同类项之前，每项都是从五个括号里各选一项来乘，这就等同于我往五个位置插入若干个O，第一个括号 `(1+x+x^2)` 就等同于最左边可插 0 个或 1 个或 2 个，其余类似，而现在总共要插三个O，所以完全展开合并同类项后 `x^3` 的系数就是插O的方法数。

业余的业余 发表于 2019-2-8 08:59

[i=s] 本帖最后由 业余的业余 于 2019-2-9 22:00 编辑 [/i]

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=29759&ptid=5872]11#[/url] [i]kuing[/i] [/b]

我似乎明白你的意思了，还要好好想一下。谢谢了。

豁然开朗，妙不可言！{:tongue:}

游客 发表于 2019-3-11 14:20

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=29759&ptid=5872]11#[/url] [i]kuing[/i] [/b]


插之前也不用先绑着，最后看6就可以了。
即：$(1+x+x^2)(x+x^2)(x+x^2)(x+x^2)(1+x+x^2)$的展开式中$x^6$的系数.

游客 发表于 2019-3-11 14:34

数字表示连续的空位数，“✔”表示观众，可分为以下3类：
✔2✔2✔2✔、2✔2✔1✔1、2✔1✔1✔1✔1.
N=(1+6x2+5)X24.

kuing 发表于 2019-3-11 14:52

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30256&ptid=5872]13#[/url] [i]游客[/i] [/b]

嗯，是的。

查看完整版本: 排列组合（不相邻且至多2个空位）