划分正整数的方法数

葡萄糖

\(x,y,z,m∈N^＊,x≠y≠z,\)不定方程\(x+y+z=m(m≥6)\)有多少组解

倪举鹏

高中奥数书上有公式，好像母函数 递推数列都可以解决

kastin

x≠y≠z这种写法，到底是理解为x≠y且y≠z，还是理解为x≠y且y≠z且x≠z？

葡萄糖

倪举鹏 发表于 2014-5-11 09:48
高中奥数书上有公式，好像母函数 递推数列都可以解决

高中奥数书上有公式，好像母函数 递推数列都可以解决？？
朦胧依稀曾相识，清晰可见若罔闻................
望能指出出处，谢谢!

wayne

先计算m表示成3个数之和的情况，这个用插板法，有：C(m+2,3)种情况。
然后再排除两个数，三个数相同的情况即可

kastin

根据不定方程正整数解的个数（隔板法）为`\text{C}_{m-1}^{2}`个
所有解可划分为三类：
1) x=y=z，解的个数为`r=1(若3|m)，否则r=0`；
2) x,y,z中有且仅有两个相等，则变为2p+q=m型(p≠q)，该不定方程正整数解的个数为`\frac{2m-(-1)^m-3}{4}-r`；
3) x,y,z两两不相等，即楼主问的情况，设有`s`组解。

根据容斥定理,
$$w+3\times(\frac{2m-(-1)^m-3}{4}-w)+s=\text{C}_{m-1}^{2}$$解出$$s=\frac{m^2}{2}-3m+\frac{3(-1)^m}{4}+\frac{13}{4}+2w$$

kastin

当然，也可以用母函数的方法来做。
思路：
1. 楼主求的是x,y,z互不相等的正整数解的个数，这相当于求`x+y+z=m \space (x\lt y\lt z)`正整数解的个数的6倍（因为`A_3^3=6`）。
2. 因为 `x+y+z=m \space(x\lt y\lt z) `的正整数解的个数`\iff 3x+2y+z=m`的正整数解的个数。

下面来求3x+2y+z=m正整数解的个数。
母函数\[\begin{equation*} \begin{split}G(x)&=(x^3+x^6+x^9+\cdots)(x^2+x^4+x^6+\cdots)(x+x^2+x^3+\cdots)\\&=\frac{x^3}{1-x^3}\frac{x^2}{1-x^2}\frac{x}{1-x}\\&=\frac{x^6}{(1-x)(1-x^2)(1-x^3)}\end{split} \end{equation*}\]
得到`x^m`项系数为
$$\frac{m^2}{12}-\frac{m}{2}+\frac{(-1)^m}{8}+\frac{2}{9}\cos \frac{2\pi m}{3}+\frac{47}{72}$$
它的6倍就是楼主问的问题的答案，即
$$\frac{m^2}{2}-3m+\frac{3(-1)^m}{4}+\frac{4}{3}\cos \frac{2\pi m}{3}+\frac{47}{12}$$

这个形式其实和7L的形式是等价的，因为$$\begin{equation*}\cos \frac{2\pi m}{3}=\begin{cases}
1, & \text{ if } m \mid 3 \\
-1, & \text{ if } m \nmid 3
\end{cases}\end{equation*}$$