A261746 Chocolate numbers.

1, 2, 4, 6, 24, 56, 120, 720, 1712, 5040, 9408, 40320, 92800, 362880, 3628800, 4948992, 7918592, 39916800, 479001600, 984237056, 6085088256, 6227020800, 63352393728, 87178291200, 168662855680, 1307674368000, 14782316470272, 20922789888000, 38238313152512

Offset

1,2

Comments

Given an m X n chocolate bar, let A(m,n) be the number of ways to break it into m*n unit pieces where each break occurs along a gridline. Order matters, and the pieces are distinguishable. Then this sequence lists the values A(m,n) in increasing order as m and n range over the positive integers.

The sequence of factorials, A000142, is a subsequence as A(1,n) = A(n,1) = (n-1)!.

For m,n>1, A(m,n) is divisible by 2^(m+n-2).

Links

Table of n, a(n) for n=1..29.

Caleb Ji, Tanya Khovanova, Robin Park, Angela Song, Chocolate Numbers, arXiv:1509.06093 [math.CO], 2015.

Caleb Ji, Tanya Khovanova, Robin Park, Angela Song, Chocolate Numbers, Journal of Integer Sequences, Vol. 19 (2016), #16.1.7.

Formula

A(m,n)=1 for max(m,n)<2 and A(m,n) = Sum_{i=1..m-1} C(m*n-2,i*n-1) *A(i,n) *A(m-i,n) + Sum_{i=1..n-1} C(m*n-2,i*m-1) *A(m,i) *A(m,n-i) else.

Example

For n = m = 2, there are two ways for the first break: breaking it horizontally or vertically. After that we need two more breaks that can be done in any order. Thus A(2,2) = 4, and 4 belongs to the sequence.

Mathematica

terms = 29;
A[m_, n_] := A[m, n] = If[Max[m, n] < 2, 1, Sum[A[i, n] Binomial[m n - 2, i n - 1] A[m - i, n], {i, 1, m - 1}]] + Sum[A[m, i] Binomial[m n - 2, i m - 1] A[m, n - i], {i, 1, n - 1}];
Table[A[m, n], {m, 1, terms}, {n, 1, terms}] // Flatten // Union //
 Take[#, terms]&

Crossrefs

Cf. A257281, A261747, A000142, A261964.

Sequence in context: A370418 A226169 A343728 * A319575 A318609 A195333

Adjacent sequences: A261743 A261744 A261745 * A261747 A261748 A261749

Keyword

nonn

Author

Caleb Ji, Tanya Khovanova, Robin Park, Angela Song, Aug 30 2015

Status

approved