GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
216 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 (47.1k points)   | 216 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.7k 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 May 2017
  1. akash.dinkar12

    3568 Points

  2. pawan kumarln

    2206 Points

  3. Bikram

    1940 Points

  4. sh!va

    1682 Points

  5. Arjun

    1650 Points

  6. Devshree Dubey

    1272 Points

  7. Debashish Deka

    1270 Points

  8. Angkit

    1056 Points

  9. LeenSharma

    1028 Points

  10. Arnab Bhadra

    904 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. Bikram

    1026 Points

  2. pawan kumarln

    832 Points

  3. Arnab Bhadra

    818 Points

  4. akash.dinkar12

    448 Points

  5. Arjun

    378 Points


22,897 questions
29,213 answers
65,336 comments
27,713 users