A239257 - OEIS

%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