Enumerating Bracelets

This is only vaguely python related, in as much as it shows one useful facet of the language: we never have to worry about integer overflows. Python will use ordinary integers if it can, but if numbers get too large it will transparently switch to a "big integer" with size limited only by memory and computing resources..

The problem is this (for a simple case)

Given a single diamond, ruby, sapphire and an emerald, how many different
bracelets (or necklaces) can we make using any number and combination of the gems? We consider
two bracelets identical if they are congruent under some combination
of rotation or reflection.

Thus the following are considered to be identical bracelets:




while the following, although comprising the same jewels, are
different:


For this particular case (four jewels) we can enumerate all the possible cases. If we just attach a single jewel there are four possibilities: it can be a ruby, emerald, sapphire or diamond, for two jewels we have six possibilities, for three jewels there are just four: we can exclude any one of the gems and then no matter how we order the other three, the result is identical

With all four gems, the order matters, but there are only three distinct patterns: the ruby can be opposite the diamond, sapphire or emerald, and we can flip the other two to get these cases.

For completeness we include the empty case, tough do not under any circumstances give this to your spouse as an anniversary gift no matter how understanding they may be of mathematics and the importance of the null set.



So we find a total of eighteen possibilities in all.


Now if we calculate the number for different values of n (the number of distinct jewels) we find:

f(0) = 1
f(1) = 2
f(2) = 1+2+1 = 4
f(3) = 1+3+3+1 = 8
f(4) = 1+4+6+4+3 = 18
f(5) = 1+5+10+10+15+12 = 53
f(6) = 1+6+15+20+45+72 = 219

The sequence continues

1, 2, 4, 8, 18, 53,219, 1201, 8055, 62860, 556070,
5488126, 59740688, 710771367, 9174170117...

It is pretty straightforward to find a formula for the series:




In Python,

def ffact2(n):
  tot = 1+n+n*(n-1)/2
  k = n*(n-1)
  for i in range(n-2, 0, -1):
      k*=i
      tot+=(k/(2*(n-i+1)))
  return tot

Now a bit of analysis suggests that:



To check this out all we need to do is take a factorial function and do a few quick calculations:

def fact(n):
  if n==0:
      return 1
  else:
      return n*fact(n-1)

def ff2(n):
  return ffact2(n)*2/(float(fact(n-1)))/(1+1./(n-1)*\
  (1+1./(n-2)*(1.+1./(n-3))))

for i in range(4,50): print ff2(n)

and we get

3.6
3.21212121212
2.88157894737
2.76091954023
2.72865853659
......
2.718282524
2.71828246475
2.71828241167

which is nicely converging on e, demonstrating the conjecture. Now the point of all of this is how easy it is to do this in Python. Try the same thing in any compiled language and you will start to get integer overflows! We calculated factorials of some very large numbers and never had to worry about the fact that integers might overflow. Python takes care of this automatically, since ordinary and big integers are unified in the language.