Find the generating function to determine the number of ways to choose k objects from n objects when the ith object appears at least n + i times for 1 ≤ i ≤ n.
the generating function for picking k objects from n objects is $(1+x)^{n}$,but I'm not sure how to go from this to taking into account "the ith object appears at least n + i times"
I am a beginner to this so if you could explain your steps to help me understand why it is things happen, I'd appreciate it
The generating function to ensure that the $i^\text{th}$ object appears at least $n+i$ times is as follows: \begin{equation} g(x) = \underset{1^{\text{st}} \text{ object}}{\underbrace{(x^{n+1}+x^{n+2}+\ldots+x^k)}}\underset{2^{\text{nd}} \text{ object}}{\underbrace{(x^{n+2}+x^{n+3}+\ldots+x^k)}}\ldots\underset{n^{\text{th}} \text{ object}}{\underbrace{(x^{2n}+x^{2n+1}+\ldots+x^k)}}. \end{equation}
Here, the power of $x$ in the first term of the product represents the number of times the first object is picked. Since the first object appears at least $n+1$ times, the smallest power of $x$ in the first term is $n+1$. The maximum number of objects to be chosen is $k$, and hence, the maximum power is $k$. Similarly, we get the later terms. Finally, the number of ways to choose $k$ objects is the coefficient of $x^k$ in the generator function $g(x)$.