GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
241 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 (51.4k points)  
retagged by | 241 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 (25.3k 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 Sep 2017
  1. Habibkhan

    7838 Points

  2. Warrior

    2812 Points

  3. Arjun

    2696 Points

  4. rishu_darkshadow

    2692 Points

  5. A_i_$_h

    2456 Points

  6. manu00x

    2040 Points

  7. nikunj

    1980 Points

  8. Bikram

    1864 Points

  9. makhdoom ghaya

    1790 Points

  10. SiddharthMahapatra

    1718 Points


26,243 questions
33,815 answers
80,261 comments
31,168 users