Combination of elements in circle

Question

Imagine we have few elements and they make some kind of circle with 1 way connections such as:

1→2→3→1 circle with 3 elements

1→2→3→4→1 circle with 4 elements

We want to choose every member by choosing elements. For example: circle with 4 elements we can choose 1 and 3(1,3) for choosing all members because 1 has connection to 2 and 3 has connection to 4. But also we can choose every member simply by (1,2,3,4) order isn't important. So the question is there are how many ways to choose all elements?

I figure out that for circle with n elements combination of $n$ by $n$ and $n$ by $n-1$ always ensure the situation but for other I couldn't.

Answer 1

Let's use the following notation: Tag a number by 1 if we just pick that number, and use tag 10 if we pick a number and its successor.

For example, in the case $n=4$ and where we pick 1, 2 and 4, and 3 as a successor of 2, the tagging would be 1101 = 1+10+1.

This means we want to compose a string of length $n$ by concatenations of the strings 1 and 10.

Let $k$ denote the number of zeros. Then we have $n-2k$ single ones because each 0 also brings an implicit 1. In order to combine $k$ 10's and $n-2k$ 1's in any order, there are $$\frac{(k+n-2k)!}{k!(n-2k)!} = \binom {n-k}k \tag 1$$ ways, and summing (1) over all possible $k$'s from $0$ to $\lfloor n/2\rfloor$, where $\lfloor \cdot\rfloor$ denotes the integral part, gives: $$p_n=\sum_{k=0}^{\lfloor n/2\rfloor} \binom {n-k}k \tag{2}$$ The integral part encodes the condition that $2k\leqslant n$. What's missing are the cases where we pick the first element via indirection from the last element, i.e. tags of the form 0···1, of which there are $p_{n-2}$ because the inner tags ··· must start with a 1 again. This yields the following formula for all possibilities $a_n$ for $n$:

$$a_n = p_n + p_{n-2},\quad (a_1,a_2) = (1,3) \tag 3$$

Computing $a_n$ for the first few $n$:

$$\begin{array}{r||r|r|r|r|r|r|r} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\\hline a_n & 1 & 3 & 4 & 7 & 11 & 18 & 29 & 47 & 76 \end{array}$$

For example for $n=5$, there are the 11 cases

11111
10111
11011
11101
11110
10101
10110
11010
01111
01011
01101

---

Note

As it appears, the numbers follow the relationship

$$a_{n+1} = a_n + a_{n-1}, \qquad (a_1,a_2) = (1,3)$$

The recurrence relation is the same like for the Fibonacci numbers, but the initial values are different: It's the starting values for the Lucas numbers, where the 1st element of the sequence is omitted. This also means that there is a simple, explicit representation similar to Binet's formula for the Fibonacci numbers:

$$a_n = \varphi^n + (-\varphi)^{-n}$$

where $\varphi = (1+\sqrt5)/2$ is the golden ratio.