5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Have a look at this question $\endgroup$ – G. Chiusole Aug 11 at 10:49
  • $\begingroup$ It is just $2^{n-1}$ by star method? I know that it can be done that way but I was interesting in find generating formula for that $\endgroup$ – Tester1998 Aug 11 at 10:51
  • $\begingroup$ Might just be $G(x)=\frac{x}{1-2x}$ if the term is $2^{n-1}$ (depending if you index by 1 or 0. $\endgroup$ – Benedict W. J. Irwin Aug 11 at 11:00
  • 1
    $\begingroup$ Your "ordered partitions" are often called compositions. $\endgroup$ – Lord Shark the Unknown Aug 11 at 11:36
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ You appear to be quite young in your profile picture. If indeed that is you, then I pay you high respects, kid. I mean, you cannot be higher than 8th grade in secondary school! What a brain! $+1$ :) $\endgroup$ – Mr Pie Aug 11 at 11:55
  • 1
    $\begingroup$ Thanks for appreciating me. You are right that the kid in the profile picture is actually me. $\endgroup$ – Isaac YIU Math Studio Aug 11 at 12:00
  • 1
    $\begingroup$ There is a conjecture that me and a couple friends of mine are working on. It is pretty simple to understand, but much harder to prove than first anticipated (like the Collatz Conjecture). Would you like to help out? Here is a chatroom where others and I often discuss this problem. I think we'd love to have you participate, see what you could come up with. (You are probably better than some of us, myself included, to be honest :P) $\endgroup$ – Mr Pie Aug 11 at 12:17
1
$\begingroup$

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} $

$\endgroup$
  • 1
    $\begingroup$ Note that OP asked for a solution using generating functions, and not a stars and bars method. Also, I have somewhat edited your formatting. Have a look here for a guide on proper formatting. $\endgroup$ – G. Chiusole Aug 11 at 11:15
  • $\begingroup$ It should be $2^{n-1}$ but not $2^{n-2}$ $\endgroup$ – Isaac YIU Math Studio Aug 11 at 12:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.