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$
4
  • $\begingroup$ Have a look at this question $\endgroup$ Aug 11, 2019 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$
    – user677339
    Aug 11, 2019 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$ Aug 11, 2019 at 11:00
  • 1
    $\begingroup$ Your "ordered partitions" are often called compositions. $\endgroup$ Aug 11, 2019 at 11:36

2 Answers 2

7
$\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$
3
  • 2
    $\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, 2019 at 11:55
  • 2
    $\begingroup$ Thanks for appreciating me. You are right that the kid in the profile picture is actually me. $\endgroup$
    – MafPrivate
    Aug 11, 2019 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, 2019 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$
2
  • 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$ Aug 11, 2019 at 11:15
  • $\begingroup$ It should be $2^{n-1}$ but not $2^{n-2}$ $\endgroup$
    – MafPrivate
    Aug 11, 2019 at 12:02

You must log in to answer this question.