%&latex \documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \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,amsmath,amssymb} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf Counting Stabilized-Interval-Free Permutations } \vskip 1cm \large David Callan \\ Department of Statistics \\ University of Wisconsin-Madison \\ 1210 W. Dayton St \\ Madison, WI \ 53706-1693 \\ \href{mailto:callan@stat.wisc.edu}{\tt callan@stat.wisc.edu} \\ \end{center} \vskip .2 in \begin{abstract} A stabilized-interval-free (SIF) permutation on $[n]= \{1,2,...,n\}$ is one that does not stabilize any proper subinterval of $[n]$. By presenting a decomposition of an arbitrary permutation into a list of SIF permutations, we show that the generating function $A(x)$ for SIF permutations satisfies the defining property: $[x^{n-1}] A(x)^n = n!$ . We also give an efficient recurrence for counting SIF permutations. \end{abstract} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}{Proposition}[section] \newtheorem{corollary}{Corollary}[section] \newtheorem{lemma}{Lemma}[section] %path-generating code courtesy of Christian Krattenthaler %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Input-Datei zum Erzeugen von Gitterpunktwegen.% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %LaTeX-Version% %%%%%%%%%%%%%%% %entering a path: % \Pfad(x-coordinate of starting point,y-coordinate of final %point),path % as 1-2-3-4-word\endPfad %(1=step in x-direction, 2=step in y-direction, 3=upward diagonal step, 4=downward diagonal step) % %entering a dotted path: % \SPfad(x-coordinate of starting point,y-coordinate of starting point),path % as 1-2-3-4-word\endSPfad %(1=step in x-direction, 2=step in y-direction, 3=upward diagonal step, 4=downward diagonal step) % %coordinate-axes: % \Koordinatenachsen(length of positive x-axes, length of positive %y-axes)(length of negative x-axes, length of negative y-axes) %The length of negative axes are entered as negative numbers. % %lattice: % \Gitter(number of points in positive x-direction, number of points %in positive y-direction)(number of points in negative x-direction, %number of points in negative y-direction) % %diagonal lines: % \Diagonale(x-coordinate of SW-most point,y-coordinate of SW-most point)length of the projection on the x-axes % %antidiagonal lines: % \AntiDiagonale(x-coordinate of NW-most point,y-coordinate of NW-most point)length of the projection on the x-axes % %labelling of points: % \Label[location?]{[label]}(x-coordinate,y-coordinate) %where: % [location?]=\l,\lo,\lu,\r,\ro,\ru,\o,\u %and l=left, r=right, u=bottom, o=top. %In addition, if by \Einheit?cm the basic unit is changed, there exist %\llo,\loo,\llu,\luu,\rro,\roo,\rru,\ruu. % %The basic unit can be changed by entering % \Einheit=?cm %The default is \Einheit=0.5cm. % %The thickness of the paths can be changed by entering % \PfadDicke{?cm} %The default is \PfadDicke=1pt. % %The following point sizes are available: %\DuennPunkt, \NormalPunkt, \DickPunkt. Syntax: % \DickPunkt(x-coordinate,y-coordinate), etc. % %Besides, a circle is available by \Kreis. Syntax: % \Kreis(x-coordinate,y-coordinate) % \catcode`\@=11 \font\tenln = line10 \font\tenlnw = linew10 \thicklines \newskip\Einheit \Einheit=.6cm \newcount\xcoord \newcount\ycoord \newdimen\xdim \newdimen\ydim \newdimen\PfadD@cke \newdimen\Pfadd@cke \PfadD@cke2pt \Pfadd@cke0.3pt \def\PfadDicke#1{\PfadD@cke#1 \divide\PfadD@cke by2 \Pfadd@cke\PfadD@cke \multiply\PfadD@cke by2} \long\def\LOOP#1\REPEAT{\def\BODY{#1}\ITERATE} \def\ITERATE{\BODY \let\next\ITERATE \else\let\next\relax\fi \next} \let\REPEAT=\fi \def\Punkt{\hbox{\raise-2pt\hbox to0pt{\hss\scriptsize$\bullet$\hss}}} \def\DuennPunkt(#1,#2){\unskip \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit \raise-1.5pt\hbox to0pt{\hss\tiny$\bullet$\hss}\hss}} \def\NormalPunkt(#1,#2){\unskip \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit \raise-3pt\hbox to0pt{\hss\large$\bullet$\hss}\hss}} \def\DickPunkt(#1,#2){\unskip \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit \raise-4pt\hbox to0pt{\hss\Large$\bullet$\hss}\hss}} \def\Kreis(#1,#2){\unskip \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit \raise-4pt\hbox to0pt{\hss\Large$\circ$\hss}\hss}} \def\Diagonale(#1,#2)#3{\unskip\leavevmode \xcoord#1\relax \ycoord#2\relax \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \unitlength\Einheit \line(1,1){#3}\hss}} \def\AntiDiagonale(#1,#2)#3{\unskip\leavevmode \xcoord#1\relax \ycoord#2\relax \advance\xcoord by -0.05\relax \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \unitlength\Einheit \line(1,-1){#3}\hss}} \def\Pfad(#1,#2),#3\endPfad{\unskip\leavevmode \xcoord#1 \ycoord#2 \thicklines\ZeichnePfad#3\endPfad\thinlines} \def\ZeichnePfad#1{\ifx#1\endPfad\let\next\relax \else\let\next\ZeichnePfad \ifnum#1=1 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \vrule height\Pfadd@cke width1 \Einheit depth\Pfadd@cke\hss}% \advance\xcoord by 1 \else\ifnum#1=2 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \hbox{\hskip-\PfadD@cke\vrule height1 \Einheit width\PfadD@cke depth0pt}\hss}% \advance\ycoord by 1 \else\ifnum#1=3 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \unitlength\Einheit \line(1,1){1}\hss} \advance\xcoord by 1 \advance\ycoord by 1 \else\ifnum#1=4 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \unitlength\Einheit \line(1,-1){1}\hss} \advance\xcoord by 1 \advance\ycoord by -1 \fi\fi\fi\fi \fi\next} \def\hSSchritt{\leavevmode\raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit} \def\vSSchritt{\vbox{\baselineskip.2\Einheit\lineskiplimit0pt \hbox{.}\hbox{.}\hbox{.}\hbox{.}\hbox{.}}} \def\DSSchritt{\leavevmode\raise-.4pt\hbox to0pt{% \hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise.2\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise.4\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise.6\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise.8\Einheit\hbox to0pt{\hss.\hss}\hss}} \def\dSSchritt{\leavevmode\raise-.4pt\hbox to0pt{% \hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.2\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.4\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.6\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.8\Einheit\hbox to0pt{\hss.\hss}\hss}} \def\SPfad(#1,#2),#3\endSPfad{\unskip\leavevmode \xcoord#1 \ycoord#2 \ZeichneSPfad#3\endSPfad} \def\ZeichneSPfad#1{\ifx#1\endSPfad\let\next\relax \else\let\next\ZeichneSPfad \ifnum#1=1 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \hSSchritt\hss}% \advance\xcoord by 1 \else\ifnum#1=2 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \hbox{\hskip-2pt \vSSchritt}\hss}% \advance\ycoord by 1 \else\ifnum#1=3 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \DSSchritt\hss} \advance\xcoord by 1 \advance\ycoord by 1 \else\ifnum#1=4 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \dSSchritt\hss} \advance\xcoord by 1 \advance\ycoord by -1 \fi\fi\fi\fi \fi\next} \def\Koordinatenachsen(#1,#2){\unskip \hbox to0pt{\hskip-.5pt\vrule height#2 \Einheit width.5pt depth1 \Einheit}% \hbox to0pt{\hskip-1 \Einheit \xcoord#1 \advance\xcoord by1 \vrule height0.25pt width\xcoord \Einheit depth0.25pt\hss}} \def\Koordinatenachsen(#1,#2)(#3,#4){\unskip \hbox to0pt{\hskip-.5pt \ycoord-#4 \advance\ycoord by1 \vrule height#2 \Einheit width.5pt depth\ycoord \Einheit}% \hbox to0pt{\hskip-1 \Einheit \hskip#3\Einheit \xcoord#1 \advance\xcoord by1 \advance\xcoord by-#3 \vrule height0.25pt width\xcoord \Einheit depth0.25pt\hss}} \def\Gitter(#1,#2){\unskip \xcoord0 \ycoord0 \leavevmode \LOOP\ifnum\ycoord<#2 \loop\ifnum\xcoord<#1 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit\Punkt\hss}% \advance\xcoord by1 \repeat \xcoord0 \advance\ycoord by1 \REPEAT} \def\Gitter(#1,#2)(#3,#4){\unskip \xcoord#3 \ycoord#4 \leavevmode \LOOP\ifnum\ycoord<#2 \loop\ifnum\xcoord<#1 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit\Punkt\hss}% \advance\xcoord by1 \repeat \xcoord#3 \advance\ycoord by1 \REPEAT} \def\Label#1#2(#3,#4){\unskip \xdim#3 \Einheit \ydim#4 \Einheit \def\lo{\advance\xdim by-.5 \Einheit \advance\ydim by.5 \Einheit}% \def\llo{\advance\xdim by-.25cm \advance\ydim by.5 \Einheit}% \def\loo{\advance\xdim by-.5 \Einheit \advance\ydim by.25cm}% %NEW DEF \O := \OX \def\o{\advance\ydim by.25cm}% \def\ro{\advance\xdim by.5 \Einheit \advance\ydim by.5 \Einheit}% \def\rro{\advance\xdim by.25cm \advance\ydim by.5 \Einheit}% \def\roo{\advance\xdim by.5 \Einheit \advance\ydim by.25cm}% \def\l{\advance\xdim by-.30cm}% \def\r{\advance\xdim by.30cm}% \def\lu{\advance\xdim by-.5 \Einheit \advance\ydim by-.6 \Einheit}% \def\llu{\advance\xdim by-.25cm \advance\ydim by-.6 \Einheit}% \def\luu{\advance\xdim by-.5 \Einheit \advance\ydim by-.30cm}% \def\u{\advance\ydim by-.30cm}% \def\ru{\advance\xdim by.5 \Einheit \advance\ydim by-.6 \Einheit}% \def\rru{\advance\xdim by.25cm \advance\ydim by-.6 \Einheit}% \def\ruu{\advance\xdim by.5 \Einheit \advance\ydim by-.30cm}% #1\raise\ydim\hbox to0pt{\hskip\xdim \vbox to0pt{\vss\hbox to0pt{\hss$#2$\hss}\vss}\hss}% } \catcode`\@=12 \marginparwidth 0pt \oddsidemargin 20pt \evensidemargin 20pt \marginparsep 0pt \topmargin 0pt \textwidth 6.0in \textheight 8.5in \renewcommand{\baselinestretch}{1.1} \parskip = 3mm \setlength{\topskip}{0mm} \setlength{\headheight}{0mm} \setlength{\footskip}{15mm} %\usepackage{amsmath} %\usepackage{amsthm} %\usepackage[colorlinks=true, %linkcolor=green, %filecolor=brown, %citecolor=green]{hyperref} %\usepackage{color} \def\green{\textcolor{green} } \def\blue{\textcolor{blue} } \def\v{\vert} \def\s{\ensuremath{\mathcal S}} \def\si{\ensuremath{\sigma}} \def\ss{\ensuremath{\s_{[n]}}} \def\ssi{\ensuremath{\s_{I}}} \section{Introduction} A permutation on $[n]=\{1,2,\ldots,n\}$ is \emph{stabilized-interval-free} (SIF) if it does not stabilize any proper subinterval of $[n]$ (proper means nonempty and $\ne [n]$). For example, $\left( \begin{smallmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 1 & 5 & 3 & 4 & 2 \end{smallmatrix} \right) $, % or $(3,5,4)(1,6,2)$ in cycle notation, or $6\,1\,5\,3\,4\,2$ in one-line notation, fails to be SIF because it stabilizes the interval $[3,5]=\{3,4,5\}$. On the other hand, the empty permutation is SIF, as is any cycle, and every SIF permutation on $[n]$ is fixed-point-free for $n\ge 2$. The SIF permutations on $[n]$ for $n\le 4$ are as follows: $n=1\!:\,1;\ n=2\!:\,2\,1;\ n=3\!:\,2\,3\,1,\ 3\,1\,2$ (the two 3-cycles) $n=4\!:\,3\,4\,1\,2$ and the six 4-cycles. Let $a_{n}$ denote the number of SIF permutations on $[n]$ and $A(x)=\sum_{n\ge 0}^{}a_{n}x^{n}=1+x+x^{2}+2x^{3}+7x^{4}+\ldots$ their generating function. The first objective of this paper is to show that $[x^{n-1}]A(x)^{n}=n!$ and hence that the number of SIF permutations on $[n]$ is given by \htmladdnormallink{A075834}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A075834}. This generating function identity amounts to the existence of a decomposition of an arbitrary permutation into a list of SIF permutations. The second objective is to obtain a recurrence relation that permits efficient computation of $a_{n}:$ \[ \ a_{0} = a_{1} = 1,\ \ a_{n} = \sum_{j=2}^{n-2}(j-1)a_{j}a_{n-j}+(n-1)a_{n-1},\quad n \ge 2. \] A little more generally, a permutation on an arbitrary set of positive integers $I$ is SIF if it does not stabilize any proper subinterval of $I$ ($J$ is a subinterval of $I$ if $a,b \in J,\ c \in I$ with $a \le c \le b$ implies $c \in J$). Thus $5\,9\,2\,3$ is SIF on $\{2,3,5,9\}$ and its reduced form (replace smallest element by 1, second smallest by 2, and so on) is $3\,4\,1\,2$. The former is a \emph{labeled} SIF permutation and the latter is \emph{unlabeled}---we take $[n]$ as the standard $n$-element totally ordered set and call a permutation on $[n]$ unlabeled. Let $\s_{I}$ denotes the set of all permutations on $I$. Given $\si \in \ssi$, one can partition $I$ into consecutive subintervals $I_{1},\ldots,I_{k}$ such that $\si$ stabilizes each $I_{j}$. The intervals in the finest such partition are called the \emph{connected intervals} of $\si$; a permutation with exactly one such interval is \emph{connected} (sometimes called indecomposable) \htmladdnormallink{A003319}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A003319}. Note that the empty permutation is not connected. The restriction of $\si$ to its connected intervals clearly gives a decomposition of $\si$ into a set of connected permutations on subintervals that partition $I$, called the \emph{connected components} of $\si$. These permutations are labeled but we also have a decomposition into a \emph{list} of unlabeled connected permutations of total length $n$ (since we can use position in the list to determine the labels) and this decomposition is bijective. For example, $3\,2\,4\,1\,5\,7\,8\,6 \longleftrightarrow \{3\,2\,4\,1,\ 5,\ 7\,8\,6$\}$ \longleftrightarrow 3\,2\,4\,1$\:--\:$1$\:--\:$2\,3\,1$ (the dashes separate list items). Now $[x^{n-1}]A(x)^{n}$ is the number of length-$n$ lists (or simply $n$-lists) of unlabeled SIF permutations of total length $n-1$ (keeping in mind that the empty permutation has length 0). So, to show $[x^{n-1}]A(x)^{n}=n!$, it suffices to exhibit a bijection from $\ss$ to $n$-lists of unlabeled SIF permutations of total length $n-1$, and we will do so below. This decomposition into unlabeled SIF permutations is analogous to the one above into unlabeled connected permutations but is not so obvious. Before presenting the bijection we recall some relevant manifestations of the Catalan numbers \cite{catalan}. A Murasaki diagram is a sequence of vertical lines some (all, or none) of which are joined at their tips by horizontal lines that never intersect the interior of a vertical line. % 1=step in x-direction, 2=step in y-direction, 3=upward diagonal step, % 4=downward diagonal step \Einheit=0.6cm \[ \Pfad(-5,0),222111111\endPfad \Pfad(-4,0),221111\endPfad \Pfad(-3,0),22\endPfad \Pfad(-2,0),2\endPfad \Pfad(-1,0),22\endPfad \Pfad(0,0),22\endPfad \Pfad(1,0),222\endPfad \Pfad(2,0),2\endPfad \Pfad(3,0),22111\endPfad \Pfad(4,0),22\endPfad \Pfad(5,0),2\endPfad \Pfad(6,0),22\endPfad \Label\u{\scriptstyle{1}}(-5,0) \Label\u{\scriptstyle{2}}(-4,0) \Label\u{\scriptstyle{3}}(-3,0) \Label\u{\scriptstyle{4}}(-2,0) \Label\u{\scriptstyle{5}}(-1,0) \Label\u{\scriptstyle{6}}(0,0) \Label\u{\scriptstyle{7}}(1,0) \Label\u{\scriptstyle{8}}(2,0) \Label\u{\scriptstyle{9}}(3,0) \Label\u{\scriptstyle{10}}(4,0) \Label\u{\scriptstyle{11}}(5,0) \Label\u{\scriptstyle{12}}(6,0) \] \noindent The diagram illustrated has 3 components; the first of which has 3 segments (connected figures), the second 1 and the last 2. A partition $\{B_{1},B_{2},\ldots,B_{k}\}$ of $[n]$ is noncrossing if $a=1 := c[n] = n!-Sum[c[i](n-i)!,{i,n-1}] (* c[n] = # connected perms on [n] *) a[n_,k_]/;n>=0 && k==n+1 := 0; a[n_,1]/;n>=1 := n!; a[n_,k_]/;2<=k<=n := a[n,k] = n!-Sum[c[j-i+1]a[n-(j-i+1),i],{i,k-1},{j,i,n}]; \end{verbatim} However, there is also a direct recurrence for $a_{n}$ (vacuous sums are 0): \[ \ a_{0} = a_{1} = 1,\ \ a_{n} = \sum_{j=2}^{n-2}(j-1)a_{j}a_{n-j}+(n-1)a_{n-1},\quad n \ge 2. \] The right hand side above counts SIF permutations $\si$ on $[n]$ by the parameter $j=n-1-s$ where $s$ is the size of the largest proper subinterval $I$ of $[n-1]$ such that $\si$ stabilizes $I \cup \{n\}$. ($I$ is necessarily an interior subinterval of $[n-1]$ and may be empty.) To see this, first note that if $\si_{n-1}$ is SIF on $[n-1]$ and $n$ is inserted anywhere into a cycle of $\si_{n-1}\ (n-1$ possible ways) to form $\si \in \ss$, then $\si$ is also SIF. This accounts for the last term. Now suppose $\si $ is SIF on $[n]$ and the result $\si_{n-1}\in \mathcal{S}_{[n-1]}$ of deleting $n$ from its cycle in $\si$ fails to be SIF. Consider the maximal proper subintervals of $[n-1]$ stabilized by $\si_{n-1}$ (necessarily disjoint, as noted above). There is at least one such by assumption and at most one, call it $I$, because otherwise $\si$ itself would stabilize all but one of them, contradicting the assumption $\si$ is SIF. Let $\rho$ denote the restriction of $\si_{n-1}$ to $I$ and $\tau$ the restriction of $\si_{n-1}$ to $[n-1]\backslash I$. Then $\si$ is obtained from the pair $\rho,\tau$ by inserting $n$ into a cycle of $\rho$, not $\tau$, otherwise $\si$ would stabilize $I$. We may write the interval $I$ as $[k+1,n-j+k-1]$ for some $1 \le k < j \le n-2$ so that the size of $I$ is $s:=n-j-1$ and $I$ is clearly the largest proper subinterval of $[n-1]$ such that $\si$ stabilizes $I \cup \{n\}$. Now $\tau$ is SIF on $[n-1]\backslash I$ since $\tau$ coincides with $\si$ on $[n-1]\backslash I$. We claim $\rho':=\si$ restricted to $I \cup \{n\}$ is SIF also: if $\rho'$ stabilized a proper subinterval of $I$, then $\si$ would too, and if $\rho'$ stabilized a proper terminal subinterval (containing $n$), then $\si$ would stabilize the corresponding initial subinterval. All told, for each $j \in [2,n-2]$, we have $j-1$ choices for $k$ and every permutation $\si$ formed in this way from SIF permutations $\rho'$ on $I \cup \{n\}$ ($a_{n-j}$ choices) and $\tau$ on $[n-1]\backslash I$ $(a_{j}$ choices) is SIF. The recurrence follows. We note that it implies the differential equation \[ xA'(x)=A(x)-x-\frac{x}{A(x)-1} \] for the generating function $A(x)$. Asymptotically, the proportion of permutations on $[n]$ that are connected (indecomposable) is $1-\frac{2}{n}+O(\frac{1}{n^{2}})$ \cite[p.\:295, Ex.\:16]{comtet} and there is a simple heuristic explanation: the easiest way for a permutation on $[n]$ to be decomposable is for it to fix $1$ or $n$ and there are $2(n-1)!-(n-2)!$ permutations that do so. Far fewer permutations stabilize any other initial interval and so the dominant term in the number of decomposable permutations on $[n]$ is $2(n-1)!$. Similarly, the easiest way for $\si \in \ss$ to fail to be SIF is for it to have a fixed point. The proportion of fixed-point-free permutations on $[n]$ is well known to be very near $\frac{1}{e}$, suggesting that the proportion of SIF permutations on $[n]$ is $\frac{1}{e} +O(\frac{1}{n})$, and indeed computer calculations suggest it is $\frac{1}{e}(1-\frac{1}{n})+O(\frac{1}{n^{2}})$ and maybe $\frac{1}{e}(1-\frac{1}{n}-\frac{5}{2n^{2}})+O(\frac{1}{n^{3}})$. It would be interesting to prove this. \begin{thebibliography}{99} \bibitem{catalan} Richard P.~Stanley, Exercises on Catalan and Related Numbers, \htmladdnormallink{\tt http://www-math.mit.edu/$\,\widetilde{\ }\,$rstan/ec/catalan.pdf}{http://www-math.mit.edu/~rstan/ec/catalan.pdf}, excerpted from Enumerative Combinatorics, Vol.\,2, Cambridge University Press, 1999. \bibitem{comtet} L.~Comtet, \emph{Advanced Combinatorics}, D. Reidel, Boston, 1974. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 05A05; Secondary 05A15. \noindent \emph{Keywords: } stabilized-interval-free, connected, indecomposable, noncrossing partition, Murasaki diagram, Dyck path. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A075834}, \seqnum{A003319}, and \seqnum{A000142}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received September 25 2003; revised version received March 15 2004. Published in {\it Journal of Integer Sequences}, March 15 2004. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}. \vskip .1in \end{document}