5

My friend gave me this problem he was asked in an interview that he was not able to answer. After hours of thinking we were not able to come up with the solution.

Consider A number three. I need to write a program to count the different ways in which you can write the number as a sum of numbers less than the number.

For example:

If the number is 2, it can be written as sum(1,1)

if the number is 3, it can be written as sum(1,1,1), sum(1,2), sum(2,1)

if the number is 4, it can be written as sum(1,1,1,1), sum(1,3), sum(3,1), sum(1,2,1), sum(2,1,1), sum(1,1,2), sum(2,2). 7 different ways

If the number is 5, it can be written as sum(1,1,1,1,1), sum(1,1,1,2), sum(1,1,2,1), sum(1,2,1,1), sum(2,1,1,1) etc.

How can I write program to determine the number of ways a number can be broken down into sums of smaller numbers

I was able to come up with a solution for the problem if sum(1,2) and sum(2,1) are considered equivalent using the algorithm in http://www.programminglogic.com/integer-partition-algorithm/

But the problem is sum(1,2) and sum(2,1) are different. I can not see a pattern to do this at all.

Any help would be appreciated. I just want to know the solution.

Ranjith Ramachandra
  • 10,399
  • 14
  • 59
  • 96

4 Answers4

6

Think of the number as a line of dots:

4     -> . . . .

Between two adjacent dots we can put a wall to break the number into smaller ones:

1+3   -> .|. . .
2+2   -> . .|. .
1+2+1 -> .|. .|.

For every of the n-1 gaps, we have the option of putting a wall or not, for a total of 2^(n-1) possibilities. However, putting no walls leaves us with just the number, which isn't allowed, so we remove that as a possibility for a final total of 2^(n-1)-1 solutions.

Abe Karplus
  • 8,350
  • 2
  • 27
  • 24
  • Your proof only proves one direction of the bijection. That is, every split of the unary representation of the number results in a way of summing to the number. But it doesn't prove that those splits are unique. You need to prove the other injection. – rliu Dec 01 '13 at 10:50
  • @roliu This wasn't really intended as a formal proof, just a reasonably intuitive explanation. This is a very common problem in combinatorics, so I didn't feel that proving it again would add much. – Abe Karplus Dec 01 '13 at 10:53
  • 1
    Fair enough. It is just a pet peeve I have that SO has a lot of logical fallacies thrown around (probably because not everyone has a math background). I notice now that you don't even prove the first injection so the informality is more obvious to me now. +1 – rliu Dec 01 '13 at 11:02
  • Thanks for the answer. But can not choose every answer as the correct answer. I have upvoted yours – Ranjith Ramachandra Dec 02 '13 at 11:40
2

You need a partitioning solution to find all the possible answers. Take a look at the following approaches to do so:

Find all ways to sum given number (with repetitions allowed) from given set

fast method to list all possible combination of numbers which sum to a const number

and a good mathematical explanation:

http://mathworld.wolfram.com/PartitionFunctionP.html

Community
  • 1
  • 1
asalic
  • 949
  • 4
  • 10
1

A program for computing the number of different sums (as specified here) could look like this:

def SumsCount(n):
  if n <= 1:
    return 0
  sumsCount = 0
  # the first number i can be 1, 2, ..., n-1
  for i in range(1,n):
    # the rest must sum up to n-i
    # or the rest is just the number (n-i)
    sumsCount += SumsCount(n-i) + 1
  return sumsCount
coproc
  • 6,027
  • 2
  • 20
  • 31
0

Here is a simple recursive equation to solve this problem:-

 F(N) = (F(N-1)+1) + (F(N-2)+1) + F(N-3)...........F(1)+1
 F(2) = 1
 F(1) = 0
 F(N-1) = (F(N-2)+1) + F(N-3)...........F(1)+1 
 F(N) = F(N-1)  + F(N-1) + 1
 F(N) = 2*F(N-1) + 1

Solving equations:

 F(N) = 2^(N-2) + 2^(N-2) - 1
      = 2^(N-1) - 1
Vikram Bhat
  • 6,106
  • 3
  • 20
  • 19