Fixed Points in Compositions and Words

M. Archibald, A. Blecher, and A. Knopfmacher The John Knopfmacher Centre for Applicable Analysis and Number Theory University of the Witwatersrand Johannesburg South Africa

                 Margaret.Archibald@wits.ac.za
                   Aubrey.Blecher@wits.ac.za
                 Arnold.Knopfmacher@wits.ac.za

Abstract We study fixed points in compositions (ordered partitions) of integers and words. A fixed point is a point with value i in position i. Using generating functions and probabilistic arguments, we enumerate the compositions and words with no fixed points and p fixed points and also how many fixed points occur on average. We briefly discuss the average maximum (respectively minimum) fixed point and the sum of sizes of fixed points. Moreover we provide asymptotic results for the above parameters.

1 Introduction

Fixed points and derangements in permutations have been widely studied; see, for example, the articles [3, 4, 10, 11]. More recently, Arratia and Tavare, Bóna, and Diaconis et al. [1, 2, 6] studied such fixed points. In addition, Deutsch and Elizalde [5] calculated the largest and smallest fixed points of permutations, and Han and Xin [8] looked at the extremal number of fixed points. In this paper we consider fixed points in compositions of n and in words of length n over the alphabet [k] = {1, 2, 3, …, k}.

1.1 Definitions and examples

1. A composition of the positive integer n is a representation of n as an ordered sum of positive integers n = a_{1} +a_{2} +⋯+a_{m} where each a_{i} is called a part of the composition.

2. A fixed point in any sequence of values is a point with value i in position i.

Example 1. The composition 1211515 has three fixed points, (in positions 1, 2 and 5). This can be seen by comparing the values in the following table.

1 2 3 4 5 6 7
1 2 1 1 5 1 5

In Section 2, we study fixed points in compositions. By using generating functions we are able to give asymptotic results for the number of fixed points as well as the number of compositions with no fixed points and p fixed points for a given p ≥ 1. Then we provide formulae for the average maximum (respectively minimum) fixed point and the sum of sizes of fixed points.

In Section 3 we provide the same results for words of length n over alphabet [k]. In this case we are able to obtain some exact results using probabilistic arguments.

2 Fixed points in compositions

By comparing a composition with m parts with the identity permutation 123 ⋯ m, we count how many fixed points occur over all compositions of n.

2.1 Number of fixed points

Counting small cases with the aid of a computer indicated that the sequence for the total number of fixed points in compositions of n matches sequence \underline{A099036} in the On-Line Encyclopedia of Integer Sequences [9] (hereafter OEIS). This is a sequence for the number of compositions of n that contain 1 as a part. This suggests the following bijection.

Bijection 2. Let A be the set of compositions of n with a particular fixed point distinguished. Let B be the set of compositions of n with at least one part of size one, with the first of these distinguished.

We define a bijection between these sets as follows:

From set A to set B: Let k be the distinguished fixed point in a composition of n. It is a fixed point and thus in position k. Map this to a composition in B by adding one to each of the k − 1 parts which precede the k, and subtracting k − 1 from the k, which will now be the first one (distinguished) to appear in the composition.

The inverse map from set B to set A is just the reverse of the above procedure.

By subtracting the generating function for compositions with no part of size one from the generating function for all compositions, we determine the generating function for the number of compositions that have at least one part of size one. Because of the bijection above, this is the same as the generating function for the total number of fixed points in compositions of n. Note that x tracks the size of the composition. Hence the generating function for the total number of fixed points in all compositions of n is

\frac{1 − x}{1 − 2x} − \frac{1}{1 − \frac{x^{2}}{1−x}} = \frac{x(1 − x)^{2}}{(1 − 2x)(1 − x − x^{2})}

with series expansion

1 + x + 3x^{2} + 6x^{3} + 13x^{4} + 27x^{5} + 56x^{6} + 115x^{7}
+ 235x^{8} + 478x^{9} + 969x^{10} + O(x^{11})

