Vending machine problem

Loading...

来自 National Research University Higher School of Economics 的课程

Introduction to Enumerative Combinatorics

68 个评分

National Research University Higher School of Economics

Introduction to Enumerative Combinatorics

68 个评分

Enumerative combinatorics deals with finite sets and their cardinalities. In other words, a typical problem of enumerative combinatorics is to find the number of ways a certain pattern can be formed. In the first part of our course we will be dealing with elementary combinatorial objects and notions: permutations, combinations, compositions, Fibonacci and Catalan numbers etc. In the second part of the course we introduce the notion of generating functions and use it to study recurrence relations and partition numbers. The course is mostly self-contained. However, some acquaintance with basic linear algebra and analysis (including Taylor series expansion) may be very helpful.

从本节课中

Linear recurrences. The Fibonacci sequence

We start with a well-known "rabbit problem", which dates back to Fibonacci. Using the Fibonacci sequence as our main example, we discuss a general method of solving linear recurrences with constant coefficients.

Fibonacci’s rabbit problem9:36

Fibonacci numbers and the Pascal triangle7:56

Domino tilings8:26

Vending machine problem10:07

Linear recurrence relations: definition7:53

The characteristic equation8:43

Linear recurrence relations of order 211:02

The Binet formula11:21

Sidebar: the golden ratio9:12

Linear recurrence relations of arbitrary order8:44

The case of roots with multiplicities12:10

与讲师见面

Evgeny Smirnov
Associate Professor
Faculty of Mathematics

[MUSIC]

Here is our next example.

It is called a vending machine problem.

Suppose you have sufficiently many coins of 5 cents nickels.

10 cents, dimes.

And 25 cents, quarters.

And you have a vending machine selling, say, kinds of soda.

And suppose that kind of soda costs $1.

And the question is, in how many ways can you pay a certain amount, say, $1?

In how many ways,

Can you pay, $1 or any other amount?

So since you have a vending machine,

the order of throwing coins into the machine is important.

So, say, if you're paying

5+10+10+3 quarters,

This is not the same as paying, say,

10, then a quarter, then again 10,

then 5, and then 2 quarters.

We'll consider these two configurations as different ones.

Okay, it is obvious that we only can pay amounts in cents which are divisible by 5.

So denote a number of ways

of paying 5n cents.

Number of ways,

To pay 5n cents

by A(n).

Okay, so what can we say about this, This sequence?

So if we're interested in the number of ways to pay $1, this will be A(20).

Okay [COUGH] let us form the following table.

So here we will have n.

And below we will have A(n).

So if n is equal to 5,

Then this is just 5 cents.

And 5 cents can be paid in a unique way.

So for n equal to 2, well, 10 cents can be paid

either by one 10 cent coin or by two 5 cent coins.

So this is 2.

15 cents can be paid in three ways.

Okay, for 4, the number of ways to pay 20 cents is equal to 5.

And so far, we have the Fibonacci sequence.

Okay, we also formerly say that the number of

ways of not paying anything will be 1.

We will need this in a minute.

So if our A(n) coincides with the Fibonacci numbers, and

this is pretty clear.

Because we had our previous description that the Fibonacci

number is equal to the number of compositions,

to the number of presentations of n as the sum of 1s and 2s.

And paying 5n cents by nickels and

dimes is exactly a composition of 5n into 1s

corresponding to nickels and 2s corresponding to dimes.

And if the amount that we're paying is less than 25 cents,

we cannot use quarters.

Okay, so what happens now?

What happens if, We want to pay 25 cents?

So this can be done in several ways.

So how to pay, 25 cents?

Well, the first possibility is just to pay 1 quarter.

And this can be done in a unique way.

Then, another possibility is that,

as our first coin, we use a dime.

And then this means that we need to pay another 15 cents.

And this can be done in three possible ways.

So if we pay 10 cents plus something, this can be done in three ways.

So this is A(3).

And if the first coin that we use is

a nickel, this means that we have

A(4) = 5 possibilities,

To pay another 20 cents.

So the total number is 1 plus 3 plus 5, that is 9.

Okay, so what about n equal to 6?

In how many ways can we present 6 as a sum of 5s, 1s, and 2s?

So same question about 30 cents.

So if we pay a quarter at first,

we have A(1), just one possibility.

If we start with a dime.

We have 5 possibilities.

If we start with a nickel, then the number of possibilities is 9.

So this makes 15.

From this, we can already deduce the recurrence of relation for A(n).

Namely, A(n), the number of ways of

paying 5n cents by nickels, dimes,

and quarters is equal to A(n-1).

Which corresponds to using a nickel as the first coin.

+ A(n-2), which corresponds

to using a dime first.

+ A(n-5), which means that the first coin you use is a quarter.

So here is our recurrence relation.

And it looks pretty similar to their relation for Fibonacci numbers.

But in this case, the nth term in this sequence depends,

not only from the previous two, but from the previous five of them.

So this is called a recurrence relation of order five.

And now, we will give a general definition of a recurrence relation.

[MUSIC]

探索我们的目录

免费加入并获得个性化推荐、更新和优惠。

Coursera 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

© 2019 Coursera Inc. 保留所有权利。

通过 App Store 下载

通过 Google Play 获取