Articles of combinatorics

Probability that no two consecutive heads occur?

A fair coin is tossed $10$ times. What is the probability that no two consecutive tosses are heads? Possibilities are (dont mind the number of terms): $H TTTTTTH$, $HTHTHTHTHTHTHT$. But except for those, let $y(n)$ be the number of sequences that start with $T$ $T _$, there are two options, $T$ and $H$ so, $y(n) […]

Show that the $k$th forward difference of $x^n$ is divisible by $k!$

Define the forward difference operator $$\Delta f(x) = f(x+1) – f(x)$$ I believe that if $f(x)$ is a polynomial with integer coefficients, $\Delta^k f(x)$ is divisible by k!. By linearity it suffices to consider a single monomial $f(x) = x^n$. I’ve checked this for small values of $n$ and $k$, and believe that a simple […]

Maximal Hamming distance

Here is a combinatorial problem: let $\Sigma=\{\alpha_1,\ldots,\alpha_n\}$ be an alphabet and we consider any words over $\Sigma$ of length $n$. We also define over the set of such words the Hamming distance: $$d(\omega,\omega’)=\#\{i\in \{1,\ldots,n\} \vert a_i\neq b_i\}$$ where $\omega=a_1\ldots a_{n}$ and $\omega’=b_1\ldots b_n$ are two words. The questions are the following: Let $\omega_0$ be the […]

What tactics could help with this probability questions

I’m not too sure if this question is solvable (I sort of just thought of it yesterday) but when I brute force numerical answers on my computer they seem to show a pattern, so I believe it to be solvable. The question: I have $N$ people in a stadium, and there are $5$ different coloured […]

Sum identity using Stirling numbers of the second kind

Experimenting with series representations of $e^{x e^x}$ I came across the two seemingly different power series $$e^{x e^x} = \sum_{n=0}^{\infty} x^n \sum_{k=0}^{n} \frac{(n-k)^k}{(n-k)! \cdot k!}$$ and $$e^{x e^x} = \sum_{n=0}^{\infty} x^n \sum_{k=0}^{n} \frac{1}{(n-k)!} \sum_{i=0}^{k} \frac{1}{(k-i)!} {k-i \brace i}\,.$$ They should be and are in fact identical. By equating the coefficients it is obvious that $$\sum_{k=0}^{n} […]

Given any nine integers show that it is possible to choose, from among them, four integers a, b, c, d such that a + b − c − d is divisible by 20.

Given any nine integers show that it is possible to choose, from among them, four integers a, b, c, d such that a + b − c − d is divisible by 20. Further show that such a selection is not possible if we start with eight integers instead of nine. i cant prove it […]

In how many ways can three numbers be selected from the numbers $1,2,\dots,300$ such that their sum is divisible by $3$?

Can someone check which logic is finally correct?: In how many ways can three numbers be selected from the numbers $1,2,\dots,300$ such that their sum is divisible by $3$? I found different answers about the exact question but everyone states something different. Dividing $\{1, \dots , 300\}$ into three groups $(A,B,C)$ where each one of […]

Prove the following relation:

I must prove the relation $$\sum_{k=0}^{n+1}\binom{n+k+1}{k}\frac1{2^k}=2\sum_{k=0}^n\binom{n+k}{k}\frac1{2^k}.$$ I got this far before I got stuck: $\begin{eqnarray*} \sum_{k=0}^{n+1}\binom{n+k+1}{k}\frac1{2^k} & = & \sum_{k=0}^{n+1}\left\{\binom{n+k}{k}+\binom{n+k}{k-1}\right\}\frac1{2^k}\\ & = & \sum_{k=0}^n\binom{n+k}{k}\frac1{2^k}+\sum_{k=0}^n\binom{n+k}{k-1}\frac1{2^k}+\binom{2n+1}{n}\frac1{2^k}. \end{eqnarray*}$ If I can combine the second and third terms and get something same as first term, I am done but I could not do that.

Number of combinations such that each pair of combinations has at most x elements in common?

I am doing research on the sense of smell and have a combinatorics problem: I have 128 different odors (n) and I mix them in mixtures of 10 (r). There are 2.26846154e+14 different mixtures. What I want to know is: What is the size of the group of mixtures such that no mixture in the […]

Count the number of paths from $(0,0)$ to $(2n,n)$ than never go above $y=x$

Count the number of paths from $(0,0)$ to $(2n,n)$ than never go above $y=x$ At first I thought of the problem by expanding the graph to $(0,0)$ to $(2n,2n)$ and messing around with adding and subtracting multiples of the Catalan number formula, but I feel this is far too rudimentary and in doing so I […]