GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
226 views
What is the coefficient of $\large\color{green}{x^{6}}$ in the following series expansion?

$$\color{maroon}{\begin{align*} \frac{1}{1-x}.\frac{1}{1-x^2}.\frac{1}{1-x^3}........ \end{align*}}$$
asked in Combinatory by Veteran (50.5k points)  
retagged by | 226 views
Is it $11$?
Yes 11 partitions

1 Answer

+7 votes
Best answer
$\large \color{navy}{\frac{1}{1-x}= 1 +x + x^2 + x^3 + x^4 \dots + \infty }$
Simplifying each term, we get an equivalent expression for finding coefficient of $x^6$. Finding coefficient of $x^6$ in $\color{green}{\frac{1}{1-x}\frac{1}{1-x^2}\frac{1}{1-x^3}}\dots$ is equivalent to finding coefficient of $x^6$ in :

$\color{navy}{\begin{align*}(1+x+x^2 + \dots + x^6)(1+x^2 +x^4+x^6)(1+x^3+x^6)(1+x^4)(1+x^5)(1+x^6)\end{align*}}$

We are interested in coefficient of $x^6$. So, neglect higher powers.

$\Rightarrow (1+x+x^2 + \dots + x^6)(1+x^2 +x^4+x^6)(1+x^3+x^6)(1 + x^4 + x^5 + x^6)$

$\Rightarrow (1+x+x^2 + \dots + x^6)(1+x^2 +x^4+x^6)(1 + x^3 + x^4 + x^5 + 2x^6)$

$\Rightarrow (1+x+x^2 + x^3 + x^4 + x^5 + x^6)(1+x^2 + x^3 + 2x^4 + 2x^5 + 4x^6)$

Coefficient of $x^6$ $=  4+2+2+1+1+1 = 11$
answered by Veteran (25k points)  
selected by
$$\begin{align*}
G(x) = \color{green}{\frac{1}{1-x} \; \frac{1}{1-x^2}\; \frac{1} {1-x^3} \;....... \; \infty}
\end{align*}$$

$G(x)$ is a generating function. The coeffcient of $\large\color{maroon}{x^n}$ in $G(x)$ is equal to the number of unordered partitions of number $n$.

if $n = 6$, then $\rightarrow$

$$\begin{align*} 6&\rightarrow 6 \\ &\rightarrow 5 \quad 1 \\ &\rightarrow 4 \quad 2 \\ &\rightarrow 4 \quad 1\quad 1 \\ &\rightarrow 3 \quad 3 \\ &\rightarrow 3 \quad 2\quad 1 \\ &\rightarrow 3 \quad 1\quad 1\quad 1 \\ &\rightarrow 2 \quad 2\quad 2 \\ &\rightarrow 2 \quad 2\quad 1\quad 1 \\ &\rightarrow 2 \quad 1\quad 1\quad 1\quad 1 \\ &\rightarrow 1\quad 1\quad 1\quad 1\quad 1\quad 1 \\ \end{align*}$$

Total $11$ partitions. So, coefficient of $\large\color{maroon}{x^6}$ in $G(x)$ is equal to $11$.
Debashish, if it was $x^{30}$ then ??
No closed form for the number of partitions of integer $n$. You also know what will happen.
The approach suggested by @mcjoshi is easy and more generic..
$G(x)$ is standard generating function ! ..
@mcjoshi how u added (1+x^5)(1+x^6) ??? they are in multiplication right?


Top Users Jul 2017
  1. Bikram

    5368 Points

  2. manu00x

    3092 Points

  3. Arjun

    1924 Points

  4. joshi_nitish

    1894 Points

  5. Debashish Deka

    1874 Points

  6. Tesla!

    1380 Points

  7. pawan kumarln

    1336 Points

  8. Hemant Parihar

    1314 Points

  9. Shubhanshu

    1136 Points

  10. Arnab Bhadra

    1124 Points


24,137 questions
31,140 answers
70,874 comments
29,458 users