# Devise a combinatorial problem in which it is easier to solve via probability theory than by counting methods

We easily find probabilities by counting the number of ways we can meet a condition and dividing it by the number of total possible outcomes. This is using combinatorics to solve probabilities.

Im looking for a scenario, or a type of complicated combinatorial problem, in which the approach at counting the number of ways of meeting a condition is actually easier by multiplying the probability of meeting the condition (determined in other ways) by the total possible number of outcomes.

I realize this may be an absurd question, but its been in the back of my mind for some time. Can anyone imagine up such a problem? This is for the sake of education, so that we may all learn of new problem solving techniques.

-
= I think therefore I think I am? – alancalvitti Feb 10 '13 at 23:04

There is a very nice proof of Hook Length Formula. Its basic idea is to create an algorithm that generates random instances with uniform (discrete) distribution and use $\frac{1}{p}$ for counting. Take a look at

C. Greene, A. Nijenhuis, H. S. Wilf, “A probabilistic proof of a formula for the number of Young tableaux of a given shape”, Adv. in Math. 31 (1979), 104-109,

and

Jean-Christophe Novelli, Igor Pak, Alexander V. Stoyanovskii, “A direct bijective proof of the hook-length formula”.

I hope it is an example of what you asking for ;-)

-

Probability theory has been applied to combinatorics for a long time. There is a rich literature for you to explore.

Here is a brief expository paper. I recommend skipping section 1 and going immediately to section 2, then returning to 1 once the method is clear to you.

A commenter (Quinn Culver) mentioned the Wikipedia article on the probabilistic method, which seems unusually good. I generally don't like to just spam Wikipedia entries as answers, but it contains some nice examples.

For more, see the book published on this topic.

Here is an example problem, from the expository paper: Let $A$ be any set of $n$ residues mod $n^2$. Show that there is a set $B$ of $n$ residues mod $n^2$ such that at least half of the residues mod $n^2$ can be written as $a + b$ with $a \in A$ and $b\in B$.

-
Did you even read my question because your response has nothing to do with it. For some reason I have to reiterate myself, I asked you to devise a combinatorics problem in which it is simpler to approach it from the perspective of probability theory. I dont need your citations or references on the history of probability or how it applies to combinatorics. Please read my questions and answer appropriately or dont waste my time. Its disrespectful to hijack my question so that you can post your own propaganda and irrelevant content. – CogitoErgoCogitoSum Feb 10 '13 at 20:22
@CogitoErgoCogitoSum I'm sorry. Perhaps I am misunderstanding, but you asked for problems in which it was easier to multiply the probability of meeting the condition by the total number of outcomes. This is very much like the expected value computations done in the paper I linked. Further, in your comment, you ask for combinatorics problems that are easier to approach from the perspective of probability. There are many in the paper I linked! The book also contains many such problems. I urge you to look at it. Still, I can delete this if it is not what you want. – Potato Feb 10 '13 at 20:25
@CogitoErgoCogitoSum You could try being more civil. People are spending their time answering questions voluntarily and without any compensation. If you don't like the answer, fine. Downvote or ignore it, but remarks as the one above is not appropriate. – mrf Feb 10 '13 at 20:31
@CogitoErgoCogitoSum I found that this response quite appropriate. Your question seems exactly about the probabilistic method. – Quinn Culver Feb 10 '13 at 20:34
@CogitoErgoCogitoSum: You are overreacting. Either calmly explain why you don't think Potato's post answers your question, or just don't say anything. Verbal abuse is not tolerated here. – Zev Chonoles Feb 10 '13 at 20:34

You can look at this problem:

Combinatorial proof involving factorials

And my solution to this problem using Probability.

http://math.stackexchange.com/a/298534/48639

-