Monday, September 10, 2007

This is not going to be simple..

Consider this restricted lattice bounded by [0,0];[x,0];[x,y];[y,0]. One can move from any point to another by a path , sequence of adjacent lattice points ( like one in the bad diagram I have written). Enumerate the number of paths from [0,0] to [x,y] ( obviously within the restricted grid). What about the paths that have loops? By a loop I mean the path coming back to the point that has already been traversed. (This diagram does not have loops)

Thursday, September 06, 2007

Recent problems

Of late, I have been studying a lot of combinatorics and attacking problems with enthusiasm.Here are a few worth mentioning ones.

1. Supposing there exists a convex polygon such that no three diagonals meet at a point, (i)find the number of intersections of the diagonals. (ii)Find the number of interior areas formed.

2. Enumerate the number of ways of arranging n black and n white balls around a circle. Two arrangements are considered same if one can be obtained by rotation of other.

3. Enumerate the number of ways of selecting a subset of size k (k<=n/2) out of set { 1,2,...,n} so that no two elements in the subset are adjacent elements of the original set.1 and n are considered adjacent.

4. Among n points,any two points are said to be joined to each other if they are connected by the means of a line.Such a system is called a graph. Enumerate all the graphs such we can reach any point on the graph from other by traversing through through the connecting lines in a unique way.Alternately, find the number of spanning trees.

I could completely solve 1(i) and 3. I shall soon post the solutions. Rest I am clueless :)