A261964 Chocolate numbers read as a triangle across rows: T(n,k), n >= 1, 1 <= k <= n.

1, 1, 1, 2, 4, 2, 6, 56, 56, 6, 24, 1712, 9408, 1712, 24, 120, 92800, 4948992, 4948992, 92800, 120, 720, 7918592, 6085088256, 63352393728, 6085088256, 7918592, 720, 5040, 984237056, 14782316470272, 2472100837326848, 2472100837326848, 14782316470272, 984237056, 5040

Offset

1,4

Comments

Given an i X j chocolate bar, let A(i,j) be the number of ways to break it into i*j unit pieces where each break occurs along a grid line. Order matters, and the pieces are distinguishable. Then this sequence lists the values A(i,j) viewed as a triangle and ordered by rows. Row n corresponds to A(i,j), where i+j = n+1. For example, the third row of a triangle is A(3,1)=2, A(2,2)=4, A(1,3)-2.

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

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

T(n,k) = A(n+1-k,k) with 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) otherwise.

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.
Triangle starts:
1,
1, 1,
2, 4, 2,
6, 56, 56, 6,
24, 1712, 9408, 1712, 24,
120, 92800, 4948992, 4948992, 92800, 120,
720, 7918592, 6085088256, 63352393728, 6085088256, 7918592, 720,
...

Maple

A:= proc(m, n) option remember; `if`(min(m, n)=0 or max(m, n)=1, 1,
       add(binomial(m*n-2, i*n-1)*A(i, n)*A(m-i, n), i=1..m-1)
      +add(binomial(m*n-2, i*m-1)*A(m, i)*A(m, n-i), i=1..n-1))
    end:
T:= (n, k)-> A(n+1-k, k):
seq(seq(T(n, k), k=1..n), n=1..10);  # Alois P. Heinz, Sep 14 2015

Mathematica

T[1, 1] = T[2, 1] = T[2, 2] = 1;
T[n_, k_] /; 1 <= k <= n := T[n, k] = Sum[Binomial[(n-k+1)*k-2, i*(n-k+1) - 1] * T[n-i, k-i] * T[n-k+i, i], {i, 1, k-1}] + Sum[T[k+i-1, k]*Binomial[ (n-k+1)*k-2, i*k-1] * T[n-i, k], {i, 1, n-k}];
T[_, _] = 0;
Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, May 23 2016 *)

Crossrefs

Cf. A000142, A257281, A261746, A261747.

Sequence in context: A229460 A154120 A361727 * A177847 A296471 A021416

Adjacent sequences: A261961 A261962 A261963 * A261965 A261966 A261967

Keyword

nonn,tabl

Author

Caleb Ji, Tanya Khovanova, Robin Park, Angela Song, Sep 06 2015

Status

approved