Combinatorics

**pankaj** · November 27th 2010, 05:53 AM

1.Given $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 $*$ on a set $A$ is said to be binary,if $x*y\in A$ ,for all $x,y\in A$ , and it is said to be commutative if $x*y=y*x$ for all $x,y\in A$ .Now if $A=\big\{a_{1},a_{2},a_{3},...,a_{n}\big\}$ then find the following

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

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

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

**HallsofIvy** · November 27th 2010, 07:29 AM

Originally Posted by pankaj

1.Given $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 $*$ on a set $A$ is said to be binary,if $x*y\in A$ ,for all $x,y\in A$ , and it is said to be commutative if $x*y=y*x$ for all $x,y\in A$ .Now if $A=\big\{a_{1},a_{2},a_{3},...,a_{n}\big\}$ then find the following

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

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

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

**Soroban** · November 27th 2010, 07:38 AM

Hello, pankaj!

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

1. Given $\,n$ equally spaced points on the circumference of a circle (the vertices
of a regular $\,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] $\,n$ is even: . $n = 2k$

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

. . $\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 $\,n$ points as the vertex of the isosceles triangle,
. . there are $k-2 \,=\,\frac{n-4}{2}$ choices for the base vertices.

The number of isosceles triangles is:

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

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

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

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

. . $\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 $\,n$ points as the vertex of the isosceles triangle,
. . there are $k-1 \:=\:\frac{n-1}{2}$ choices for the base vertices.

The number of isosceles triangles is:

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

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

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

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

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

**Plato** · November 27th 2010, 11:17 AM

Originally Posted by pankaj

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

For (i) we count the number of functions from $A\times A\to A$ .

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

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

Thread: Combinatorics

LinkBack

Thread Tools

Display

Combinatorics

Similar Math Help Forum Discussions

[SOLVED] Combinatorics.

Combinatorics

Combinatorics

combinatorics

Combinatorics

Search Tags