计数(排列组合)问题

力工

某校一年级有10个班，5人任教，每人2个班。若姜一定教1班，张一定教3班，王一定教8班，但不教5班；秋至少教9班和10班中的一个班，曲不能教2班和6班，则不同的排课安排共有多少种？
太乱了，我是一笔胡涂账了。求求大家给个好思路。

realnumber

准备一张大些的草稿纸，....

Czhang271828

闲来无事试一下, 翻车概率大, 蹲一个程序验证.

原题目信息化简作以下草稿, 应该可以看懂, 就不说明了
$$
\begin{matrix}
\text{姜}&\text{张}&\text{王}&\text{秋}&\text{曲}\\
[1]&[3]&[8]&[9]'&\\
&&-5&[10]'&-2\\
&&&&-6
\end{matrix}
$$
Step I 从秋的情况分类. 得以下两类情况

(1) 秋教 9 但不教 10 ;

(2) 秋同时教 9 与 10 .

以上 (1) 等价于命题 '秋教 9 但不教 10 ' 从而总排课数为 $2\cdot |(1)|+|(2)|$.

Step II 若 (1), 则
$$
\begin{matrix}
\text{姜}&\text{张}&\text{王}&\text{秋}&\text{曲}\\
[1]&[3]&[8]&[9]&\\
&&-5&-10&-2\\
&&&&-6
\end{matrix}
$$
根据对称性, 只需考虑下三类情况

(a) 曲教 5 与 10, 此时计算满足下图的排列数, 得 $24$.
$$
\begin{matrix}
\text{姜}&\text{张}&\text{王}&\text{秋}&\text{曲}\\
[1]&[3]&[8]&[9]&[5]\\
&&&&[10]\\
\end{matrix}
$$
(b) 曲教 4 与 5, 此时计算满足下图的排列数, 得 $24-6=18$.
$$
\begin{matrix}
\text{姜}&\text{张}&\text{王}&\text{秋}&\text{曲}\\
[1]&[3]&[8]&[9]&[4]\\
&&&-10&[5]\\
\end{matrix}
$$
(c) 曲教 4 与 7. 此时计算满足下图的排列数, 得 $24-6-6+2=14$.
$$
\begin{matrix}
\text{姜}&\text{张}&\text{王}&\text{秋}&\text{曲}\\
[1]&[3]&[8]&[9]&[4]\\
&&-5&-10&[7]\\
\end{matrix}
$$
因此 Step II 中的排课方法数为 $|(1)|=|(a)|+4\cdot |(b)|+|(c)|=110$.

Step III 若 (2), 则
$$
\begin{matrix}
\text{姜}&\text{张}&\text{王}&\text{秋}&\text{曲}\\
[1]&[3]&[8]&[9]&\\
&&&[10]&\\
&&-5&&-2\\
&&&&-6
\end{matrix}
$$
根据对称性, 只需考虑下两类情况

(e) 王教 2. 此时计算满足下图的排列数, 得 $24/2-6=6$.
$$
\begin{matrix}
\text{姜}&\text{张}&\text{王}&\text{秋}&\text{曲}\\
[1]&[3]&[8]&[9]&\\
&&[2]&[10]&\\
&&&&-6\\
\end{matrix}
$$
(f) 王教 4 此时计算满足下图的排列数, 得 $2$.
$$
\begin{matrix}
\text{姜}&\text{张}&\text{王}&\text{秋}&\text{曲}\\
[1]&[3]&[8]&[9]&\\
&&[4]&[10]&\\
&&&&-2\\
&&&&-6
\end{matrix}
$$
因此 Step III 中的排课方法数为 $|(2)|=2\cdot |(e)|+2|(f)|=16$.

Step IV 计算 Step I 中的总排课数 $2\cdot |(1)|+|(2)|=236$.

力工

Czhang271828 发表于 2023-5-29 20:10
闲来无事试一下, 翻车概率大, 蹲一个程序验证.

原题目信息化简作以下草稿, 应该可以看懂, 就不说明了

考试时这样的题15分钟太难了。😇

tommywong

$\begin{array}{|c|c|c|c|c|c|c|c|c|c|}
\hline
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\
\hline
a & X~e & b & ~ & X~c & X~e & ~ & c & d? & d?\\
\hline
\end{array}$
薑=a, 張=b, 王=c, 秋=d, 曲=e
coefficient[(2d(a+b+c+e)+d^2)(a+b+d+e)(a+b+c+d)^2 (a+b+c+d+e)^2,abcd^2 e^2]
展開好麻煩, 我掉畀WolframAlpha
wolframalpha.com/input?i=coefficient%5B%282d% … %2Cabcd%5E2+e%5E2%5D