as per the above sequence \underline{A099036} in the On-Line Encyclopedia of Integer Sequences (OEIS). Consequently, the total number of fixed points over all compositions of n is

[x^{n}]\frac{x(1 − x)^{2}}{(1 − 2x)(1 − x − x^{2})}

= \frac{1}{5 · 2^{n+1}} (5 · 4^{n} + (\sqrt{5} − 5) (1 + \sqrt{5})^{n} − (5 + \sqrt{5}) (1 − \sqrt{5})^{n}) ,

and the average per composition of n (divide by 2^{n−1}, the number of compositions of n) is

1 + O (\frac{1 + \sqrt{5}}{4})^{n} .  (1)

2.2 Compositions with no fixed points

The generating function for compositions with k parts having no fixed points is given below. The expression in brackets represents a part in position i which may have any value except i. Hence, if y tracks the number of parts in the composition, the generating function for compositions of n with no fixed points is

∑_{k≥0} y^{k} ∏_{i=1}^{k} (\frac{x}{1 − x} − x^{i})  (2)

with series expansion, when y = 1,

x^{2} + 2x^{3} + 3x^{4} + 6x^{5} + 11x^{6} + 22x^{7} + 42x^{8} + 82x^{9} + 161x^{10} + O(x^{11}).

This is sequence \underline{A238351} in the OEIS.

In order to obtain asymptotic estimates, we put y = 1 and rewrite (2) as

F (x) := ∑_{k≥1} ∏_{i=1}^{k} (\frac{x}{1 − x} − x^{i})

= ∑_{k≥1} (\frac{x}{1 − x})^{k} ∏_{i=1}^{k} (1 − (1 − x)x^{i−1})

= ∑_{k≥1} (\frac{x}{1 − x})^{k} ∏_{i=1}^{∞} (1 − (1 − x)x^{i−1})−

∑_{k≥1} (\frac{x}{1 − x})^{k} ∏_{i=1}^{∞} (1 − (1 − x)x^{i−1})(1 − ∏_{i=k+1}^{∞} \frac{1}{1 − (1 − x)x^{i−1}} )

= ∏_{i=1}^{∞} (1 − (1 − x)x^{i−1})

· (\frac{x}{1 − 2x} − ∑_{k≥1} (\frac{x}{1 − x})^{k}(1 − ∏_{i=k+1}^{∞} \frac{1}{1 − (1 − x)x^{i−1}} )).  (3)

We now show that the last sum is analytic for |x| < \frac{\sqrt{5}−1}{2}:

∏_{i=k+1}^{∞} (\frac{1}{1 − (1 − x)x^{i−1}} ) = exp ( − ∑_{i=k+1}^{∞} log (1 − (1 − x)x^{i−1}))

= exp ( ∑_{i=k+1}^{∞} ((1 − x)x^{i−1} + O(x^{2i})))

= exp ((1 − x)\frac{x^{k}}{1 − x} + O(x^{2k}))

= exp (x^{k} + O(x^{2k}))

= 1 + x^{k} + O(x^{2k}).  (4)

This implies that

∑_{k≥1} (\frac{x}{1 − x})^{k}(1 − ∏_{i=k+1}^{∞} \frac{1}{1 − (1 − x)x^{i−1}} )) = ∑_{k≥1} (\frac{x}{1 − x})^{k}( − x^{k} + O(x^{2k})),

which converges if |\frac{x^{2}}{1−x} | < 1, i.e., |x| < \frac{\sqrt{5}−1}{2}. Thus the dominant singularity in (3) is in the first term of the square bracket, namely \frac{x}{1−2x}, which is analytic for |x| < \frac{1}{2}.

By expanding F (x) from (3) about the point x = \frac{1}{2}, we obtain

F (x) ∼ \frac{x}{1 − 2x} ∏_{i=1}^{∞} (1 − (1 − \frac{1}{2})(\frac{1}{2})^{i−1})

= \frac{x}{1 − 2x} ∏_{i=1}^{∞} (1 − \frac{1}{2^{i}} ).  (5)

