# 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

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

• That link just takes me back to my own question – Brownie Apr 8 at 19:41
• I'm sorry about that. I accidentally copied the URL from the browser tab with this post instead of the correct one. The appropriate link is How can I learn about generating functions?. – John Omielan Apr 8 at 19:44

The generating function to ensure that the $$i^\text{th}$$ object appears at least $$n+i$$ times is as follows: $$$$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)}}.$$$$
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)$$.
• Nice breakdown! So if we were talking about a generating function the number of ways to pick k objects from n objects when repetitions are not allowed. The generating function for 1 object would be (1+x) ,now if you do that for all n objects you have $(1+x)^{n}$. Is there similarly a way to condense or simplify this function? – Brownie Apr 8 at 20:38