maths.free › Probability Theory › 11. Applying Probability to Combinatorics › Estimating Ramsey Numbers

Estimating Ramsey Numbers

We will find it convenient to utilize the following approximation due to Stirling. You can find a proof in almost any advanced calculus book.

Estimating Ramsey Numbers

We will find it convenient to utilize the following approximation due to Stirling. You can find a proof in almost any advanced calculus book. \[\begin{aligned}\end{aligned}\] Of course, we will normally be satisfied with the first term: \[\begin{aligned}\end{aligned}\] Using Stirling's approximation and the binomial coefficients from the proof of , we have the following upper bound: \[\begin{aligned}\end{aligned}\]

Symbols used here

n!
factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.
\binom{n}{k}
binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).
\sum_{k=1}^{n} a_k
summation
Add a_k for k = 1 up to n.
\int f(x)\,dx,\ \int_a^b
integral
Antiderivative (indefinite) or signed area from a to b (definite).
A \cup B,\ A \cap B,\ A \setminus B
union, intersection, difference
In either; in both; in A but not B.
\bar{x},\ \mu
sample mean, population mean
Average of the data; average of the whole population.
\sigma,\ s,\ \sigma^2
standard deviation, sample s.d., variance
Typical distance from the mean; its square.
P(A),\ P(A \mid B)
probability, conditional probability
Chance of A; chance of A given that B happened.
E[X],\ \operatorname{Var}(X)
expected value, variance
Probability-weighted average of X; its spread.
N(\mu, \sigma^2),\ z
normal distribution, z-score
The bell curve with mean μ and variance σ²; (x − μ)/σ.
\mu(A),\ \sigma\text{-algebra}
measure of A
Size of a set; the family of sets that can be measured.

Questions people ask

What is the difference between probability and statistics?

Probability goes from a known model to what the data should look like; statistics goes from data back to the model. Probability theory is the deductive half.

What does the law of large numbers promise?

That the average of many independent samples converges to the expected value. It says nothing about any single trial.

Փորձեք ինքներդ

Parts of this page are adapted from Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

Ցուցադրել Probability Theory

Sample spaces and the axiomsRandom variables and expectationThe common distributionsThe law of large numbers and the central limit theorem