Essential Mathematics: Combinatorics

16 flashcards · Mathematics · by lakesare

1. Disjoint sets VS pairwise disjoint sets?

   Pairwise disjoint - such that any 2 distinct sets are disjoint (have an intersection equal to the empty set). The condition is a generalisation of the concept of disjoint sets from two to a collection of sets. When applied to a collection, the original formulation - that the sets have an intersection equal to the empty set - becomes ambiguous and in need of clarification.

2. Is this collection of sets pairwise disjoint?

   It's not pairwise disjoint. Pairwise disjoint - such that any 2 distinct sets are disjoint (have an intersection equal to the empty set).

3. Along what axes are Permutation, Combination, Sequence, and Multiset divided?

   Importance of order (arrangement VS selection) Whether repetitions are allowed The four different ways of choosing k objects from n objects.

4. Arrangement VS selection?

   arrangement - order is important selection - order is not important

5. How many different ways of choosing k objects from n objects are there?

   4.

6. What are good analogies for permutation VS combination?

   permutation - strange string where letters can't repeat combination - selecting team members

7. What's the intuitive formula for choosing k permutations (out of n elements)?

   Although formula (2) is neater, you’ll usually find that formula (1) is more convenient for calculating values of nPk.

8. What's the intuitive formula for choosing k combinations (out of n elements)?

   Formula (3) is usually the most convenient to use for practical calculations.

9. Why is this a linear first-order constant-coefficient recurrence relation? a is the first term, r and d are constants, with r ≠ 0.

   linear - no powers of xn−1. first-order - only immediately preceding xn-1 is present (no xn-2, etc.). Note that a second-order recurrence relation involves the previous two terms xn−1 and xn−2, and no others.constant-coefficient - coefficient r is a constant (rather than a function of the index variable n).

10. Why is this a linear first-order constant-coefficient recurrence relation? a is the first term, r and d are constants, with r ≠ 0.

    linear - no powers of xn−1. first-order - only immediately preceding xn-1 is present (no xn-2, etc.). Note that a second-order recurrence relation involves the previous two terms xn−1 and xn−2, and no others.constant-coefficient - coefficient r is a constant (rather than a function of the index variable n).

11. Why is this a linear first-order constant-coefficient recurrence relation? r and d are constants, with r ≠ 0.

    linear - no powers of xn−1. first-order - only immediately preceding xn-1 is present (no xn-2, etc.). Note that a second-order recurrence relation involves the previous two terms xn−1 and xn−2, and no others.constant-coefficient - coefficient r is a constant (rather than a function of the index variable n). You may be interested to know that a recurrence relation of the form above would still be a linear first-order constant-coefficient recurrence relation if it included a function of n in plac…

12. In what way are arithmetic sequences, and geometric sequences special cases of the linear first-order constant-coefficient recurrence sequence? For brevity, we'll refer to a recurrence relation above as first-order recurrence system.

    arithmetic sequences - r = 1 geometric sequences - d = 0 So first-order recurrence sequences are indeed a generalisation of both arithmetic and geometric sequences.

13. What does it mean to solve a recurrence system?

    To find its closed form. Solving a recurrence system means obtaining a closed-form solution: a non-recursive function of n.

14. How would you find a closed form for this infinite first-order recurrence sequence:

    Find r (it's r = 2 in this case) Find first 2 terms, and solve a system of equations.

15. [Counting principles] It's not about the action of 'choice' per se - it's about whether you can represent your situation in a tree. After you create the tree, you can use any multiplications you like. What's a _ Draw a tree (does it reduce by 1 on each step) Does order matter (should we divide by 1/k!)

    How many different 3-course meals are possible?

16. [Counting principles]

    How many different meals are possible if a meal must consist of three courses, or a starter and a main course, or a main course and a dessert?