Using singularity analysis (see [7]) this gives us the asymptotic estimate of

∏_{i=1}^{∞} (1 − \frac{1}{2^{i}} )2^{n−1} + O((\frac{\sqrt{5} + 1}{2} + ε)^{n}).  (6)

Thus after dividing by the total number of compositions (2^{n−1}), we obtain:

Theorem 3. The generating function for compositions of n with no fixed points is

∑_{k≥0} y^{k} ∏_{i=1}^{k} (\frac{x}{1 − x} − x^{i})  (7)

where x tracks the size of the composition and y tracks the number of parts in the composition. As n → ∞ the proportion of compositions of n with no fixed points tends to

∏_{i=1}^{∞} (1 − \frac{1}{2^{i}} ) = 0.2887880951 · · · .

The first few terms in the expansion of the generating function (starting at n = 1) are

0, 1, 2, 3, 6, 11, 22, 42, 82, 161, 316, 624, 1235, 2449,
4864, 9676, 19267, 38399, 76582, 152819

which is sequence \underline{A238351} in the OEIS.

2.3 Compositions with p fixed points

We now consider the cases where fixed points do occur in the composition.

First we allow exactly one fixed point (in position j). By setting y = 1 and making use of the generating function in (2), we obtain

∑_{j≥1} ∑_{k≥j} \frac{∏_{i=1}^{k} (\frac{x}{1−x} − x^{i})}{\frac{x}{1−x} − x^{j}}x^{j}

since all parts are not fixed points except j, which is divided out of the product in (7), and included as a fixed point with the final x^{j} factor.

The series expansion for the series for one fixed point is

x + x^{2} + x^{3} + 4x^{4} + 7x^{5} + 16x^{6} + 29x^{7} + 60x^{8} + 120x^{9} + 238x^{10} + O(x^{11})

and appears in the OEIS as sequence \underline{A240736}.

Using a similar argument to that presented in the proof of Theorem 3, we find that the generating function for the number of compositions of n with one fixed point is

∑_{j≥1} ∑_{k≥j} ∏_{{i=1 \atop i≠j}}^{k} (\frac{x}{1 − x} − x^{i})x^{j} = ∑_{j≥1} x^{j} ∑_{k≥j} (\frac{x}{1 − x})^{k−1} ∏_{{i=1 \atop i≠j}}^{∞} (1 − (1 − x)x^{i−1})

∼ ∑_{j≥1} \frac{(\frac{x}{1−x})j−1}{1 − \frac{x}{1−x}} x^{j} ∏_{{i=1 \atop i≠j}}^{∞}(1 − 2^{−i}) (as x → \frac{1}{2})

= ∏_{i=1}^{∞}(1 − 2^{−i})\frac{1 − x}{1 − 2x} ∑_{j≥1} \frac{(\frac{x^{2}}{1−x})^{j−1}x}{1 − 2^{−j}}.  (8)

Thus as n → ∞, using (8)

[x^{n}] ∑_{j≥1} ∑_{k≥j} ∏_{{i=1 \atop i≠j}}^{k} (\frac{x}{1 − x} − x^{i})x^{j} ∼ 2^{n−1} ∏_{i=1}^{∞}(1 − 2^{−i}) ∑_{j≥1} \frac{1}{2^{j} − 1}.

Thus we have proved the following theorem.

Theorem 4. The generating function for compositions of n with exactly one fixed point is

∑_{j≥1} ∑_{k≥j} \frac{∏_{i=1}^{k} (\frac{x}{1−x} − x^{i})}{\frac{x}{1−x} − x^{j}}x^{j}.

As n → ∞ the proportion of compositions of n with one fixed point is

∏_{i=1}^{∞}(1 − 2^{−i}) ∑_{j≥1} \frac{1}{2^{j} − 1} = 0.4639944325 · · · .

In the case of exactly two fixed points, we obtain the following theorem.

Theorem 5. The generating function for the number of compositions of n with exactly two fixed points is

