Counting Necklaces Suppose we have a necklace with $n$ beads. Each bead is either red or blue. I'd like to ask how to count the number of necklaces $f(n,m,k)$ satisfying the following requirements:
1) There are exactly $m$ red beads; $(0 \leq m \leq n)$.
2) No two adjacent red beads;
3) The number of blue beads with two adjacent red beads is $k$ exactly.
Note that rotation of necklace is counted differently. For example, "blue blue blue red" is different from "red blue blue blue".
Some test cases: $f(4,2,2)=2: \color{red}{1}0\color{red}{1}0, 0\color{red}{1}0\color{red}{1}$
$f(5,2,1)=5: 0\color{red}{1}011, 10\color{red}{1}01, 110\color{red}{1}0, 0110\color{red}{1}, \color{red}{1}0110$, where $0$ represents a red bead and $1$ represents a blue one. I've colored the blue beads satisfying the third requirement.
Note that $a_n=\sum_{m,k}f(n,m,k)$ are Lucas numbers.
I've also noticed that for fixed $m$ and $k$, the series $f(n,m,k)$ seems to have a generating function which looks like $\frac{a-bx}{(1-x)^c}$ where $a$, $b$ and $c$ are constants related to $m$ and $k$.
 A: The magic formula
$$f(n,m,k)=2{m-1 \choose k-1}{n-2m-1\choose m-k-1}+3{m-1 \choose k}{n-2m \choose m-k}$$
Derivation
Any necklace satisfying the three requirements has $m$ strings of one or more consecutive blue beads bordered by red beads. It must therefore have $m-k$ strings of two or more consecutive blue beads.
Consider those necklaces which do not contain three consecutive blue beads (we will call them minimal necklaces). Clearly $n=3m-k$ for a minimal necklace.
We will consider two cases:


*

*The first bead is red and the last two beads are red then blue OR
    the last bead is red and the first two beads are blue then red.

*Either the first and last bead OR the first two beads OR the last
    two beads are both blue.


There are $2{m-1 \choose k-1}$ minimal necklaces of type 1 and $3{m-1 \choose k}$ minimal necklaces of type 1. 
Finally, we can use the second theorem of stars and bars to calculate the number of ways to add an extra $n-3m+k$ blue balls to a minimal necklace by appending them to strings of two or more consecutive blue balls. 
For type 1 necklaces there are $n-2m-1 \choose m-k-1$ ways to do this. 
For type 2 necklaces, blue balls can be added at either the start or the end of the necklace so there are $n-2m \choose m-k$ ways to do this.
The Lucas number connection
We will call a necklace good if it does not have adjacent red beads. Since rotations are counted differently, we will assume that each necklace has a special location where beads can be inserted. 
$a_n$ is the number of good n-bead necklaces. I can explain why $a_n=a_{n-1}+a_{n-2}$. This is the recurrence relation for Lucas numbers.
Any good necklace of length $n-1$ can be turned into a good necklace of length $n$ by inserting a blue bead. 
Any good necklace of length $n-2$ which has one red bead adjacent to its special location can be turned into a good necklace of length $n$ by inserting a blue bead and a red bead, and there is a unique order in which these two beads can be inserted. 
Now consider the good necklaces of length $n-2$ which have two blue beads adjacent to their special location. By inserting first a blue bead then a red bead we can create a good necklace of length $n$ which has not already been counted. Note that, if the second bead to be inserted is blue, then we end up adding a blue bead to a length $n-1$ good necklace and creating a necklace that has already been counted.
