Available online
Description
The programme explores the use of the mathematical technique called Rook polynomial for solving such problems as allocating jobs in a factory or places around a dinner table.
The programme explores the use of the mathematical technique called Rook polynomial for solving such problems as allocating jobs in a factory or places around a dinner table.
| Module code and title: | TM361, "Graphs, networks and design" |
|---|---|
| Item code: | TM361; 09 |
| First transmission date: | 08-07-1981 |
| Published: | 1981 |
| Rights Statement: | |
| Restrictions on use: | |
| Duration: | 00:22:10 |
| + Show more... | |
| Producer: | Andrew Millington |
| Contributors: | Roy Nelson; Richard Scott |
| Publisher: | BBC Open University |
| Keyword(s): | Dinner; Polynomial; Rook |
| Footage description: | Film shots of a television set assembly line during production. Commentary points out that workers have to be skilled in several jobs so that the production line doesn't come to a halt if one is absent. Roy Nelson, with a graphics board, explains that the problem above is essentially one of how many ways there are of assigning a given number of people to a given number of jobs. Richard Scott points out that a mathematical approach to this type of problem is to look at the way rooks move on a chessboard. He demonstrates with a chessboard and several rooks and works out the number of ways two non-attacking rooks can be placed on a chessboard. Roy Nelson goes on to look at the generalised solution to the problem; placing K rooks on a chessboard. He derives a generating function, the Rook polynomial, which is used for solving a variety of problems of this type. Roy Nelson applies the Rook polynomial to several different boards. The polynomials are shown on a graphics board in each case. Nelson introduces a new notation which is useful for showing the set of squares whose Rook polynomial is being manipulated. He illustrates several cases using this notation. Richard Scott relates the Rook polynomial to non-standatd board squares and derives the recurrence rule from this. He demonstrates with a specific example. Nelson introduces the theorem which is applied in any situation where n rooks are arranged on an nxn board and which avoid certain prohibited squares. The theorem is similar to the inclusion/exclusion theorem which is introduced to students in their texts. Having presented the mathematics for finding the Rook polynomial for a general set of squares. Richard Scott now applies it to the jobs problem discussed at the beginning of the programme. In this case there are twelve ways of distributing the jobs among five people. Over film shots of a dinner party, commentary by Richard Scott sets out the problem for the host of seating couples so that no wife is next to her husband at the table. He then asks students to write out the number of ways this can be done. Roy Nelson, wery briefly, sums up the programme. |
| Production number: | FOUT084Y |
| Videofinder number: | 1530 |
| Available to public: | no |
