On a combinatorial problem

In the process of scientific work, I have accumulated several interesting results, which, from my point of view, are rather weak for publication in a scientific publication, but in themselves are of interest, for example, in the field of sports programming. One of these results, which I will formulate below, in some variation can be offered to an applicant for an interview at a large IT company.

So, I'll start from afar. I studied stationary localized structures in the one-dimensional Gross – Pitaevskii equation, [work example] . Such structures, under certain sufficient conditions on the parameters of the problem, can be encoded with infinite in both directions, symbolic sequences, which we call codes. That is, continuous solutions of a differential equation are classified by discrete codes. The encoding alphabet is usually finite and consists of some odd number of characters, for example, from characters where - natural number. The alphabet has a null character , and all other symbols are divided into pairs connected by some symmetry. For simplicity, we will denote the alphabet encoding where symbols and symmetrical to each other. Number we will call the power of the alphabet .

Since the structures studied by us are localized in space, their codes begin and end with an infinite number of zero symbols, that is, they have the form

Central part of the code , or its carrier, consists of characters, with the extreme characters of the carrier, and , are not null characters. Number we will call the code length . Now, for each code we can write three symmetric codes,

Where and - two codes of symmetry of interest. The task is set as follows: find the number of all codes of length composed of a power alphabet accurate to two symmetries and . That is, if two arbitrary codes are connected by symmetries , or then we consider such codes to be the same. In terms of time trouble, at the interview, you can quickly answer that the number of all codes without symmetries is equal to . Further, from my point of view, the task should be solved with a pencil in hand. At once I will say that my solution may not be optimal (in the sense of the number and simplicity of mathematical operations). User mihaild offered a very elegant solution to this problem through the group of invariant permutations and the Burnside Lemma.

Decision

Denote the set of all codes . Break up into three disjoint subsets

In a subset codes have the following structure

In a subset codes have the following structure

Accordingly, by definition, in subsets and codes are divided into pairs , and in a subset - on four , i.e

Where - the number of different codes in a subset , - power . Consider the case of the odd . For subsets , and write down

For the original set get an estimate

Consider the case of even . For subsets , and write down

For the original set get an estimate

Answer

As a result, as a response, we can write the following system of equations (we replace the notation on , because depends on variables and )

In conclusion, I note that the answer was a bit more complicated than it seemed at the first acquaintance with the task. Such a task is hardly suitable for a blitz survey, but it is also not too difficult, in order not to be offered at an interview in any variation. To check the resulting formula, we give the following values: , , , . Accordingly, we present a table of various codes that occurs in this case. Because then we will write down the codes made up of the simplified alphabet .