|
%I #33 Jun 09 2018 10:54:37
%S 1,3,7,16,35,73,151,304,604,1198,2362,4637,9117,17954,35350,69760,
%T 137959,273213,542015,1076870,2141996,4265350,8501015,16954408,
%U 33833943,67549763,134912857,269532456,538603324,1076479708,2151817116,4301833827,8600826484
%N Number of canyon polycubes of a given volume.
%C A polycube P is a canyon polycube if the following conditions are satisfied: - if the cell with coordinates (a,b,c) belongs to P, then the cell with coordinate (a-1,b,c) also belongs to P (for a>1); - for each cell with coordinates (a,b,c) in P such that a = max { a' , (a',b,c) in P }, either a = max { a' , (a',b',c) in P } or a = max { a' , (a',b,c') in P }.
%H Christophe Carré et al., <a href="http://arxiv.org/abs/1311.4836">Dirichlet convolution and enumeration of pyramid polycubes</a>, arXiv:1311.4836 [math.CO], 2013.
%H C. Carre, N. Debroux, M. Deneufchatel, J.-Ph. Dubernard, C. Hillariet, J.-G. Luque, O. Mallet, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Dubernard/dub4.html">Enumeration of Polycubes and Dirichlet Convolutions</a>, J. Int. Seq. 18 (2015) 15.11.4
%F If n(i,j,h,v) denotes the number of canyons of height h, volume v such that the highest plateau has volume i * j, the following recurrence relation holds: n(i,j,h,v) = sum_{0 <= a <= i} sum_{0 <= b <= j} binomial(i+a,i) binomial(j+h,j) n(i+a,j+b,h-1,v-i*j).
%p calc2can:=proc(i, j, k, l) option remember;
%p if (l<0) then 0
%p elif (i*j*k>l) then 0
%p elif k=1 then if (i*j=l) then 1 else 0; fi;
%p else s:=0; a:=0; b:=0;
%p while ((i+a)*j*(k-1)<=l-i*j) do
%p b:=0;
%p while ((i+a)*(j+b)*(k-1)<=l-i*j) do
%p s:=s+binomial(i+a, a)*binomial(j+b, b)*calc2can(i+a, j+b, k-1, l-i*j);
%p b:=b+1;
%p od;
%p a:=a+1;
%p od;
%p s;
%p fi;
%p end;
%p comptec:=proc(l)
%p s:=0;
%p for k to l do
%p i:=1:
%p while (i*k<=l) do
%p j:=1;
%p while (i*k*j<=l) do
%p s:=s+t^k*calc2can(i, j, k, l);
%p j:=j+1;
%p od:
%p i:=i+1;
%p od;
%p od;
%p s;
%p end;
%p enumc:=[seq(comptec(ii), ii=1..485)]:
%p convert([seq(enumc[i]*x^i, i=1..nops(%))], `+`):seriec:=subs(t=1, %);
%t calc2can[i_, j_, k_, l_] := calc2can[i, j, k, l] = Module[{}, Which[l < 0, 0, i*j*k > l, 0, k == 1, If [i*j == l, 1, 0], True, s = 0; a = 0; b = 0;
%t While[(i + a)*j*(k - 1) <= l - i*j, b = 0; While[(i + a)*(j + b)*(k - 1) <= l - i*j, s = s + Binomial[i + a, a]*Binomial[j + b, b]*calc2can[i + a, j + b, k - 1, l - i*j]; b++]; a++]; s]];
%t comptec[l_] := Module[{s = 0}, For[k = 1, k <= l, k++, i = 1; While[i*k <= l, j = 1; While[i*k*j <= l, s = s + t^k*calc2can[i, j, k, l]; j++]; i++] ]; s ];
%t Array[comptec, 40] /. t -> 1 (* _Jean-François Alcover_, Dec 05 2017, translated from Maple *)
%Y Cf. A229915, A227926.
%K nonn
%O 1,2
%A _Matthieu Deneufchâtel_, Mar 13 2014
|
