Articles of combinatorics

Counting functional graphs with no 1 or 2-cycles.

I can easily work out that the number of functional graphs (directed graphs in which all vertices have out-degree one) of size $n$ is $n^n$ and the number of functional graphs without one-cycles is ${(n-1)}^n$. Is there an straight-forward way to work out the number of functional graphs of size $n$ which have no 1-cycles […]

Finding an algebraic proof for $r{n \choose r} = n{n-1 \choose r-1}$

I can’t seem figure this proof out. How are both sides equal. $$r{n \choose r} = n{n-1 \choose r-1}$$

Variance for the number of trials before success in an urn problem without replacement

This question is asked as an extension of: Expectation of number of trials before success in an urn problem without replacement (Note: I am not the author of the original question.) We have $b$ blue balls and $r$ red balls in an urn. Sampling the urn sequentially and without replacement, we remove red balls until […]

Drawing $n-3$ diagonals of a convex $n$-gon

$A_{1}A_{2}\dots A_{n}$ is a convex $n$-gon. How many ways are there to to divide the $n$-gon into $n-2$ triangles that have at least one segment in common with the $n$-gon using $n-3$ non-intersecting diagonals? Because it is a bit hard I nearly can’t find anything special, I want you to give hints and let me […]

Formula for $\sum_{k=1}^n k\binom nk^2$.

I know that $$\binom n1^2+\binom n2^2+\binom n3^2+\binom n4^2+\dots+\binom nn^2=\binom{2n}n.$$ Is there a similar formula $$\binom n1^2+2\binom n2^2+3\binom n3^2+4\binom n4^2+\dots+n\binom nn^2=\cdots?$$ Thanks in advance.

Drawing colored balls

I have a sack with $15$ red balls, $15$ blue balls, $15$ green balls and $15$ yellow balls (balls of the same color are indistingishable). In how many ways can I take $30$ balls from the sack? $\\ $ I tried using $(\binom{4}{30})$, combination with repetition, but that ignores the restriction of having at most […]

Number of $k\times n$ matrices of rank $k$

How can I determine the number of $k\times n$ matrices with entries in $\mathbb F_p$ with rank $k$ (of course $k<n$) The formula if $k=n$ is $(p^n-1)(p^n-p)\dots(p^n-p^{n-1})$, now how can I modify this ? If I pick any $k$ columns of $n$, and apply the formula, and let the $n-k$ columns be arbitrary, then this […]

How do we determine if the set of rational numbers and the set of all english sentences are countable or not?

How do we determine if the set of rational numbers and the set of all english sentences are countable or not? I had proved it for the set of Integers in graduation. Our instructor at that time told us that there is some special way to prove it for these two sets but he did […]

Bose-Einstein counting method

The question I’d like to ask stems from De Mere’s puzzle which is a basic problem in probability. A six-sided die is tossed three times and we are asked to judge which event is more probable : a sum of 11 or a sum of 12? The approach taken in every book I’ve read up […]

Different ways to write a number given digit constraints

Originally I was just going to ask the problem on my practice math contest, which is asking how many ways there are to write a nine-digit number containing each digit 1-9 so that the first digit is twice as big as the second and the last two digits are odd. (e.g. 846527913). I understood that […]