You have $N$ buckets and $N$ balls. What is the the expected number of filled buckets such that no $2$ adjacent buckets can be simultaneously filled? "Filled" here means the bucket has exactly $1$ ball. Each ball is placed in a non-adjacent random bucket one after the other.
First assume the buckets are arranged in a line. Next assume the buckets are arranged in a circle (basically the same as the line except the ends are now connected to each other).
I am totally lost on how to solve this problem. I wrote out a recursion, but it is very messy, and I don't think that's the right approach, nor do I know how to solve it and get a closed expression. I also tried finding a solution for a few small $N$'s to see if I could identify a pattern and try induction, but no luck.
Is there some trick that makes this problem simple/simpler?
Here is an example for the case where the buckets are arranged in a line. Consider $n=5$. If the first ball is placed in bucket $1$, then the second ball will either be placed in bucket $3,4,5$ with probability $\frac{1}{3}$. If the second ball is placed in the $3$rd bucket, then the $3$rd ball will be placed in the $5$th bucket.
Now consider the buckets arranged in a circle. So now bucket $1$ and $5$ are adjacent to each other. So the only possible ways to fill the buckets are filling buckets $(1,3)$, $(1,4)$, $(2,4)$, $(2,5)$, $(3,5)$.
I'm going to write out some basic work that I did. Consider the circular case. Let $S_N$ be a random variable denoting the number of filled buckets starting with $N$ empty buckets. The first ball can be placed in any of the $N$ buckets with probability $\frac{1}{N}$.
From the law of total expectation, and using $A_i$ to denote the event that the i-th bucket is chosen for the first ball, we have $$ E[S_N] = \sum_{i=1}^{N} E[S_N | A_i] P(A_i) \\ $$
By symmetry, we know $E[S_N | A_i] = E[S_N | A_j] \ \ \forall i,j$. Thus, $$ E[S_N] = E[S_N | A_1] = \ldots = E[S_N | A_N] \\ $$
Further, after placing the first ball in the i-th bucket, we have $N-3$ choices for the placement of the next ball. Based on this, I was originally (wrongly) thinking that the following is true: $$ E[S_N | A_1] = 1 + E[S_{N-3}] $$
However, this is not correct because I have defined $S_N$ to be the random variable for the number of filled buckets where the original $N$ empty buckets are arranged circularly. When we place the first ball, we are left with $N-3$ buckets, but the $N-3$ buckets are not arranged circularly. They are effectively arranged linearly. So we introduce $L_i$ to be the number of filled buckets when starting out with $i$ empty buckets arranged linearly.
Then we can write $$ E[S_N | A_1] = E[L_{N-3}] \\ E[S_N] = 1 + E[L_{N-3}] $$
Based on this and using this approach, it seems the circular problem is coupled to the linear problem.
Note that I have disregarded the number of balls remaining (or the number of balls available to be placed for a given number of empty buckets) because it is guaranteed that we will run out of available buckets before we run out of balls.
Now consider the linear case. The law of total expectation yields the same equation $$ E[L_N] = \sum_{i=1}^{N} E[L_N | A_i] P(A_i) \\ $$
But now, a symmetry argument for $E[L_N | A_i]$ no longer holds. If the first ball is placed in the i-th bucket, then we have 2 subproblems to recurse on. The valid buckets to the left and right of the i-th bucket. Specifically we have $\max(0, i - 2)$ valid buckets to the left and $\max(0, N- i - 1)$ valid buckets to the right. Valid here means that the next ball is able to be placed in any of the buckets.
So $$ E[L_N | A_i] = 1 + E[L_{\max(0,i - 2)}] + E[L_{\max(0, n - i - 1)}] $$
and $$ E[L_N] = \sum_{i=1}^{N} (1 + E[L_{\max(0,i - 2)}] + E[L_{\max(0, n - i - 1)}]) P(A_i) \\ = 1 + P(A_1)\sum_{i=1}^{N} E[L_{\max(0,i - 2)}] + E[L_{\max(0, n - i - 1)}] $$
We have the following boundary condition: $L_0 = 0$.