Articles of combinatorics

Finding binomial coefficients of product of two binomials

Suppose the expression is given like this: $(1+x) ^{10} (1+x)^{20}$. How can I find out the coefficient of $x^m$ in the above expression, given that $0≤m≤20$.

Generalized birthday problem (or continuous capture recapture?)

Let’s say I don’t know how many days there are in a year (N) and want to figure this out by asking people for their birthday. I ask D random people for their birthday and find there are E duplicate birthdays. How can I estimate N? For example, say I draw: 24, 49, 52, 28, […]

homework combinatorics carousel

I was asked this question in my homework: How many different combinations are there to paint a carousel with $n$ seats, in $r$ different colors, such that any combination that you can get via rotating is considered the same combination? Example: $red -> green -> blue$ is the same arrangement as $blue -> red -> […]

Number of distinct numbers picked after $k$ rounds of picking numbers with repetition from $$

If we pick a random number from $[1, n]$ with repetition $k$ times. What is the probability distribution of number of distinct numbers picked for a given $k$? The number of distinct numbers picked is $\in [1, min(k, n)]$.

Inclusion–exclusion principle

Find the number of soultion to this equation: $$x_1+x_2+x_3+x_4+x_5+x_6= 20$$ $$1 <= x_1, x_2, \ldots, x_6 \leq 4 $$ I know that at the start we need to define: $y_1=x_1-1$ $y_2=x_2-1$ $y_3=x_3-1$ $y_4=x_4-1$ $y_5=x_5-1$ $y_6=x_6-1$ So we end up with this: $$y_1+y_2+y_3+y_4+y_5+y_5=14$$ and now I need to use the “Inclusion–exclusion principle” but how?

Determining the position of a binary value with $k$ one bits and $n-k$ zeros in an enumeration of $C_k^n$ bit strings

I first enumerate a list of all possible binary strings for a length $n$ (e.g., [“00”, “01”, “10”, “11”] for $n=4$). This leads to a list of $2^n$ binary strings. Within that list of $2^n$ elements, I’m principally interested in the $C_k^n$ combinations of strings, for example all binary strings with a single bit set […]

Prove that $\binom{n+1}k = \binom nk + \binom n {k-1}$

This question already has an answer here: Proving Pascal's Rule : ${{n} \choose {r}}={{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$ 11 answers

Does a matrix represent a bijection

We have a square binary matrix that represents a connection from rows to columns. Is there a way to tell if a bijection exists (other than checking for all possible bijections and iterating through them)? EXAMPLE: 1 0 0 0 0 1 0 0 0 0 1 1 0 0 1 1 ANSWER: Yes, here […]

Prove that $C(r, r) + C(r+1, r) +\dotsb+C(n, r) = C(n+1, r+1)$ using combinatoric arguments.

Prove that $C(r, r) + C(r+1, r) +\dotsb+C(n, r) = C(n+1, r+1)$ using combinatoric arguments. I know we can use an analogy of picking people to form a committee, but I can’t see how to prove it.

The marriage problem with the constraint that a particular boy has to find a wife.

Here I’m considering the version of the marriage problem in which there can be more boys than girls. Suppose there are two sets, one of boys and one of girls, the two satisfying Hall’s condition for each girl being able to find a husband. Take a particular boy X liked by at least one girl. […]