A239257 Number of canyon polycubes of a given volume.

1, 3, 7, 16, 35, 73, 151, 304, 604, 1198, 2362, 4637, 9117, 17954, 35350, 69760, 137959, 273213, 542015, 1076870, 2141996, 4265350, 8501015, 16954408, 33833943, 67549763, 134912857, 269532456, 538603324, 1076479708, 2151817116, 4301833827, 8600826484

Offset

1,2

Comments

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

Links

Table of n, a(n) for n=1..33.

Christophe Carré et al., Dirichlet convolution and enumeration of pyramid polycubes, arXiv:1311.4836 [math.CO], 2013.

C. Carre, N. Debroux, M. Deneufchatel, J.-Ph. Dubernard, C. Hillariet, J.-G. Luque, O. Mallet, Enumeration of Polycubes and Dirichlet Convolutions, J. Int. Seq. 18 (2015) 15.11.4

Formula

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

Maple

calc2can:=proc(i, j, k, l) option remember;
    if (l<0) then 0
    elif (i*j*k>l) then 0
    elif k=1 then if (i*j=l) then 1 else 0; fi;
    else s:=0; a:=0; b:=0;
        while ((i+a)*j*(k-1)<=l-i*j) do
            b:=0;
            while ((i+a)*(j+b)*(k-1)<=l-i*j) do
                s:=s+binomial(i+a, a)*binomial(j+b, b)*calc2can(i+a, j+b, k-1, l-i*j);
                b:=b+1;
            od;
            a:=a+1;
        od;
        s;
    fi;
end;
comptec:=proc(l)
    s:=0;
    for k to l do
        i:=1:
        while (i*k<=l) do
            j:=1;
            while (i*k*j<=l) do
                s:=s+t^k*calc2can(i, j, k, l);
                j:=j+1;
            od:
            i:=i+1;
        od;
    od;
    s;
end;
enumc:=[seq(comptec(ii), ii=1..485)]:
convert([seq(enumc[i]*x^i, i=1..nops(%))], `+`):seriec:=subs(t=1, %);

Mathematica

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;
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]];
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 ];
Array[comptec, 40] /. t -> 1 (* Jean-François Alcover, Dec 05 2017, translated from Maple *)

Crossrefs

Cf. A229915, A227926.

Sequence in context: A026734 A026767 A240740 * A268394 A238913 A133124

Adjacent sequences: A239254 A239255 A239256 * A239258 A239259 A239260

Keyword

nonn

Author

Matthieu Deneufchâtel, Mar 13 2014

Status

approved