Articles of combinatorics

Arrangement of $100$ points inside $13\times18$ rectangle

Prove that you can’t arrange 100 points inside a $13\times18$ rectangle so that the distance between any two points is at least 2. I tried many ways to divide the rectangle, but I can’t get the parts to be small enough, and also less than 100.

A closed form for $T_N = 1 + \sum\limits_{k=0}^{N-2}{(N-1-k)T_k}$?

I’ve narrowed down a problem I am working on to the following recurrence: $$\begin{align*} T_0 &= T_1 = 1\\ T_N &= 1 + \sum_{k=0}^{N-2}{(N-1-k)T_k} \end{align*}$$ I’m stuck on how to close it up, or at least make it linear or $O(n\log n)$. Any clues as to what technique I can use to make the sum […]

No of n-digit numbers with no adjacent 1s.

Suppose there are {1,2,3} in a set. How many n digit numbers can you form such that there are no adjacent 1s. I tried randomly and tried to induce. I do not know how far I am correct. For n=2, it is $2^3$, for n=3, it is $2^4$ and … Well, making induction by applying […]

There exists a vector $c\in C$ with $c\cdot b=1$

Let $n$ be a positive integer, and $A$ be the set of all non-zero vectors of the form $(e_1,e_2,\dots,e_n)$, where $ e_i\in\{0,1\}$. So $|A|=2^n-1$. Let $B$ be a proper subset of $A$. Does there always exists a subset $C\subseteq A$ of size at most $n-1$ such that for any vector in $b\in B$, there exists […]

Schedule 8 teams for 6 events. Each team plays each event twice.

I have a seemingly simple question. I’m holding a Beer Olympics at my house tomorrow. There are 8 teams competing in 6 different events (Beer Pong, Beerball, Can Jam, Corn Hole, Beersbee, and Flip Cup). Each event is seeing two teams compete. Is there a way to arrange the schedule so that each team plays […]

Help with a Binomial Coefficient Identity

The following (conjectured) identity has come up in a research problem from representation theory that I am working on: $$\binom{i}{n-1} =\frac{(n+k+i)!}{(n-1)!(k+i)!} \sum_{j=0}^{n-1} \frac{(-1)^j }{(n+k+i-j)}\binom{n-1}{j} \binom{2n+k-j-2}{n-1}$$ where $k, i, n$ are positive integers and I interpret $\binom{i}{n-1}=i*(i-1)\cdots (i-n+1)/(n-1)!$ even if $i<n-1$. (That is, $\binom{i}{n-1}=0$ if $i<n-1$.) I’ve verified the identity holds for small values of $n$, […]

Solutions to Binary Equations

Let $A \in \mathrm{Mat}(m,n,\{0,1\})$ (i.e. $m \times n$ matrices with entries in $\{0,1\}$ ) and $x,y\in \{0,1\}^n$. We will denote the $i$-th row of $A$ as $\mathrm{row}_i(A)\in \{0,1\}^n$. Define, $$ z_i := \begin{cases} 1~: & (x-y)\cdot \mathrm{row}_i(A) = \sum_{j=1}^n x_j\\ 0~: & \text{otherwise}\\ \end{cases} $$ where $x_j$ is the $j$-th component of $x$ and $\cdot$ […]

Minimum set of US coins to count each prime number less than 100

Say I wanted to be able to carry enough coins in my pocket such that at any time, I could count out exact change totaling any of the prime numbers less than 100. How would I determine the minimum set of coins I would need to carry? I don’t care about being able to count […]

Is there some way to simplify $\sum_{i=1}^n \sum_{j\neq i}(\frac{j-1}{2})(\frac{i-1}{2}) $ To obtain a closed form.

Is there some way to simplify $\sum_{i=1}^n \sum_{j\neq i}(\frac{j-1}{2})(\frac{i-1}{2}) $? Does it have a closed form? It’s the last piece of a puzzle I need to solve a similar question Differentiate $P_{x_n}(z) = \prod_{i=1}^n\frac{1+z+z^2+…+z^{i-1}}{i}$ twice to calculate the variance of involutions. Taking the example $\sum_{i=1}^4 \sum_{j\neq i}(\frac{j-1}{2})(\frac{i-1}{2}) = (\frac{2-1}{2} + \frac{3-1}{2} + \frac{4-1}{2})(\frac{1-1}{2}) + (\frac{1-1}{2} […]

Are there further transformation principles similar to the Inclusion-Exclusion Principle (IEP)?

This question is motivated by the elaboration of the question Combinatorial Proof of Inclusion-Exclusion Principle (IEP). Let’s consider the following two aspects: 1.) IEP transforms at least information to exact information Applying the Inclusion-Exclusion Principle to $n$ sets $A_1,\dots,A_n$ gives: \begin{align*} \left|\bigcup_{j=1}^{n}A_j\right|=\sum_{j=1}^{n}\left|A_j\right| -\sum_{1\leq i \leq j \leq n}\left|A_i\cap A_j\right|\pm\cdots+(-1)^{n-1}\left|\bigcap_{j=1}^{n}A_j\right|\tag{1} \end{align*} We observe that the LHS […]