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 a_{n} if :a_{n} = a_{n - 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.

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

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

Quote:

Originally Posted by

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

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?

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

Quote:

Originally Posted by

**RoseEsque** 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.

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 is unknown so call it .

Then, by repeated substitution,

and so on.

It appears then as if we need to find some way of generating the number sequence etc.

A difference table shows that the sequence comes from a quadratic so assume that

substitute for three values of and solve for

(Ans: )

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

Hello, RoseEsque!

Quote:

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?

Quote:

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.

**

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

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

Quote:

Originally Posted by

**RoseEsque** 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**

@awkward, You are exactly right. That is what the question means.

The answer is the coefficient of in this expansion.

The clue is that right above the question is about generating functions.

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

Quote:

Originally Posted by

**RoseEsque** 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 a_{n} if :a_{n} = a_{n - 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

Using the recurrence given, we will find a closed form for f(x), and

then use that to find an expression for .

First, we would like to find the generating function for

, i.e., a closed form for

. A standard trick here

is to start with

.

Differentiate w.r.t. x, then multiply by . The result is

.

Now we apply the recurrence relation for

. If we interpret this in terms of the generating

functions above, it becomes

(Write out a few terms of the infinite series for f and g if you have

trouble seeing this.)

Solving for f(x),

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 . To do this,

we will apply the binomial theorem for negative exponents (twice) on

the right-hand side of the equation. The result is

It is now possible to "read off" the coefficient of on

the right-hand side of the equation: it is

,

which is the same result found by BobP.