# Combinatorics - Expanding the Wiki

$$\color{red} {\text{ Updated 11/21/2014}}$$

I have now updated the Combinatorics maps. I would appreciate if you would be willing to contribute to the wiki pages and help us build out this store of knowledge for others to learn from.

I have not built out certain specific areas like Graph Theory, Incidence Matrices, Coloring Proofs. Over time, I will add these in when it becomes appropriate.

Problem creators, I would greatly appreciate your help in sorting your combinatorics questions into the corresponding skill. You can do so by editing your problem and selecting from the drop-down menu. If your problem is not easily classified, please let me know.

Thanks for your suggestions for the Mechanics Map. I encourage you to check it out, and contribute to the Wiki where you can.

I am now extending out the Combinatorics Map, which will include more on statistics and on Olympiad problem solving. We can easily add additional skills, if you voice out what you want. Please take a look at Upcoming Skill Maps - Combinatorics Extension for the (most updated) proposed extension.

I have the following questions. Please reply to the appropriate comment, to make it easy for me to track.

1)Is there a preference to split apart "Probability and Statistics" and "Combinatorics"?

2) Probability and Random Variables- Are there any other chapters that you want to see here? I kept this to mostly high school / college material. Are there any enrichment topics that you would be interested in writing wikis for?

3) Applications of Counting - I decided to sort it according to types of problems. I'm quite certain that there are several classifications that I missed out, so please enlighten me. Also, if you have suggestions for a different organization approach, I'm all ears.

4) Binomial Theorem - This looks quite standard to me. Any comments?

5) Recurrence Relations - Is there interest in expanding beyond linear recurrence relations? If so, please let me know.

6) Combinatorics Techniques - I don't know what the best way of splitting this out is, other than just listing all the numerous approaches that there are.

7) Incidence Matrices - Are people interested in this? Else I will KIV this to after we have Matrices

Note: To keep the discussion on topic, I will be removing irrelevant comments.

Note by Calvin Lin
3 years, 8 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

1)Is there a preference to split apart "Probability and Statistics" and "Combinatorics"?

Staff - 3 years, 8 months ago

I would surely not like this. For me these two should be thought of as two sides of the same coin.

- 3 years, 8 months ago

2) Probability and Random Variables- Are there any other chapters that you want to see here? I kept this to mostly high school / college material. Are there any enrichment topics that you would be interested in writing wikis for?

Conditional Probability - Bayes' Theorem, Conditional Probability Distribution, Selection Bias, Monty Hall Problem
Expectation - Definition, Properties of Expected Value, Problem Solving, Linearity of Expectation, Independent RV, Conditional Linearity of Expectation
Variance - Definition, Properties of Variance, Standard Deviation, Covariance, Properties of Covariance, Problem Solving
Geometric Probability 1-dimensional (length), 2-dimensional (area), 3-dimensional (volume), Problem solving

Random Variables

Discrete Random variables - Definition, Probability distribution / density, Uniform distribution, Joint probability distribution, Independent RV, Dice throws,
Discrete Probability distributions - Uniform Distribution, Bernoulli Distribution, Binomial Distribution, Geometric Distribution, Poisson Distribution, Hypergeometric distribution
Indicator Variables - Definition, Usage / Identification
Continuous Random Variables - Definition, Probability distribution, Expectation, Variance, Uniform Distribution
Continuous Probability Distribution - Uniform Distribution, Normal Distribution, Exponential Distribution, Cauchy Distribution, Chi Squared Distribution, T-distribution, Multivariate normal distribution
Approximation distribution - Which ones do you want?

Staff - 3 years, 8 months ago

I can write about Poisson Distribution if you want @Calvin Lin

- 3 years, 8 months ago

Thanks for volunteering :)

I've just pushed out the map, and would welcome additions to the Wiki pages. Here's a direct link to Poisson Distribution

Staff - 3 years, 7 months ago

What a coincidence, I'm in AP Statistics right now. Based on what I currently know, it looks pretty adequate, but if I find anything extra I'll come back here to add.

- 3 years, 8 months ago

4) Binomial Theorem - This looks quite standard to me. Any comments?

