31
Solving combinatorial problems by listing choices
Textbook: pp. 200–202
GoalSolve combinatorial problems by listing all possibilities in order and by using a tree of options.
New words
combinatorial problem · kombinatorik masalalisting method · tanlash (sanab chiqish) usulitree of options · variantlar daraxtinumber of possibilities · imkoniyatlar soni
Explanation
In combinatorial problems we must find the number of all ways (options) satisfying a condition. To skip no option and repeat none, we write them in an orderly way, for example in increasing order or grouped by the first element. Another convenient tool is the tree of options: from the root, a branch for each possibility of the first choice, and from each of these, branches for the next choice; the number of final ends of the tree is the number of all options. When making numbers from digits, the condition says whether repetition is allowed.
Worked examples
Choosing a captain and an assistant from four pupils A, B, D, G (order matters): AB, AD, AG, BA, BD, BG, DA, DB, DG, GA, GB, GD — 12 in total.
Four classmates A, B, C, D pick a pair for class duty (order does not matter): AB, AC, AD, BC, BD, CD — 6 pairs.
Class activity
“Draw the tree”: groups draw on the board a tree of lunch options with two juices and three pastries and count all kinds of lunch.
Practice
1
Write all three-digit numbers from the digits 1 and 2 (repetition allowed) and say how many there are.
111, 112, 121, 122, 211, 212, 221, 222 — 8 numbers
2
In how many orders can Ali, Vali and Sami sit on three seats? List them.
6
3
Two of 3 kinds of sweets are chosen (order does not matter). How many ways are there?
3
4
Why is it important to list the options in an orderly way?
If they are listed in order, no option is missed or repeated.