CODEWITHSUNDEEP
algorithmnumbersdynamic-programming
coderx
coderx

Reputation: 519

Number of ways to divide a number

Given a number N, print in how many ways it can be represented as 

N = a + b + c + d

with

1 <= a <= b <= c <= d; 1 <= N <= M

My observation:

For N = 4: Only 1 way - 1 + 1 + 1 + 1

For N = 5: Only 1 way - 1 + 1 + 1 + 2

For N = 6: 2 ways     - 1 + 1 + 1 + 3
                        1 + 1 + 2 + 2

For N = 7: 3 ways     - 1 + 1 + 1 + 4
                        1 + 1 + 2 + 3
                        1 + 2 + 2 + 2

For N = 8: 5 ways     - 1 + 1 + 1 + 5
                        1 + 1 + 2 + 4
                        1 + 1 + 3 + 3
                        1 + 2 + 2 + 3
                        2 + 2 + 2 + 2

So I have reduced it to a DP solution as follows:
 DP[4] = 1, DP[5] = 1;

for(int i = 6; i <= M; i++)
   DP[i] = DP[i-1] + DP[i-2];

Is my observation correct or am I missing any thing. I don't have any test cases to run on. So please let me know if the approach is correct or wrong.

Upvotes: 3

Views: 2466

Answers (4)

Tharun raj
Tharun raj

Reputation: 11

#include <iostream>

using namespace std;

int func_count( int n, int m )
{

     if(n==m)
        return 1;
     if(n<m)
        return 0;
     if ( m == 1 )
        return 1;
     if ( m==2 )
        return (func_count(n-2,2) + func_count(n - 1, 1));
     if ( m==3 )
        return (func_count(n-3,3) + func_count(n - 1, 2));

     return (func_count(n-1, 3) + func_count(n - 4, 4));
}

int main()
{

     int t;
     cin>>t;
     cout<<func_count(t,4);
     return 0;
}

Upvotes: 1

Niklas B.
Niklas B.

Reputation: 95298

Unfortunately, your recurrence is wrong, because for n = 9, the solution is 6, not 8.

If p(n,k) is the number of ways to partition n into k non-zero integer parts, then we have 

p(0,0) = 1
p(n,k) = 0 if k > n or (n > 0 and k = 0)
p(n,k) = p(n-k, k) + p(n-1, k-1)

Because there is either a partition of value 1 (in which case taking this part away yields a partition of n-1 into k-1 parts) or you can subtract 1 from each partition, yielding a partition of n - k. It's easy to show that this process is a bijection, hence the recurrence.

UPDATE:

For the specific case k = 4, OEIS tells us that there is another linear recurrence that depends only on n:

a(n) = 1 + a(n-2) + a(n-3) + a(n-4) - a(n-5) - a(n-6) - a(n-7) + a(n-9)

This recurrence can be solved via standard methods to get an explicit formula. I wrote a small SAGE script to solve it and got the following formula:

a(n) = 1/144*n^3 + 1/32*(-1)^n*n + 1/48*n^2 - 1/54*(1/2*I*sqrt(3) - 1/2)^n*(I*sqrt(3) + 3) - 1/54*(-1/2*I*sqrt(3) - 1/2)^n*(-I*sqrt(3) + 3) + 1/16*I^n + 1/16*(-I)^n + 1/32*(-1)^n - 1/32*n - 13/288

OEIS also gives the following simplification:

a(n) = round((n^3 + 3*n^2 -9*n*(n % 2))/144)

Which I have not verified.

Upvotes: 3

Petar Ivanov
Petar Ivanov

Reputation: 93020

It's not correct. Here is the correct one:

Lets DP[n,k] be the number of ways to represent n as sum of k numbers. Then you are looking for DP[n,4]. 

DP[n,1] = 1
DP[n,2] = DP[n-2, 2] + DP[n-1,1] = n / 2
DP[n,3] = DP[n-3, 3] + DP[n-1,2]
DP[n,4] = DP[n-4, 4] + DP[n-1,3]

I will only explain the last line and you can see right away, why others are true.

Let's take one case of n=a+b+c+d.

If a > 1, then n-4 = (a-1)+(b-1)+(c-1)+(d-1) is a valid sum for DP[n-4,4].

If a = 1, then n-1 = b+c+d is a valid sum for DP[n-1,3].

Also in reverse:

For each valid n-4 = x+y+z+t we have a valid n=(x+1)+(y+1)+(z+1)+(t+1).

For each valid n-1 = x+y+z we have a valid n=1+x+y+z.

Upvotes: 9

moreON
moreON

Reputation: 2008

I think that the definition of a function f(N,m,n) where N is the sum we want to produce, m is the maximum value for each term in the sum and n is the number of terms in the sum should work.

f(N,m,n) is defined for n=1 to be 0 if N > m, or N otherwise.

for n > 1, f(N,m,n) = the sum, for all t from 1 to N of f(S-t, t, n-1)

This represents setting each term, right to left.

You can then solve the problem using this relationship, probably using memoization.

For maximum n=4, and N=5000, (and implementing cleverly to quickly work out when there are 0 possibilities), I think that this is probably computable quickly enough for most purposes.

Upvotes: 0

Related Questions