带限制的可重复排列组合问题

kastin

有m个2，n个3，p个5和q个7，用这些数字组成一个 `\lfloor \frac{m+n+p+q}{4} \rfloor`位数，问这样的不同的数共有多少种？

若给定m,n,p,q的话，可以求出所有组合中2,3,5,7出现次数的可能性，然后分别计算排列数，最后求和。但是若这些数字过大，则不不定方程`x+y+z+u=\lfloor \frac{m+n+p+q}{4} \rfloor`的解过多，分别计算则显得麻烦。
试问有无巧算思路？

可以先从简单的实例化讨论。

BeerRabbit

似乎可以考虑指数型母函数。

Lwins_G

用容斥原理，计算$2^4-1=15$个组合数的加减即可。

northwolves

$S=\lfloor \frac{m+n+p+q}{4} \rfloor$,求$x+y+z+u=S$,,$x,y,z,u$分别在0 与$m,n,p,q$间取值

gxqcn

对于满足楼上不定方程的一组任意解\((x,y,z,u)\)，则对应的排列数为\(\dfrac{S!}{x!y!z!u!}\)；然后由加法原理，求总数。
注：刚刚我翻了一本《组合数学》，里面多重集的子排列，举得的例子就是楼主描述的方法，估计没有更加有效精巧的方法吧。

northwolves

母函数\((1+x+x^2+\dots+x^m)(1+x+x^2+\dots+x^n)(1+x+x^2+\dots+x^p)(1+x+x^2+\dots+x^q)=\frac{(1-x^{m+1})(1-x^{n+1})(1-x^{p+1})(1-x^{q+1})}{(1-x)^4}\)
中，\(x^S\)的系数怎么求方便？

northwolves

northwolves 发表于 2014-6-12 19:38
$S=\lfloor \frac{m+n+p+q}{4} \rfloor$,求$x+y+z+u=S$,,$x,y,z,u$分别在0 与$m,n,p,q$间取值

我用递归，m,n,p,q分别等于200，400，600，800时，求得解数  188496701 。确实很慢

northwolves

重新考虑，似乎答案就是 $P(m+n+p+q,\lfloor \frac{m+n+p+q}{4} \rfloor)=\frac{(m+n+p+q)!}{(m+n+p+q-\lfloor \frac{m+n+p+q}{4} \rfloor)!}$

kastin

这个问题3楼的思路应该可行，只不过稍微复杂一点。

刚刚看到又一个带限制的重复元素排列问题，来自数学竞赛吧的帖子http://tieba.baidu.com/p/4834680971，@Lwins_G 不知容斥原理如何进行分析？
问题

由数字1,2,3,4,5,6构成的含有1,6相邻的n位数有多少种？

这个问题意思应该是“至少出现一对1,6相邻”。大家来思考一下。

kastin

kastin 发表于 2016-10-27 12:12
这个问题3楼的思路应该可行，只不过稍微复杂一点。

刚刚看到又一个带限制的重复元素排列问题，来自数学 ...

想到方法了，考虑原问题的反面——由数字1,2,3,4,5,6构成的没有1,6相邻的 `n` 位数，设有 `p_n` 种，那么可以分解为三种情形：

1. 由数字1,2,3,4,5,6构成的没有1,6相邻，且最后一位数为数字1的 `n` 位数，共有 `a_n` 种；
2. 由数字1,2,3,4,5,6构成的没有1,6相邻，且最后一位数为数字6的 `n` 位数，共有 `b_n` 种；
3. 由数字1,2,3,4,5,6构成的没有1,6相邻，且最后一位数为数字2~5的 `n` 位数，共有 `c_n` 种.

根据加法原理可知，`p_n=a_n+b_n+c_n`.

考虑递推关系可得$$\begin{cases}a_{n+1}=a_n+c_n\\b_{n+1}=b_n+c_n\\c_{n+1}=4a_n+4b_n+4c_n\tag{1}\end{cases}$$写成矩阵形式$$\begin{pmatrix}
a_{n+1}\\ b_{n+1}\\ c_{n+1} \end{pmatrix}=
\begin{pmatrix}
1 & 0 &1 \\
0 & 1 & 1\\
4 & 4 & 4 \end{pmatrix}\begin{pmatrix} a_n\\ b_n\\ c_n \end{pmatrix}\\\begin{pmatrix} a_1\\ b_1\\ c_1 \end{pmatrix}=\begin{pmatrix} 1\\ 1\\ 4 \end{pmatrix}$$解得$$\begin{pmatrix}
a_n\\ b_n\\ c_n \end{pmatrix}=
\begin{pmatrix}
1 & 0 &1 \\
0 & 1 & 1\\
4 & 4 & 4 \end{pmatrix}^{n-1}\begin{pmatrix} 1\\ 1\\ 4 \end{pmatrix}=\frac{1}{{2^n\sqrt{41}}}\begin{pmatrix}(5+\sqrt{41})^n-(5-\sqrt{41})^n\\(5+\sqrt{41})^n-(5-\sqrt{41})^n\\
\D\frac{(3+\sqrt{41}) (5+\sqrt{41})^n-(3-\sqrt{41}) (5-\sqrt{41})^n}{2} \end{pmatrix}$$从而 `p_n=a_n+b_n+c_n=\D\frac{(7+\sqrt{41}) (5+\sqrt{41})^n-(7-\sqrt{41}) (5-\sqrt{41})^n}{2^{n+1}\sqrt{41}}`

于是原问题的结果应该是 `q_n=6^n-p_n=\D 6^n-\frac{(7+\sqrt{41}) (5+\sqrt{41})^n-(7-\sqrt{41}) (5-\sqrt{41})^n}{2^{n+1}\sqrt{41}}`.
验证 `q_1=0,\;q_2=2,\;q_3=22` 均符合。