题目
有 2024 个有标号的球（即球与球之间是不同的）将要被红、绿、蓝、白四种颜色染色，每个球都独立等概率的随机被染成四种颜色之一，求恰好有奇数个球被染成红色、偶数个球被染成绿色、奇数个球被染成蓝色的概率。
若是 2023 个球呢？若是 n 个球呢？
解析
法一：直觉分析
对于 2024 个球来说，恰好有奇数个球被染成红色、偶数个球被染成绿色、奇数个球被染成蓝色、偶数个球被染成白色的概率，直觉上来说就是 \dfrac{ 1 }{ 8 }，用数学归纳法也容易证明。
但是这种做法只能停留在偶数个球上，如果是奇数个球的话，恰好有奇数个球被染成红色、偶数个球被染成绿色、奇数个球被染成蓝色、奇数个球被染成白色的概率，直觉上来说就不再是 \dfrac{ 1 }{ 8 }，而是略小于该值，多次实验可以发现概率是 \dfrac{ 1 }{ 8 } - \dfrac{ 1 }{ 4^{ n + 1 } }，用数学归纳法也容易证明。
但是这种做法局限性很大，完全是在猜答案，所以我们需要更优秀的做法。
法二：矩阵递推
直接考虑 n 个球的染色方案。
设向量：
\boldsymbol{ P }_{ n } =
\begin{pmatrix}
a_{ 1, n } \\
a_{ 2, n } \\
a_{ 3, n } \\
a_{ 4, n } \\
a_{ 5, n } \\
a_{ 6, n } \\
a_{ 7, n } \\
a_{ 8, n }
\end{pmatrix}
其中 a_{ i, n } 代表给 n 个球染色，染色状态为 i 的方案数（其中状态为 1 就是偶红偶绿偶蓝也可记为 000，其他状态类似，所求即为状态 6 可记为 101）。不难列出转移方程 P_{ n } = A \cdot P_{ n - 1 }，其中：
\boldsymbol{ A } =
\begin{pmatrix}
1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\
1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\
1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 \\
0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\
0 & 1 & 0 & 0 & 1 & 1 & 0 & 1 \\
0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 \\
0 & 0 & 0 & 1 & 0 & 1 & 1 & 1
\end{pmatrix}
且有：
\boldsymbol{ P }_{ 0 } =
\begin{pmatrix}
1 \\
0 \\
0 \\
0 \\
0 \\
0 \\
0 \\
0
\end{pmatrix}
则有
\boldsymbol{ A }^{ n } =
2^{ n - 3 } \begin{pmatrix}
3 + ( -1 )^{ n } + 2^{ n } & 1 - ( -1 )^{ n } + 2^{ n } & 1 - ( -1 )^{ n } + 2^{ n } & -1 + ( -1 )^{ n } + 2^{ n } & 1 - ( -1 )^{ n } + 2^{ n } & -1 + ( -1 )^{ n } + 2^{ n } & -1 + ( -1 )^{ n } + 2^{ n } & -3 - ( -1 )^{ n } + 2^{ n } \\
1 - ( -1 )^{ n } + 2^{ n } & 3 + ( -1 )^{ n } + 2^{ n } & -1 + ( -1 )^{ n } + 2^{ n } & 1 - ( -1 )^{ n } + 2^{ n } & -1 + ( -1 )^{ n } + 2^{ n } & 1 - ( -1 )^{ n } + 2^{ n } & -3 - ( -1 )^{ n } + 2^{ n } & -1 + ( -1 )^{ n } + 2^{ n } \\
1 - ( -1 )^{ n } + 2^{ n } & -1 + ( -1 )^{ n } + 2^{ n } & 3 + ( -1 )^{ n } + 2^{ n } & 1 - ( -1 )^{ n } + 2^{ n } & -1 + ( -1 )^{ n } + 2^{ n } & -3 - ( -1 )^{ n } + 2^{ n } & 1 - ( -1 )^{ n } + 2^{ n } & -1 + ( -1 )^{ n } + 2^{ n } \\
-1 + ( -1 )^{ n } + 2^{ n } & 1 - ( -1 )^{ n } + 2^{ n } & 1 - ( -1 )^{ n } + 2^{ n } & 3 + ( -1 )^{ n } + 2^{ n } & -3 - ( -1 )^{ n } + 2^{ n } & -1 + ( -1 )^{ n } + 2^{ n } & -1 + ( -1 )^{ n } + 2^{ n } & 1 - ( -1 )^{ n } + 2^{ n } \\
1 - ( -1 )^{ n } + 2^{ n } & -1 + ( -1 )^{ n } + 2^{ n } & -1 + ( -1 )^{ n } + 2^{ n } & -3 - ( -1 )^{ n } + 2^{ n } & 3 + ( -1 )^{ n } + 2^{ n } & 1 - ( -1 )^{ n } + 2^{ n } & 1 - ( -1 )^{ n } + 2^{ n } & -1 + ( -1 )^{ n } + 2^{ n } \\
-1 + ( -1 )^{ n } + 2^{ n } & 1 - ( -1 )^{ n } + 2^{ n } & -3 - ( -1 )^{ n } + 2^{ n } & -1 + ( -1 )^{ n } + 2^{ n } & 1 - ( -1 )^{ n } + 2^{ n } & 3 + ( -1 )^{ n } + 2^{ n } & -1 + ( -1 )^{ n } + 2^{ n } & 1 - ( -1 )^{ n } + 2^{ n } \\
-1 + ( -1 )^{ n } + 2^{ n } & -3 - ( -1 )^{ n } + 2^{ n } & 1 - ( -1 )^{ n } + 2^{ n } & -1 + ( -1 )^{ n } + 2^{ n } & 1 - ( -1 )^{ n } + 2^{ n } & -1 + ( -1 )^{ n } + 2^{ n } & 3 + ( -1 )^{ n } + 2^{ n } & 1 - ( -1 )^{ n } + 2^{ n } \\
-3 - ( -1 )^{ n } + 2^{ n } & -1 + ( -1 )^{ n } + 2^{ n } & -1 + ( -1 )^{ n } + 2^{ n } & 1 - ( -1 )^{ n } + 2^{ n } & -1 + ( -1 )^{ n } + 2^{ n } & 1 - ( -1 )^{ n } + 2^{ n } & 1 - ( -1 )^{ n } + 2^{ n } & 3 + ( -1 )^{ n } + 2^{ n }
\end{pmatrix}
则：
\boldsymbol{ P }_{ n } = \boldsymbol{ A }^{ n } \cdot \boldsymbol{ P }_{ 0 } =
2^{ n - 3 } \begin{pmatrix}
3 + ( -1 )^{ n } + 2^{ n } \\
1 - ( -1 )^{ n } + 2^{ n } \\
1 - ( -1 )^{ n } + 2^{ n } \\
-1 + ( -1 )^{ n } + 2^{ n } \\
1 - ( -1 )^{ n } + 2^{ n } \\
-1 + ( -1 )^{ n } + 2^{ n } \\
-1 + ( -1 )^{ n } + 2^{ n } \\
-3 - ( -1 )^{ n } + 2^{ n }
\end{pmatrix}
则答案即为：
\begin{aligned}
\dfrac{ 1 }{ 4^{ n } } \cdot ( \boldsymbol{ P }_{ n } )_{ 6 }
& = \dfrac{ 1 }{ 4^{ n } } \cdot
\left ( 2^{ n - 3 } \begin{pmatrix}
3 + ( -1 )^{ n } + 2^{ n } \\
1 - ( -1 )^{ n } + 2^{ n } \\
1 - ( -1 )^{ n } + 2^{ n } \\
-1 + ( -1 )^{ n } + 2^{ n } \\
1 - ( -1 )^{ n } + 2^{ n } \\
-1 + ( -1 )^{ n } + 2^{ n } \\
-1 + ( -1 )^{ n } + 2^{ n } \\
-3 - ( -1 )^{ n } + 2^{ n }
\end{pmatrix} \right )_{ 6 } \\
& = 2^{ -n - 3 } \left ( -1 + ( -1 )^{ n } + 2^{ n } \right ) \\
& = \dfrac{ 1 }{ 8 } - \dfrac{ 1 - ( -1 )^{ n } }{ 2^{ n + 3 } }
\end{aligned}
这种做法看似很优美，但是矩阵求幂的化简是极为痛苦的步骤，所以我们仍然需要更优秀的做法。
法三：生成函数
对于有标号计数，考虑使用 EGF 生成函数，不难列出四种颜色的生成函数分别为：
\begin{aligned}
\hat{ G }_{ R } ( x ) & = \dfrac{ x^{ 1 } }{ 1! } + \dfrac{ x^{ 3 } }{ 3! } + \dfrac{ x^{ 5 } }{ 5! } + \ldots = \dfrac{ \mathrm{ e }^{ x } - \mathrm{ e }^{ -x } }{ 2 } \\
\hat{ G }_{ G } ( x ) & = \dfrac{ x^{ 0 } }{ 0! } + \dfrac{ x^{ 2 } }{ 2! } + \dfrac{ x^{ 4 } }{ 4! } + \ldots = \dfrac{ \mathrm{ e }^{ x } + \mathrm{ e }^{ -x } }{ 2 } \\
\hat{ G }_{ B } ( x ) & = \dfrac{ x^{ 1 } }{ 1! } + \dfrac{ x^{ 3 } }{ 3! } + \dfrac{ x^{ 5 } }{ 5! } + \ldots = \dfrac{ \mathrm{ e }^{ x } - \mathrm{ e }^{ -x } }{ 2 } \\
\hat{ G }_{ W } ( x ) & = \dfrac{ x^{ 0 } }{ 0! } + \dfrac{ x^{ 1 } }{ 1! } + \dfrac{ x^{ 2 } }{ 2! } + \ldots = \mathrm{ e }^{ x }
\end{aligned}
所以总染色方案数的生成函数即为：
\begin{aligned}
\hat{ G } ( x ) & = \hat{ G }_{ R } ( x ) \cdot \hat{ G }_{ G } ( x ) \cdot \hat{ G }_{ B } ( x ) \cdot \hat{ G }_{ W } ( x ) \\
& = \mathrm{ e }^{ x } \cdot \dfrac{ \mathrm{ e }^{ x } + \mathrm{ e }^{ -x } }{ 2 } \cdot \left ( \dfrac{ \mathrm{ e }^{ x } - \mathrm{ e }^{ -x } }{ 2 } \right )^{ 2 } \\
& = \dfrac{ \mathrm{ e }^{ 4 x } - \mathrm{ e }^{ 2 x } - 1 + \mathrm{ e }^{ -2 x } }{ 8 } \\
& = \dfrac{ 1 }{ 8 } \sum_{ n = 1 }^{ \infty }{ \left ( 4^{ n } - 2^{ n } + ( -2 )^{ n } \right ) \dfrac{ x^{ n } }{ n! } }
\end{aligned}
所以 n 个球的染色方案数就为 \left [ \dfrac{ x^{ n } }{ n! } \right ] \hat{ G } ( x ) = \dfrac{ 4^{ n } - 2^{ n } + ( -2 )^{ n } }{ 8 }。
所以概率就为 \dfrac{ 1 }{ 4^{ n } } \cdot \dfrac{ 4^{ n } - 2^{ n } + ( -2 )^{ n } }{ 8 } = \dfrac{ 1 }{ 8 } - \dfrac{ 1 - ( -1 )^{ n } }{ 2^{ n + 3 } }。
by CXY。