排列组合

问题

给定正整数$k$与$n$, 求$n$个正整数之和不大于$k$的所有方法数.

求满足不等式$k_1+k_2+k_3+\cdots k_n \leq k$的所有方法数, 其中$k_i(i=1,2,\cdots,n)$为非负整数.

解答

设$k_i(i=1,2,\cdots,n)$为非负整数, 满足

$k_1+k_2+k_3+\cdots k_n \leq k$.

设$k_{n+1}$使得

$k_1+k_2+k_3+\cdots k_n +k_{n+1} = k$,

则$k_{n+1}$也为正整数.

令 $x_i=1+k_{i}$, 则$x_i(i=1,2,\cdots,n)$为正整数, 且有

$x_1+x_2+\cdots + x_n + x_{n+1}=k+n+1$

求$k+n+1$个球分成$n+1$堆, 每堆至少一个球的方法数,

等同于, 把球排成一条, 然后从$k+n$个空位中插入$n$个挡板的方法数,

也就是 $C_{k+n}^n$

---

返回主页

点我返回主页, 查看更多精彩