[seqfan] 3D version of A000938: 3-in-line inside the nXnXn cube

Richard Mathar mathar at strw.leidenuniv.nl
Fri May 21 14:46:47 CEST 2010


What is the 3D variant of A000938?
This should count the number of collinear point-triples in the n X n X n cube (i.d.,
in the simple cubic lattice). By scanning the binomial(n^3,3) 
triples of distinct points in the cube (which is C(n^3,3) = 2925, 41664, 317750,...for n>=3),
I guess this starts (offset n=3): 49,376,1858,5696 (? to be confirmed)

For n=3, for example, the 49 collinear triples have coordinates (sorting according
to the base-n representation of numbers from 0 to n^3-1):
[0, 0, 0], [1, 0, 0], [2, 0, 0]
[0, 0, 0], [0, 1, 0], [0, 2, 0]
[0, 0, 0], [1, 1, 0], [2, 2, 0]
[0, 0, 0], [0, 0, 1], [0, 0, 2]
[0, 0, 0], [1, 0, 1], [2, 0, 2]
[0, 0, 0], [0, 1, 1], [0, 2, 2]
[0, 0, 0], [1, 1, 1], [2, 2, 2]
[1, 0, 0], [1, 1, 0], [1, 2, 0]
[1, 0, 0], [1, 0, 1], [1, 0, 2]
[1, 0, 0], [1, 1, 1], [1, 2, 2]
[2, 0, 0], [1, 1, 0], [0, 2, 0]
[2, 0, 0], [2, 1, 0], [2, 2, 0]
[2, 0, 0], [1, 0, 1], [0, 0, 2]
[2, 0, 0], [2, 0, 1], [2, 0, 2]
[2, 0, 0], [1, 1, 1], [0, 2, 2]
[2, 0, 0], [2, 1, 1], [2, 2, 2]
[0, 1, 0], [1, 1, 0], [2, 1, 0]
[0, 1, 0], [0, 1, 1], [0, 1, 2]
[0, 1, 0], [1, 1, 1], [2, 1, 2]
[1, 1, 0], [1, 1, 1], [1, 1, 2]
[2, 1, 0], [1, 1, 1], [0, 1, 2]
[2, 1, 0], [2, 1, 1], [2, 1, 2]
[0, 2, 0], [1, 2, 0], [2, 2, 0]
[0, 2, 0], [0, 1, 1], [0, 0, 2]
[0, 2, 0], [1, 1, 1], [2, 0, 2]
[0, 2, 0], [0, 2, 1], [0, 2, 2]
[0, 2, 0], [1, 2, 1], [2, 2, 2]
[1, 2, 0], [1, 1, 1], [1, 0, 2]
[1, 2, 0], [1, 2, 1], [1, 2, 2]
[2, 2, 0], [1, 1, 1], [0, 0, 2]
[2, 2, 0], [2, 1, 1], [2, 0, 2]
[2, 2, 0], [1, 2, 1], [0, 2, 2]
[2, 2, 0], [2, 2, 1], [2, 2, 2]
[0, 0, 1], [1, 0, 1], [2, 0, 1]
[0, 0, 1], [0, 1, 1], [0, 2, 1]
[0, 0, 1], [1, 1, 1], [2, 2, 1]
[1, 0, 1], [1, 1, 1], [1, 2, 1]
[2, 0, 1], [1, 1, 1], [0, 2, 1]
[2, 0, 1], [2, 1, 1], [2, 2, 1]
[0, 1, 1], [1, 1, 1], [2, 1, 1]
[0, 2, 1], [1, 2, 1], [2, 2, 1]
[0, 0, 2], [1, 0, 2], [2, 0, 2]
[0, 0, 2], [0, 1, 2], [0, 2, 2]
[0, 0, 2], [1, 1, 2], [2, 2, 2]
[1, 0, 2], [1, 1, 2], [1, 2, 2]
[2, 0, 2], [1, 1, 2], [0, 2, 2]
[2, 0, 2], [2, 1, 2], [2, 2, 2]
[0, 1, 2], [1, 1, 2], [2, 1, 2]
[0, 2, 2], [1, 2, 2], [2, 2, 2]


