Results 1 to 4 of 4

Thread: Combinatorics

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

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

  2. #2
    MHF Contributor

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

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    12,028
    Thanks
    849
    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).$

    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,797
    Thanks
    2828
    Awards
    1
    Quote Originally Posted by pankaj View Post
    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 $?
    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: Jul 20th 2010, 02:29 AM
  2. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Jun 18th 2010, 08:14 PM
  3. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Jun 3rd 2010, 05:24 PM
  4. combinatorics
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 1st 2010, 10:53 PM
  5. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Oct 10th 2009, 06:03 AM

Search Tags


/mathhelpforum @mathhelpforum