Articles of combinatorics

What is so special about Higman's Lemma?

Is there a motivational example of an application of Higman’s Lemma that brings out the true beauty and importance of Higman’s Lemma? What is the thing that made so many people care about it? For an example, I was thinking that given a singleton set $\{1\}$ with the linear order $\preceq$ such that basically $1\preceq1$. […]

Evaluating a limit involving binomial coefficients.

If $N_c=\lfloor \frac{1}{2}n\log n+cn\rfloor$ for some integer $n$ and real constant $c$, then how would one go about showing the following identity where $k$ is a fixed integer: $$\lim_{n\rightarrow \infty} \binom{n}{k}\frac{\binom{\binom{n-k}{2}}{N_c}}{\binom{\binom{n}{2}}{N_c}}=\frac{e^{-2kc}}{k!}.$$ It feels like using Stirling’s approximation would help but I can’t quite figure out how… I ask this question because I am currently trying […]

Inequality involving sums of fractions of products of binomial coefficients

Let $n\in\mathbb{N}$. For $0\le l\le n$ consider \begin{equation} b_l:=4^{-l} \sum_{j=0}^l \frac{\binom{2 l}{2 j} \binom{n}{j}^2}{\binom{2 n}{2 j}}\text{.} \end{equation} Do you know a technique how to prove that \begin{equation} b_l\ge b_n\text{,$\quad 0\le l\le n-1$?} \end{equation} Going through a long list of binomial identities I did not find epiphany. Addition: Plot of $b_l$ for $n=20$.

Zeilbergers algorithm in Maple

I try to prove several hard combinatorial identities. One of them is following \begin{align*} \sum_{s=0}^{\min\{k,n-1\}} \sum_{i=0}^{k-s} (-1)^{i} {2n+k-i-1 \choose k-s-i} {i-n \choose s} {n+i-1 \choose i} {n+k-s-1 \choose k} =\\ =\sum_{j=0}^{[\frac k2]} \sum_{i=0}^{min\{j, n-1\}}{ n-1 \choose i}^2 {{2n+j-i-2} \choose j-i} { n+k-2j-1 \choose n-1} .\text{ ($n,k$ are nonnegative integer)} \end{align*} Using the identity of Le-Jen […]

How many words of length $n$ can we make from $0, 1, 2$ if $2$'s cannot be consecutive?

How many words we can make from $0,1,2$? The restriction is we can’t put the digit $2$ after the digit $2$. My solution: I tried to solve it with Inclusion-Exclusion Principle. Count the number of the words without restriction and then I decreased the options that I don’t want. The number of ways to make […]

Generating function for the number of positive integer solutions to the equation: $4a+2b+c+3d=n$

Let $a_n$ be the number of positive integer solutions to the equation: $4a+2b+c+3d=n$, What’s the generating function for the series $a_n$? I’m pretty much stuck on how to even start.

Complement Probability- Choose A Ball

An urn contains $n$ balls, one of which is special. If $k$ of these balls are withdrawn one at a time, with each selection being equally likely to be any of the balls that remain at the time, what is the probability that the special ball is chosen? Can we say the following? $\# \Omega={n\choose […]

number of derangements

In the normal derangement problem we have to count the number of derangement when each counter has just one correct house,what if some counters have shared houses. A derangement of n numbers is a permutation of those numbers in which none of the numbers appears in its original place. For example, the numbers {1,2,3} can […]

Number of Relatively Prime Factors

Given a number $n$, in how many ways can you choose two factors that are relatively prime to each other (that is, their greatest common divisor is 1)? Also, am I going in the correct direction by saying if $n$ is written as $p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}$, where $p_i$ is a prime and $a_i\geq 1$, then the […]

Proof sought for a sum involving binomials that simplifies to 1/2

A proof of: $$\begin{align*}(1/2)^{2m+1} \sum_{k=0}^{m} \binom{m}{k} \sum_{j=0}^{k} \binom{m+1}{j} = \frac{1}{2} \end{align*} $$ Conjecture based on the following Maple code: Q := (1/2)^(2*m+1) * sum( binomial(m, k) * sum(binomial(m+1, j), j = 0 .. k), k = 0 .. m): simplify([seq(Q, m = 1 .. 20, 1)]); [1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, […]