每日一题[1802]映射计数

一种密码锁的密码设置是在正 $n$ 边形 $A_1A_2\cdots A_n$ 的每个顶点处赋值 $0$ 和 $1$ 两个数中的一个,同时在每个顶点处涂染红、蓝两种颜色之一,使得任意相邻的两个顶点的数字或颜色中至少有一个相同.问:该种密码锁共有多少种不同的密码设置?

答案    $3^n+2+(-1)^n$.

解析   

引入映射    对于该种密码锁的一种密码设置,如果相邻两个顶点上所赋值的数字不同,在它们所在的边上标上 $a$,如果颜色不同,则标上 $b$,如果数字和颜色都相同,则标上 $c$.于是对于给定的点 $A_1$ 上的设置(共有 $4$ 种),按照边上的字母可以依次确定点 $A_2,A_3,\cdots,A_n$ 上的设置.为了使得最终回到 $A_1$ 时的设置与初始时相同,标有 $a$ 和 $b$ 的边都是偶数条.所以这种密码锁的所有不同的密码设置方法数等于在边上标记 $a,b,c$,使得标有 $a$ 和 $b$ 的边都是偶数条的方法数的 $4$ 倍.

开始计数    设标有 $a$ 的边有 $2i$ 条,$0\leqslant i \leqslant \left[\dfrac n2\right]$,标有 $b$ 的边有 $2j$ 条,则\[0\leqslant j \leqslant \left[\dfrac {n-2i}{2}\right],\]选取 $2i$ 条边标记 $a$ 的有 $\mathop{\rm C}\nolimits_n^{2i}$ 种方法,在余下的边中取出 $2j$ 条边标记 $b$ 的有 $\mathop{\rm C}\nolimits_{n-2i}^{2j}$ 种方法,其余的边标记 $c$.由乘法原理,此时共有 $\mathrm C_n^{2i}\mathrm C_{n-2i}^{2j}$ 种标记方法.对 $i,j$ 求和,密码锁的所有不同的密码设置方法数为\[f(n)=4\sum \limits_{i=1}^{\left[\frac n2\right]}\left(\mathop{\rm C}\nolimits_n^{2i}\sum \limits_{j=0}^{\left[\frac {n-2i}{2}\right]}\mathop{\rm C}\nolimits_{n-2i}^{2j}\right),\]这里我们约定 $\mathop{\rm C}\nolimits_0^{0}=1$.

化简计算

情形一    当 $n$ 为奇数时,$n-2i>0$,此时$$\sum \limits_{j=0}^{\left[\frac {n-2i}{2}\right]}\mathop{\rm C}\nolimits_{n-2i}^{2j}=2^{n-2i-1},$$从而\[f(n)=4\sum \limits_{i=0}^{\left[\frac n2\right]}\left(\mathop{\rm C}\nolimits_n^{2i}2^{n-2i-1}\right)=2\sum \limits_{i=0}^{\left[\frac n2\right]}\left(\mathrm C_n^{2i}2^{n-2i}\right)=\sum \limits_{k=0}^{n}\mathop{\rm C}\nolimits_ n^{k}2^{n-k}+\sum \limits_{k=0}^{n}\mathop{\rm C}\nolimits_ n^{k}2^{n-k}(-1)^k=3^n+1.\]

情形二    当 $n$ 为偶数时,若 $i <\dfrac n2$,与奇数情形类似;若 $i=\dfrac n2$,则正 $n$ 边形的所有边都标记 $a$,此时只有一种标记方法.于是当 $n$ 为偶数时,所有不同的密码设置的方法数为\[f(n)=4\left(1+\sum \limits_{i=0}^{\left[\frac n2\right]-1} (\mathop{\rm C}\nolimits_n^{2i}2^{n-2i-1})\right)= 2+4\sum \limits_{i=0}^{ \left[\frac n2\right]}(\mathop{\rm C}\nolimits_ n^{2i}2^{n-2i-1})=3^n+3.\]

综上所述,这种密码锁的所有不同的密码设置方法数 $3^n+2+(-1)^n$.

此条目发表在每日一题分类目录,贴了标签。将固定链接加入收藏夹。

发表回复