∑_{j_{1}≥1} \frac{x^{j_{1}}}{\frac{x}{1−x} − x^{j_{1}}} ∑_{j_{2}>j_{1}} \frac{x^{j_{2}}}{\frac{x}{1−x} − x^{j_{2}}} ∑_{k≥j_{2}} ∏_{i=1}^{k} (\frac{x}{1 − x} − x^{i}).

As n → ∞ the proportion of compositions of n with two fixed points is

∑_{j_{2}≥1} \frac{1}{2^{j_{2}} − 1} ∑_{j≥j_{2}+1} \frac{1}{2^{j} − 1} ∏_{i=1}^{∞}(1 − 2^{−i}) = 0.2085238591 · · · .

This appears in the OEIS as \underline{A240737} and the series expansion is

x^{3} + x^{4} + 3x^{5} + 4x^{6} + 12x^{7} + 23x^{8} + 47x^{9} + 100x^{10} + O(x^{11}).

We generalize the above and obtain

Theorem 6. The generating function for p fixed points in compositions of n is

∑_{1≤j_{1}<j_{2}<···<j_{p}} \frac{x^{j_{1}+j_{2}+···+j_{p}}}{∏_{t=1}^{p} (\frac{x}{1−x} − x^{j_{t}})} ∑_{k≥j_{p}} ∏_{i=1}^{k} (\frac{x}{1 − x} − x^{i}) .

The proportion of compositions with p fixed points tends to

∑_{1≤j_{1}<j_{2}<···<j_{p}} \frac{1}{2^{j_{1}+j_{2}+···+j_{p}}} ∏_{t=1}^{p} \frac{1}{1 − 2^{−j_{t}}} ∏_{i=1}^{∞} (1 − 2^{−i}) ,

as n → ∞.

Remark 7. For the case p = 3 the proportion is 0.03591263561 ⋯ and the series expansion is

x^{6} + x^{7} + 3x^{8} + 7x^{9} + 12x^{10} + 30x^{11} + 61x^{12} + 126x^{13} + 258x^{14} + 537x^{15} + O[x]^{16},

which appears as \underline{A238349} in the OEIS: “Triangle T (n, k) read by rows is the number of compositions of n with k parts p at position p”.

The following two sections deal with minimum and maximum fixed points which Deutsch and Elizalde [5] studied in the case of permutations.

2.4 Average minimum fixed point

Suppose the first fixed point in a composition of n is of size j (in position j). Then all parts to the left cannot be a fixed point and there is no restriction on the parts to the right (i.e., there may or may not be fixed points in positions j + 1, j + 2, …). For compositions with no fixed points, we define j to be zero. The generating function for this is

∑_{j≥1} ∏_{i=1}^{j−1} (\frac{x}{1 − x} − x^{i})jx^{j} \frac{1 − x}{1 − 2x}.

The series expansion is

x + x^{2} + 2x^{3} + 6x^{4} + 12x^{5} + 27x^{6} + 54x^{7} + 115x^{8} + 237x^{9} + 486x^{10} + O(x^{11}),

and this sequence is now in the OEIS as sequence \underline{A335712}.

By similar techniques to the previous section, as n → ∞ the average minimum size tends to the constant

∑_{j=1}^{∞} j2^{−j} ∏_{i=1}^{j−1} (1 − 2^{−i}) = 1.085105550 · · · .

2.5 Average maximum fixed point

Suppose now that j is the maximum fixed point in a composition of n, then the j − 1 parts before it can be anything (may or may not be fixed points) but everything from position j + 1 onwards cannot be a fixed point. So we obtain the generating function

∑_{j≥1} (\frac{x}{1 − x})^{j−1}jx^{j} ∑_{k≥j} ∏_{i=j+1}^{k} (\frac{x}{1 − x} − x^{i}).

The series expansion is

x + x^{2} + 3x^{3} + 7x^{4} + 16x^{5} + 34x^{6} + 73x^{7} + 155x^{8} + 324x^{9} + 674x^{10} + O(x^{11})

which is in the OEIS as \underline{A335713}.

