Articles of combinatorics

How Many Symmetric Relations on a Finite Set?

How many symmetric relations are there for an $n$-element set? Thank you.

Circular permutations with indistinguishable objects

Given n distinct objects, there are $n!$ permutations of the objects and $n!/n$ “circular permutations” of the objects (orientation of the circle matters, but there is no starting point, so $1234$ and $2341$ are the same, but $4321$ is different). Given $n$ objects of $k$ types (where the objects within each type are indistinguishable), $r_i$ […]

Proving identity $ \binom{n}{k} = (-1)^k \binom{k-n-1}{k} $. How to interpret factorials and binomial coefficients with negative integers.

I at a loss on how to prove $$ \binom{n}{k} = (-1)^k \binom{k-n-1}{k} \tag{1} $$. I want to prove this because it appears to be a fundamental result, that is applied liberally in combinatorics problems such as Proving $\sum\limits_{m=0}^M \binom{m+k}{k} = \binom{k+M+1}{k+1}$, especially in this answer. In this sketch of a pr oof, I start […]

Tiling a $3 \times 2n$ rectangle with dominoes

I’m looking to find out if there’s any easy way to calculate the number of ways to tile a $3 \times 2n$ rectangle with dominoes. I was able to do it with the two codependent recurrences f(0) = g(0) = 1 f(n) = f(n-1) + 2g(n-1) g(n) = f(n) + g(n-1) where $f(n)$ is the […]

Very elementary number theory and combinatorics books.

I know the basics of logic, sets, relations and the like, so studying intros to abstract algebra and real analysis is not that hard. That said, I have a deficiency when it comes to elementary number theory and combinatorics topics. Things like divisibility, modular arithmetic, congruences, prime numbers and such like regularly pop up as […]

Number of possible permutations of n1 1's, n2 2's, n3 3's, n4 4's such that no two adjacent elements are same?

Given $n_1 $ number of $1 $’s, $n_2 $ number of $2 $’s, $n_3 $ number of $3 $’s, $n_4 $ number of $4 $’s. form a sequence using all these numbers such that two adjacent numbers should not be same. I have tries lot of things but nothing worked. can somebody tell me how […]

Covering with most possible equal size subsets having pairwise singleton intersections

Assume I have a non-empty finite set $S$ with $x=|S|$. I want to divide the set $S$ into subsets $S_1, S_2, .., S_n$ (Edit: Yes, $S = \cup S_i$, and I’m embarrassed that I forgot to include that) such that: $ |S_i| = y, \forall 1 \le i \le n$ (The cardinality of each subset […]

Combinatorial Identity $(n-r) \binom{n+r-1}{r} \binom{n}{r} = n \binom{n+r-1}{2r} \binom{2r}{r}$

Show that $(n-r) \binom{n+r-1}{r} \binom{n}{r} = n \binom{n+r-1}{2r} \binom{2r}{r}$. In the LHS $\binom{n+r-1}{r}$ counts the number of ways of selecting $r$ objects from a set of size $n$ where order is not significant and repetitions are allowed. So you have $n$ people you form $r$ teams and select $r$ captains and select $(n-r)$ players. The […]

Show that if $G$ is simple a graph with $n$ vertices and 􏰈the number of edges $m>\binom{n-1}{2}$, then $G$ is connected.

I’m trying to pick up a little graph theory out of Bondy and Murty’s Graph Theory as suggested here. Problem 1.1.12 has given me a little hitch. Let $G$ be a simple graph of order $n$ and size $m$. (So there are $n$ vertices and $m$ edges). If $m>\binom{n-1}{2}$, then $G$ is connected. I’m following […]

Number of solutions to $a_1 + a_2 + \dots + a_k = n$ where $n \gt 0$ and $0 \lt a_1 \leq a_2 \leq \dots \leq a_k$ are integers.

I know how to find the number of solutions to the equation: $$a_1 + a_2 + \dots + a_k = n$$ where $n$ is a given positive integer and $a_1$, $a_2$, $\dots$, $a_n$ are positive integers. The number of solutions to this equation is: $$\binom{n – 1}{k – 1}$$ This can be imagined as $n$ […]