Chocolate numbers

Question

Given an m by n chocolate bar, m,n positive, output the number of ways to break the bar into mn 1 by 1 pieces where each break occurs on a gridline.

Order is important. Pieces are also distinguishable, so the two pieces on either end of a 1 by 3 chocolate bar are not equivalent.

For instance, for a 2 by 2 block we have:

 _ _            _   _            _   _            _   _
|_‖_|    ->    |‗| |_|    ->    |_| |‗|    ->    |_| |_|
|_‖_|          |_| |_|           _  |_|           _   _
                                |_|              |_| |_|


 _ _            _   _            _   _            _   _
|_‖_|    ->    |_| |‗|    ->    |‗| |_|    ->    |_| |_|
|_‖_|          |_| |_|          |_|  _            _   _
                                    |_|          |_| |_|


 _ _            _ _              _   _            _   _
|‗|‗|    ->    |_‖_|      ->    |_| |_|    ->    |_| |_|
|_|_|           _ _               _ _             _   _
               |_|_|             |_‖_|           |_| |_|


 _ _            _ _               _ _             _   _
|‗|‗|    ->    |_|_|      ->     |_‖_|    ->     |_| |_|
|_|_|           _ _              _   _            _   _
               |_‖_|            |_| |_|          |_| |_|

Hence there are 4 ways to break up a 2 by 2 chocolate bar.

Rules

• Input will be two integers via function input, STDIN, command line or similar. Output a single number, the number of ways to break up the chocolate bar.

• Since the numbers go up pretty quickly, don't worry if the output exceeds the integer limits of your language – your submission will be valid as long as the algorithm theoretically works for all possible inputs.

Test cases

The output doesn't depend on the order of m,n, so the test cases are listed such that m <= n.

1 1 -> 1
1 2 -> 1
1 3 -> 2
1 4 -> 6
1 5 -> 24
1 10 -> 362880

2 2 -> 4
2 3 -> 56
2 4 -> 1712
2 5 -> 92800
2 10 -> 11106033743298560

3 3 -> 9408
3 4 -> 4948992
3 5 -> 6085088256
3 10 -> 76209753666310470268511846400

4 4 -> 63352393728

A261964 is the chocolate numbers arranged in a triangle such that each row corresponds to the sum m+n.

Answer 1

Mathematica, 85 bytes

f=If[##==1,1,Tr[Sum[Binomial[1##-2,i#-1]f[i,#]f[#2-i,#],{i,#2-1}]&@@@{{##},{#2,#}}]]&

Test case

f[4,4]
(* 63352393728 *)

Answer 2

Python 3, 168, 156, 147 bytes

Made improvements thanks to chat

f=lambda n:n<1or n*f(n-1);a=lambda m,n,c=lambda m,n:sum(f(m*n-2)/f(i*n-1)/f((m-i)*n-1)*a(i,n)*a(m-i,n)for i in range(1,m)):+(m+n<4)or c(m,n)+c(n,m)

Ungolfed:

f=lambda n:n<1or n*f(n-1) # Factorial
def a(m, n):
    if m+n < 4:
        return 1
    first = 0
    for i in range(1,m):
        first += f(m*n-2) * 1/f(i*n-1) * 1/f((m-i)*n-1) * a(i,n) * a(m-i,n)
    second = 0
    for i in range(1,n):
        second += f(m*n-2) * 1/f(i*m-1) * 1/f((n-i)*m-1) * a(i,m) * a(n-i,m)
    return first + second

Algorithm was based on this paper.

I could probably cut it down a lot more, I'm just not sure where

Answer 3

R, 208 198 bytes

f=function(m,n){g=function(i,j){a=0;if(j>1)for(x in 2:j-1)a=a+choose(j*i-2,x*i-1)*M[x,i]*M[j-x,i];a};s=max(m,n);M=matrix(1,s,s);for(i in 1:s)for(j in 1:s)if(i*j>2)M[i,j]=M[j,i]=g(i,j)+g(j,i);M[m,n]}

Indented, with newlines:

f = function(m,n){
    g=function(i,j){
        a = 0
        if(j>1) for(x in 2:j-1) a = a + choose(j*i-2,x*i-1) * M[x,i] * M[j-x,i]
        a
    }
    s = max(m,n)
    M = matrix(1,s,s)
    for(i in 1:s) for(j in 1:s) if(i*j>2) M[i,j] = M[j,i] = g(i,j) + g(j,i)
    M[m,n]
}

Usage:

> f(3,1)
[1] 2
> f(3,2)
[1] 56
> f(3,3)
[1] 9408
> f(4,3)
[1] 4948992
> f(5,3)
[1] 6085088256

Answer 4

Python 2, 135 bytes

C=lambda A:sum(C(A[:i]+A[i+1:]+[(c,H),(W-c,H)])for i,Q in enumerate(A)for W,H in(Q,Q[::-1])for c in range(1,W))or 1
print C([input()])

Here's what I came up with. It's really slow, but here's a faster version (needs repoze.lru):

from repoze.lru import lru_cache
C=lru_cache(maxsize=9999)(lambda A:sum(C(tuple(sorted(A[:i]+A[i+1:]+((c,H),(W-c,H)))))for i,Q in enumerate(A)for W,H in(Q,Q[::-1])for c in range(1,W))or 1)
print C((input(),))

Examples

$ time python2 chocolate.py <<< 2,5
92800

real    0m2.954s
user    0m0.000s
sys     0m0.015s

$ time python2 chocolate-fast.py <<< 3,5
6085088256

real    0m0.106s
user    0m0.000s
sys     0m0.015s

Explanation

The code defines a function C that takes an array of pieces. The algorithm is as such:

1. for i,Q in enumerate(A): loop through the array of pieces.
2. for W,H in(Q,Q[::-1]): calculate ways twice, rotating 90 degrees.
3. for c in range(1,W): loop through possible positions to split at.
4. A[:i]+A[i+1:]+[(c,H),(W-c,H)]: get a list without the split piece and with the two new pieces.
5. C(…): call the function again on that list.
6. sum(…): sum the results for each possible split.
7. or 1: if no splits are possible, there is exactly one way to split the chocolate.

Finally, the code is called with an array containing the input.

Answer 5

ES6, 141 bytes

c=(m,n)=>(f=n=>n<2||n*f(n-1),h=(m,n)=>[...Array(m-1)].reduce((t,_,i)=>t+f(m*n-2)/f(++i*n-1)/f((m-i)*n-1)*c(i,n)*c(m-i,n),0),h(m,n)+h(n,m))||1

Based on the formula found by @CameronAavik. Ungolfed:

function fact(n) {
    return n < 2 ? 1 : n * f(n - 1);
}
function half(m, n) {
    total = 0;
    for (i = 1; i < m; i++)
        total += fact(m * n - 2) / fact(i * n - 1) / fact((m - i) * n - 1) * choc(i, n) * choc(m - i, n)
    return total;
}
function choc(m, n) {
    total = half(m, n) + half(n, m);
    if (!total) total = 1;
    return total;
}