Results 1 to 9 of 9
Like Tree1Thanks
  • 1 Post By awkward

Math Help - A few simple exercies I need someone to explain to me how to do them.

  1. #1
    Newbie
    Joined
    Jun 2012
    From
    Poland
    Posts
    2

    A few simple exercies I need someone to explain to me how to do them.

    Hello, I want to learn DM by myself, and asked a university prof. (different faculty) to give me a few exercises to solve.

    Can You point me to subjects those are from and what should I learn as well as explain how those should be solved (with the solving itself done if possible)?

    Use generating functions to find an if :an = an - 1 + 3n, for n >= 1

    Find the number of ways to select 8 balls from the set of 5 identical red balls, 3 identical
    yellow balls and 7 identical green balls.

    Use the extended version of the Euclid's algorithm to compute EXT-EUCLID(24,42)

    How many ways are there to distribute 18 balls among 6 different persons if
    a) each ball is different and each person should get 3 balls
    b) all balls are identical ?

    How many permutations of the letters a, a, a, b, b, b, c, c, c, d, d, d, are there with no three
    consecutive letters the same?


    Show that P(n, k) = P(n - 1; k - 1) + P(n - k; k) for each 1 < k < n.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,316
    Thanks
    1225

    Re: A few simple exercies I need someone to explain to me how to do them.

    For the second one, you want to know how many combinations of 8 balls you can get from the 15. This is evaluated using

    \displaystyle \begin{align*} {15\choose{8}} = \frac{15!}{8!(15 - 8)!} \end{align*}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2012
    From
    Poland
    Posts
    2

    Re: A few simple exercies I need someone to explain to me how to do them.

    Quote Originally Posted by Prove It View Post
    For the second one, you want to know how many combinations of 8 balls you can get from the 15. This is evaluated using

    \displaystyle \begin{align*} {15\choose{8}} = \frac{15!}{8!(15 - 8)!} \end{align*}
    Thats it? There is no trick to it? When I saw that exercise I though there's gotta be a trick to it. Don't the colours make it harder?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,316
    Thanks
    1225

    Re: A few simple exercies I need someone to explain to me how to do them.

    Quote Originally Posted by RoseEsque View Post
    Thats it? There is no trick to it? When I saw that exercise I though there's gotta be a trick to it. Don't the colours make it harder?
    No because you aren't asked for a particular combination of colours, so essentially you're just choosing 8 balls from the 15 you are given.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Jun 2009
    Posts
    658
    Thanks
    131

    Re: A few simple exercies I need someone to explain to me how to do them.

    For the first problem, and without any specialist knowledge of methods, the following approach seems to work.
    The first term in the sequence a_{0} is unknown so call it a_{0}.
    Then, by repeated substitution,
    a_{1}=a_{0}+3
    a_{2}=a_{0}+9,
    a_{3}=a_{0}+18,
    a_{4}=a_{0}+30,
    a_{5}=a_{0}+45,
    and so on.
    It appears then as if we need to find some way of generating the number sequence 3,9,18,30,45 etc.
    A difference table shows that the sequence comes from a quadratic so assume that f(n)=a*n^{2}+b*n+c,
    substitute for three values of n and solve for a,b,c.
    (Ans: a_{n}=a_{0}+3(n^{2}+n)/2.)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,659
    Thanks
    599

    Re: A few simple exercies I need someone to explain to me how to do them.

    Hello, RoseEsque!

    How many ways are there to distribute 18 balls among 6 different persons if

    a) each ball is different and each person gets 3 balls?

    {18\choose3,3,3,3,3,3} \:=\:\frac{18!}{(3!)^6}




    b) all balls are identical and each person gets 3 balls?

    The balls are identical.
    Give any three balls to each of the six people.
    . . There is one way.




    **
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1

    Re: A few simple exercies I need someone to explain to me how to do them.

    Quote Originally Posted by Prove It View Post
    For the second one, you want to know how many combinations of 8 balls you can get from the 15. This is evaluated using

    \displaystyle \begin{align*} {15\choose{8}} = \frac{15!}{8!(15 - 8)!} \end{align*}
    Hi Prove It,

    Are you sure this is what the problem is asking?
    It seems to me that it is asking how many triples (r, y, g) there are that satisfy
    r+y+g = 8
    where
    0 \le r \le 5
    0 \le y \le 3
    0 \le g \le 7
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1

    Re: A few simple exercies I need someone to explain to me how to do them.

    Quote Originally Posted by RoseEsque View Post
    Hello, I want to learn DM by myself, and asked a university prof. (different faculty) to give me a few exercises to solve. Can You point me to subjects those are from and what should I learn as well as explain how those should be solved (with the solving itself done if possible)?
    Find the number of ways to select 8 balls from the set of 5 identical red balls, 3 identical
    yellow balls and 7 identical green balls.
    Quote Originally Posted by awkward View Post
    It seems to me that it is asking how many triples (r, y, g) there are that satisfy
    r+y+g = 8
    where
    0 \le r \le 5
    0 \le y \le 3
    0 \le g \le 7
    @awkward, You are exactly right. That is what the question means.
    The answer is the coefficient of x^{8} in this expansion.
    The clue is that right above the question is about generating functions.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1

    Re: A few simple exercies I need someone to explain to me how to do them.

    Quote Originally Posted by RoseEsque View Post
    Hello, I want to learn DM by myself, and asked a university prof. (different faculty) to give me a few exercises to solve.

    Can You point me to subjects those are from and what should I learn as well as explain how those should be solved (with the solving itself done if possible)?

    Use generating functions to find an if :an = an - 1 + 3n, for n >= 1

    [snip]
    BobP has already given you a solution to the first part, and I think he
    is right that it's easier witout generating functions in this case, but since the
    problem statement says to use generating functions, here is a go at
    it. I'm going to assume you know something about infinite series.

    The standard approach is to let
    f(x) = \sum_{n=0}^{\infty} a_n x^n
    Using the recurrence given, we will find a closed form for f(x), and
    then use that to find an expression for a_n.

    First, we would like to find the generating function for
    3n, i.e., a closed form for
    g(x) = \sum_{n=1}^{\infty} 3n x^n. A standard trick here
    is to start with
    (1-x)^{-1} = \sum_{n=0}^{\infty} x^n.
    Differentiate w.r.t. x, then multiply by 3x. The result is
    g(x) = 3x (1-x)^{-2}.

    Now we apply the recurrence relation a_n = a_{n-1} + 3n for
    n \ge 1. If we interpret this in terms of the generating
    functions above, it becomes
    f(x) = a_0 + x f(x) + 3 x (1-x)^{-2}
    (Write out a few terms of the infinite series for f and g if you have
    trouble seeing this.)
    Solving for f(x),

     f(x) = a_0 (1-x)^{-1} + 3 x (1-x)^{-3}

    This is the closed form for f(x) we were looking for. The next step
    is to use this to find a closed form for a_n. To do this,
    we will apply the binomial theorem for negative exponents (twice) on
    the right-hand side of the equation. The result is

    f(x) = a_0 \sum_{i=0}^{\infty} x^i + 3x \sum_{j=0}^{\infty} \binom{j+2}{j} x^j

    It is now possible to "read off" the coefficient of x^n on
    the right-hand side of the equation: it is

    a_n = a_0 + 3 \binom{n+1}{n} = a_0 + \frac{3}{2} n (n+1),

    which is the same result found by BobP.
    Thanks from BobP
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. can some one explain this
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: December 13th 2010, 07:43 PM
  2. Replies: 1
    Last Post: November 29th 2009, 11:13 AM
  3. Replies: 1
    Last Post: September 19th 2009, 01:12 AM
  4. Replies: 1
    Last Post: January 25th 2009, 08:50 PM
  5. Please explain a simple differentiation
    Posted in the Calculus Forum
    Replies: 4
    Last Post: August 23rd 2008, 07:49 AM

Search Tags


/mathhelpforum @mathhelpforum