How to show that there exists a constant $c>0$ such that $|C|\le c^n?$ Give lattice graph $G(\mathbb{Z}^2)=(V(\mathbb{Z}^2), E(\mathbb{Z}^2))$ and a connected set $C$ with $n$ vertices containing the original point $(0,0)$, how to show that there exists a constant $c>0$ such that
$$|C|\le c^n?$$
Here $|C|$ is the number of such connected sets.
 A: This was first bounded by Murray Eden in the paper A two-dimensional growth process. I will give a simplified version of the proof that gives a bound of $2^{4n} = 16^n$, but just by analyzing it more carefully, Eden gets $\binom{3n-2}{n-1}$, and since then the bound has been improved further. (A highly related quantity is the number of polynominoes of size $n$.)
The argument is that we'll represent all connected $n$-vertex sets containing $(0,0)$ by distinct sequences of $4n$ bits. The algorithm for doing it is this:

*

*Begin with the vertex $(0,0)$ on a stack; mark it as explored.

*Pop the top vertex $v$ off the stack. Write down a $4$-bit sequence $(n,s,e,w)$ where each bit corresponds to one of the four cardinal directions from $v$, and it is $1$ if there is another vertex from $C$ adjacent to $v$ in that direction.

*For each unexplored vertex $w \in C$ adjacent to $v$, going in the same N,S,E,W order, put $w$ on the stack and mark it as explored.

For concreteness, I've used a stack, making this depth-first search, but a queue or really any consistent method would work equally well.
After we've explored all $n$ vertices, we get a $4n$-bit sequence, and we can recover $C$ from the sequence. By the time we get to the $i^{\text{th}}$ $4$-bit block, we know where the $i^{\text{th}}$ vertex we processed is; the $4$-bit block lets us deduce which vertices were added to the stack at that time, and accordingly where they are.
To improve the bound of $2^{4n}$ to something smaller, we argue that:

*

*We can skip many of the bits, because we knew they were there. Each vertex $v$ after the first has a "parent" $u$ that was the first to explore $v$. We can skip the $1$ bit in $v$'s sequence that corresponds to the direction $u$ is from $v$, because we already know $u$ is there. This leaves us with only $3n+1$ bits.

*We can also skip the other three bits on the last vertex, since they'll be $0$, leaving us with $3n-2$.

*We can write down $1$ only if there's an unexplored vertex in a direction, and $0$ otherwise. Now there are only $n-1$ bits that are $1$, so there's $\binom{3n-2}{n-1}$ sequences. These still encode all possible sets $C$.

