Isomers of alkanes

[eklavya sharma 2]

I want to make a program which finds the number of isomers of an alkane ,given the number of carbon atoms (mainly for those who know the basics of organic chemistry). For those who know what enantiomers are, I don't want to count them.

For those who can't remember what alkanes are, looking at the images will probably give you a hint about what I'm trying to ask. Just remember that a carbon atom can link to a maximum of 4 other carbon atoms.

In the images, all hydrogen atoms are stripped off (for clarity).

For eg. butane (4 carbons) has 2 isomers
http://www.dropbox.com/s/uvpvo5lsgnrdmff/butane.png

Pentane (5 carbons) has 3 isomers
http://www.dropbox.com/s/194keoy5yn0l0bk/pentane.png

Hexane(6) has 5 isomers
http://www.dropbox.com/s/0u1lg737ztiwlmn/hexane.png

Heptane(7) has 9 isomers
http://www.dropbox.com/s/mzt6vomxjk05r3p/heptane.png

Methane(1), Ethane(2) and Propane(3) have one isomer each.

Here is a list of number of isomers for upto 32 carbon atoms:
http://www.dropbox.com/s/o8r3hkbikakg69s/Isomers%20of%20alkanes.txt

I tried thinking of an algorithm but nothing is coming to my mind. If there is a topic in mathematics that I need to read to be able to attempt this problem, please tell me.

I have however made a program to find the number of alkyl groups (i.e. branches):
I wrote this code a long time ago, so its not well documented and I have used new[] instead of std::vector.

#include<iostream.h>
#include<math.h>
#include<eku\ekulib.h>

bool ismore(int* a,int n);//check if array can be further incremented
bool next(int* a,int n);//put the next number in the array storing number of 
//substituents at each C
void init(int* a,int n,int r);//initialize an array storing number of substituents at each C
//n - no. of C atoms in principal chain		r - no. of C atoms as substituents
int  iso(int n,int r);//gives the number of isomers of a carbon compound with
//n C atoms in principal chain and r C atoms as substituents
int  isoall(int n,int r);//gives all isomers with n C atoms and maximum length of
//principal chain as r

inline int maxalk(int n)
{return int(pow(3,double(n))-1)/2;}

bool ismore(int* a,int n)
{
	int i,r=0,t;
	for(i=0;i<n;i++)r+=a[i];
	if(r==0)return false;
	for(i=0;i<n;i++)
	{
		t=maxalk(i);
		if(a[i]>=t || r==a[i])r-=a[i];
		else return true;
	}
	return false;
}

bool next(int* a,int n)
{
	int i,r=0;
	for(i=0;i<n;i++)r+=a[i];
	if(n==3 && ismore(a,3)){a[1]++;a[2]--;return true;}
	else if(!ismore(a,n))return false;
	else if(ismore(a,n-1)){next(a,n-1);return true;}
	else {a[n-2]++;a[n-1]--;return true;}
}

void init(int* a,int n,int r)
{
	int p=r,t,i;
	for(i=n-1;i>=0;i--)
	{
		if(p==0)a[i]=0;
		else
		{
			t=maxalk(i);
			if(p<=t){a[i]=p;p=0;}
			else {a[i]=t;p-=i;}
		}
	}
}

int iso(int n,int r)
{
	int *a,i,j,count=0,p,q;
	if(r>maxalk(n)-n || r<0)return 0;
	if(n==1 || n==2 || r==0)return 1;
	a=new int[n];
	init(a,n,r);
	do
	{
		for(i=1;i<n;i++)for(j=0;j<=a[i]/2;j++)
		{
			p=isoall(j,i);
			q=isoall(a[i]-j,i);
			if(p==0 || q==0)count+=p+q;
			else count+=p*q;
		}
	}
	while(next(a,n));
	delete[] a;
	return count;
}

int isoall(int n,int r)
{
	if(n<r)r=n;
	if(r<=0 || n==0)return 0;
	else if(n==1 || n==2)return 1;
	int i,s=0;
	for(i=2;i<=r;i++)if(n-i<=maxalk(i)-i)s+=iso(i,n-i);
	return s;
}

void main()
{
	int n;
A:	cout<<"Enter n ";cin>>n;
	cout<<"Isomers of alkyl groups with "<<n<<" carbons = "<<isoall(n,n)<<endl;
	if(cont())goto A;
}

[Cubbi]

I tried thinking of an algorithm but nothing is coming to my mind. If there is a topic in mathematics that I need to read to be able to attempt this problem, please tell me.

The algorithm (or, rather, the theory behind the algorithm) is called Pólya's theorem: http://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem (until that theorem, all people could do was up to C13 since 1870s and up to C20 since 1931). This isn't an easy thing to do.

Wikipedia has a longer list if you want extra validation: http://en.wikipedia.org/wiki/List_of_straight-chain_alkanes

I have used new[] instead of std::vector.

you also used "void main" and goto

[eklavya sharma 2]

you also used "void main" and goto

This is why:
http://www.cplusplus.com/forum/beginner/88726/#msg476317
When I wrote this code, I was still learning the basics.

The math link you gave me is certainly difficult. I'm not well versed with most definitions on that page. I'll try looking at this problem after my vacations start.