The Combinatorics

avatar
Created by
Marc

Cards (15)

  • Counting is not just 1, 2, 3, …, it is to determine the number of possible ways of arrangements or selections in each values.
  • Counting techniques are a set of mathematical methods used to determine the possible number of outcomes for a given situation or occurrence of certain events.
  • Applications of counting principles:
    • Probability and Statistics
    • Algorithms
    • Cryptography
    • Decision Making
  • Combinatorics is a branch of mathematics that deals about counting and arranging.
  • Fundamental Principles:
    • Sum Rule
    • Product Rule
  • The sum rule states that, if there are m ways to arrange one thing, and there are n ways to arrange another thing, and these arrangements cannot both happen or these things are mutually exclusive, then the number of ways to arrange either of those things is m + n.
  • Sum Rule: Keywords: or, either...or
  • Sum Rule
    Example#1: A restaurant offers three (3) vegetarian and five (5) non-vegetarian main courses. How many ways can a customer order either vegetarian or non vegetarian main course?
    Answer: 3 + 5 = 8 ways
    The total number of main course options is 8 ways.
  • The product rule states that, if there are m ways to arrange one thing, and then n ways to arrange another thing, and the choices are independent (i.e., the choice of one doesn't affect the choice of the other), then the number of ways to arrange both of those things is m × n.
  • Sum Rule
    Example#2: A clothing store offers 15 different styles of jeans and 20 different styles of t-shirts. A customer wants to buy either a pair of jeans or a t-shirt. How many ways can a customer choose one outfit from different styles?
    Answer: 15 + 20 = 35 ways
    The total number of options is 35 ways.
  • Product Rule: Keyword: and
  • Product Rule
    Example#1: A website requires a password with two lowercase letters, and two digits. How many passwords are possible?
    Answer:
    26 lowercase letters from a to z
    10 digits from 0 to 9
    26 x 26 x 10 x 10 = 67,600 ways
  • Product Rule
    Example#2: A website requires a password with two lowercase letters, and two digits. How many passwords are possible, and repetition is not allowed?
    Answer:
    26 lowercase letters from a to z
    10 digits from 0 to 9
    26 x 25 x 10 x 9 = 58,500 ways
  • An arrangement refers to the objects that can be arranged in order where it uses the permutation.
  • A selection refers to choosing from the given objects, and the order of the objects does not matter where it uses combinations.