Results 1 to 4 of 4

Math Help - Combinatorics

  1. #1
    Senior Member pankaj's Avatar
    Joined
    Jul 2008
    From
    New Delhi(India)
    Posts
    318

    Combinatorics

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,447
    Thanks
    1863
    Quote Originally Posted by pankaj View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,914
    Thanks
    779
    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}<br />
&&&&& a_{_1} \\<br />
&& a_{2k} &&&&&& a_{_2} \\<br />
a_{_{2k-1}} &&&&&&&&& a_{_3} \\ \\<br />
* &&&&&&&&& * \\ \\<br />
* &&&&&&&&& * \\ \\<br />
&& a_{_{k+1}} &&&&&& a_{_{k-1}} \\<br />
&&&&& a_{_k}<br />
\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}<br />
&&&&& a_}_1} \\<br />
&& a_{_{2k-1}} &&&&&& a_{_2} \\<br />
a_{_{2k-2}} &&&&&&&&& a_{_3} \\ \\<br />
* &&&&&&&&& * \\ \\<br />
* &&&&&&&&& * \\ \\<br />
&& * &&&&&& * \\<br />
&&&& a_{_{k+1}} && a_{_k} <br />
\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).

    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    Quote Originally Posted by pankaj View Post
    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 ?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Combinatorics.
    Posted in the Discrete Math Forum
    Replies: 16
    Last Post: July 20th 2010, 03:29 AM
  2. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 18th 2010, 09:14 PM
  3. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 3rd 2010, 06:24 PM
  4. combinatorics
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 1st 2010, 11:53 PM
  5. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 10th 2009, 07:03 AM

Search Tags


/mathhelpforum @mathhelpforum