Binomial Coefficients - Definitions, Properties, N Choose K, Positive Integer, General Term, Middle Term, Applications
Generalized Binomial Theorem - Negative Binomial Coefficients, Negative powers, Fractional Binomial Coefficients, Fractional Powers
Multinomial Theorem - Multinomial coefficients, Multinomial Theorem, Applications, Multi-binomial
Combinatorial Identities - Combinatorical interpretation, Bijections, Vandermonde's Identity

Staff - 3 years, 8 months ago

Yes thats nice

- 3 years, 8 months ago

3) Applications of Counting - I decided to sort it according to types of problems. I'm quite certain that there are several classifications that I missed out, so please enlighten me. Also, if you have suggestions for a different organization approach, I'm all ears.

Integer equations - Stars and bars, Non-negative integer solutions, Basic transformations, PIE
Distribution into bins - Identical objects into identical bins (partitions of an integer), Distinct objects into (many) identical bins (compositions of an integer). Distinct objects into finitely many identical bins (Multinomial Theorem) Identical Objects into distinct bins. No restriction (k^n), no empty bins (PIE), At most 1 object (k!/(k-n)!), Order of objects matter ((n+k-1)!/(k-1)!)
Rectangular grid walks - No restriction: nCk, With restriction (street/vertex blocked off), With restriction (no higher than y=x, have to take X steps): Catalan numbers Could be built out more?
What else??

Staff - 3 years, 8 months ago

6) Combinatorics Techniques - I don't know what the best way of splitting this out is, other than just listing all the numerous approaches that there are.

Pigeonhole Principle - Definitions, Problem solving, Dilworth's Theorem, Ramsey Theory
Double Counting - Handshaking lemma, Applications Extremal Principle
Coloring - Parity (combinatorial), Orientation, Standard colorings, Brouwer's Fixed point
System of Distinct Representatives - Theorem, Hall Marriage Theorem, Equivalent Statements Games - Definition, Examples, Finding Winning positions, Sprague Grundy Theorem, Nim

Staff - 3 years, 8 months ago

5) Recurrence Relations - Is there interest in expanding beyond linear recurrence relations? If so, please let me know.

Fibonacci Numbers - Definition, Properties, Applications
Linear Recurrence Relations - Sequences and Series, Linear Recurrence Relations, Linear Recurrence Relations with repeated roots, Advanced Linear (2 terms with constants, ie an = a{n-1} + a_{n-2} + 5), Advanced Linear 3 (reducible to 1 or 2 terms)
Generating Functions - What do you want to see here?

Staff - 3 years, 8 months ago

7) Incidence Matrices - Are people interested in this? Else I will KIV this to after we have Matrices

Staff - 3 years, 8 months ago

What about $$multinomial. theorem$$ @Calvin Lin sir?

- 3 years, 7 months ago

Staff - 3 years, 8 months ago

We can have Odds For and Odds Against concept in our wiki.

- 3 years, 7 months ago

We can have De Morgan's Laws under the Sets heading.

- 3 years, 8 months ago

Thanks. I added it as Composition of Operations, which would include De Morgan's Laws.

Staff - 3 years, 7 months ago

hi calvin, where can i find maths olympiad question , tips and notes?

- 3 years, 8 months ago

Most of the Level 3-5 problems would constitute math olympiad questions.

We are working on building out more substantial notes / wiki writeups, with this "expanding the wiki" being the first step. You can take a look at my sets of "Olympiad Algebra/Combinatorics/NT/etc", which consists of notes that I wrote up in the past, and will be merging into the wiki section.

Staff - 3 years, 7 months ago

No martingale theory???

- 3 years, 7 months ago

If you are interested in writing such an article, you can use the Add Wiki functionality.

I would like to get to Martingale Theory eventually. I'm building the maps from the ground up, and am adding the next few layers each time. Martingale Theory will require a firm understanding of probability, statistics and analysis in order to fully comprehend it. That will take a while to build out.

Staff - 3 years, 7 months ago

Good

- 3 years, 8 months ago

Map looks cool to me! :)

- 3 years, 8 months ago