I have some probability notions but now I face a problem merging combinatorial and probability. Suppose one has $k$ objects and $n$ containers with infinite capacity, $k$ and $n$ being natural integers. $k$ can be smaller, equal or greater than $n$. The question is: What is the probability $P(x)$ of distributing the $k$ objects within […]

Is it possible to have a planar graph with a chromatic number of $4$ such that all vertices have degree $4$? Every time I try to make the degree condition to work on a graph, it loses its planarity.

The problem is: Show that among any 5 points in a equilateral triangle of unit side length, there are 2 whose distance is at most 1/2 units apart.

It is well known that the number of walks of length $m=2k+1$ starting at $0$ and ending at $0$ of step size $\pm 1$ and always nonnegative is the number of Dyck paths from $(0,0)$ to $(k,k)$ i.e. the $k^{th}$ Catalan number $C_k$. The following seems like it should be well known but I have […]

I have the following recurrence relation: $$a_n = 2a_{n-1} + 2^n; a_0 = 0$$ I used the characteristic equation method and some method I found online by calculating the $n+1$ th term and subtracting accordingly the equation with $a_{n+1}$ minus the equation with $a_{n}$: $$a_{n+1} = 2a_n + 2^{n+1} \\ a_{n+1} – 2a_n = 2a_n […]

Let $G$ be a planar graph with degrees all at least three. Suppose we can draw $G$ in a plane such that every face is a square. Prove the number of vertices of degree three is greater than the number of vertices with degree at least five. Let $D$ be a planar drawing of a […]

Prove by induction that $$ D_n = (n-1)(D_{n-1}+D_{n-2}), n>2 $$ where $D_n$ is the number of derangements of $n$ objects. I am a little rusty in induction, and here’s what I have done so far. Basis step: This is easy to prove and trivial, it works for $n=3$ and this is the basis step. Induction […]

You have many identical cube-shaped wooden blocks. You have four colors of paint to use, and you paint each face of each block a solid color so that each block has at least one face painted with each of the four colors. Find the number of distinguishable ways you could paint the blocks. (Two blocks […]

How many different equivalence relations can be defined on a set of five elements?

I’m working from Kenneth Rosen’s book “Discrete Mathematics and its applications (7th edition)”. One of the topics is counting, he gives an example of how to count the total number of possible passwords. Question: Each user on a computer system has a password, which is six to eight characters long, where each character is an […]

Intereting Posts

Prove that 3 is a primitive root of $7^k$ for all $k \ge 1$
Proving A Theorem Concerned With Prime Numbers
Closed form for $\sum_{k=1}^{\infty} \zeta(2k)-\zeta(2k+1)$
A golden ratio series from a comic book
What is the coefficient of $x^{2k}$ in the $n$-th iterate, $f^{(n)}(x)$, if $f(x)=1+x^2$?
How to make sense of fractions?
Suggestions for high school?
Help minimizing function
Does the change of variable function have to be injective?
Ring of order $p^2$ is commutative.
What is the expected number of trials until x successes?
Asymptotic expansion of the complete elliptic integral of the first kind
Does regular representation of a finite group contain all irreducible representations?
Equalities and inequalities for quadrilaterals in hyperbolic space
Polynomials, finite fields and cardinality/dimension considerations