As a motivation see for example

Hanno Lefmann, No l Grid-Points in spaces of small dimension, Lecture Notes in Comp. Sci. , 5034 (2008) 259-270
http://dx.doi.org/10.1007/978-3-540-68880-8

Attilo Por, David R. Wood, No-Three-in-Line-in-3D, Algorithmica 47 (4) (2007) 481-488
http://dx.doi.org/10.1007/s00453-006-0158-9

Reid Andersen, Fan Chung, Linyuan Lu, No-Three-in-Line-in-3D Aglorithmica 47 (4) (2007) 379-497
http://dx.doi.org/10.1007/s00453-006-0160-2


# return true if xtrip1, xtrip2 and xtrip3 are three collinear points in 3D
iscolin := proc(xtrip1,xtrip2,xtrip3)
        local diff21x, diff21y, diff21z, diff31x, diff31y, diff31z ;
        # build the difference vectors diff2=xtrip2-xtrip1 and diff3=xtrip3-xtrip1
        # and test whether  diff2=t*diff3 with some parameter t
        diff21x := xtrip2[1]-xtrip1[1] ;
        diff21y := xtrip2[2]-xtrip1[2] ;
        diff21z := xtrip2[3]-xtrip1[3] ;
        diff31x := xtrip3[1]-xtrip1[1] ;
        diff31y := xtrip3[2]-xtrip1[2] ;
        diff31z := xtrip3[3]-xtrip1[3] ;
        if xtrip1 = xtrip2 or xtrip2 = xtrip3 or xtrip1 = xtrip3 then
                error("degen triple") ;
        end if ;
        # is diff31[] = t * diff21[] ?
        if diff21x = 0 then
                if diff31x = 0 then
                        # both difference vectors in the y-z plane
                        if diff21y = 0 then
                                if diff31y = 0 then
                                        # both diff vects on the z-axis
                                        return true;
                                else
                                        # one on the z-axis, the other not
                                        return false;
                                end if;
                        else
                                if diff31y = 0 then
                                        # one on the z-axis, the other one not
                                        return false; 
                                else
                                        # general directions in the y-z plane
                                        t := diff31y/diff21y ; 
                                        if t*diff21z = diff31z then
                                                return true ;
                                        else
                                                return false;
                                        end if;
                                end if;
                        end if;
                else
                        # one diff vector in the y-z plane, the other not
                        return false;
                end if;
        else
                if diff31x = 0 then
                        # one diff vector in the y-z plane, the other not
                        return false;
                else
                        t := diff31x/diff21x ; 
                        if t*diff21y = diff31y and t*diff21z = diff31z then
                                return true;
                        else
                                return false;
                        end if;
                end if;
        end if;
end proc:

# convert a number n=0,1,2,3,... into a triple [n1,n2,n3], all 0<=ni<sid
linidx := proc(n,sid)
        local tr ;
        tr := convert(n,base,sid) ;
        while nops(tr) < 3 do
                tr := [op(tr),0] ;
        end do:
        tr ;
end proc:

# 3D variant of A000938: the number of collinear triples in n-by-n-by-n
num3in := proc(n)
        local a,ncub,nlin1,nlin2,xtrip2,xtrip3 ;
        a := 0 ;
        ncub := n^3 ;
        # linearized index of first point
        for nlin1 from 0 to ncub-1 do
                xtrip1 := linidx(nlin1,n) ; # [x,y,z], 0<=x,y,z<n
                # linearized index of second point
                for nlin2 from nlin1+1 to ncub-1 do
                        xtrip2 := linidx(nlin2,n) ; # [x,y,z], 0<=x,y,z<n
                        # linearized index of third point
                        for nlin3 from nlin2+1 to ncub-1 do
                                xtrip3 := linidx(nlin3,n) ; # [x,y,z], 0<=x,y,z<n
                                # count one more if collinear
                                if iscolin(xtrip1,xtrip2,xtrip3) then
                                        a := a+1 ;
                                end if;
                        end do:
                end do;
        end do:
        a ;
end proc:

for n from 3 do
        print(n,num3in(n)) ;
end do:





More information about the SeqFan mailing list