In how many ways you can count till N using the numbers <= with N

Question

in how many ways you can sum the numbers less or equal with N to be equal with n. What is the algorithm to solve that?

Example: lets say that we have

n =10;

so there are a lot of combinations but for example we can do:

1+1+1+1+1+1+1+1+1+1 = 10
1+2+1+1+1+1+1+1+1=10
1+1+2+1+1+1+1+1+1=10
.....
1+9=10
10=10
8+2=10

and so on.

If you think is the Catalan questions, the answer is: the problem seems to be Catalan problem but is not. If you take a look to the results you will see that lets say for N=5 In Catalan algorithm you have 14 possibilities. But in right answer you have 2^4=16 possibilities if you count all, or the Fibonacci array if you keep only the unique combinations. Eg N=5 we have 8 possibilities, so the Catalan algorithm doesn't verify.

This was a question received by me in a quiz done for fun, at that time i thought that the solution is a well known formula, so i lost a lot of time trying to remember it :) I found 2 solutions for this problem and 1 more if you are considering only the unique combinations. Eg 2+8 is the same as 8+2, you are considering only 1 of them. So what is the algorithm to solve it?

Answer 1

All the 3 solutions that I fount use Math induction:

solution 1:

if n =0 comb =1
if n =1 comb = 1 
if n=2 there are 1+1, 2 comb =2 = comb(0)+comb(1)
if n=3 there are 1+1+1, 1+2, 2+1, 3 comb = 4 = comb(0)+comb(1)+comb(2)
if n=4 there are 1+1+1+1, 1+2+1,1+1+2,2+1+1,2+2,1+3,3+1,4 comb = 8 =comb(0)+comb(1)+comb(2)+comb(3)

Now we see a pattern here that says that:

at k value we have comb(k)= sum(comb(i)) where i between 0 and k-1
using math induction we can prove it for k+1 that:
comb(k+1)= sum(comb(i)) where is is between 0 and k

Solution number 2:

If we pay a little more attention to the solution 1 we can say that:

comb(0)=2^0
comb(1)=2^0
comb(2)=2^1
comb(3)=2^2
comb(4)=2^3

comb(k)=2^(k-1)
again using the math induction we can prove that 
comb(k+1)=2^k

Solution number 3 (if we keep only the unique combinations) we can see that:

comb(0)=1
comb(1)=1
comb(2)= 1+1,2=2
comb(3)= 1+1+1, 1+2, 2+1, 3 we take out 1+2 because we have 2+1 and its the same comb(3)=3
comb(4) = 1+1+1+1, 1+2+1,1+1+2,2+1+1,2+2,1+3,3+1,4, here we take out the 1+2+1,,2+1+1 and 1+3 because we have them but in different order comb(4)= 5.

If we continue we can see that:

comb(5) = 8
comb(6)=13 

we now can see the pattern that:

comb (k) = comb (k-1) + comb(k-2) the Fibonacci array
again using Math induction we can prove that for k+1
comb(k+1) = comb(k)+comb(k-1)

now it's easy to implement those solutions in a language using recursion for 2 of the solutions or just the non recursive method for the solution with 2^k.

And by the way this has serious connections with graph theory (how many sub-graphs you can build starting from a bigger graph - our number N, and sub-graphs being the ways to count )

Amazing isn't it?

Answer 2

This is an interesting problem. I do not have the solution (yet), but I think this can be done in a divide-and-conquer way. If you think of the problem space as a binary tree, you can generate it like this:

The root is the whole number n Its children are floor(n/2) and ceil(n/2)

Example: n=5

     5
   /   \
  2     3
 / \   / \
1   1 1   2
         / \
        1   1

If you do this recursively, you get a binary tree. If can then traverse the tree in this manner to get all the possible combinations of summing up to n:

get_combinations(root_node)
{
   combinations=[]
   combine(combinations, root_node.child_left, root_node.child_right)
}

combine(combinations, nodeA, nodeB)
{
   new_combi = "nodeA" + "+nodeB"
   combinations.add(new_combi)
   if nodeA.has_children(): combinations.add( combine(combinations, nodeA.child_left, nodeA.child_right) + "+nodeB" )
   if nodeB.has_children(): combinations.add( "nodeA+" + combine(combinations, nodeB.child_left, nodeB.child_right) )
   return new_combi
}

This is just a draft. Of yourse you don't have to explicitly generate the tree beforehand, but you can do that along the way. Maybe I can come up with a nicer algorithm if I find the time.

EDIT:

OK, I didn't quite answer OPs question to the point, but I don't like to leave stuff unfinished, so here I present my solution as a working python program:

import math

def print_combinations(n):
    for calc in combine(n):
        line = ""
        count = 0
        for op in calc:
            line += str(int(op))
            count += 1
            if count < len(calc):
                line += "+"
        print line

def combine(n):

    p_comb = []
    if n >= 1: p_comb.append([n])
    if n >1: 
        comb_left = combine(math.floor(n/float(2)))
        comb_right = combine(math.ceil(n/float(2)))
        for l in comb_left:
            for r in comb_right:
                lr_merge = []
                lr_merge.extend(l)
                lr_merge.extend(r)
                p_comb.append(lr_merge)
    return p_comb

You can now generate all possible ways of summing up n with numbers <= n. For example if you want to do that for n=5 you call this: print_combinations(5)

Have fun, be aware though that you run into memory issues pretty fast (dynamic programming to the rescue!) and that you can have equivalent calculations (e.g. 1+2 and 2+1).