Generating function of ordered partitions

Question

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.

Answer 1

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.

Answer 2

Let us say we want to partition $n$.

There are $\underbrace{1.1.1. \ldots .1}_{n ~ \text{times}}$

Between these $n$ times $1$ there exist $(n-1)$ spaces which can be filled in two ways either numbers are combined to increase the count or can be seperated.

e.g let us say you have $$ 3 :::: 1. 1. 1 $$ $$ 1 +1+1 $$ $$ 1+1(1) \; \\e.g\; 1\, + \,2 $$ $$ 1(1)\,+\,1 \; \\e.g \; 2\,+\,1 $$ $$ 1(1)(1) \;\\e.g \; 3 $$ Similarly for n it will be $ {2}^{n-1} $