[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