Articles of combinatorics

Distributing $k$ objects in $n$ containers – Probability distribution for Combinatorial problems

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 […]

Planar graph with a chromatic number of 4 where all vertices have a degree of 4.

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.

geometric problem solved with Pigeon Hole Principle

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.

Number of positive integer walks from 0 to b.

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 […]

recurrence relation concrete way to solve it

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 […]

Questions of the form “let $G$ be a planar graph such that every face is a…$” Prove that…

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 the number of derangements of length $n$ is $D_n = (n-1)(D_{n-1}+D_{n-2}), n>2$

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 […]

Counting distinguishable ways of painting a cube with 4 different colors (each used at least once)

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 […]

Number of equivalence relations

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

Counting the total number of possible passwords

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 […]