How to calculate the possible number of password options with add. conditions?

Question

Mathematics

Hello, dear professionals and connoisseurs! I completely broke my head over the task, which at first glance seemed to me not at all difficult, or maybe I just learned it by heart))
Given a known set of characters of n elements in a certain order, for example, let's take the English alphabet - 26 characters: abc ... xy z.
There is a password that consists of these characters. The password matches the following. conditions:
1) The password does not have a fixed length, it can be either 1 character or several tens, but the characters cannot be repeated.
2) The characters in the password go in the same order in which they are located in the set, only in reverse )))))
3) The characters cannot be adjacent in the set.

Using all of the above, the password can be: z, g, zxv, xkca, etc., options like asy, zy, bba, etc. it can not be. That's all that "reached" me))) well, the fact that the maximum password length for a given character set is 13 (zxvtrpnljhfdb), but you need to somehow calculate the number of possible options and create an algorithm for obtaining these options.

I would be glad for any hint, idea or thought))

Answer 1

Standard task for recursion.
Imagine that you already know how to solve this problem for an alphabet of length n-1, n-2, etc. Let F(k) be the number of passwords for an alphabet of length k.
Then for an alphabet of length n, you have options:
1. Do not use the last character in the password - such passwords are obviously F (n-1)
2. Use the last character in the password - then the password cannot have the penultimate character and then you can continue it with everyone password options of n-2 characters. Those. there are F(n-2)
3 such passwords. The password from one last character is one.
Total passwords of n characters F(n) = F(n-1) + F(n-2) + 1.
Recursion base: obviously F(1) = 1, F(2) = 2.

Answer 2

from paragraphs 2-3, form two sets of maximum length
and then go through them with password lengths moving from left to right with overlap on the last character