[seqfan] Re: unlabeled Motzkin numbers
Richard Mathar
mathar at strw.leidenuniv.nl
Wed Oct 27 23:36:05 CEST 2010
In http://list.seqfan.eu/pipermail/seqfan/2010-October/006304.html
someone wanted to count
ma> That is, number of ways of drawing any number of nonintersecting
ma> chords joining n unlabeled equally spaced points on a circle (in other
ma> words, the points and chords are distinguished up to rotations of the
ma> circle).
For n=1 point we have 1 (no chord at all)
For n=2 point we have 2 (no chord at all or connecting the 2 points)
For n=3 point we have 2 (no chord at all or connecting any 2 points)
For n=4 point we have 4 (no chord at all, connecting all 2 adjacent pairs,
connecting only one adjacent pair or connecting
diagonally)
For n=5 we have again 4 (no chord, one diagonally, one adjacent, two pairs)
So my guess would be
1,2,2,4,4,8,10,20,30,56,94,180,316
which is algorithmically defined as:
Build all sets with k=0, 2, 4, 6, 8, ... points chosen from (0,..,n-1),
the enumerated (labelled) points on the circle.
This accounts for chords connecting pairs and for the fact that the
order of the chords is enforced on a "nearest neighbor" basis as they
must not intersect.
Two sets of points [c1,c2,c3,...,ck] and [d1,d2,d3,..,dk] are equivalent
if the transformation [(d1+s)mod n, (d2+s) mod n,... (dk+s) mod n]
of the second set with any shift "s" and followed by sorting yields the same
sequence as [c1,c2,c3,..,ck] . This basically is equivalent to rotation
or cyclic permutation.
In each of the sets retain only one member (and count it) of such a
set.
This is, of course, only a crude approximation to the full problem...
RJM
# return true if the two lists L1 and L2 are equivalent in the
# sense that "rigit" shifting of all members L2 (mod n) generates
# the same list as L1.
equivPerm := proc(L1,L2,n)
L1s := sort(L1) ;
# Try to shift (cyclically) L2 by any amount from 0 up to n-1
# positions.
for shif from 0 to n-1 do
L2s := [seq( (op(i,L2)+shif) mod n,i=1..nops(L2)) ];
L2s := sort(L2s) ;
if L2s = L1s then
return true;
end if;
end do:
return false;
end proc:
A := proc(n)
local a,c,cs,c1,c2,isuni ;
a := 0 ;
# select points subsets of size 0, 2,4,6,8,...
for cs from 0 to n by 2 do
c := combinat[choose]([seq(i,i=0..n-1)],cs) ;
# the first in such a set (no chords) is a unique solution: count it
a := a+1 ;
# for all pairs (c2,c1) of these sets of the same number
# of chords, compare them. Move c2 upwards and check for all
# c1 earlier in the combinations whether c1 is equivalent.
for c2 from 2 to nops(c) do
# is c2 a unique chord diagram?
isuni := true;
for c1 from 1 to c2-1 do
# c2 is found not to be unique...
if equivPerm( op(c1,c),op(c2,c),n) then
isuni := false ;
break;
end if;
end do;
# if c2 is found to have no equivalent ealrier member
# in the combinations: count it
if isuni then
a := a+1 ;
end if;
end do;
end do:
a ;
end proc:
for n from 1 do
print(n,A(n)) ;
end do:
seq(A(n),n=1..12) ;
More information about the SeqFan
mailing list