免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] 一道答案错误的指派问题

某市践行“干部村村行”活动,现有3名干部可供选派,下乡到5个村蹲点指导工作,每个村至少有1名干部,每个干部至多住3个村,则不同的选派方案共多少种?
答案给的是150,是按每村刚好一名干部,并且干部不能空闲来算的。
我那电脑算的是 如果3名干部可以空闲,算的是5220;如果3名干部不能空闲,算的是5070.
想问下有没有笔算的方法。
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

分配表相当于5x3的真值表,因此可用5组3位数的二进制数表示,其中二进制各位数码分别表示三个干部是否分配到该村(数码1表示分配,0表示不分配)。

若每村刚好一名干部,说明二进制数对应的十进制值只能是1,2,4中的一个;干部不能空闲,说明5组二进制数对应的十进制数值中1,2,4必须都出现(至少一次)。因此可能的组合是:
a. {1,2,4,4,4},{1,2,2,2,4},{1,1,1,2,4}
五个元素其中有三个相同元素的全排列,共3种情况,故一共$3A_5^5/3!=60$种。
b. {1,1,2,2,4},{1,2,2,4,4},{1,1,2,4,4}
五个元素中有两对相同的全排列,一共3组,故为$3A_5^5/(2!2!)=90$种。
综上可知,一共有90+60=150种分配方案。

TOP

回复 2# Infinity
谢谢,我也是按3X5的真值表做的。如果去掉每村只有一个干部的限制呢?

TOP

“每个村至少有1名干部”说明只能是数字1到7,“每个干部至多住3个村”说明1357至多出现3次(包括重复),类似地,2367和4567同样是如此。于是出现这三组可候选数字:3-1-5-7,2-3-6-7,4-5-6-7,将其拼接可以绘制出一个数字关联图模型。

从图中可以看出,7是三组数的连接点,故是关键数,而1,2,4则是独立数(因为没有出现在多组数中)。因此可以不断去拆分关键数来分析情况。比如讨论7出现和不出现,在7不出现的情况中6又成为关键数,则又分为6出现和不出现。6不出现的情况中,3,5是关键数。这样去分析就能得到最终结果。

如果干部不可以空闲,只需减去空闲的情况即可。计算至少有一个空闲、至少有两个空闲的情况。然后利用容斥原理可算出不全空闲的结果。将前面算出的结果减去这个结果就是不能空闲的结果。

其实很容易看出,这类问题没有通解公式,因为它跟图相关,也就是约束条件不同,产生了不同的图关系,且随着状态数以及网格大小的变化,会改变图的关系(因此没有显式通用表达)。类似之前那个红蓝染色nxn方格,要求每行每列都有红蓝色的帖子一样。

TOP

本帖最后由 tommywong 于 2019-4-28 11:52 编辑

$(a+b+c+ab+ac+bc+abc)^5=\sum f(k_a,k_b,k_c)a^{k_a}b^{k_b}c^{k_c}$

$(a+b+c+ab+ac+bc+abc)^5=((1+a)(1+b)(1+c)-1)^5$

$=\displaystyle \sum_{r=0}^5 (-1)^{5-r}\binom{5}{r}((1+a)(1+b)(1+c))^r

=\sum_{r=0}^5 (-1)^{5-r}\binom{5}{r}\left(\sum_{k_a=0}^r\binom{r}{k_a}a^{k_a}\right)
\left(\sum_{k_b=0}^r\binom{r}{k_b}b^{k_b}\right)
\left(\sum_{k_c=0}^r\binom{r}{k_c}c^{k_c}\right)$

$\displaystyle \sum_{0\le k_a,k_b,k_c\le 3}f(k_a,k_b,k_c)
=\sum_{r=0}^5 (-1)^{5-r}\binom{5}{r}
\left(\sum_{k=0}^{min\{r,3\}}\binom{r}{k}\right)^3$

$=-\binom{5}{0}1^3+\binom{5}{1}2^3-\binom{5}{2}4^3+\binom{5}{3}8^3
-\binom{5}{4}15^3+\binom{5}{5}26^3=5220$

$\displaystyle \sum_{1\le k_a,k_b,k_c\le 3}f(k_a,k_b,k_c)
=\sum_{r=1}^5 (-1)^{5-r}\binom{5}{r}
\left(\sum_{k=1}^{min\{r,3\}}\binom{r}{k}\right)^3$

$=\binom{5}{1}1^3-\binom{5}{2}3^3+\binom{5}{3}7^3
-\binom{5}{4}14^3+\binom{5}{5}25^3=5070$

TOP

本帖最后由 tommywong 于 2019-4-28 13:59 编辑

某市践行“干部村村行”活动,现有n名干部可供选派,下乡到m个村蹲点指导工作,
每个村至少有1名干部,每个干部至少住a个村,至多住b个村,则不同的选派方案共多少种?

$\displaystyle \sum_{r=a}^m (-1)^{m-r}\binom{m}{r}\left(\sum_{k=a}^{min\{r,b\}}\binom{r}{k}\right)^n
=\sum_{r=a}^b (-1)^{m-r}\binom{m}{r}\left(\sum_{k=a}^{r}\binom{r}{k}\right)^n+
\sum_{r=b+1}^m (-1)^{m-r}\binom{m}{r}\left(\sum_{k=a}^{b}\binom{r}{k}\right)^n$

TOP

返回列表 回复 发帖