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
.