Articles of combinatorics

How prove this $2^{2012}-\binom{2012}{1006}<m<2^{2012}$

let $A=\{1,2,3,\cdots,2013\}$,and $A_{1},A_{2},A_{3},\cdots,A_{m}\subset A,A_{i}\neq A_{j},1\le i\le m,1\le j\le n$ and such that:For any $i,j\in \{1,2,3,\cdots,m\},i\neq j$,then $$|A_{i}\bigcap A_{j}|\neq 1$$ prove that $$2^{2012}-\binom{2012}{1006}<m_{\max}<2^{2012}$$ I think this is interesting problem, and This is my frend ask me, I think This problem may be use http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle

What's the shape of this “addsTo” function …?

Note that in this combinatronics question, How many lists of 100 numbers (1 to 10 only) add to 700? I was asking: For an array of 100 numbers, each 1 to 10 inclusive, and the total is T – how many such arrays exist? In fact due to the ASTOUNDING answers there, we now know […]

Graph with girth 5 and exactly $k^2+1$ vertices

I’m doing a homework and I’ve already done the proof that a graph with girth 5 and degree of atleast $k$ has at least $k^2+1$ vertices. Also I’ve been able to found a graph for $k=2$ and $k=3$ but searching over the web I’ve found it’s impossible to found one with $k=4$. How can I […]

Divisors of $2^kp^r$

Let $p$ be an odd prime number. What is the necessary and sufficient condition (in terms of $p$ and $k,r$) such that we can partition the divisors of $2^kp^r$ into two set with equal sum. You may want to LOOK HERE where the special case $2^kp$ is dealed.

Counting the number of partitions having blocks of cardinality 2 and non-distinct elements

Say I have a set of integers $\{1,2,\cdots,n\}$, then there exists $B_n$ partitions of this set where $B_n$ is a Bell number. For instance, there are $B_3$=5 partitions of the set $\{1,2,3\}$: $$ \begin{align} \Pi[\{1,2,3\}] &= \left[\{\{1\},\{2\},\{3\}\}+\{\{1,2\},\{3\}\}\right.\\ &\qquad\left. +\{\{1\},\{2,3\}\}+\{\{1,3\},\{2\}\}+\{\{1,2,3\}\}\right]. \end{align} $$ For a set having an even number of elements, what is the number of […]

Frog on a 3 by 3 matrix

Imagine a frog (f) on a 3 by 3 matrix, with the frog being able to jump to neighboring places from where it sits. So for example if the frog is at $s_{0,1}$, it can subsequently jump to $s_{0,0}, s_{0,2},s_{1,0},s_{1,1}$ and $s_{1,2}$. $$ \left( \begin{array}{ccc} s_{0,0} & f & s_{0,2} \\ s_{1,0} & s_{1,1} & […]

what is the usage of combination $C(r,k)$ where $r$ extends to real number?

Combination is defined as $C(n,k) = \dfrac{n!}{k!(n-k)!}$, where $n$ and $k$ are non-negative integers. Now, the definition can be extended to $C(r,k)$, where $r$ is real number and $k$ is an integer: $$ C(r, k) = \cases{ \frac{r(r-1)\cdots(r-k+1)}{k!} & $k \ge 0$ \\ 1 & $k = 0$ \\ 0 & $k < 0 $} […]

Is there only one counter example in $K_5$ for $R(3,3)$?

Title says it all. And the one that I know is below. (image from wikipedia) My question is: Is there only one counter example in $K_5$ for $R(3,3)$ where $K_5$ is a complete graph of 5 points and $R(s,t)$ is Ramsey number.

Problem with counting method – full house

I’ve never been particularly good at counting, and I was pleasantly surprised to learn today that many typical probability-counting problems can be solved using the equation: $$P(A\cap B) = P(A)P(B|A)$$ and it’s generalisations, rather than by more traditional counting methods. However, my first attempt to apply this equation to a more difficult counting problem has […]

The primes $s$ of the form $6m+1$ and the greatest common divisor of $2s(s-1)$

I had trouble coming up with a good title. Let $\psi(s) = 2s(s-1)$. I write $(\psi(s),\psi(s+2))$ to be the greatest common divisor of $\psi(s)$ and $\psi(s+2)$. Then if $s$ is prime and $(\psi(s),\psi(s+2))=12$ we have that $s=6m+1$ for some positive integer $m$. Conversely if $s=6m+1$ is prime then $(\psi(s),\psi(s+2))=12$. I would like to solve this […]