给定抽取次数N，求从{1,…,n}抽无放回无序数和为n的组合数

首先，咱们先把问题的本质明确下来：你要找的组合数m，其实就是整数n拆分成恰好N个不同正整数的分拆数，通常记为q(n, N)。比如你提到的n=11、N=3的情况，对应的组合就是(1,2,8)、(1,3,7)、(1,4,6)、(2,3,6)、(2,4,5)，共5种，这就是q(11,3)=5。

接下来咱们把这个问题和欧拉五角数定理挂钩，一步步拆解推导的突破口：

1. 生成函数的对应关系 #

欧拉五角数定理的核心是分拆函数的生成函数等式：

∏_{k=1}^∞ (1 - x^k) = ∑_{k=-∞}^∞ (-1)^k x^{k(3k-1)/2}

而你关注的「不同正整数分拆」的生成函数是∏_{k=1}^∞ (1 + x^k)——每个正整数要么选一次（+x^{k）要么不选（+1），刚好对应无放回抽取的要求。把这个生成函数展开后，x}n项的系数就是n的所有不同分拆总数，而其中拆成恰好N个部分的项数，就是你要的m=q(n,N)。

我们还可以把这个生成函数做个变形，关联到普通分拆：

∏_{k=1}^∞ (1 + x^k) = ∏_{k=1}^∞ (1 - x^{2k}) / (1 - x^k) = 1 / ∏_{k=1}^∞ (1 - x^{2k-1})

这说明不同分拆的总数等于奇分拆的总数，不过这是整体情况，咱们需要聚焦到固定N部分的场景。

2. 转化为普通分拆问题（简化推导） #

对于「拆成N个不同正整数」的情况，我们可以做一个变量替换：假设这N个数是a₁ < a₂ < ... < a_N，令b_i = a_i - i（i从1到N），那么每个b_i ≥ 0，且它们的和为：

∑b_i = ∑a_i - ∑i = n - N(N+1)/2

这时候问题就转化为：求n - N(N+1)/2拆成最多N个非负整数的分拆数（也就是普通分拆中，部分数不超过N的情况），记为p(n - N(N+1)/2, ≤N)。而普通分拆数正是欧拉五角数定理能直接计算的对象！

举个例子，n=11、N=4：n - N(N+1)/2 = 11 - 10 = 1，p(1, ≤4)=1，对应唯一的组合(1,2,3,5)（因为b₁=0, b₂=0, b₃=0, b₄=1，所以a₁=1+0=1, a₂=2+0=2, a₃=3+0=3, a₄=4+1=5），和实际情况一致。

3. 结合欧拉五角数定理计算 #

普通分拆数p(m)可以用欧拉五角数定理的递推式计算：

p(m) = ∑_{k=-∞}^∞ (-1)^{k+1} p(m - k(3k-1)/2)

其中当括号里的数小于0时，该项为0，且p(0)=1。而我们需要的p(m, ≤N)（m = n - N(N+1)/2），可以通过分拆数的性质转化：p(m, ≤N) = p(m + N, N)（费勒斯图转置，最多N部分的分拆等于恰好N部分的分拆，允许部分为0，等价于m+N拆成N个正整数的分拆），而p(m+N, N)可以用递推：

p(t, k) = p(t-1, k-1) + p(t-k, k)

边界条件：p(0,0)=1，p(t,k)=0如果t<0或k<0。

4. 图形规律的对应 #

你观察到的图表规律，大概率和**费勒斯图（Ferrers Diagram）**的对称性有关。拆成N个不同正整数的分拆，对应的费勒斯图是N行，每行长度严格递增；转置后得到的是最多N列的普通分拆图，这可能就是你看到的图形规律的来源——比如行和列的对称关系，或者部分长度的分布特征。

如果你的图表是基于分拆的结构绘制的，可以尝试从费勒斯图的角度去拆解，比如统计每行的长度分布，或者转置后的列分布，这会帮你把图形规律和分拆数的代数性质关联起来。

内容的提问来源于stack exchange，提问作者Raphael J.F. Berger