每日一题[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$．