0
$\begingroup$

Define $$G(x)=\sum_{n\geq0}n!x^n$$ (we don't care if it converges).

A permutation is indecomposable if it cannot be cut into two non-empty parts so that everything before the cut is smaller than everything after the cut. For example, $21, 3142, 2413 $ and many other permutations are indecomposable, while $23165$ is decomposable, since we can cut it as $231|65$. Let $a_n$ denote the number of indecomposable permutations with $a_0 = 0$ and $A(x)= \sum_{n\geq 0}a_n x^n$. Express $A(x)$ in terms of $G(x)$.

I see how $n!$ and permutations are related but am struggling to produce anything resembling an answer.

$\endgroup$
  • $\begingroup$ Ignoring $A$ for the time being, can you find an expression for $a_n$? $\endgroup$ – Peter Taylor Nov 8 at 17:09
  • $\begingroup$ Typo alert? Do you mean $231|54$ instead of $231|65$? I assume this is one-line notation, in which case I don't know what $6$ is doing in a size-$5$ permutation. $\endgroup$ – antkam Nov 8 at 18:05

Your Answer

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

Browse other questions tagged or ask your own question.