3
$\begingroup$

I was given the next question:

$A_n$ is marked to be the number of all of the sequences from a subset of the naturals to $\{1,2,3,4,5,6\}$ such that their sum is $n$ (a natural number) ** which means that the order matters

For example: for $A_5$ some part of the sequences are <1,1,1,1,1> , <1,2,2> , <2,2,1>

I was asked to find the generating function that suits this problem, and what I mean by this is finding the function $f$ such that $f$= $A_0$ + $A_1x$ + $A_2x^2$+...

I'd really like some help with this question, Thank you very much!

p.s.: $A_0=0$

$\endgroup$
3
  • $\begingroup$ Did you try to find the possible recursive relation of $A_n$'s? $\endgroup$ – Στέλιος Σαχπάζης Jan 14 '17 at 9:05
  • $\begingroup$ @SachpazisStelios Sadly I cannot use recursive methods because we did not study those yet =( $\endgroup$ – Lola Jan 14 '17 at 9:11
  • $\begingroup$ I was asked to prove it using generating functions..how will induction be helpful in this case? @charMD $\endgroup$ – Lola Jan 16 '17 at 22:59
3
+50
$\begingroup$

We observe: $$\frac{x}{1-x}=x^1+x^2+x^3+\ldots$$ carries as exponents the possible solutions $1,2,3,\ldots$ of one $x_i$ in $$x_1+x_2+x_3+\ldots+x_k=n\qquad k\geq 1, n\geq k$$ Therefore the number of compositions of $n$ with $k$ variables $x_1,x_2,\ldots,x_k$ is the coefficient of $x^n$ of $$\left(\frac{x}{1-x}\right)^k$$

Since we want to restrict the solutions to be elements from $\{1,2,3,4,5,6\}$ we take \begin{align*} \frac{x-x^7}{1-x}=x^1+x^2+x^3+x^4+x^5+x^6 \end{align*}

Since the number of variables is at least $1$ up to $n$ for $A_n$ we obtain as generating function \begin{align*} f(x)&=\sum_{n=1}^\infty A_nx^n\\ &=\sum_{n=1}^\infty \left(\frac{x-x^7}{1-x}\right)^n\\ &=\frac{x-x^7}{1-x}\cdot\frac{1}{1-\frac{x-x^7}{1-x}}\\ &=x+2x^2+4x^3+8x^4+\color{blue}{16}x^5+32x^6+63x^7+\cdots \end{align*}

whereby the last line was obtained with some help of Wolfram Alpha.

$$ $$

Example: We find e.g. $A_5=16$ which represents the $\color{blue}{16}$ compositions of $5$ \begin{align*} &<1,1,1,1,1,1>,\\ &<1,1,1,2>,<1,1,2,1>,<1,2,1,1>,<2,1,1,1>,\\ &<1,1,3>,<1,3,1>,<3,1,1>\\ &<1,2,2>,<2,1,2>,<2,2,1>\\ &<1,4>,<4,1>\\ &<2,3>,<3,2>\\ &<5> \end{align*}

$\endgroup$
4
  • $\begingroup$ @Lola: You're welcome! :-) $\endgroup$ – Markus Scheuer Jan 16 '17 at 23:17
  • $\begingroup$ @Lola: Thanks a lot for granting the bounty! :-) $\endgroup$ – Markus Scheuer Jan 17 '17 at 13:09
  • $\begingroup$ No problem :) Sorry for the bother Markus Scheuer, but could you help me with my recent question in generating functions? The answer that was given there was a false one =( $\endgroup$ – Lola Jan 18 '17 at 7:33
  • $\begingroup$ @Lola: I've added an answer. Regards, $\endgroup$ – Markus Scheuer Jan 18 '17 at 17:13

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.