Collapsing Duplicate Combinations

$\sum_{i} (i A + i) (K - i B + K - i) = (K A + B + K + 1)$ This expression variant can be interpreted as a convolution of nested combination with another duplicate combination

nested combination : number of ways to select k out of n, allowing for duplication
$H_{k}^{n} = (k n + k - 1)$

The left side is a duplicate combination that selects i from A+1 and K-i from B+1, and the convolution of this is a duplicate combination that selects K from A+B+2.

$\sum_{i} (i A + i) (K - i B + K - i) = \sum_{i} H_{i}^{A + 1} H_{K - i}^{B + 1} = H_{K}^{A + B + 2} = (K A + B + K + 1)$

from binomial coefficient formula

ARC110D

The problem of adding all patterns under the condition that the lower part of the binomial coefficient is fixed and the upper number has a constant sum.
$\sum_{i} (i A + i) (K - i B + K - i) = \sum_{i} (A A + i) (B B + K - i)$ - Lower fixed binomial coefficient → overlapping combination
- Can you make a direct duplicate combination with the lower fixed?
- $\sum_{i} (A A + i) (B B + K - i) = \sum_{i} H_{A}^{i + 1} H_{B}^{K - i + 1} = H_{A + B}^{K + 2} = (A + B A + B + K + 1)$
  - The math doesn’t add up.
    - $(A + B + 1 A + B + K + 1)$ should be
  - This is because the number of frames itself is changing, which is causing double counting.
  - If we think of adding a bounding ball, the bottom would likely be A+B+1, but then wouldn’t we need to increase the top as well? I’m inclined to think that
  - In fact, this is fine because the boundary does not play the role of only a boundary (the ball can be placed in the same position as the boundary) by being a duplicate combination, but this may be confusing.

This page is auto-translated from /nishio/重複組合せの畳み込み using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.

🪴 Quartz 4.0

Collapsing Duplicate Combinations

Graph View

Backlinks