Logic behind Simple Equation Problem

What is the logic behind in solving Simple Equation Problem.

I checked some of the solutions and most of them uses

ct=f(n)-f(n-a-1)-f(n-b-1)-f(n-c-1)+f(n-a-b-2)+f(n-b-c-2)+f(n-a-c-2)-f(n-a-b-c-3);

where f(n) denotes

long long f(long long n)
{
            long long r;
            if(n<0)
                   return 0;
            r=((n+1)*(n+2)*(n+3));
            return r/6;
}
  • At first, you should be familiar with the Inclusion-Exclusion Principle concept
  • Do you recognize the ct expression now ?
  • What (n+1)(n+2)(n+3)/6 makes you think about ? A sum ? A count ?

Good luck ! :stuck_out_tongue:

I did analysis of your problem in my dream last night, I read your question and during my sleep, I saw a dream in which I was analyzing the equation :stuck_out_tongue: , so here is what I got

Since you already know the concept of Inclusion-Exclusion, lets consider the case

4 3 2 1

here given n = 4, a = 3, b = 2, c = 1

denotation of f(n) shows all the possible cases that can occur for all n = 1,2,3,…n

if n = 4, f(n) = 35, where various combinations will be(in sequence a,b,c)

0(combinations 1) = 0 0 0

1(combinations 3) = 1 0 0, 0 1 0, 0 0 1

2(combinations 6) = 2 0 0, 0 2 0, 0 0 2, 1 1 0, 1 0 1, 0 1 1

3(combinations 10) = 3 0 0, 0 3 0, 0 0 3, 2 1 0, 2 0 1, 1 2 0, 1 0 2, 0 1 2, 0 2 1, 1 1 1

4(combinations 15) = 4 0 0, 0 4 0, 0 0 4, 3 1 0, 3 0 1, 1 0 3, 1 3 0, 0 1 3, 0 3 1, 2 2 0, 2 0 2, 0 2 2, 2 1 1, 1 2 1, 1 1 2

but as asked in the question, we have to restrict a, b, c with 3, 2, 1 respectively, for that we exclude all the undesired cases which can be done easily with Inclusion-Exclusion Principle

f(n-a-1) = f(4-3-1) = f(0) = 1 (combinations (4 0 0))

f(n-b-1) = f(4-2-1) = f(1) = 4 (combinations (0 3 0, 0 4 0, 1 3 0, 0 3 1))

f(n-c-1) = f(4-1-1) = f(2) = 10 (combinations (0 0 2, 0 0 3, 1 0 2, 0 1 2, 0 0 4, 1 0 3, 0 1 3, 2 0 2, 0 2 2, 1 1 2))

f(n-a-b-2) = f(4-3-2-2) = f(-3) = 0

f(n-b-c-2) = f(4-2-1-2) = f(-1) = 0

f(n-a-c-2) = f(4-3-1-2) = f(-2) = 0

f(n-a-b-c-3) = f(4-3-2-1-3) = f(-5) = 0

so, by the Principle of Inclusion we get

ct = 35 - 1 - 4 - 10 = 20
2 Likes

I knew Inclusion-Exculsion Principle but why we are subtracting it from f(n).

How did we get (n+1)(n+2)(n+3)/6 ? nCr??