# Chocolate numbers

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.

# 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 *)

# Python 3, 168, 156, 147 bytes

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

# 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
• In theory, one can write a shorter recursive version of ca. 160 bytes but it quickly reaches the default recursion limit and the default protection stack size and modifying these defaults (respectively using options(expressions=...) and argument --max-ppsize=) would result in a longer code than this one. – plannapus Feb 15 '16 at 10:26
• You can save two bytes by omitting f=. – Alex A. Feb 15 '16 at 17:12

# 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.

## 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)