CS70 Guide
  • This site is now deprecated
  • LaTeX Reference
  • Discrete Math
    • Overview
    • Propositional Logic
    • Proofs
    • Stable Matching
    • Graphs
    • Modular Arithmetic
    • RSA Cryptography
    • Polynomials
    • Countability
    • Computability
  • Probability
    • Overview
    • Counting
    • Discrete Probability
    • Hashing and the Union Bound
    • Expectation and Variance
    • Concentration Inequalities
    • Continuous Probability
    • Markov Chains
    • The Beta Family
    • The Gamma Family
    • Conditional Expectation and Variance
Powered by GitBook
On this page
  • Introduction
  • The First Rule of Counting: When the order matters
  • The Second Rule: When the order doesn't matter
  • Stars and Bars
  • The Inclusion-Exclusion Principle

Was this helpful?

  1. Probability

Counting

PreviousOverviewNextDiscrete Probability

Last updated 2 years ago

Was this helpful?

Introduction

If you're reading this, I think it's safe to assume you already know how to count... (1, 2, 3, whatever) so what's the big deal about counting?

When we say counting in this context, we mean counting sequences of decisions. For example, we might want to get the total number of ways to choose toppings on a pizza or something.

There are two main types of problems: those where order matters and those where it doesn't.

The First Rule of Counting: When the order matters

Here's a sample problem: let's try to figure out the total number of unique 5-character strings we can make with the letters 'A' through 'E'. For instance, 'ABCDE' and 'DABBA' are both valid.

Lots of these types of problems can be visualized using slots, where each slot is one character or option:

To get the total number of ways to fill the slots, we can multiply the number of ways each individual slot can be filled together.

So for the problem above, we get that there are 5 ways to fill each slot, and 5 slots in total. So, 5×5×5×5×5=31255 \times 5 \times 5 \times 5 \times 5 = 31255×5×5×5×5=3125strings.

The Second Rule: When the order doesn't matter

In order to tackle these types of problems, we'll need to introduce the combinatorial (nk)=n!k!(n−k)!\binom{n}{k} = \frac{n!}{k!(n-k)!}(kn​)=k!(n−k)!n!​. When you see this, it means "the number of ways we can choose nnnthings from kkktotal elements if order doesn't matter".

Stars and Bars

When we need to split items into groups, it's sometimes nice to add bars that separate the items. This is great if there are particular classes of items rather than unique ones (if they're unique, just use slots.)

How this works is that we can treat each item as a star, and the stars are separated by bars that designate one group from another.

This means that if there are nnnstars and kkkgroups, then there must be (n+k−1k−1)\binom{n+k-1}{k-1}(k−1n+k−1​)total ways to split the stars into groups.

One application of this is to get the total number of equations y0+y1+⋯+yk=ny_0 + y_1 + \cdots + y_k = ny0​+y1​+⋯+yk​=nfor a fixed nnn. We can think of there being nnnnumber of ones (our stars), and kkknumber of plus signs (our bars). There can also be an empty group (representing yi=0y_i = 0yi​=0), which bumps us up to k+1k+1k+1groups. By the Stars and Bars principle, there are (n+kk)\binom{n+k}{k}(kn+k​)such equations for non-negative numbers.

The Inclusion-Exclusion Principle

Used to calculate the probability of the union of events.

http://prob140.org/textbook/content/Chapter_05/02_Inclusion_Exclusion.html