1. ## Combinatorics

1.Given $\displaystyle n$ equally spaced points on the circumference of a circle(the vertices of a regular n-gon).Find number of ways to select three points such that the triangle formed by joining them is isosceles.

2.Find number of ways to select 3 vertices from a polygon of sides 2n+1 such that the centre of the polygon lies inside the triangle.

3.An operation $\displaystyle *$ on a set $\displaystyle A$ is said to be binary,if $\displaystyle x*y\in A$,for all $\displaystyle x,y\in A$, and it is said to be commutative if $\displaystyle x*y=y*x$ for all $\displaystyle x,y\in A$.Now if $\displaystyle A=\big\{a_{1},a_{2},a_{3},...,a_{n}\big\}$ then find the following

(i)Total number of binary operations on $\displaystyle A$

(ii)Total number of binary operations on $\displaystyle A$ such that $\displaystyle a_{i}*a_{j}\neq a_{i}*a_{k},if j\neq k$

(iii)Total number of binary operations on $\displaystyle A$ such that $\displaystyle a_{i}*a_{j}<a_{i}*a_{j+1},\forall i,j$

2. Originally Posted by pankaj
1.Given $\displaystyle n$ equally spaced points on the circumference of a circle(the vertices of a regular n-gon).Find number of ways to select three points such that the triangle formed by joining them is isosceles.
Select any one of the n points to be the vertex where the two congruent sides intersect. There are n ways to do that.

What you do next depends upon whether n is even or odd. If n is odd, there are now (n-1)/2 points to the "left" of the chosen vertex, (n-1)/2 on the "right". Choose any one of the (n-1)/2 points on the "left" (there are (n-1)/2 ways to do that) and the point on the "right" that completes the isosceles triangle if automatically selected also.

If n is even, there are n/2 points on either side so there are n/2 ways, rather than (n- 1)/2, to choose the second vertex.

2.Find number of ways to select 3 vertices from a polygon of sides 2n+1 such that the centre of the polygon lies inside the triangle.
Very similar. There are 2n+1 ways to select the first vertex, leaving (2n+1-1)/2= n points on either side. Choosing any of the n points on the "right" and any of the n points on the left guarentees that the center of the polygon will lie within the triangle.

3.An operation $\displaystyle *$ on a set $\displaystyle A$ is said to be binary,if $\displaystyle x*y\in A$,for all $\displaystyle x,y\in A$, and it is said to be commutative if $\displaystyle x*y=y*x$ for all $\displaystyle x,y\in A$.Now if $\displaystyle A=\big\{a_{1},a_{2},a_{3},...,a_{n}\big\}$ then find the following

(i)Total number of binary operations on $\displaystyle A$

(ii)Total number of binary operations on $\displaystyle A$ such that $\displaystyle a_{i}*a_{j}\neq a_{i}*a_{k},if j\neq k$

(iii)Total number of binary operations on $\displaystyle A$ such that $\displaystyle a_{i}*a_{j}<a_{i}*a_{j+1},\forall i,j$

3. Hello, pankaj!

I have a clumsy start on the first one . . .

1. Given $\displaystyle \,n$ equally spaced points on the circumference of a circle (the vertices
of a regular $\displaystyle \,n$-gon). .Find the number of ways to select 3 points such that
the triangle formed by joining them is isosceles.

I found three cases to consider . . .

[1] $\displaystyle \,n$ is even: .$\displaystyle n = 2k$

Number the vertices: .$\displaystyle a_1,a_2,a_3,\hdots a_{2k}$

. . $\displaystyle \begin{array}{cccccccccc} &&&&& a_{_1} \\ && a_{2k} &&&&&& a_{_2} \\ a_{_{2k-1}} &&&&&&&&& a_{_3} \\ \\ * &&&&&&&&& * \\ \\ * &&&&&&&&& * \\ \\ && a_{_{k+1}} &&&&&& a_{_{k-1}} \\ &&&&& a_{_k} \end{array}$

Using any of the $\displaystyle \,n$ points as the vertex of the isosceles triangle,
. . there are $\displaystyle k-2 \,=\,\frac{n-4}{2}$ choices for the base vertices.

The number of isosceles triangles is:

. . $\displaystyle f(n) \;=\;n\left(\dfrac{n-4}{2}\right) \:=\:\dfrac{n(n-4)}{2}\:\text{ for even }n$ .[1]

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

[2] $\displaystyle \,n$ is odd: $\displaystyle \,n \:=\:2k-1$

Number the vertices: .$\displaystyle a_1,a_2,a_3, \hdots a_{2k-1}$

. . $\displaystyle \begin{array}{cccccccccc} &&&&& a_}_1} \\ && a_{_{2k-1}} &&&&&& a_{_2} \\ a_{_{2k-2}} &&&&&&&&& a_{_3} \\ \\ * &&&&&&&&& * \\ \\ * &&&&&&&&& * \\ \\ && * &&&&&& * \\ &&&& a_{_{k+1}} && a_{_k} \end{array}$

Using any of the $\displaystyle \,n$ points as the vertex of the isosceles triangle,
. . there are $\displaystyle k-1 \:=\:\frac{n-1}{2}$ choices for the base vertices.

The number of isosceles triangles is:

. . $\displaystyle f(n) \;=\;n\left(\dfrac{n-1}{2}\right) \;=\;\dfrac{n(n-1)}{2}\:\text{ for odd }n$ .[2]

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

[3] $\displaystyle \,n$ is a multiple of 3: .$\displaystyle n \:=\:3k$

Then some of the isosceles triangles are equilateral
. . resulting in an overcount in the above formulas.

Therefore, if $\displaystyle \,n$ is a multiple of 3,
. . formulas [1] and [2] must be reduced by $\displaystyle (n-1).$

4. Originally Posted by pankaj
3.An operation $\displaystyle *$ on a set $\displaystyle A$ is said to be binary,if $\displaystyle x*y\in A$,for all $\displaystyle x,y\in A$, and it is said to be commutative if $\displaystyle x*y=y*x$ for all $\displaystyle x,y\in A$.Now if $\displaystyle A=\big\ a_{1},a_{2},a_{3},...,a_{n}\big\}$ then find the following
(i)Total number of binary operations on $\displaystyle A$
(ii)Total number of binary operations on $\displaystyle A$ such that $\displaystyle a_{i}*a_{j}\neq a_{i}*a_{k},if j\neq k$
(iii)Total number of binary operations on $\displaystyle A$ such that $\displaystyle a_{i}*a_{j}<a_{i}*a_{j+1},\forall i,j$
For (i) we count the number of functions from $\displaystyle A\times A\to A$.

For (ii) lets take an example:$\displaystyle A=\big\{a_{1},a_{2},a_{3}\big\}$.
We can assign $\displaystyle a_1\circ a_1$ in 3 ways.
Then we can assign $\displaystyle a_1\circ a_2$ in 2 ways.
Finally w can assign $\displaystyle a_1\circ a_3$ in 1 way.
But there are three first terms. That gives a total of $\displaystyle (3!)^3$
You do the general case.

Part (iii) is ill defined. I think that $\displaystyle <$ must be a total order on the set $\displaystyle A$. Otherwise how could we define $\displaystyle a_n\circ a_n$?