From the generating function, using the same methods as above and again dividing by 2^{n−1}, we see that as n → ∞ the average maximum size tends to

∑_{j=1}^{∞} j2^{−j} ∏_{i=j+1}^{∞} (1 − 2^{−i}) = 1.606695152 · · · .

2.6 Average sum of sizes of fixed points

The generating function for summing the sizes (alternatively, positions) of fixed points is:

\frac{1 − x}{1 − 2x} ∑_{j=1}^{∞} \frac{x^{j−1}}{(1 − x)^{j−1}} jx^{j} = \frac{(1 − x)^{3}x}{(1 − 2x) (1 − x − x^{2})^{2}}  (9)

with series expansion

x + x^{2} + 4x^{3} + 8x^{4} + 19x^{5} + 41x^{6} + 89x^{7} + 189x^{8} + 398x^{9} + 830x^{10} + O(x^{11})

which is sequence \underline{A335714} in the OEIS.

By splitting (9) into partial fractions, we find that the average sum of sizes tends to 2 as n → ∞.

3 Fixed points in words of length n over alphabet [k]

The total number of words of length n over the alphabet [k] is k^{n}.

Since fixed points occur when the ith letter in the word is i, there can be no fixed points after position k (the largest letter in the alphabet).

3.1 Words with no fixed points

For each position i = 1, 2, …, k, the probability of it not being a fixed point in positions 1 to k is \frac{k−1}{k}. Thereafter the probability of this event is 1. Hence the probability that a word of length n ≥ k has no fixed points is

(\frac{k − 1}{k})^{k}.

It is interesting to note that as k → ∞ this tends to 1/e which is also the proportion of derangements of permutations of {1, …, n}, see [10, 11] among many others.

By considering the number of words with no fixed points over alphabet k = [3], we obtain the sequence for n = 1, 2, …

2, 4, 8, 24, 72, 216, 648, 1944, 5832, 17496, 52488, ….  (10)

This sequence already exists in the OEIS as sequence \underline{A026097}. The description given there is the number a(n) of sequences of the form (s(0), s(1), ..., s(n)) such that every s(i) is an integer; s(0) = 0;

|s(i) − s(i − 1)| = 1 for i = 1, 2, 3;  (11)

and

|s(i) − s(i − 1)| ≤ 1 for i ≥ 4.  (12)

We present a bijection between these two sets.

Bijection 8. By dropping the initial zero of each sequence counted by a(n) in \underline{A026097}, we obtain a sequence of length n where each of the first three entries has a choice of two possibilities (add one or subtract one from the previous entry and start with 1 or −1) and all the rest have a choice of three.

In words of length n over alphabet k = [3], the only places where a fixed point could occur are in positions 1, 2 or 3. In order to avoid a fixed point in these positions there are only two possibilities (one less than the alphabet size). For the remaining letters, any member of the alphabet is permitted as there cannot be a fixed point from position 4 onwards.

3.2 Words with p fixed points

The probability of having p fixed points for a word of length n ≥ k is

\binom{k}{p}(\frac{1}{k})^{p}(\frac{k − 1}{k})^{k−p}.

3.3 Total number of fixed points in words

In order to construct the generating function for the total number of fixed points in words, we use u to track fixed points and x to track the number of parts. Thus the ux below is the one possible size of letter which would be a fixed point and the x(k − 1) represents the k − 1 other sizes of letter that would not be a fixed point. If n < k, there are n choices for this. For n ≥ k, the first k letters in the word are subject to the same conditions but thereafter the letter can be any of the k letter sizes. This yields

∑_{n=0}^{k−1}(x(k − 1) + xu)^{n} + ∑_{n=k}^{∞}(x(k − 1) + xu)^{k}(kx)^{n−k}.  (13)

Only the second term is relevant to us since we are interested in n ≥ k. We differentiate partially with respect to u and then set u = 1 to obtain

\frac{∂}{∂u} ∑_{n=k}^{∞}(x(k − 1) + xu)^{k}(kx)^{n−k}|_{u=1} = ∑_{n=k}^{∞} kx(x(k − 1) + xu)^{k−1}(kx)^{n−k}|_{u=1}

