1
$\begingroup$

There is this corollary:

Let $h_{n,k}$ be the number of ways to split the interval $[1,\cdots , n]$ $(n\geq 0, k\geq 0)$ into $k$ (possibly empty) subintervals and then building structure $A$ on each of these subintervals.
Note that $A(x)=\sum_{n\geq 0}a_nx^n$ $$H_k(x)=\sum_{n=0}^{\infty} h_{n,k}x^n=(A(x))^k=\underbrace{(a_0+a_1x+a_2x^2+\cdots)\cdots (a_0+a_1x+a_2x^2+\cdots)}_{k\text{ times} } \\=\sum_{n\geq 0}\big(\sum_{i_1+\cdots+i_k=n\\ i_{ij}\geq 0} a_{i_1}a_{i_2}\cdots a_{i_k}\big)x^n$$

How does the following $$(a_0+a_1x+a_2x^2+a_3x^3+\cdots)^k$$ become $$\sum_{n\geq 0}\big(\sum_{i_1+\cdots+i_k=n\\ i_{ij}\geq 0} a_{i_1}a_{i_2}\cdots a_{i_k}\big)x^n$$

$\endgroup$
  • $\begingroup$ start with $k=2$ and try to notice some pattern, then induction maybe works. $\endgroup$ – Arian Mar 25 '18 at 14:40
0
$\begingroup$

Observe we have \begin{align} \left(\sum^\infty_{i=0}a_ix^i \right)^k=&\ \underbrace{\left(\sum^\infty_{i_1=0}a_{i_1}x^{i_1} \right)\cdots \left(\sum^\infty_{i_k=0}a_{i_k}x^{i_k} \right)}_{k-\text{times}}\\ =&\ \sum^\infty_{i_1=0}\cdots \sum^\infty_{i_k=0}\ [a_{i_1}a_{i_2}\ldots a_{i_k}]\ x^{i_1+\ldots +i_k}\\ =&\ \sum^\infty_{n=0}\left(\sum_{i_1+\ldots +i_k=n} a_{i_1}\ldots a_{i_k} \right)x^n \end{align}

$\endgroup$
  • $\begingroup$ Wow, it's so clear actually. Thanks! $\endgroup$ – Leyla Alkan Mar 25 '18 at 14:47

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.