差分拆的个数与奇分拆的个数是一样多的

hbghlyj

整數拆分（Integer partition）是給定正整數 $n$，求不同數組 $(a_{1},a_{2},...,a_{k})$ 的數目，符合下面的條件：

• $a_{1}+a_{2}+\cdots+a_{k}=n$（$k$的大小不定）
• $a_{1}\geq a_{2}\geq ...\geq a_{k}>0$
• 其他附加條件（例如限定「$k$是偶數」，或「$a_{i}$不是1就是2」等）

(Elder定理) 对于任意正整数 $n$，各个分拆方案中出现了至少 $k$ 次的数的个数之和，一定等于所有方案中 $k$ 出现的总次数。见Matrix67—整数分拆中的一个出人意料的结论

差分拆是满足下面条件的分拆
$a_{1}+a_{2}+\cdots +a_{k}=n$（$k$ 的大小不定）
$a_{1}>a_{2}>\cdots >a_{k}$ 即分拆的每个数都不相等。

奇分拆是满足下面条件的分拆
$a_{1}+a_{2}+\cdots +a_{k}=n$（$k$的大小不定）
$a_{1}\geq a_{2}\geq \cdots \geq a_{k}$ 要求 $a_{i}(i=1,2,\ldots ,k)$ 为奇数

差分拆的个数与奇分拆的个数是一样多的。(Odd partition and distinct parts)
例如 $ 5+1 = 3+3 = 3+1+1+1 = 1+1+1+1+1+1 $ and $ 6 = 5+1 = 4+2 = 3+2+1 $, so there are four of each kind for $ n = 6 $.

通过生成函数证明

Introduction to the Theory of Numbers (4th ed.) G. Hardy, E. Wright, page 277
Some properties of partitions may be deduced at once from the forms of these generating functions. Thus
\begin{align}(1+x)\left(1+x^{2}\right)\left(1+x^{3}\right)\nonumber \ldots &=\frac{1-x^{2}}{1-x} \frac{1-x^{4}}{1-x^{2}} \frac{1-x^{6}}{1-x^{3}} \cdots \\ &=\frac{1}{(1-x)\left(1-x^{3}\right)\left(1-x^{5}\right) \ldots}\tag{19.4.7}\end{align}Hence
Theorem 344. The number of partitions of $n$ into unequal parts is equal to the number of its partitions into odd parts.

通过构造双射证明

Introduction to the Theory of Numbers (4th ed.) G. Hardy, E. Wright, page 277
It is interesting to prove this without the use of generating functions. Any number $l$ can be expressed uniquely in the binary scale, i.e. as\[l=2^a+2^b+2^c+\ldots \quad(0 \leqslant a<b<c \ldots) . \dagger\]Hence a partition of $n$ into odd parts can be written as\begin{aligned}n=l_1\cdot1+l_2\cdot3+l_3\cdot5 &+\ldots \\&=\left(2^{a_1}+2^{b_1}+\ldots\right) 1+\left(2^{a_2}+2^{b_2}+\ldots\right) 3+\left(2^{a_3}+\ldots\right) 5+\ldots ;\end{aligned}and there is a $(1,1)$ correspondence between this partition and the partition into the unequal parts\[2^{a_1}, 2^{b_1}, \ldots, 2^{a_2}, 3,2^{b_2}\cdot3, \ldots, 2^{a_3}\cdot5,2^{b_3}\cdot5, \ldots, \ldots\]
_________________________________
$\dagger$ This is the arithmetic equivalent of the identity $(1+x)\left(1+x^{2}\right)\left(1+x^{4}\right)\left(1+x^{8}\right) \ldots=\frac{1}{1-x}$

通过杨表证明

kuing

标题：[整数分拆] ...
内容：整數拆分（Integer partition）...

到底是“分拆”还是“拆分”

hbghlyj

kuing 发表于 2022-11-12 03:17
标题：[整数分拆] ...
内容：整數拆分（Integer partition）...

是从维基百科照搬的, 好像是两者通用

hbghlyj

通过构造双射证明 It is interesting to prove this without the use of generating functions. Any number $l$ can be expressed uniquely in the binary scale, i.e. as
...

bijective functions #partitions

Proof

The goal is to give a prescription for turning one kind of partition into the other kind and then to show that the prescription gives a one-to-one correspondence (a bijection). It is probably more natural to start with a partition into distinct parts and "break it down" into one with odd parts. The most obvious thing to do is to take an even part and rewrite it as a sum of odd parts, and for simplicity's sake, it is best to use odd parts that are equal to each other.

That is, take the parts of the partition and write them as $ 2^a b $, where $ b $ is odd. Rewrite each part as $ 2^a $ parts equal to $ b $. For example, for $ n = 6 $, $$\begin{aligned} 6 &= 3+3 \\ 5+1 &= 5+1 \\ 4+2 &= (1+1+1+1)+(1+1) \\ 3+2+1 &= 3+(1+1)+1. \end{aligned}$$ To show that this correspondence is one-to-one and onto, it is easiest to construct its inverse. Given a partition of $ n $ into odd parts, collect the parts of the same size into groups. Suppose there are $ d$ parts of size $ r $. Then write $ d$ in binary as $ 2^{a_1} + 2^{a_2} + \cdots + 2^{a_k},$ where the $ a_i $ are distinct. Change the $ d $ parts into $ k $ parts: $ 2^{a_1}r + 2^{a_2}r + \cdots + 2^{a_k}r $. For instance, $$\begin{aligned} 3+3 &= 2\cdot 3 = 6 \\ 5+1 &= 5+1 \\ 1+1+1+1+1+1 &= 6 \cdot 1 = (4+2) \cdot 1 = 4+2 \\ 3+1+1+1 &= 3+ 3\cdot 1 = 3+(2+1)\cdot 1 = 3+2+1. \end{aligned}$$ It is straightforward to check that this gives a partition into distinct parts and that these two conversions are inverses of each other. $_\square$

Two Kinds Of Partitions
Let $p(n)$ be the number of partitions of $n$. Let $q(n)$ be the number of partitions of $2n$ into exactly $n$ parts. For example, $q(3)=3$ because 6=4+1+1=3+2+1=2+2+2. Compute $p(12)-q(12)$.