cp's OEIS Frontend

A239257 Number of canyon polycubes of a given volume.

%I A239257 #33 Jun 09 2018 10:54:37
%S A239257 1,3,7,16,35,73,151,304,604,1198,2362,4637,9117,17954,35350,69760,
%T A239257 137959,273213,542015,1076870,2141996,4265350,8501015,16954408,
%U A239257 33833943,67549763,134912857,269532456,538603324,1076479708,2151817116,4301833827,8600826484
%N A239257 Number of canyon polycubes of a given volume.
%C A239257 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 A239257 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 A239257 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 A239257 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 A239257 calc2can:=proc(i, j, k, l) option remember;
%p A239257     if (l<0) then 0
%p A239257     elif (i*j*k>l) then 0
%p A239257     elif k=1 then if (i*j=l) then 1 else 0; fi;
%p A239257     else s:=0; a:=0; b:=0;
%p A239257         while ((i+a)*j*(k-1)<=l-i*j) do
%p A239257             b:=0;
%p A239257             while ((i+a)*(j+b)*(k-1)<=l-i*j) do
%p A239257                 s:=s+binomial(i+a, a)*binomial(j+b, b)*calc2can(i+a, j+b, k-1, l-i*j);
%p A239257                 b:=b+1;
%p A239257             od;
%p A239257             a:=a+1;
%p A239257         od;
%p A239257         s;
%p A239257     fi;
%p A239257 end;
%p A239257 comptec:=proc(l)
%p A239257     s:=0;
%p A239257     for k to l do
%p A239257         i:=1:
%p A239257         while (i*k<=l) do
%p A239257             j:=1;
%p A239257             while (i*k*j<=l) do
%p A239257                 s:=s+t^k*calc2can(i, j, k, l);
%p A239257                 j:=j+1;
%p A239257             od:
%p A239257             i:=i+1;
%p A239257         od;
%p A239257     od;
%p A239257     s;
%p A239257 end;
%p A239257 enumc:=[seq(comptec(ii), ii=1..485)]:
%p A239257 convert([seq(enumc[i]*x^i, i=1..nops(%))], `+`):seriec:=subs(t=1, %);
%t A239257 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 A239257 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 A239257 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 A239257 Array[comptec, 40] /. t -> 1 (* _Jean-François Alcover_, Dec 05 2017, translated from Maple *)
%Y A239257 Cf. A229915, A227926.
%K A239257 nonn
%O A239257 1,2
%A A239257 _Matthieu Deneufchâtel_, Mar 13 2014