Someone asked me this question:

“How many beans make 5?”

The answer given was:

“Two beans, one and a half beans, half a bean and a bean”

It’s a silly question given to children where the child should reply with any combination of beans that adds to 5. Historically it has also been used to describe someone who has their wits about them or “knows their stuff”. Originating in the 18th/early 19th century where the beans may be referring to the beads on an abacus. “If you did not know how to use an abacus, then you did not know your beans”.

But how many solutions are there to this problem? I began by trying to solve this problem from scratch, before realising that I am finding integer partitions.

What are beans?

For my answers I have assumed that:

• Beans can be whole (1, 2, 3) or fractional (0.5, 1.5, 2.5, etc.).
• “One and a half beans” (1.5) differs from “one bean and half a bean” (1 + 0.5).
• The order of beans doesn’t matter (e.g. “1 bean, 2 beans” = “2 beans, 1 bean”).

For clarity, I’ll use digits instead of words, remove “and” and sort numbers high to low.

The original example “2 beans, 1.5 beans, 1 bean, 0.5 beans” becomes [2, 1.5, 1, 0.5] when used in the following diagrams.

Splitting beans

There are two ways to think about this, you could either start with as many half beans as possible and add them together in pairs to create unique solutions, or you can start with the the final number of beans and break it up into parts. I chose the first approach as it was more intuitive to me.

First split the target number into as many half beans as possible, then look at which beans can be combined to make more solutions.

One bean

I’ll start with the simplest case, 1 bean. There are only two half beans so that leads to two solutions:

graph TD;
    A[0.5, 0.5]-->B[1];
  

Two beans

For two beans, there is only one way to combine the half beans, to make [1, 0.5, 0.5]. But then there are two ways to combine these, either [1, 1] or [1.5, 0.5]. There are five solutions:

graph TD;
    A[0.5, 0.5, 0.5, 0.5]-->B[1, 0.5, 0.5];
    B-->C[1.5, 0.5];
    B-->D[1,1];
    C-->E[2];
    D-->E;
  

Three beans

Wow! Suddenly there are so many more solutions, I’ve highlighted the unique solutions from left to right. There are 11 if you count 3 beans.

graph TD

    A[0.5, 0.5, 0.5, 0.5, 0.5] --> B[1, 0.5, 0.5, 0.5]
    B --> C[1.5, 0.5, 0.5]
    C --> E[2, 0.5, 0.5]
    C --> F[1.5, 1, 0.5]

    E --> G[2.5, 0.5] --> 3
    E --> H[2, 1] --> 3

    F--> I[2.5, 0.5]--> 3
    F--> J[1.5, 1.5]--> 3


    B--> D[1, 1, 0.5, 0.5]

    D--> K[2, 0.5, 0.5]
    K--> L[2.5, 0.5] --> 3
    K--> M[2, 1] --> 3

    D--> N[1, 1, 1] --> O[2, 1] --> 3

    D--> P[1.5, 1, 0.5]
    P--> Q[2.5, 0.5] --> 3
    P--> R[1.5, 1.5] --> 3

    classDef highlighted fill:#77e6f2,stroke:#333,stroke-width:2px;

    class A,B,C,D,E,F,G,H,J,N highlighted;
  

Writing some code

I’m going to write some Python code that emulates these graphs with a recursive approach.

From the three beans example, some optimizations can be implemented. If a node already exists in the solution list it can be ignored and its children are skipped.

thisSol represents the current node being examined, while allSols contains all the solutions found so far.

def findBeans(thisSol, allSols):
    # If the solution has already been found,
    # don't add it and don't check its children
    if thisSol in allSols:
        return allSols

    allSols.add(thisSol)

    # If the solution just added was at the bottom of the tree
    # it has no children
    if len(thisSol) == 1:
        return allSols

    # Get all the child nodes of the current solution
    # and explore them recursively
    theseSols = getDifferentSums(thisSol)
    for i in theseSols:
        findBeans(i, allSols)

    return allSols

toMake = 20
halfBeans = tuple([0.5] * int(toMake / 0.5))
solutions = findBeans(halfBeans, set())

getDifferentSums looks like this:

def getDifferentSums(beanCs):
    differentSums = set()
    sumVariations = set()

	# For each pair of unique values in the array
    for i in range(len(beanCs)):
        for j in range(i + 1, len(beanCs)):
            newSum = beanCs[i] + beanCs[j]

			# If this sum has already been made then this solution is a duplicate
            if newSum in sumVariations:
                break

            sumVariations.add(newSum)

			# Remove elements at indices i and j, add the new sum and
            # sort to ensure uniqueness before adding to the set
            newBeanCombos = (newSum, ) + beanCs[:i] + beanCs[i + 1:j] + beanCs[j + 1:]
            differentSums.add(
                tuple(
                    sorted(newBeanCombos)
                )
            )


    return differentSums

The time complexity of this solution scales so quickly that finding the answer for 10 takes a few milliseconds, whereas finding 25 takes over 7 seconds!

After running the code for some different numbers of beans, these are the numbers of solutions: 2, 5, 11, 22, 42, 77, 135. I put this series into OEIS and this is how I discovered integer partitions. Specifically, the number of ways to partition 2n into positive integers. 2n is used because integer partitions mean that 0.5 and 1.5 aren’t partitions, however doubling the input gets to the same result as there are now two partitions for every integer partition.

Full beans!

Now I knew that I was looking for integer partitions, I could find a faster way to calculate the partitions.

def partitions(n, I=1):
    yield (n,)
    for i in range(I, n//2 + 1):
        for p in partitions(n-i, i):
            yield (i,) + p

Ah, this is quite a lot simpler.

Whether found with the diagrams, or with Python, in answer to the original question; there are 42 different solutions to how many beans make 5.