Skip to content

Inclusion-exclusion digit sum problem details #1176

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 4 commits into from
Oct 22, 2023
Merged

Inclusion-exclusion digit sum problem details #1176

Changes from all commits
Commits
Show all changes
4 commits
Select commit Hold shift + click to select a range
09d444c
Inclusion-exclusion: Add example problem
jxu Oct 20, 2023
a200120
Inclusion-exclusion: add formula, comparison to other approaches
jxu Oct 20, 2023
22f7e89
Inclusion-Exclusion: clarify binomial formula
jxu Oct 20, 2023
b22e03f
remove base-b example
jakobkogler Oct 22, 2023
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
8 changes: 8 additions & 0 deletions src/combinatorics/inclusion-exclusion.md
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -169,6 +169,14 @@ Combining all this into the formula of inclusions-exceptions and given that we s

$$\binom{25}{5} - \left(\binom{6}{1} \cdot \binom{16}{5} - \binom{6}{2} \cdot \binom{7}{5}\right) $$

This easily generalizes to $d$ numbers that sum up to $s$ with the restriction $0 \le x_i \le b$:

$$\sum_{i=0}^d (-1)^i \binom{d}{i} \binom{s+d-1-(b+1)i}{d-1}$$

As above, we treat binomial coefficients with negative upper index as zero.

Note this problem could also be solved with dynamic programming or generating functions. The inclusion-exclusion answer is computed in $O(d)$ time (assuming math operations like binomial coefficient are constant time), while a simple DP approach would take $O(ds)$ time.

### The number of relative primes in a given interval

Task: given two numbers $n$ and $r$, count the number of integers in the interval $[1;r]$ that are relatively prime to n (their greatest common divisor is $1$).
Expand Down