Articles of combinatorics

How to find this limit with following constraints?

Question: If a,b are 2 positive , co-prime integers such that $$\lim _{n \rightarrow \infty}(\frac{^{3n}C_n}{^{2n}C_n})^\frac{1}{n}=\frac{a}{b}$$Then a+b?? I tried to break down the limit to: $$\frac{[(3n)(3n-1)\dot{}\dot{}\dot{})^\frac{1}{n}][n(n-1)(n-2)\dot{}\dot{}\dot{})^\frac{1}{n}]}{[2n(2n-1)(2n-2)\dot{}\dot{}\dot{}]^\frac{2}{n}}$$ but I’m lost ahead of it. Answer given in my text books is 43. Please guide me

Ramsey lower bounds

I’m doing some self study on Ramsey graph theory. One of the first theorems concerning lower bounds shows that if $${n \choose k} \cdot \frac {1}{2^{( \frac {k}{2}-1)}} <1$$ then $N(k,k)> n$ In the derivation of a later result, the claim is made that due to stirlings formula, $${n \choose k} \cdot \frac {1}{2^{( \frac […]

A) Find a recurrence relation for the number of n-digit binary sequences with no pair of consecutive 1s.

A) Find a recurrence relation for the number of n-digit binary sequences with no pair of consecutive 1s. (A binary sequence only uses the numbers 0 and 1 for those who don’t know) B) Repeat for n-digit ternary sequences. (only uses numbers 0, 1, and 2) C) Repeat for n-digit ternary sequences with no consecutive […]

Counting certain paths in a complete graph

Let $K_n$ be the complete graph with $n$ vertices, where the vertices are labelled $1,2,3,\dots,n$. How many paths are there between $v_1$ and $v_n$ that the labels on the path are strictly increasing? I know that I need to first choose the possible vertices in the path, then consider the possible order of those vertices.

selecting 5 doughnuts counting problem

(a) For breakfast, you have a choice of 4 kinds of doughnuts: glazed, chocolate, sugar and plain. In how many different ways can you choose 5 of these doughnuts? (b) What is the answer in the general case that there are k kinds of dough- nuts and you want to select n doughnuts? i think […]

Simple problem on restricted partition

When finding number of ways to partition n distinct chocolates among m children such that each child has at most $$\left\{\begin{matrix} \left \lfloor \frac{n}{m} \right \rfloor & \text{if} \ \ n\ \ \left (mod \ \ m \right )\equiv 0 \\ \\ \left \lceil \frac{n}{m} \right \rceil & \text{if} \ \ n\ \ \left (mod […]

Prove that a graph is a maximal planar graph if and only if $e = 3v − 6$

Definition: A planar graph with no multi-edges $G$ is called a maximal planar graph if the graph formed by addition of any edge (not already in the $G$) is not planar or the graph is $K_3 $ or $K_4$ (in these cases we can’t add any more edges!) I am asked to prove that a […]

Number of ways to distribute five red balls and five blues balls into 3 distinct boxes with no empty boxes allowed

Find the number of distributions of five red balls and five blues balls into 3 distinct boxes with no empty boxes allowed so I know if I have just 5 identical balls and 3 distinct boxes, the answer would be $\binom{7}{2}$ but because i have another set of 5 balls, I’m unsure how to proceed […]

Pigeonhole principle exercises

I have an exam in combinatorics on Friday and the pigeonhole principle is a part of the material. Can someone give me a reference to a book with the hardest(!) questions on this material? Thank you very much, it can help me a lot!

Counting permutations, with additional restrictions

There are 10 slots and some marbles: 5 red, 3 blue, 2 green, how many ways can you fit those marbles into those slots? Those marbles fit in 10!/(5! 3! 2!) ways Now we have 10 slots but the slots have a restriction: slots #1 thru #4 can fit red, blue, or green marbles. But […]