tommywong

$s=a+b+c+d+e$
$[abcd^2 e^2](2ds-d^2)(s-c)(s-e)^2 s^2$
$=[abcde^2](2s-d)(s-c)(s-e)^2 s^2$
$=(2[abcde^2]s^3-[abce^2]s^2)(s-c)(s-e)^2$
$=(2[abcde^2]s^4-3[abde^2]s^3+[abe^2]s^2)(s^2-2es+e^2)$
$=(2[abcde^2]s^6-3[abde^2]s^5+[abe^2]s^4)$
$~-2(2[abcde]s^5-3[abde]s^4+[abe]s^3)$
$~+(2[abcd]s^4-3[abd]s^3+[ab]s^2)$
$=2\times\dfrac{6!}{2!}-3\times\dfrac{5!}{2!}+\dfrac{4!}{2!}
-4(5!)+6(4!)-2(3!)+2(4!)-3(3!)+2!$
$=236$

abababa

这就是有约束的二部图匹配问题吧？可能是能用整数规划那种来求一个解，但不知道能不能求出解的个数。

tommywong

實際上嘅問題係要其中一個解，但係有教無類，根本就冇嘢值得匹配。我哋只不過係同緊一堆垃圾數據打交道嘅戇鳩仔。

kuing

tommywong 发表于 2023-5-30 10:01
$\begin{array}{|c|c|c|c|c|c|c|c|c|c|}
\hline
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\
\hline
a & X~e & b & ~ & X~c & X~e & ~ & c & d? & d?\\
\hline
\end{array}$
薑=a, 張=b, 王=c, 秋=d, 曲=e
...

明白鸟
2 班不让 e，可选 abcd，6 班同理，所以有 `(a+b+c+d)^2`；
4、7 班无限制，所以有 `(a+b+c+d+e)^2`；
5 班不让 c，所以有 `(a+b+d+e)`；
9、10 班有两种情况：两个都是 d，即 `d^2`；一 d 一非 d，就是 `2d(a+b+c+e)`，所以有 `\bigl(d^2+2d(a+b+c+e)\bigr)`。
所以符合的排课数为
\[(a+b+c+d)^2(a+b+c+d+e)^2(a+b+d+e)\bigl(d^2+2d(a+b+c+e)\bigr)\]
的展开式中 `abcd^2e^2` 的系数。

乌贼

realnumber 发表于 2023-5-29 14:11
准备一张大些的草稿纸，....

拿一张更大的草稿纸
先让秋选，再分析曲的情况进行排列组合。
首先让曲在$ 2、4、5、6、7 $五个班中任选两个班，有$ 10 $种情况，逐个计算😂
1
   曲教$ 9、10 $班时不符合
2
   曲教$ 9、5 $班时，$ 10 $班必须秋教，余$ 2、4、6、7 $班姜张王秋任选，有$ 24 $种
3  
    曲教$ 10、5 $班时，$ 9 $班必须秋教，余$ 2、4、6、7 $班姜张王秋随便选，也有$ 24 $种
4  
    曲教$ 4、5$班时，秋教的班有二种情况
    1）秋同时教$ 9、10 $班的情况下余$ 2、6、7 $任姜张王任选，有$ 6 $种
    2）秋只教$ 9、10 $中一个班的情况下剩$ 2、6、7 $及$ 9、10 $班中的另一个班共$ 4 $个班，先由秋在$ 2、6、7 $班中任选一个班，余$ 3 $个班由姜张王任选，有$ 36 $种
   共有$ 6+36=42 $种
5
    同理曲教$ 7、5$班时，有$ 42 $种
6
     曲教$ 4、9$班时，$ 10 $班必须秋教，余$ 2、,5、6、7 $班姜张王秋选，秋不能选$ 5 $班，有$ 18 $种
7
   同理曲教$ 4、10$班时，有$ 18 $种
8
   同理曲教$ 7、9$班时，有$ 18 $种
9
   同理曲教$ 7、10$班时，有$ 18 $种
10
   曲教$ 4、7 $班时，秋教的班有三种情况：
  1）同时教$ 9、10 $班，有$ 4 $种
  2）教$ 5 $班及$ 9、10 $中的一个，有$ 12 $种
  3）分别教$ 9、10 $班及$ 4、7 $班中的任一个，有$ 16 $种
   共有$ 32 $种
综上一共有$ 236 $种