= \frac{(xk)^{k}}{1 − xk} .  (14)

Dividing by k^{n} gives us an average of one. This can be seen directly since each of the first k letters of every word is a fixed point with probability \frac{1}{k}.

3.4 Further parameters for fixed points in words

In this subsection we consider three parameters, the size or position of the average minimum and maximum and the average sum of sizes of fixed points in words.

To compute the average minimum fixed point in a word over [k], we argue as follows. If the first (minimum) fixed point is j in position j, all the points to its left are not fixed and each occurs with probability \frac{k−1}{k}. In the case where there are no fixed points, we set j to be zero. This implies that the size or position of the average minimum fixed point for all words of length n ≥ k is

∑_{j=1}^{k} j(\frac{k − 1}{k})^{j−1}(\frac{1}{k}) = k − 2k(\frac{k − 1}{k})^{k}.  (15)

Note that as k → ∞, the right-hand side of (15) tends to k(1 − \frac{2}{e}) = (0.2642411 ⋯)k.

For the average maximum fixed point, if the largest point is j which is at most k, all the points to its left may be any letter whereas points to its right cannot be fixed. This latter occurs with probability \frac{k−1}{k} in positions ≤ k and with probability one thereafter. This implies that the size or position of the average maximum fixed points for all words with n ≥ k is

∑_{j=1}^{k} j(\frac{1}{k})(\frac{k − 1}{k})^{k−j} = 1 + (\frac{k}{k − 1})^{k}(k − 1).  (16)

As k → ∞, the right-hand side of (16) tends to (1 + (k − 1)\frac{1}{e}) ∼ \frac{k}{e} ∼ (0.36787944 ⋯)k. Finally, we note that the average sum of sizes of fixed points in words is

∑_{j=1}^{k} j(\frac{1}{k}) = \frac{k + 1}{2}.  (17)

4 Acknowledgments

This material is based upon work supported by the National Research Foundation under grant numbers 89147 (Archibald), BLEC 018 (Blecher) and 81021 (Knopfmacher).

We would like to thank Stephan Wagner for his help with the asymptotics in Theorem 3.

References

[1] R. Arratia and S. Tavare, The cycle structure of random permutations, Ann. Probab. 20 (1992), 1567–1591.

[2] M. Bóna, On a balanced property of derangements, Electron. J. Combin. 13 (2006), Paper #R102.

[3] R. A. Brualdi, Introductory Combinatorics, 5th ed., Prentice-Hall, 2010.

[4] P. J. Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, 1994.

[5] E. Deutsch and S. Elizalde, The largest and the smallest fixed points of permutations, European J. Combin. 31 (2010), 1404–1409.

[6] P. Diaconis, J. Fulman, and R. Guralnick, On fixed points of permutations, J. Algebraic Combin., 28 (2008), Article 189.

[7] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press,

   2008. Available at http://algo.inria.fr/flajolet/Publications/books.html.

[8] G.-N. Han and G. Xin, Permutations with extremal number of fixed points, J. Combin. Theory Ser. A 116 (2009), 449–459.

[9] N. J. A. Sloane et al., The On-line Encyclopedia of Integer Sequences, 2020. Available

   at https://oeis.org/.

[10] R. P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge University Press, 1986.

[11] H. S. Wilf, generatingfunctionology, A. K. Peters, 1990.

2010 Mathematics Subject Classification: Primary 05A05; Secondary 05A15, 05A16, 05A19. Keywords: composition, word, fixed point, derangement.

(Concerned with sequences \underline{A026097}, \underline{A099036}, \underline{A238349}, \underline{A238351}, \underline{A240736}, \underline{A240737}, \underline{A335712}, \underline{A335713}, and \underline{A335714}.)

Received March 23 2020; revised version received July 15 2020; October 28 2020. Published in Journal of Integer Sequences, November 7 2020.

Return to Journal of Integer Sequences home page.