\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{amscd} \usepackage{graphicx} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics} \usepackage{latexsym} \usepackage{epsf} \usepackage{breakurl} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{bijection}[theorem]{Bijection} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf Fixed Points in Compositions and Words } \vskip 1cm \large M. Archibald, A. Blecher, and A. Knopfmacher\\ The John Knopfmacher Centre for\\ Applicable Analysis and Number Theory\\ University of the Witwatersrand\\ Johannesburg \\ South Africa \\ \href{mailto:Margaret.Archibald@wits.ac.za}{\tt Margaret.Archibald@wits.ac.za} \\ \href{mailto:Aubrey.Blecher@wits.ac.za}{\tt Aubrey.Blecher@wits.ac.za} \\ \href{mailto:Arnold.Knopfmacher@wits.ac.za}{\tt Arnold.Knopfmacher@wits.ac.za} \end{center} \vskip .2in \begin{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. \end{abstract} \section{Introduction} Fixed points and derangements in permutations have been widely studied; see, for example, the articles \cite{brualdi, cameron, stanley, wilf}. More recently, Arratia and Tavare, B\'ona, and Diaconis et al.\ \cite{arta, bona, dfg} studied such fixed points. In addition, Deutsch and Elizalde \cite{deel} calculated the largest and smallest fixed points of permutations, and Han and Xin \cite{haxi} 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,\ldots,k\}$. \subsection{Definitions and examples} \begin{enumerate} \item A \emph{composition} of the positive integer $n$ is a representation of $n$ as an ordered sum of positive integers $n=a_1+a_2+\dots+a_m$ where each $a_i$ is called a {\em part} of the composition. \item A \emph{fixed point} in any sequence of values is a point with value $i$ in position $i$. \end{enumerate} \begin{example}\label{eg:fixed} 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. \begin{center} \begin{tabular}{|c|c|c|c|c|c|c|} \hline $1$&$2$&$3$&$4$&$5$&$6$&$7$\\ \hline $1$&$2$&$1$&$1$&$5$&$1$&$5$\\ \hline \end{tabular} \end{center} \end{example} In Section~\ref{sec:comps}, 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\ge1$. Then we provide formulae for the average maximum (respectively minimum) fixed point and the sum of sizes of fixed points. In Section~\ref{sec:words} 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. \section{Fixed points in compositions}\label{sec:comps} By comparing a composition with $m$ parts with the identity permutation $123\cdots m$, we count how many fixed points occur over all compositions of $n$. \subsection{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 \seqnum{A099036} in the {\it On-Line Encyclopedia of Integer Sequences} \cite{sloane} (hereafter OEIS). This is a sequence for the number of compositions of $n$ that contain 1 as a part. This suggests the following bijection. \begin{bijection} 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. \end{bijection} 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 \begin{displaymath} \frac{1-x}{1-2x}-\frac{1}{1-\frac{x^2}{1-x}} = \frac{x(1-x)^2}{(1-2x)(1-x-x^2)} \end{displaymath} with series expansion \begin{align*} &1+x+3 x^2+6 x^3+13 x^4+27 x^5+56 x^6+115 x^7\\ &+235 x^8+478 x^9+969 x^{10}+O(x^{11}) \end{align*} as per the above sequence \seqnum{A099036} in the On-Line Encyclopedia of Integer Sequences (OEIS). Consequently, the total number of fixed points over all compositions of $n$ is \begin{align*} [x^n]&\frac{x(1-x)^2}{(1-2x)(1-x-x^2)}\\ & \qquad =\frac{1}{5\cdot 2^{n+1}} \left(5\cdot 4^n+\left(\sqrt{5}-5\right) \left(1+\sqrt{5}\right)^n-\left(5+\sqrt{5}\right) \left(1-\sqrt{5}\right)^n\right), \end{align*} and the average per composition of $n$ (divide by $2^{n-1}$, the number of compositions of $n$) is \begin{equation} 1 + O \left(\frac{1+\sqrt{5}}{4}\right)^n. \end{equation} \subsection{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 \begin{equation}\label{gf:nofixedpoints} \sum_{k \ge 0} y^k \prod_{i=1}^k \Big(\frac{x}{1-x} - x^i\Big) \end{equation} with series expansion, when $y=1$, \begin{displaymath} x^2+2 x^3+3 x^4+6 x^5+11 x^6+22 x^7+42 x^8+82 x^9+161 x^{10}+O(x^{11}). \end{displaymath} This is sequence \seqnum{A238351} in the OEIS. In order to obtain asymptotic estimates, we put $y=1$ and rewrite (\ref{gf:nofixedpoints}) as \begin{align}\label{eq:SWargument} F(x)& := \sum_{k \ge 1} \prod_{i=1}^k \Big(\frac{x}{1-x} - x^i\Big)\notag\\ & = \sum_{k \ge 1}\Big(\frac{x}{1-x}\Big)^k \prod_{i=1}^k \Big(1-(1-x)x^{i-1}\Big)\notag\\ & =\sum_{k \ge 1}\Big(\frac{x}{1-x}\Big)^k \prod_{i=1}^\infty \Big(1-(1-x)x^{i-1}\Big)-\notag\\ &\quad\quad \sum_{k \ge 1}\Big(\frac{x}{1-x}\Big)^k \prod_{i=1}^\infty \Big(1-(1-x)x^{i-1}\Big)\Big(1-\prod_{i=k+1}^\infty \frac{1}{1-(1-x)x^{i-1}}\Big)\notag\\ & =\prod_{i=1}^\infty \Big(1-(1-x)x^{i-1}\Big)\notag \\ & \qquad \cdot \bigg(\frac{x}{1-2x}-\sum_{k \ge 1}\Big(\frac{x}{1-x}\Big)^k \Big(1-\prod_{i=k+1}^\infty \frac{1}{1-(1-x)x^{i-1}}\Big)\bigg). \end{align} We now show that the last sum is analytic for $|x|< \frac{\sqrt5 -1}{2}$: \begin{align} \prod_{i=k+1}^\infty \Big(\frac{1}{1-(1-x)x^{i-1}}\Big) &=\exp\Big(-\sum_{i=k+1}^\infty\log\Big(1-(1-x)x^{i-1}\Big)\Big)\notag\\ &=\exp\Big(\sum_{i=k+1}^\infty\Big((1-x)x^{i-1}+O(x^{2i})\Big)\Big)\notag\\ &=\exp\Big((1-x)\frac{x^k}{1-x}+O(x^{2k})\Big)\notag\\ &=\exp\Big({x^k}+O(x^{2k})\Big)\notag\\ &= 1+{x^k}+O(x^{2k}). \end{align} This implies that \begin{align} \sum_{k \ge 1}\Big(\frac{x}{1-x}\Big)^k \Big(1-\prod_{i=k+1}^\infty \frac{1}{1-(1-x)x^{i-1}}\Big)\Big) &=\sum_{k \ge 1}\Big(\frac{x}{1-x}\Big)^k \Big(-{x^k}+O(x^{2k})\Big)\notag, \end{align} which converges if $\big|\frac{x^2}{1-x}\big|<1$, i.e., $|x|<\frac{\sqrt5 -1}{2}$. Thus the dominant singularity in (\ref{eq:SWargument}) is in the first term of the square bracket, namely $\frac{x}{1-2x}$, which is analytic for $|x|<\frac 12$. By expanding $F(x)$ from (\ref{eq:SWargument}) about the point $x=\frac12$, we obtain \begin{align} F(x) & \sim \frac{x}{1-2x} \prod_{i=1}^\infty \bigg(1-\Big(1-\frac{1}{2}\Big)\Big(\frac{1}{2}\Big)^{i-1}\bigg)\notag\\ &=\frac{x}{1-2x} \prod_{i=1}^\infty \bigg(1-\frac{1}{2^i}\bigg). \end{align} Using singularity analysis (see \cite{Flajolet}) this gives us the asymptotic estimate of \begin{equation} \prod_{i=1}^\infty \bigg(1-\frac{1}{2^i}\bigg) 2^{n-1}+O\bigg(\Big(\frac{\sqrt{5}+1}{2}+\varepsilon\Big)^n\bigg). \end{equation} Thus after dividing by the total number of compositions $(2^{n-1})$, we obtain: \begin{theorem}\label{th:nfp} The generating function for compositions of $n$ with no fixed points is \begin{equation}\label{eq:nfp} \sum_{k \ge 0} y^k \prod_{i=1}^k \Big(\frac{x}{1-x} - x^i\Big) \end{equation} where $x$ tracks the size of the composition and $y$ tracks the number of parts in the composition. As $n\rightarrow\infty$ the proportion of compositions of $n$ with no fixed points tends to \[\prod_{i=1}^\infty \bigg(1-\frac{1}{2^i}\bigg)= 0.2887880951\cdots. \] \end{theorem} The first few terms in the expansion of the generating function (starting at $n=1$) are \begin{align*} &0, 1, 2, 3, 6, 11, 22, 42, 82, 161, 316, 624, 1235, 2449,\\ &4864, 9676, 19267, 38399, 76582, 152819 \end{align*} which is sequence \seqnum{A238351} in the OEIS. \subsection{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 (\ref{gf:nofixedpoints}), we obtain \begin{displaymath} \sum_{j\ge 1}\sum_{k \ge j} \frac{\prod_{i=1}^k \Big(\frac{x}{1-x} - x^i\Big)}{\frac{x}{1-x} - x^j} x^j \end{displaymath} since all parts are not fixed points except $j$, which is divided out of the product in (\ref{eq:nfp}), 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+4 x^4+7 x^5+16 x^6+29 x^7+60 x^8+120 x^9+238 x^{10}+O(x^{11}) \] and appears in the OEIS as sequence \seqnum{A240736}. Using a similar argument to that presented in the proof of Theorem \ref{th:nfp}, we find that the generating function for the number of compositions of $n$ with one fixed point is \begin{align} \sum_{j\ge1}\sum_{k \ge j} \prod_{i=1 \atop{i\ne j} }^k \Big(\frac{x}{1-x} - x^i\Big)x^j & =\sum_{j\ge 1}x^j\sum_{k \ge j}\Big(\frac{x}{1-x}\Big)^{k-1} \prod_{i=1 \atop{i\ne j}}^\infty \Big(1-(1-x)x^{i-1}\Big)\notag\\ & \sim \sum_{j\ge 1}\frac{\Big(\frac{x}{1-x}\Big)^{j-1}}{1-\frac{x}{1-x}}x^j \prod_{i=1 \atop{i\ne j}}^\infty (1-2^{-i})\qquad \bigg( \text{as } x \rightarrow \frac 12 \bigg)\notag\\ & = \prod_{i=1}^\infty (1-2^{-i})\frac{1-x}{1-2x} \sum_{j\ge 1}\frac{\Big(\frac{x^2}{1-x}\Big)^{j-1}x}{1-2^{-j}}. \label{eq:last} \end{align} Thus as $n\rightarrow\infty$, using (\ref{eq:last}) $$[x^n]\sum_{j\ge1}\sum_{k \ge j} \prod_{i=1 \atop{i\ne j} }^k \Big(\frac{x}{1-x} - x^i\Big)x^j \sim 2^{n-1}\prod_{i=1}^\infty (1-2^{-i})\sum_{j\ge 1}\frac{1}{2^j-1}.$$ Thus we have proved the following theorem. \begin{theorem} The generating function for compositions of $n$ with exactly one fixed point is \begin{displaymath} \sum_{j\ge 1}\sum_{k \ge j} \frac{\prod_{i=1}^k \Big(\frac{x}{1-x} - x^i\Big)}{\frac{x}{1-x} - x^j} x^j. \end{displaymath} As $n \rightarrow \infty$ the proportion of compositions of $n$ with one fixed point is \[ \prod_{i=1}^\infty (1-2^{-i})\sum_{j\ge 1}\frac{1}{2^j-1}= 0.4639944325\cdots . \] \end{theorem} In the case of exactly two fixed points, we obtain the following theorem. \begin{theorem} The generating function for the number of compositions of $n$ with exactly two fixed points is \begin{displaymath} \sum_{j_1\ge 1}\frac{x^{j_1}}{\frac{x}{1-x} - x^{j_1}}\sum_{j_2>j_1}\frac{x^{j_2}}{\frac{x}{1-x} - x^{j_2}}\sum_{k \ge j_2} \prod_{i=1}^k \Big(\frac{x}{1-x} - x^i\Big). \end{displaymath} As $n \rightarrow \infty$ the proportion of compositions of $n$ with two fixed points is \[ \sum_{{j_{2}}\ge 1}\frac{1}{2^{j_{2}}-1}\sum_{j\ge{j_{2}}+1}\frac{1}{2^j-1}\prod_{i=1}^\infty (1-2^{-i})= 0.2085238591\cdots . \] \end{theorem} This appears in the OEIS as \seqnum{A240737} and the series expansion is \[ x^3+x^4+3 x^5+4 x^6+12 x^7+23 x^8+47 x^9+100 x^{10}+O(x^{11}). \] We generalize the above and obtain \begin{theorem} The generating function for $p$ fixed points in compositions of $n$ is \[ \sum_{1 \le j_1 < j_2 < \dots < j_p}\frac{x^{j_1 + j_2 + \dots + j_p}}{\prod_{t=1}^p \left(\frac{x}{1-x} - x^{j_t}\right)} \sum_{k \ge j_p} \prod_{i=1}^{k} \left(\frac{x}{1-x} - x^i\right). \] The proportion of compositions with $p$ fixed points tends to \begin{displaymath} \sum_{1 \le j_1 < j_2 < \dots < j_p}\frac{1}{2^{j_1 + j_2 + \dots + j_p}}\prod_{t=1}^p \frac{1}{1 - 2^{-j_t}} \prod_{i=1}^{\infty} \left(1 - 2^{-i}\right), \end{displaymath} as $n \rightarrow \infty$. \end{theorem} \begin{remark} For the case $p=3$ the proportion is $0.03591263561\cdots$ and the series expansion is \[ x^6+x^7+3 x^8+7 x^9+12 x^{10}+30 x^{11}+61 x^{12}+126 x^{13}+258 x^{14}+537 x^{15}+O[x]^{16}, \] which appears as $\seqnum{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$". \end{remark} The following two sections deal with minimum and maximum fixed points which Deutsch and Elizalde \cite{deel} studied in the case of permutations. \subsection{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,\dots$). For compositions with no fixed points, we define $j$ to be zero. The generating function for this is \begin{displaymath} \sum_{j\ge 1}\prod_{i=1}^{j-1} \Big(\frac{x}{1-x} - x^i\Big) j x^j \frac{1-x}{1-2x}. \end{displaymath} The series expansion is \[ x+x^2+2 x^3+6 x^4+12 x^5+27 x^6+54 x^7+115 x^8+237 x^9+486 x^{10}+O(x^{11}), \] and this sequence is now in the OEIS as sequence \seqnum{A335712}. By similar techniques to the previous section, as $n \rightarrow \infty$ the average minimum size tends to the constant \[ \sum _{j=1}^{\infty} j 2^{-j}\prod _{i=1}^{j-1} \left(1-2^{-i}\right) = 1.085105550 \cdots . \] \subsection{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 \begin{displaymath} \sum_{j\ge 1}\Big(\frac{x}{1-x}\Big)^{j-1} j x^j \sum_{k \ge j}\prod_{i=j+1}^{k} \Big(\frac{x}{1-x} - x^i\Big). \end{displaymath} The series expansion is \[ x+x^2+3 x^3+7 x^4+16 x^5+34 x^6+73 x^7+155 x^8+324 x^9+674 x^{10}+O(x^{11}) \] which is in the OEIS as \seqnum{A335713}. From the generating function, using the same methods as above and again dividing by $2^{n-1}$, we see that as $n \rightarrow \infty$ the average maximum size tends to \[ \sum _{j=1}^{\infty} j2^{-j}\prod _{i=j+1}^{\infty} \left(1-2^{-i}\right) = 1.606695152\cdots. \] \subsection{Average sum of sizes of fixed points} The generating function for summing the sizes (alternatively, positions) of fixed points is: \begin{equation}\label{avsumf} \frac{1-x}{1-2x}\sum_{j=1}^{\infty } \frac{x^{j-1}}{(1-x)^{j-1}}j x^j = \frac{(1-x)^3 x}{(1-2x) \left(1-x-x^2\right)^2} \end{equation} with series expansion \[ x+x^2+4 x^3+8 x^4+19 x^5+41 x^6+89 x^7+189 x^8+398 x^9+830 x^{10}+O(x^{11}) \] which is sequence \seqnum{A335714} in the OEIS. By splitting (\ref{avsumf}) into partial fractions, we find that the average sum of sizes tends to $2$ as $n\rightarrow\infty$. \section{Fixed points in words of length $n$ over alphabet $[k]$}\label{sec:words} The total number of words of length $n$ over the alphabet $[k]$ is $k^n$. Since fixed points occur when the $i$th letter in the word is $i$, there can be no fixed points after position $k$ (the largest letter in the alphabet). \subsection{Words with no fixed points} For each position $i=1,2,\dots,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\ge k$ has no fixed points is \[ \bigg(\frac{k-1}{k}\bigg)^k. \] It is interesting to note that as $k \rightarrow \infty$ this tends to $1/e$ which is also the proportion of derangements of permutations of $\{1,\dots ,n\}$, see \cite{stanley, wilf} 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,\ldots$ \begin{equation} 2, 4, 8, 24, 72, 216, 648, 1944, 5832, 17496, 52488, \dots . \end{equation} This sequence already exists in the OEIS as sequence \seqnum{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$; \begin{equation} | s (i) - s (i - 1) | = 1 \text{ for } i = 1, 2, 3; \end{equation} and \begin{equation} | s (i) - s (i - 1) | \le 1 \text{ for } i \ge 4. \end{equation} We present a bijection between these two sets. \begin{bijection} By dropping the initial zero of each sequence counted by $a(n)$ in $\seqnum{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. \end{bijection} \subsection{Words with $p$ fixed points} The probability of having $p$ fixed points for a word of length $n \ge k$ is \[ \binom{k}{p}\bigg(\frac1k\bigg)^p \bigg(\frac{k-1}{k}\bigg)^{k-p}. \] \subsection{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