1 reply to this topic

[Explorer]

Có bao nhiêu cách viết số nguyên dương n thành tổng các số nguyên dương? (hai cách viết 1+3+1+2 và 2+1+1+3 được coi là giống nhau)

[Nobodyv3]

Có bao nhiêu cách viết số nguyên dương n thành tổng các số nguyên dương? (hai cách viết 1+3+1+2 và 2+1+1+3 được coi là giống nhau)

Gọi $p(n)$ là số phân hoạch của số $n$ thì ta có hàm sinh :
$\sum_{n}p(n) x^n = \prod_{k=1}^{\infty}\frac{1}{1-x^k}$
Dễ thấy vế phải là :
$$VP=(1+x^{1\cdot1}+x^{2\cdot1}+x^{3 \cdot 1}+\dots)(1+x^{1\cdot2}+x^{2\cdot2}+x^{3\cdot 2}+\dots)(1+x^{1\cdot3}+x^{2\cdot3}+x^{3\cdot3}+\dots)\dots$$
$\begin {align*}
\text{ Thí dụ với $n=6$:}\\
x^{1\cdot 6}&\rightarrow 6\\
x^{1\cdot5}x^{1\cdot1} &\rightarrow 5+1\\
x^{1\cdot4}x^{1\cdot2} &\rightarrow 4+2\\
x^{2\cdot3}& \rightarrow 3+3\\
x^{1\cdot3}x^{1\cdot 2}x^{1\cdot1}& \rightarrow 3+2+1\\
x^{1\cdot4}x^{2\cdot1} &\rightarrow 4+1+1\\
x^{3\cdot2}&\rightarrow 2+2+2\\
x^{1\cdot3}x^{3\cdot1} &\rightarrow 3 + 1 + 1+1\\
x^{2\cdot2}x^{2\cdot1}&\rightarrow 2+2+1+1\\
x^{1\cdot2}x^{4\cdot1} &\rightarrow 2+1+1+1+1\\
x^{6\cdot1} &\rightarrow 1+1+1+1+1+1\\
\text { Vậy $p(6)=11$.}
\end{align*}$
Theo mình biết thì hiện nay hình như chưa có công thức tính chính xác số phân hoạch của 1 số $n$, nhưng có công thức gần đúng là :
$p(n)\approx \frac{e^{\sqrt n \,c}}{4\sqrt 3 \,n}$ trong đó $c = \sqrt \frac{2}{3} \pi$.

Edited by Nobodyv3, 04-05-2024 - 23:11.