<s>[INST] Generating function of ordered partitions What is exactly generating function of ordered partitions and how can I get number of ordered partitions from that?
Example:
$$ 4 = 1+1+1+1 \\ = 2+2  \\ = 1+1+2 \\ = 1+2+1 \\ = 2+1+1 \\ = 1+3 \\ = 3+1 \\ = 4 $$
so we have $8$ partitions. I was thinking about exponential generating function:
$$(1+t+\frac{t^2}{2!} + ...)(1+\frac{t^2}{2!} +\frac{t^4}{4!} +...)...(1+\frac{t^n}{n!} + ... ) = e^x e^{2x} e^{3x} \cdots e^{nx} = e^{n(n+1)/2} = \sum_{k \ge 0}\frac{\left(\frac{n(n+1)}{2}x\right)^k}{k!} $$
so the number of ordered partitions of $n$ is
$$\left(\frac{n(n+1)}{2}\right)^n $$
bot for $n=4$ it is
$$10^4$$ It seems to be completely wrong.
 [/INST] We can do this by generating functions which you want to.
For partition $n$,
If we separate $n$ into $n$ numbers, we can generate the function $x+x^2+\cdots+x^n$ and the coefficient of $x^n$ is the number of combination.
If we separate $n$ into $\left(n-1\right)$ numbers, we can generate the function $\left(x+x^2+\cdots+x^n\right)^2$ and the coefficient of $x^n$ is the number of combination.
...
If we separate $n$ into $2$ numbers, we can generate the function $\left(x+x^2+\cdots+x^n\right)^{n-1}$ and the coefficient of $x^n$ is the number of combination.
If we separate $n$ into $1$ number, we can generate the function $\left(x+x^2+\cdots+x^n\right)^n$ and the coefficient of $x^n$ is the number of combination.
Therefore the total number of combination of partition of $n$ is the coefficient of $x^n$ of this function $$\small f:\left(x+x^2+\cdots+x^n\right)+\left(x+x^2+\cdots+x^n\right)^2+\cdots+\left(x+x^2+\cdots+x^n\right)^{n-1}+\left(x+x^2+\cdots+x^n\right)^n$$
However, this function $$\small g:\left(x+x^2+\cdots+x^n+\cdots\right)+\left(x+x^2+\cdots+x^n+\cdots\right)^2+\cdots+\left(x+x^2+\cdots+x^n+\cdots\right)^n+\cdots$$ has the same coefficient of $x^n$ as $f$. Then, we can simplify $g$ like that:
\begin{align}\small\dfrac{x}{1-x}+\left(\dfrac{x}{1-x}\right)^2+\cdots+\left(\dfrac{x}{1-x}\right)^n+\cdots&\small=\dfrac{\dfrac{x}{1-x}}{1-\dfrac{x}{1-x}}\\&\small=\dfrac{x}{1-2x}\\&\small=x\left(1+\left(2x\right)+\left(2x\right)^2+\cdots+\left(2x\right)^{n-1}+\cdots\right)\\&\small=x+2x^2+4x^3+8x^4+\cdots+2^{n-1}x^n+\cdots\end{align}
Therefore, the number of partition of $n=2^{n-1}$
The cases you have shown is $n=4$, which the number of partition is $8$, same as counting.
</s>