Articles of combinatorics

The sum of a polynomial over a boolean affine subcube

Let $P:\mathbb{Z}_2^n\to\mathbb{Z}_2$ be a polynomial of degree $k$ over the boolean cube. An affine subcube inside $\mathbb{Z}_2^n$ is defined by a basis of $k+1$ linearly independent vectors and an offset in $\mathbb{Z}_2^n$. [See “Testing Low-Degree Polynomials over GF(2)” by Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron – – for more details] […]

Combinatorial Proof -$\ n \choose r $ = $\frac nr$$\ n-1 \choose r-1$

I’m reading about combinatorics, specifically ‘Cohen’s Introduction to Combinatorial Theory’, and am stuck on one of the problems. I’m looking for a combinatorial proof for the following : $\ n \choose r $ = $\frac nr$$\ n-1 \choose r-1$ If anyone can offer me any help, it would be much appreciated. I haven’t been able […]

Square covered with tiles

A square $666\times666$ has been covered using tiles $5\times1$. A single square $1\times 1$ hasn’t been covered. Find in how many places the not covered square can be.

'Randomness' of inverses of $(\mathbb{Z}/p \mathbb{Z})^\times$

Suppose you are given the group $(\mathbb{Z} / p \mathbb{Z})^{\times}$, where $p$ is prime. Let $A_p$ denote the sequence whose $j$th element is the inverse of $[j]$. For instance, if $p = 7$, the sequence $A_7$ is $(1,4,5,2,3,6)$. Suppose you truncate the sequence upto the $\alpha p$th term (where $\alpha$ is a very small constant […]

Formula of a sum

Lets define formula: $f(n)=\sum_{i=0}^n i^2 \binom{n}{i}$ What would be genral formula of that? I first went to discover $f(n)=\sum_{i=0}^n \binom{n}{i}=2^n$ (cardinality of power set), and $f(n)=\sum_{i=0}^n i^2=\frac{2n^3+3n^2+n}{6}$ then multiplied those together, realising that i am way off. Then I tried to deduce general presentation of $f(n)$, finding difference of $f(1),f(2),f(3)\cdots$, differences of differences, etc etc, […]

What is the maximum length of a non-repeating word on $n$ letters?

Let $X$ denote a set and $F_{\mathbf{Mon}}X$ denote the free monoid on $X$. Call a word $w \in F_{\mathbf{Mon}}X$ non-repeating iff for all words $x,y,z \in F_{\mathbf{Mon}}X,$ we have: $$w = xy^2 z \rightarrow y = 1$$ For example, if $X = \{a,b\}$, then the non-repeating words in $F_{\mathbf{Mon}}X$ are: $$\{1,a,b,ab,ba,aba,bab\}$$ It turns out that […]

2011 AIME Problem 12, probability round table

Nine delegates, three each from three different countries, randomly select chairs at a round table that seats nine people. Let the probability that each delegate sits next to at least one delegate from another country be $\frac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Find $m+n$. I have been searching around math stackexchange […]

Permutations and Derangements

Determine the number of permutations of $\{1,2,…,9\}$ in which at least one odd integer is in its natural position. __ __ __ __ __ __ __ __ __ There are nine numbers to permute in the $9$ different position. There are $5$ odd numbers and $4$ even numbers. This is my idea- I’m not sure […]

Extension of the Birthday Problem

How do you find the expected number of people (or the expected number of pairs) among the n that share their birthday within r days of each other? For the regular birthday problem, it’s $n\left(1-(1-1/N)^{n-1}\right)$ expected people or ${n\left(1-(1-1/N)^{n-1}\right) \choose 2}$ pairs (see In this link, is it correct to derive the expected number […]

Minimum number of out-shuffles required to get back to the start in a pack of $2n$ cards?

So I’m stuck on this problem. If you perform a faro out-shuffle (i.e. a perfect “riffle shuffle” where the top and bottom cards stays in place) on a pack of 52 cards ($n=26$), you can get back the original order in 8 shuffles. Call $8$ the order for $n=26$. That’s easily seen if you write […]