On alternating anagrams (Q1969780): Difference between revisions

The authors show various congruences on integer sequences counting the numbers of anagrams and irreducible anagrams over \(n\) letters. An anagram is a sequence \(w = x_1 y_1 \dots x_n y_n\) over \(\{1, \ldots, n\}\) where each letter appears exactly twice, satisfying \(x_i \geq i\) and \(y_i \leq i\). Anagrams were previously investigated in [\textit{G. Kreweras} and \textit{J. Barraud}, Eur. J. Comb. 18, No. 8, 887-891 (1997; Zbl 0882.05007)]. Anagrams on \(n\) letters can be obtained from anagrams on fewer letters either by concatenation, or by shuffling letters of two anagrams according to previously chosen positions (with an obvious shift of letters in both cases). The paper looks at the sets of anagrams that are indecomposable with respect to those composition products. Recurrences are given to compute the cardinality of those sets (ranked according to \(n\)). The main results of the paper state regularity results on those sequences of integers. The sequence \(a(n)\) of anagrams over \(n\) letters is shown to be alternatively congruent to 2 or 7 \(\pmod {36}\). The sequence \(b(n)\) of anagrams that are indecomposable with respect to concatenation is shown to be periodically congruent to the sequence \(1 1 4 1 1 4 \dots\). A similar result is given for the sequence \(c(n)\) of indecomposable anagrams with respect to the ``shuffle'' product.