GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
203 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 (45.6k points)   | 203 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 (24.6k 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 ! ..


Top Users Apr 2017
  1. akash.dinkar12

    3366 Points

  2. Divya Bharti

    2536 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Shubham Sharma 2

    1610 Points

  7. Debashish Deka

    1584 Points

  8. Prashant.

    1462 Points

  9. Arunav Khare

    1444 Points

  10. Kapil

    1414 Points

Monthly Topper: Rs. 500 gift card

22,072 questions
28,030 answers
63,191 comments
24,128 users