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

Author

Matthieu Deneufchâtel, Mar 13 2014

Keywords

• nonn

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

• 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

Crossrefs

Cf. A229915, A227926.

Programs

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

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