|
%I #30 Jan 21 2017 10:43:39
%S 1,1,1,2,4,2,6,56,56,6,24,1712,9408,1712,24,120,92800,4948992,4948992,
%T 92800,120,720,7918592,6085088256,63352393728,6085088256,7918592,720,
%U 5040,984237056,14782316470272,2472100837326848,2472100837326848,14782316470272,984237056,5040
%N Chocolate numbers read as a triangle across rows: T(n,k), n >= 1, 1 <= k <= n.
%C 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.
%C The sequence of factorials, A000142, is a subsequence as A(1,n) = A(n,1) = (n-1)!.
%C For m,n>1, A(m,n) is divisible by 2^(m+n-2).
%H Caleb Ji, Tanya Khovanova, Robin Park, Angela Song, <a href="http://arxiv.org/abs/1509.06093">Chocolate Numbers</a>, arXiv:1509.06093 [math.CO], 2015.
%H Caleb Ji, Tanya Khovanova, Robin Park, Angela Song, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Khovanova/khova9.html">Chocolate Numbers</a>, Journal of Integer Sequences, Vol. 19 (2016), #16.1.7.
%F 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.
%e 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.
%e Triangle starts:
%e 1,
%e 1, 1,
%e 2, 4, 2,
%e 6, 56, 56, 6,
%e 24, 1712, 9408, 1712, 24,
%e 120, 92800, 4948992, 4948992, 92800, 120,
%e 720, 7918592, 6085088256, 63352393728, 6085088256, 7918592, 720,
%e ...
%p A:= proc(m, n) option remember; `if`(min(m, n)=0 or max(m, n)=1, 1,
%p add(binomial(m*n-2, i*n-1)*A(i, n)*A(m-i, n), i=1..m-1)
%p +add(binomial(m*n-2, i*m-1)*A(m, i)*A(m, n-i), i=1..n-1))
%p end:
%p T:= (n, k)-> A(n+1-k, k):
%p seq(seq(T(n, k), k=1..n), n=1..10); # _Alois P. Heinz_, Sep 14 2015
%t T[1, 1] = T[2, 1] = T[2, 2] = 1;
%t 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 T[_, _] = 0;
%t Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, May 23 2016 *)
%Y Cf. A000142, A257281, A261746, A261747.
%K nonn,tabl
%O 1,4
%A _Caleb Ji_, _Tanya Khovanova_, _Robin Park_, _Angela Song_, Sep 06 2015
|
