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

  • $\begingroup$ That link just takes me back to my own question $\endgroup$ – Brownie Apr 8 at 19:41
  • 1
    $\begingroup$ 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?. $\endgroup$ – 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: \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)$.

  • $\begingroup$ 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? $\endgroup$ – Brownie Apr 8 at 20:38
  • $\begingroup$ I don't know! :) Looks like it is difficult to solve this question using generator functions! In some cases, it helps. For example, see this answer: math.stackexchange.com/questions/3168665/… $\endgroup$ – Geethu Joseph Apr 9 at 11:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.