Yubai's blog

An Interesting combination problem
By Yubai, history, 2 years ago, In English

Try to solve the following problem, only by combining meaning but not the generating function.

$$$\sum_x \binom{2x+k}{x}\binom{P-2x-k}{a-x}$$$

There are q times inquiries, Given k, P, a, each time, print the value of this sum, $$$q,k,P,a \leq 1e5$$$.

I'll give an answer in 24 hours. If solved, please write the method in the comments and try the harder problems below, which replace 2 by t, t will be given before all queries.

$$$\sum_x \binom{tx+k}{x}\binom{P-tx-k}{a-x}$$$
  • Vote: I like it
  • +54
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

interesting

→ Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it
hint
→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    sad that no one is interested in it. If anyone wants an answer, please reply to me and I will give the answer as soon as possible

    → Reply
»
2 years ago, # |
  Vote: I like it +12 Vote: I do not like it
sol

But I think there should be a more direct combination explanation, I very much hope that who are interested will come to discuss.

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Motivated by your problem, I once encountered this long time back but left it because couldn't make any progress.

$$$\sum_i {i\choose k} {n-i\choose l-k}$$$

There are q times inquiries, Given k, l, n, each time, print the value of this sum

$$$ 1 \leq k \leq l \leq n \leq 2e6 \ and \ q \leq 2e3$$$

I thought it seems like choosing l object out of n but it was wrong iirc.

Any hints?

Yubai

Thank you

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    This is a classic combinatorial problem. Consider there are n+1 balls, and you need to choose l+1 balls. One way to calculate it is enumerate the position of the (k+1)th ball, suppose its current position is $$$i+1$$$, then you only need to choose k balls from the first i balls, and choose (l+1-1-k) balls from the last (n+1-i-1) balls, got the sum you gave.

    so, the answer is $$$\binom{n+1}{l+1}$$$, which can make $$$q\leq 2e6$$$ too.

    → Reply