Articles of combinatorics

Fibonacci and Lucas series technique

Well, I have the following two problems involving Fibonacci sequences and Lucas numbers. I know that they share the same technique, but I don’t have clear the procedure: $$f_n = f_{n-1} + f_{n-2}: f_0 =0, f_1=1$$ $$l_n=l_{n-1} +l_{n-2}:l_0=2,l_1=1$$ Now, I want to prove that: $$\sum\limits_{k=0}^nf_k= f_{n+2}-1 $$ $$\sum\limits_{k=0}^n l_k^2= l_nl_{n+1} +2$$ My question is, what […]

Can the complete graph $K_9$, be 2-coloured with no blue $K_4$ or red triangles?

I am working on the following problem on 2-coloured complete graphs: $K_9$ is coloured red and blue and contains no red triangle and no blue $K_4$ then every vertex must have red degree 3 and blue degree 5. Is this possible? I am pretty sure the answer is ‘no’ but I am not sure how […]

Combinatorial Proof of Binomial Coefficient Identity, summing over the upper indices

This question already has an answer here: Combinatorial proof of binomial coefficient summation 2 answers

Smallest Graph that is Regular but not Vertex-Transitive?

I’m trying to find the smallest graph that is regular but not vertex-transitive, where by smallest I mean “least number of vertices”, and if two graphs have the same number of vertices, then the smaller is the one with the lower number of edges. I currently have that the smallest such graph is the disjoint […]

Calculate winning outcomes of plurality voting

My problem is similar to this one, but different in some significant ways. As in the above question, I have voting with $n$ voters and $m$ candidates. However, I care about which voter voted for which candidate. As such, there are a total of $m^n$ possible configurations. Also, of these possible configurations, how many did […]

The number of equivalence classes of finite symmetric difference relation

Let $\Sigma$ be an infinite set. Let $A,B \subseteq \Sigma$ be of finite symmetric difference iff they have a finite difference, more formally: $A \sim B$ iff $|A \Delta B| \in \mathbb{N}$ How many equivalence classes does $\sim$ have?

Combinatorial proof of binomial coefficient summation

While doing some Computer Science problems, I found one which I thought could be solvable using combinatorics instead of programming: Given two positive integers $n$ and $k$, in how many ways do $k$ numbers, all of which are between $0$ and $n$ (inclusive), add up to $n$? In the problem, order does matter. For example, […]

Is $\sum_{k=0}^{r}\binom{r}{k}(r-k-1)^{r-k}(k-1)^{k-1}+(r-2)^r=0$ right?

How to prove $$\sum_{k=0}^{r}\binom{r}{k}(r-k-1)^{r-k}(k-1)^{k-1}+(r-2)^r=0$$ I met this function when I tried to give another proof of the known lower bound of Tur\’an functions of complete hypergraphs ( Based on a same construction, instead of using shifting method, I tried to count edges directly ) Here is the question: Define $a_0=-1$ and $a_1=1$. For all $r\geqslant2$, […]

Number of handshakes

32 people were invited at a party and started exchanging handshakes. Because of the confusion, each of them shook hands with each other multiple times: at least twice and up to X times. However, every two people exchanged different number of handshakes from every other two. What is the minimum possible number X, so that […]

Combining symbols with symmetry

So this question has probably been answered already, but I can’t find a good answer through searching google or this site. Basically, if I have n symbols, how many n-length combinations of the symbols can I make, excluding symmetrical duplicates and duplicates made by switching symbols for each other? For instance, with the following sets […]