text:
# Blue Stragglers, Young White Dwarfs and UV-excess stars in the core of 47 Tuc1footnote 11footnote 1Based on observations with the NASA/ESA HST, obtained at the Space Telescope Science Institute, which is operated by AURA, Inc., under NASA contract NAS5-26555

## 1 Introduction

A large variety of exotic objects have been found to populate the cores of the most concentrated Galactic Globular Clusters (GGCs): Blue Straggler Stars (BSSs), low mass X-ray binaries (LMXBs), low luminosity GC X-ray sources (LLGCXs), cataclysmic variables (CVs) and millisecond pulsars (MSPs) (e.g. see Bailyn 1995). As most of these objects result from Interacting Binaries (IBs), their formation is strongly favoured in the dense stellar environment of a GC, where stellar collisions provide additional channels for the formation and evolution of binary systems, e.g., via tidal captures (Fabian, Pringle & Rees 1975; Di Stefano & Rappaport 1994) and exchange interactions (Hut, Murphy & Verbunt 1991).
In this framework, we are performing an extensive search for various by-products of binary evolution in the cores of a sample of GGCs selected on the basis of their photometric properties. In particular, a large population of BSSs (see Ferraro et al. 1997a, 1999; Paltrinieri et al. 1998) and a few faint ultraviolet (UV) sources suspected to be IBs (see Ferraro et al. 1997a, 1998, 2000a, 2000b) have been already discovered in the framework of an UV survey of a sample of GGCs carried out with the HST (see Ferraro, Paltrinieri & Cacciari 1999 for a review of the results).
Among GGCs, 47 Tuc is definitely the most promising target for this kind of investigation since it harbours a crowded zoo of stellar species, including BSSs, LMXBs, candidate CVs and MSPs. In particular, 21 BSSs have been discovered by Paresce et al. (1991, hereafter P91), and confirmed by De Marchi, Paresce & Ferraro (1992), Guhatakurta et al. (1992) and Gilliland et al. (1998). In addition, 20 MSPs have been detected by Camilo et al. (2000), 13 of which are in binary systems. Recently, Freire et al. (2001) presented accurate timing position for most of them. Moreover, the cluster hosts a number of unidentified X-ray sources (Verbunt & Hasinger 1998; Grindlay et al. 2001), a dwarf nova (V2, Paresce & De Marchi 1994; see also Shara et al. 1996) and a suspected interacting binary ($`V1`$) found in the error circle of a bright X-ray source by Paresce, De Marchi & Ferraro (1992)- see also De Marchi, Paresce & Ferraro (1993). Systematic searches for variability in the core of 47 Tuc have been performed by many groups (see Shara et al. 1996; Edmond et al. 1996; Albrow et al. 2001), also exploting the large data-base provided by the survey of Gilliland which was originally coinceved to search for planetary transits (Gilliland et al 2000).
Here we report on the results of recent HST UV observations of the core of 47 Tuc. These observations yielded the discovery of a large population of UV objects (§3) which significantly expand the list of the interesting objects (Tables 2, 3, & 4) known to reside in the core of 47 Tuc and surely will deserve a more detailed study when higher resolution/sensitivity observations and deeper imaging/spectroscopy will be available.
In addition, we have used the same data-set to search for the optical counterparts to LLGCXs and MSPs in the core of 47 Tuc. The results of this search and all the relative caveats are discussed in section (§4).

## 2 Observations and data analysis

The data-set used in the present work consist of a series of public HST/WFPC2 exposures mapping the core of the cluster 47 Tuc, taken through the filters F218W, F336W and F439W. The observing epochs, the filter mean wavelength and width, the integration times and the number of exposures are summaried in Table 1. The images have been retrieved from the public HST Archive after the on-the-fly recalibration with the most recent reference files and tables. Images taken throught the same filter have been combined and cleaned from cosmic ray hits using the automatic WFPC2 Archive Association Procedure. In all the selected observations, the core of 47 Tuc was roughly centered on the Planetary Camera (PC) chip, which has the highest angular resolution ($`0\stackrel{}{\mathrm{.}}045`$/px). We thus decided to focus our analysis on the PC frames only. Note that the F336W images have been taken at a different epoch and with a different telescope roll angle with respect to the F218W/F439W data-sets. For this reason, they cover only $`70\%`$ of the PC field of view imaged in the other two filters. The standard procedure described in Ferraro et al. (1997a) was adopted. In short, in order to perform a deep search for faint UV objects we used the combined F218W image (with an equivalent total exposure time of 3200 sec) as the reference frame for object detection. The same image was also used as a reference for the frame registration. The photometric reductions have been carried out using ROMAFOT (Buonanno et al. 1983), a package specifically developed to perform accurate photometry in crowded fields. The object list derived from the F218W image was then matched to the corresponding ones obtained from the F336W and F439W images. A final catalogue with the instrumental magnitude in each filter and coordinates has been compiled for all the identified stars. The instrumental magnitudes were finally transformed to the STMAG photometric system using Table 9 by Holtzman et al. (1995).

## 3 Results and Discussion

Figure 1 shows the $`(m_{F218W},m_{F218W}m_{F336W})`$ Color Magnitude Diagram (CMD) obtained from the photometry of more than 4 000 stars identified in the PC field of view of the combined F218W image. As it can be seen, the overall morphologies of the branches in this diagram are deformed with respect to the classical $`(V,BV)`$-plane. For clarity, the main evolutionary sequences are labelled in the diagram (see also Figure 1 in Ferraro, Paltrinieri & Cacciari 1999). Figure 2 shows the $`(m_{F218W},m_{F218W}m_{F439W})`$ CMD, where the F439W detections have been included.
As expected, the cluster emission at these wavelengths is dominated by hot stars. In particular, since 47 Tuc is a metal rich cluster with essentially a red Horizontal Branch (HB), hot HB stars are missing, and the brightest population turns to be composed of BSSs. Schematically, two prominent features appear in Figure 1 and are fully confirmed in the CMD of Figure 2: (1) the population of BSSs (highlighted by open circles) which defines a clean sequence spanning $`3.5`$ mag and is reminiscent of the sequences already observed in other UV-CMDs like, e.g., M3 (Ferraro et al. 1997) and M80 (Ferraro et al. 1999); (2) the large number of UV-excess stars (marked by filled triangles) which populate the extreme blue region of the diagram ($`m_{F218W}m_{F336W}<0`$). Although the observations presented here span three different epochs, an independent search for variability is beyond the aims of this paper and we refer to the extensive work by Shara et al. (1996), Edmonds et al. (1996, hereafter E96) and Albrow at al. (2001) in order to check for the variability of the UV objects found in this work.
In the following, we will describe and discuss separetely the results of our analysis of these peculiar populations.

### 3.1 Blue Straggler Stars

The presence of BSSs in the core of 47 Tuc is well known since the pioneering UV observations performed with the Faint Object Camera (FOC) by P91, who discovered 21 BSSs. Most of these identifications are now confirmed by the CMDs shown in Figure 1 and Figure 2, which unveil a total of 43 BSS with $`m_{F218W}<19.4`$. Magnitudes and positions for these objects are listed in Table 2. All the coordinates are in PC pixel units ($`0\stackrel{}{\mathrm{.}}045`$/px) and have been measured in the F218W image reference frame. In Table 2 we adopted the BSS identification code (BSS #) originally used by P91 and we followed this numeration for the other candidates successively discovered by Guhathakurtha et al. (1992, hereafter G92) and E96, as well as for the additional 20 new candidates discovered in the present work. The original identification number by G92 is also listed in column 8, together with the one used by E96 to flag variables objects (namely V1, V3, V6, V10, V11, V12). Some of these stars have been successively studied by Gilliland et al. (1998). In particular, V10 (our BSS-24) was classified as eclipsing variables by E96, while V12 (our BSS-16) was suggested to be a low amplitude SX Phe variable in a binary system. On the basis of its light curve shape, V11222a.k.a AKO9, as named in the original work by Auriere, Koch-Miramond & Ortolani (1989) (our BSS-26) was classified by E96 as an Algol eclipsing binary, with a period of $`1.1`$ day. The true nature of V11 is not completely understood. Indeed, while the CMD presented by E96 shows this object as “located near the main sequence turn-off”, our photometry shows that it is in the BSS region. In addition, its light curve is known to show anomalous features like, e.g., the rapid brightening detected by Minniti et al. (1997).
Only three BSSs discovered by P91 (namely BSS9, BSS11 and BSS17) have not been confirmed as BSS by our criteria. In particular, BSS11 is located in the region between the cluster Turn Off (TO) and the BSS sequence in Figure 2, but it is below the threshold assumed here ($`m_{F218W}=19.4`$). BSS9 (ID #2800 in our list) is the object at $`m_{F218W}18.1`$ and colour $`(m_{F218W}m_{F439W})3.3`$ located between the BSS sequence and the HB. BSS17 (ID #1798 in our list) has been classified as UV-excess star (UVE2, see Section 3.3) since its location in the CMD ($`m_{F218W}18.05`$; $`(m_{F218W}m_{F439W})0.9`$) is significantly bluer than that of the BSS sequence.

### 3.2 Young White Dwarfs

The extended colour baseline provided by the CMD in Figure 2 allows us to further investigate the nature of the UV-excess stars, identified in Figure 1. In particular, we note how the bluest side of the UV-excess star distribution seems to define a sort of sequence. This would suggest that at least part of the UV-excess stars could be white dwarfs, accordingly with the previous findings by (Paresce, De Marchi & Jedrzejewski 1995). To check this hypothesis we have computed the expected location of the WD cooling sequence in the $`(m_{F218W},m_{F218W}m_{F439W})`$ CMD. To do this, we run the theoretical cooling sequence for $`0.5M_{}`$ hydrogen-rich WDs (Wood 1995) through the standard IRAF simulation package SYNPHOT in order to derive the UV-colours and magnitudes for the theoretical WD sequence. A reddening of $`E(BV)=0.04`$ in the direction of 47 Tuc was assumed. The computed WD sequence is overplotted to the data in Figure 2. As it can be seen, the cooling sequence nicely fits the bluest side of the UV-excess distribution and fully supports the conclusion that about half of the UV-excess stars detected in the core of 47 Tuc are indeed WDs. In addition, by comparing the observed WD distribution with the expected location of 3 and 13 million year old cooling WDs (marked by the two open squares along the WD cooling sequence in Figure 2) we can conclude that the WD population discovered here basically consists of very young objects.
Though the sample presented in Figure 1 and Figure 2 is surely affected by incompleteness at least at the faint end of the sequence ($`m_{F218W}>20.5`$), we can try to perform a first order test to check if the number of the candidate bright WDs observed in the central region of 47 Tuc is in agreement with the theoretical expectations. To do this, we computed (accordingly with the suggestion by Richer et al. 1997) the number of WD expected in the PC field of view by comparison with the observed number of a tracer population with known lifetime (as the HB). Taking into account that in the field of view of the PC we observed $`100`$ HB stars, and assuming the HB lifetime $`t_{HB}=10^8yr`$ (Renzini & Fusi Pecci 1988), we derive from their eq. (1) the following relation for our sample:

$$N_{WD}(<m_{F218W}^{})=10^6t_{cool}(<m_{F218W}^{})$$
(1)
Here $`N_{WD}(<m_{F218W}^{})`$ is the number of WDs brighter than magnitude $`m_{F218W}^{}`$ and $`t_{cool}(<m_{F218W}^{})`$ is the corresponding cooling time in yrs. According to the Wood’s models (Wood 1995), $`t_{cool}(m_{F218W}<18.9)3\times 10^6`$ yr and $`t_{cool}(m_{F218W}<20.4)1.3\times 10^7`$ yr. Thus, Eq. (1) predicts $`N_{WD}(m_{F218W}<18.9)3`$ and $`N_{WD}(m_{F218W}<20.4)13.`$ Since from Figure 2 we count 3 and 12 WDs brighter than $`m_{F218W}=18.9`$ and $`20.4`$, respectively, we can conclude that the agreement with the theoretical prediction turns out to be exceptionally good. Thus, we can reasonably assume that all the objects with colour $`m_{F218W}m_{F439W}<1.6`$ are young cooling WD candidates.
Magnitudes, colours and positions for these stars are listed in Table 2.

### 3.3 UV-Excess stars

Although about half of the UV-excess stars detected in the core of 47 Tuc turn out to be young cooling WDs, there is still a significant number of objects in Figure 2 lying between the BSS sequence and the WD cooling sequence. A zoom of the ($`m_{F218W},m_{F218W}m_{F439W}`$) CMD is shown in Figure 3, where we have now marked with large empty triangles the WD candidates identified in the previous section and listed in Table 3. As it can be seen from Figure 3, there are at least a dozen of UV-excess stars (plotted as filled triangles) lying between the WD and the BSS sequence. In the following, we refere to these objects as UV-excess stars (hereafter UVE).
The identification numbers, magnitudes and positions for the 11 brightest ($`m_{F218W}<20.5`$) UVE stars are listed in Table 4. UVE-3 has been identified with the blue object V1 (Paresce, De Marchi & Ferraro 1992, hereafter PDF92), which is now clearly confirmed to be an object with strong UV emission. UVE-2 was originally classified as a BSS (BSS17) by P91. However, this object is bluer than the BSS sequence, an evidence also confirmed by previous CMDs of the field (see Figure 5 by De Marchi, Paresce & Ferraro (1993), where it clearly stands out from the BSS sequence). UVE-2 is also the variable PC1-V36 discussed by Albrow et al. (2001) and classified as a semi-detached binary.
In a recent review, Ferraro et al. (2000a) listed 10 UVE objects (associated to LLGCXs) detected in the core of 6 GGCs. The population discovered here is much larger than that previously found in any GGCs (see Paresce et al. 1991; Paresce & De Marchi 1994; Shara & Drissen 1995; Cool et al. 1995, 1998; Ferraro et al. 1997, 2000a, 2000b). Moreover, although we conservatively listed in Table 4 only the 11 brightest UVE sources, a population of faint ($`m_{F218W}>20.5`$) UVE candidates (marked as open squares) is clearly visible in Figure 3, with more than 30 UVE sources counted down to $`m_{F218W}21.3`$. Unfortunately, the faintness of these objects in all the images prevents to firmly assess their colours. Among the faint UVE stars, we have identified the dwarf nova V2 discovered by Paresce & De Marchi (1994) and the blue variable V3 (suspected to be a CV) discovered by Shara et al (1996). V2 ($`\mathrm{\#}5400`$ in our list) appears in a quiescence state at the epoch covered by the present obervations, as it is quite faint ($`m_{F218W}=20.7`$ and $`m_{F439W}=20.2`$) in both the F218W and F439W images. Also the variable V3 ($`\mathrm{\#}713`$ in our list) appears to be faint at the epoch of the observations: it is one of the faintest objects in the UV region of the CMD shown in Figure 1 and it is not visible in the F439W images.
From the number of bona-fide identifications and likely candidates pinpointed by our UV-CMDs, we conservatively conclude that there is a clear indication for the existence of a large population of faint UVE stars in the core of 47 Tuc. This conclusion is supported by additional, independent, observations. While we were writing this paper, a work by Knigge et al. (2001) reported on the possible detection of a large population of UVE stars ($`30`$) in the core of 47 Tuc from far-ultraviolet photometric and spectroscopic HST/STIS observations. The availability of a spectroscopic analysis suggested that these stars (or at least part of them) could be CVs. If this is the case, the UVE objects discovered here could represent the brightest extension of the long searched population of CVs predicted by the models (see Di Stefano & Rappaport 1994) and never found by previous observations.
However, alternative evolutionary scenarios exist, which can produce objects populating the same region of the CMD. For instance, Edmonds et al. (1999) suggested that at least one UVE star found in the center of NGC6397 (Cool et al. 1998) is actually a low-mass helium WD, resulting from the stripped core of a red giant (Castellani & Castellani 1993).

## 4 Absolute positions: limits to the search of optical counterparts to X-ray sources and MSP companions

Most of the exotic objects (BSSs, LMXBs, CVs, MSPs) hosted in the core of GGCs are thought to result from the evolution of various kinds of binary systems. In particular, when a binary system contains a compact object (like a neutron star or a white dwarf) and a close enough secondary, mass transfer can take place, producing an IB. The streaming gas, its impact on the compact object, the presence of an accretion disk can give such systems observational signatures which make them stand out above ordinary cluster stars. These signatures include X-ray emission, significant radiation in the ultraviolet (UV), emission lines, or rapid time variations. For this reason, the study of peculiars objects usually benefits from a comprehensive multiwavelength approach.
In the case of the UVE stars found in other GGCs, some were found coincident with X-ray sources (Ferraro et al. 1997b, 2000a) while others, like the ones discovered by Cool et al. (1995) in NGC6397, by Carson et al. (1999) in $`\omega `$-Cen and by Ferraro et al. (2000b) in the core of NGC6712, were found to exhibit significant H$`\alpha `$ emission. These multiwavelength observations allow one to classify UVE stars as high-confidence IB candidates and/or probable CVs. For this reason, it is particularly interesting here to investigate possible associations between the blue populations (BSSs, WDs, and UVE stars), with some of X-ray sources and MSP companions which are known to harbour in the core of 47 Tuc.
Since the first guess to claim an optical identification is based on the positional coincidence, $`X`$ and $`Y`$-pixel positions of the objects detected in the PC have been converted to $`RA`$ and $`DEC`$ using the task METRIC in the IRAF/STSDAS package, which also accounts for the geometric distorsions of the PC. Of course, the accuracy on the final coordinates is entirely dominated by the intrinsic error on the absolute coordinates of the GSC1.1 (Guide Star Catalog ) stars (Lasker et al. 1990), which are used both to point HST and to compute the astrometric solution in the focal plane. According to the current estimates, the mean uncertainty on the absolute positions quoted in the GSC1.1 is $`1\stackrel{}{\mathrm{.}}5`$ ($`3\sigma `$ level of confidence). Thus, we conservatively assume $`2^{\prime \prime }`$ as the global error on the absolute positions of our objects.
Note that such estimate is consistent with the average difference between the absolute positions of the same set of stars, as measured in independent HST pointings. For instance, G92 measured the absolute position of its star E to be $`RA(2000)_{G92}=00^\mathrm{h}\mathrm{\hspace{0.17em}24}^\mathrm{m}\mathrm{\hspace{0.17em}05}\stackrel{\mathrm{s}}{\mathrm{.}}33`$ and $`DEC(2000)_{G92}=72\mathrm{°}\mathrm{\hspace{0.17em}04}\mathrm{}\mathrm{\hspace{0.17em}54}\stackrel{}{\mathrm{.}}46`$, while star ($`\mathrm{\#}2187`$ in our catalog) turns out to be at $`RA(2000)=00^\mathrm{h}\mathrm{\hspace{0.17em}24}^\mathrm{m}\mathrm{\hspace{0.17em}04}\stackrel{\mathrm{s}}{\mathrm{.}}92`$ and $`DEC(2000)=72\mathrm{°}\mathrm{\hspace{0.17em}04}\mathrm{}\mathrm{\hspace{0.17em}54}\stackrel{}{\mathrm{.}}25`$, i.e. at $`2^{\prime \prime }`$ from the G92 determination, which fully confirms the uncertainty estimated above.

### 4.1 X-ray sources

Verbunt & Hasinger (1998, hereafter VH98) have recently re-analized all the ROSAT/HRI images of 47 Tuc obtained in the recent years and finally produced a list of accurate positions and fluxes for nine X-ray sources detected in the cluster core. However, while we were writing this paper Grindlay et al. (2001, hereafter G01) reported the discovery of additional $``$ 100 X-ray sources detected from CHANDRA observations. This catalog, listing 108 X-ray sources with $`L_X<10^{30.5}`$ erg $`s^1`$, represents the largest and most complete X-ray source catalog ever published in 47 Tuc. For this reason, in the following, we will adopt Table 1 of G01 as reference list for the positions of X-ray sources in 47 Tuc. Among these, 36 CHANDRA sources fall within the field of view of the PC.
In order account for RA/DEC off-sets between the HST coordinate system and the CHANDRA one, we have converted the coordinates listed in Table 1 of G01 in PC pixels using the WFPC2 astrometric solution and we have shifted the G01 catalog to match the position of the CHANDRA source W46 (X9 in VH98) with the one of its putative counterpart UVE-3 (V1 in PDF92). The choice of the V1/X9 pair as a fiducial position reference is justified by the work of many authors (see, for example, Geffer, Auriere & Koch-Miramond 1997 and VH98), which confirm the physical association between the two objects. The shift between the two coordinate systems was admittedly small: $`\delta X=1^{\prime \prime }`$ ($`20`$ PC pixels) and $`\delta Y=0\stackrel{}{\mathrm{.}}1`$ ($`2`$ PC  pixels).
After registering the objects coordinates on a unique reference grid, we cross correlated the positions of the X-ray sources with the ones derived here for the blue objects. In this way we found an acceptable ($`d<1\stackrel{}{\mathrm{.}}5`$) positional coincidence for at least 25 X-ray sources. The identification of all the possible optical counterparts to the X-ray sources of G01 are listed in Table 5 while their positions in the UV CMD are marked in Figure 4. Since we intend to use Table 5 as a working progress list and not a definitive counterparts catalog, in some cases we listed two UV-objects as possible counterparts to a single X-ray source (see the case of W28, W55, W80 and W98).
It is interesting to note that at least 12 possible optical counterpart to the X-ray sources are faint-UVE stars, suggesting, once more, the existence of a large population of faint IBs in the core of 47 Tuc. We confirm the possible association (proposed by VH98) between V2 and X19 (W30 in the G01 list), and we propose (in agreement with G01) the association of V3 and X10 (W27 in the G01 list). Other position-wise associations appears possible from our data-set (see Table 5 for the complete list). In particular, these are the ones between (i) UVE-2 (the bright blue object discussed in (§3.3)) and the X-ray source W75, (ii) AKO9 (BSS26 in our list - see Section 3.1) and source W36, (iii) UVE-6 and UVE-9 and sources W34 and W105, respectively.
However, it should be noted that all the positions of the putative optical counterparts could be still affected by residual uncertanties, since the shifts applied to match the V1/X9 pair represent only a first-order correction. Even though, establishing a physical connection supported only on the positional coincidence is risky, expecially because of the large number of peculiar objects found in the crowded core of 47 Tuc. In view of all these caveats, we conservatively conclude that the identifications proposed here are possible, and as such useful reference for future investigations, but not conclusive.

### 4.2 MSPs

Freire et al. (2001) have recently published accurate timing positions (typical uncertainty $`<0\stackrel{}{\mathrm{.}}1`$) for 15 MSPs in the core of 47 Tuc. Eight of these pulsars have been found in binary systems and, of these, 3 (namely MSP-I, MSP-O, MSP-T) lie in the PC field of view. Exchange interactions in the core of the cluster could in principle produce a significant number of systems comprising a MSP and a main sequence star. If the MSP is an active X-ray source, its energy emission could also affect such not-degenerate companion, perhaps making it a blue source. For this reason we cross-correlated the MSP positions with our master source list, and we have found interesting matches both with the CHANDRA X-ray source and the UV object lists. First, we confirmed the finding by G01 that three CHANDRA sources (namely W19, W105, W39) are nearly coincident with the three binary MSP (MSP-I, MSP-T, MSP-O, respectively) lying in the PC field of view. In addition, we found interesting matches with peculiar blue objects. In particular, MSP-I is at $`1\stackrel{}{\mathrm{.}}2`$ from a white dwarf (WD-4) and MSP-T is nearly coincident (at only $`0\stackrel{}{\mathrm{.}}3`$) with a faint ultraviolet excess object (UVE-9). The case of $`MSPO`$ is more complex. Only a TO star (namely $`\mathrm{\#}2167`$) has been found at $`0\stackrel{}{\mathrm{.}}4`$ from the nominal position of this $`MSP`$. However, $`MSPO`$ is located in the region of the peculiar binary AKO9 (BSS26 in our list, see Section 3.1). Unfortunately this objects is relatively far away ($`2^{\prime \prime }`$) from the nominal position of $`MSPO`$ to be considered a promising optical counterpart candidate to this MSP. Moreover, the matching with the X-ray CHANDRA catalog suggests that AKO9 is nearly coincident with another CHANDRA source: W36 (see Table 5). Thus, the physical association between $`MSPO`$ and the peculiar binary AKO9 appears unlikely. On the other hand, the only other blue object found in its vicinity (at $`1\stackrel{}{\mathrm{.}}5`$) is AKO6 (which corresponds to BSS2 in our list). This object did not show significant variability, since it is not coincident with any of the 13 variables detected by E96.
The case of a possible association between MSP-I and WD-4 is probably the more intriguing since MSP companions in binary systems are indeed expected to be WDs (e.g. see the reviews of Verbunt 1993 and Phinney & Kulkarni 1994), with cooling ages longer than at least a few $`10^8`$ yrs (Hansen & Phinney 1998). According to its position along the WD cooling sequence, WD-4 seems to be a quite young object, approximately $`10^6`$ yr old. It is thus unlikely that it is the companion to MSP-I. Although the irradiation of the surface layers of the WD by the MSP beam could modify its photometric properties, making it brighter and slightly bluer (e.g. D’Antona 1995 for a review) and eventually producing an apparent rejuvanation, this would require an unlikely variation of 4-5 magnitudes to reconcile the cooling age of $`WD4`$ with the expected cooling age for a typical MSP companion. Moreover, the induced brightening of the WD should be recognizable by a strong modulation in its light curve, while its heated surface rotates in and out of the line of sight (see e.g. Stappers et al. 1999). Conversely, from the analysis of the F218W images we have not found any evidence for luminosity variation larger than a few tenths of magnitude for $`WD4`$. However, it should be noted that the images analyzed here do not allow a proper time coverage of the orbital period of the MSP-I system. In fact, the F218W images cover less than $`16\%`$ of the $`P5.5h`$ period estimated by Freire et al (2001). For this reason, we cannot exclude variability for this system.
Finally, UVE-9 is closely blended with a main sequence star, and its photometry turns presently to be too uncertain for allowing further speculations.
Table 6 lists the absolute positions for the three MSPs and for the blue sources lying nearby. However, in none of the above cases the positional coincidence alone is an argument strong enough to support the identification. Indeed, astrophysical and statistical considerations suggest that all of the above positional coincidences are probably due to chance, thus, probably the optical counterparts to these MSPs are much fainter than the detection limit of the observations analyzed here.
The probabilities of a physical connection between these 3 binary MSP systems and the blue objects in their proximity are further reduced if one examines also the optical sources located in the vicinity of the single, isolated, MSPs detected in the core of 47 Tuc and included in the field of view covered by the PC. Although no optical counterpart is expected for these objects, it appears (see Table 6) that two of them (over the three non-binary MSP listed by Freire et al. 2001), namely MSP-F and MSP-L, are positionally coincident, within the above uncertainties, with WD-8 and BSS-29, respectively.
While reaching fainter limiting magnitudes would certainly help the search to MSP companions, the current uncertainties on the absolute PC astrometry would still represent the major problem, suggesting that even the availability of much deeper exposures would not solve the ambiguities. We can use Eq. (1) in order to compute the expected number of WD (younger than a given cooling time) lying in the fraction of the 47 Tuc core covered by the PC. In doing this, we assumed a WD cooling age of 1 Gyr, i.e. at the median of the WD cooling age distribution of $`10^810^{10}`$ yrs as suggested by some $`WD+MSP`$ systems studied in the field (see Hansen & Phinney 1998; Schönberner, Driebe & Blöcker 2000). Adopting the Wood (1995) models, this cooling age corresponds to an absolute magnitude $`M_V13`$ (which yealds $`m_{F218W}27`$ at the distance of 47 Tuc). Under these assumptions, Eq. (1) gives a total of $`1000`$ WDs with $`m_{F218W}\stackrel{<}{}27`$. Assuming that $`2`$ ′′is the typical uncertainty in registering the MSP coordinates on the PC frame, the previous number implies an average of 6 WDs brighter than $`m_{F218W}=27`$ within the uncertainty region. The situation can certainly improved by obtaining a new astrometric solution for the PC using the GSC2.2 (McLean et al. 2001), which has an average absolute astrometric accuracy of $`0\stackrel{}{\mathrm{.}}5`$ i.e. three times better than the one of the GSC1.1. However, even a remarkable improvement of a factor of 3 in the absolute astrometry of the PC will reduce the probability of a chance coincidence between the MSP and a 1 Gyr-old WD, only to a $`70\%`$, still too high to claim a position-wise identification.
In summary, the conspiracy of the overcrowded field in the core of 47 Tuc and the extreme faintness of the expected optical counterpart (an old WD) of the companion to a MSP makes extremely difficult a firm identification using only photometric colors and positioning. Further hints will be necessary, such as the discovery of photometric modulations due to orbital motion, peculiarities in the optical and UV companion candidate spectra and/or emissivity at other wavelengths.

## 5 Conclusions

Using data collected with the Planetary Camera of HST, we have more than doubled the sample of Blue Stragglers detected in the core of the globular cluster 47 Tuc and have reported on the discovery of a large number of UV stars, with the hottest of them being probably young WDs. The others UV objects are anomalous UV-excess stars whose true nature and evolution cannot be satifactorily assessed yet. In fact many different evolutionary mechanisms involving stellar collisions and interactions could account for them. High resolution, deeper imaging and spectroscopic observations in the UV (as those preliminary presented by Knigge et al. 2001) are required to discriminate among the various models. However, the large number of positional coincidences with X-ray sources (from the recent CHANDRA catalog) indeed suggests that part of them could be IBs. In particular, a significant number of X-ray sources ($`30\%`$) have been found to be possibly associated with the faint UVE population discovered here, supporting the presence of a large population of faint CV in the core of this cluster.
We have also explored the possibility of identifying some of the detected blue objects as the optical counterparts to millisecond pulsar companions hosted in the core of the cluster. However, although a few positional coincidences have been found, none of them is suggestive yet of a physical association.

The financial support of the Agenzia Spaziale Italiana (ASI) and of the Ministero della Università e della Ricerca Scientifica e Tecnologica (MURST) to the project Stellar Dynamics and Stellar Evolution in Globular Clusters is kindly acknowledged.


format: text

text:
# Direct Investigation of Superparamagnetism in Co Nanoparticle Films

## Abstract

A direct probe of superparamagnetism was used to determine the complete anisotropy energy distribution of Co nanoparticle films. The films were composed of self-assembled lattices of uniform Co nanoparticles of 3 nm or 5 nm in diameter, and a variable temperature scanning-SQUID microscope was used to measure temperature-induced spontaneous magnetic noise in the samples. Accurate measurements of anisotropy energy distributions of small volume samples will be critical to magnetic optimization of nanoparticle devices and media.

There has been a recent explosion of research into the fabrication and understanding of assemblies of magnetic nanoparticles. Increasing ability to controllably produce superlattices of these nanoparticles with uniform material properties will have important consequences on technology and our basic comprehension of magnetism. Technologically, nanoparticle films with sharp distributions of magnetic properties can be used to tailor nanodevices and high-density recording media with reliable, reproducible characteristics. Scientifically, a uniform array of identical particles is an ideal model system for the study of single-particle and interparticle magnetic properties, without interference from broad or irregular volume and lattice-spacing distributions.

Although most magnetic nanoparticle technological applications depend on the ferromagnetic state of the particles, understanding their superparamagnetic state is crucial to controlling their behavior. For nanoparticles, very small absolute deviations in particle size can lead to large changes in blocking temperature, interfering with device function at operational temperatures. Fundamental magnetic parameters like anisotropy energy and flipping times can be extracted from superparamagnetic data, and these parameters can in turn be used to predict the magnetic response of a sample or device. Superparamagnetic behavior is a primary enemy to faithful operation of nanodevices and nanoparticle memories, so it is vital that an accurate and complete method for extracting magnetic distributions from nanoparticle systems be developed. With such methods, magnetic optimization of these technologies will be hastened.

We have directly probed superparamagnetism in films of self-assembled cobalt nanoparticles by measuring the spontaneous magnetic noise arising from these films as a function of temperature, a method some have pursued to measure nanoparticle properties. Nanoparticle spin flips, induced by thermal energy, are directly sensed by a micro-SQUID, giving statistical information on the magnetic properties of millions of particles in the array. Not only can the average anisotropy energy and width be determined, but it is shown below how the entire magnetic anisotropy energy distribution can be extracted, a complete magnetic fingerprint. The extracted distribution is shown to be self-consistent, closely reproducing the data from which it was derived. The micro-SQUID noise technique described here is ideally suited for the statistical study of nanoparticle films because it can determine the anisotropy distribution without requiring the easy axes of the nanoparticles to be aligned and has the magnetization sensitivity to investigate submicron area samples only a nanometer thick.

The samples investigated were films of Co nanoparticles deposited on thermally oxidized silicon substrates. Monodisperse Co nanoparticles with the multiply-twinned face-centered cubic structure (mt-fcc structure) were prepared using high-temperature solution-phase synthesis. The size of the nanoparticles can be controlled by the details of synthesis and separation techniques, and TEM studies indicate $`\sigma <5\%`$ for the diameter distributions of these particles. Each nanoparticle was produced with an oleic acid coat of 2 nm thickness which served to stabilize the particles, prevent oxidation, and control interparticle spacing. The nanoparticles were dispersed in hexane and deposited on oxidized silicon

substrates, where the hexane was allowed to slowly evaporate, leaving 5-10 layers of particles. The Co nanoparticles self-assemble on the substrates into close-packed arrays with lattice spacing approximately (d + 4 nm), where d is the diameter of the nanoparticles. In this study, samples with nominal nanoparticle diameters of 3 nm and 5 nm were investigated. Figure 1 shows a TEM image of a superlattice of 5 nm particles on a thin layer of silicon-oxide.

Samples were measured using a variable temperature scanning-SQUID microscope, employing a niobium SQUID with an integrated 17.8$`\mu `$m square pickup loop. This SQUID was modulated at 100 kHz using a standard flux modulation and feedback method. The ac output from the SQUID electronics was fed into an HP35665A digital signal analyzer to study the magnetic activity of the nanoparticles at frequencies from 10-10000 Hz and temperatures from 4-100 K. The power spectral density of the SQUID output voltage was recorded and could be easily converted to find the magnetic noise power density produced by the sample. The SQUID could be moved into and out of contact with the sample, so background signals and the frequency response of the SQUID could be separated from the sample signal. Measurements were made in a shielded room and the sample space had ambient fields of about 1 $`\mu `$T. Data were taken in near-contact with the nanoparticles ($`3\mu m`$ away) and at heights of 100-500 $`\mu `$m. In addition, the magnetization-temperature curves of the samples were characterized with a Quantum Magnetics MPMS system before execution of the noise measurement.

In the simple case of a bistable, single-domain particle with no interactions, the magnetic noise power measured at a temperature T, cyclic frequency $`\omega `$ and distance d away is :

$$S_B(\omega ,T)=\left(\frac{\mu _o}{4\pi }\frac{MV}{d^3}\right)^2\frac{\tau }{1+\omega ^2\tau ^2}$$
(1)
where M is the particle magnetization, V is the particle volume and $`\tau `$ is the average cyclic flipping time for the moment. This flipping time follows the standard activated form $`\tau =\tau _oexp(U/k_BT)`$, where U is the anisotropy energy of the particle; U=KV, where K is the effective anisotropy constant. The noise power is flat at low frequencies with a falloff near $`\tau ^1`$. As a function of temperature, $`S_B`$ displays a single peak centered at $`T_{peak}=U/k_Blog(\omega \tau _o)`$. Simply put, $`S_B(T)`$ peaks when the measurement frequency equals the inverse flipping time; i.e., when $`\omega =\tau ^1=\tau _o^1exp(U/k_BT)`$.

For a distribution D(U) of particle anisotropy energies, one finds for the noise power (approximating with use of an average prefactor to the Lorentzian in Eq. 1):

$$S_B(\omega ,T)_0^{\mathrm{}}\frac{\tau _oe^{U/k_BT}}{1+\omega ^2\tau _o^2e^{2U/k_BT}}D(U)𝑑U$$
(2)
A peaked distribution will exhibit a peaked noise power as a function of temperature, just as in the single particle case, but the peak will be broadened. Approximate average values $`\overline{\tau _o}`$ and $`\overline{U}`$ for the flipping time and anisotropy energy can be found by assuming this peak occurs at $`T_{peak}=\overline{U}/k_Blog(\omega \overline{\tau _o})`$.

Results of noise power as a function of frequency from a film of 5 nm diameter nanoparticles are shown for various temperatures in figure 2. As expected, noise decreases

monotonically in the frequency window for each particular temperature, having an approximate form of $`S_Bf^\alpha `$. For the 5 nm nanoparticles, $`\alpha `$ decreases from about 1.0 to 0.6 as temperature is increased from 25 K to 85 K, as shown in the inset to figure 2. Noise power as a function of temperature for both 3 nm and 5 nm diameter nanoparticle samples is shown in figure 3 for various frequencies. Each curve peaks at a temperature that increases as the measurement frequency increases. The 3 nm sample peaks near T=20 K, and the 5 nm sample peaks near T=55 K. These temperatures approximate the average superparamagnetic blocking temperature for each sample and agree with the peak location in the zero-field-cooled magnetization-temperature curves measured on each sample. In the following analysis, it is assumed that the noninteracting form of the equations for $`S_B`$ and $`\tau `$ (with $`\tau _o`$ and U possibly renormalized by interactions) is sufficient to describe the behavior of the system.

Average values for $`\tau _o`$ and U can be extracted from the noise data peak locations as discussed above, and a least squares fit was made of the log($`\omega `$) vs. $`T_{peak}^1`$ data to find these parameters for the two samples. For the 3 nm particles, the attempt time $`2\pi \overline{\tau _o}`$ and anisotropy energy $`\overline{U}`$ are $`2.16\times 10^{11}`$ s and $`5.22\times 10^{21}`$ J, respectively. The average attempt time is $`5.22\times 10^{11}`$ s and average anisotropy energy is $`1.35\times 10^{20}`$ J for the 5 nm particles. In the determination of the full energy distribution to follow, the only input parameter will be the approximate value calculated for the attempt time.

By rewriting Eq. 2 as an infinite series, the complete anisotropy energy can be easily extracted from the noise power data under certain conditions. Let $`F(U)=\frac{\tau _oe^{U/k_BT}}{1+\omega ^2\tau _o^2e^{2U/k_BT}}`$, then Eq. 2 can be expressed as $`S_B(\omega ,T)_0^{\mathrm{}}F(U)D(U)𝑑U`$. F(U) is a function peaked at $`\stackrel{~}{U}=k_BTlog(\omega \tau _o)`$ with width of approximately $`k_BT`$, falling quickly to zero outside this window. D(U) is slowly varying with respect to $`k_BT`$ in this region. Expanding D(U) in a power series and evaluating the F(U)- containing integrals (integrals of the form $`_0^{\mathrm{}}\frac{x^{2n}}{cosh(ax)}𝑑x`$ ), one finds :

$$S_B(\omega ,T)\frac{1}{\omega }\underset{n=0}{\overset{\mathrm{}}{}}\frac{|E_{2n}|}{(2n)!}\left(\frac{\pi k_BT}{2}\right)^{2n+1}D^{(2n)}(\stackrel{~}{U})$$
(3)
where $`E_m`$ is the $`m^{th}`$ Euler number. As long as D(U) is very slowly varying over a scale of $`k_BT`$ around $`\stackrel{~}{U}`$ (the width of D(U) is much more than $`k_BT`$ around $`\stackrel{~}{U}`$), the first term alone will give a good approximation of the noise power. Thus, the distribution can be found from the noise power according to:

$$D(k_BTlog(\omega \tau _o))\frac{2\omega }{\pi k_BT}S_B(\omega ,T)$$
(4)
If this approximation was not good enough, an iterative procedure using higher order terms could be used to calculate D(U) from the noise power.

The noise power data as a function of temperature for both the 3 nm and 5 nm samples were used to derive their anisotropy energy distributions, according to Eq. 4. At each frequency the distribution was calculated and normalized to make the total probability under the distribution equal to unity. Figure 4 shows all the data for numerous frequencies plotted together. For each sample, the data defines a single universal curve, the anisotropy energy distribution. The distribution for the 3 nm particles reaches a peak at $`4.35\times 10^{21}`$ J, has a full-width half-maximum (FWHM) of about 110%, and has a tail at high energies. For the 5 nm particles, the distribution is more symmetric, has a peak at $`1.22\times 10^{20}`$ J, and a FWHM of about 64%.

To demonstrate the reliability of these extracted distributions, it is important to show they can reproduce the data from which they were derived. By plugging the derived distributions into Eq. 2, one can generate the calculated form for the noise power. The dotted lines in figures 2 and 3 show these generated curves, and they provide excellent fits to all the data.

The derived energy distributions are wider than the apparent volume distributions, which generally appear Gaussian with $`\sigma <15\%`$ (FWHM $`<35\%`$). As it is more difficult to stabilize uniform smaller particles, it is not surprising that the distribution for the 3 nm particles is wider than that of the 5 nm particles and shows a tail indicative of a noticeable fraction of larger diameter particles. If one assumes the energy peak for each sample is that of a single-domain, spherical nanoparticle of the nominal diameter, then $`K_{3nm}=3.08\times 10^5J/m^3`$ and $`K_{5nm}=1.87\times 10^5J/m^3`$, in general agreement with other values derived for mt-fcc Co nanoparticles. It is believed that surface anisotropy dominates in near-spherical nanoparticles (and is uniaxial, even for cubic crystal structures), and in this case the anisotropy constant is expected to scale as the inverse of particle diameter . In this study the nominal ratio of the inverse particle diameters of the two types of samples measured is 1.67, while the ratio in anisotropy constants is 1.65, in good agreement with the relation expected for surface anisotropy. Various reasons could account for energy distributions significantly wider than nanoparticle volume distributions, including: existence of nonuniformity in the surface anisotropy; the actively magnetic regions of the particles do not correspond with their full TEM-defined sizes; distributions exist in the values of the crystalline, strain, or shape anisotropies across the nanoparticles; or dipolar interactions between nanoparticles are significant.

We investigated the possible effects of dipolar interactions on the nanoparticle films through Monte Carlo simulations on close-packed monolayers of particles. The nanoparticles are given random easy axis directions and allowed to relax to a low energy state through the rotation and flipping of nanoparticle magnetizations. Results indicate that interparticle dipolar energies are relatively insignificant in the case of the 3 nm particles but could account for about 15% of the full width spread in the flipping energy distribution of the 5 nm particles. In the case where the 5 nm particles are given a Gaussian diameter distribution with $`\sigma =5\%`$, the simulation renders an anisotropy energy distribution with a width of 51%, accounting for a significant part of the 64% width measured on the 5 nm diameter sample.

We have presented data gathered by a direct probe of superparamagnetism in a magnetic nanoparticle system. The noise power technique with a variable temperature micro-SQUID can be used to extract precise magnetic energy information on technologically important magnetic nanoparticle films and devices of small area and thickness. Even for films with sharp volume distributions of nanoparticles, our magnetic measurement shows that the magnetic distributions can be relatively wide. Thus, such a technique is essential to optimize particle growth conditions for magnetic uniformity, critical for any application. A similar scanning-SQUID microscope system employing a high-$`T_c`$ SQUID could be used to characterize films at room temperature. The noise measurement technique also holds promise as a sensitive method to probe and understand interactions in nanoparticle superlattices as the interparticle spacing is changed.


text:
# Enumerating permutations avoiding a pair of Babson-Steingrímsson patterns

## 1. Introduction

Classically, a pattern is a permutation $`\sigma 𝒮_k`$, and a permutation $`\pi 𝒮_n`$ avoids $`\sigma `$ if there is no subword of $`\pi `$ that is order equivalent to $`\sigma `$. For example, $`\pi 𝒮_n`$ avoids $`132`$ if there is no $`1i<j<kn`$ such that $`\pi (i)<\pi (k)<\pi (j)`$. We denote by $`𝒮_n(\sigma )`$ the set permutations in $`𝒮_n`$ that avoids $`\sigma `$.

The earliest result to an instance of finding $`|𝒮_n(\sigma )|`$ seems to be MacMahon’s enumeration of $`S_n(123)`$, which is implicit in chapter V of . The first explicit result seems to be Hammersley’s enumeration of $`S_n(321)`$ in . In \[7, Ch. 2.2.1\] and \[8, Ch. 5.1.4\] Knuth shows that for any $`\sigma S_3`$, we have $`|S_n(\sigma )|=C_n=\frac{1}{n+1}\left(\genfrac{}{}{0pt}{}{2n}{n}\right)`$, the $`n`$th Catalan number. Later Simion and Schmidt  found the cardinality of $`𝒮_n(P)`$ for all $`P𝒮_3`$.

In  Babson and Steingrímsson introduced generalized permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. The motivation for Babson and Steingrímsson in introducing these patterns was the study of Mahonian statistics. Two examples of such patterns are $`1\text{ }32`$ and $`13\text{ }2`$ ($`1\text{ }32`$ and $`13\text{ }2`$ are of type $`(1,2)`$ and $`(2,1)`$ respectively). A permutation $`\pi =a_1a_2\mathrm{}a_n`$ avoids $`1\text{ }32`$ if there are no subwords $`a_ia_ja_{j+1}`$ of $`\pi `$ such that $`a_i<a_{j+1}<a_j`$. Similarly $`\pi `$ avoids $`13\text{ }2`$ if there are no subwords $`a_ia_{i+1}a_j`$ of $`\pi `$ such that $`a_i<a_j<a_{i+1}`$.

Claesson  presented a complete solution for the number of permutations avoiding any single pattern of type $`(1,2)`$ or $`(2,1)`$ as follows.

###### Proposition 1 (Claesson ).

Let $`n`$. We have

$$|𝒮_n(p)|=\{\begin{array}{cc}B_n\hfill & \text{if }p\{1\text{ }23,3\text{ }21,12\text{ }3,32\text{ }1,1\text{ }32,3\text{ }12,21\text{ }3,23\text{ }1\},\hfill \\ C_n\hfill & \text{if }p\{2\text{ }13,2\text{ }31,13\text{ }2,31\text{ }2\},\hfill \end{array}$$

where $`B_n`$ and $`C_n`$ are the $`n`$th Bell (# ways of placing $`n`$ labelled balls into $`n`$ indistinguishable boxes, see \[10, A000110\]) and Catalan numbers, respectively.

In addition, Claesson gave some results for the number of permutations avoiding a pair of patterns.

###### Proposition 2 (Claesson ).

Let $`n`$. We have

$$|𝒮_n(1\text{ }23,\mathrm{\hspace{0.17em}12}\text{ }3)|=B_n^{},|𝒮_n(1\text{ }23,\mathrm{\hspace{0.17em}1}\text{ }32)|=I_n,\text{ and }|𝒮_n(1\text{ }23,\mathrm{\hspace{0.17em}13}\text{ }2)|=M_n,$$

where $`B_n^{}`$ is the $`n`$th Bessel number (# non-overlapping partitions of $`[n]`$ (see )), $`I_n`$ is the number of involutions in $`𝒮_n`$, and $`M_n`$ is the $`n`$th Motzkin number (# ways of drawing any number of nonintersecting chords among $`n`$ points on a circle, see \[10, A001006\]).

This paper is organized as follows. In Section 2 we define the notion of a pattern and some other useful concepts. For a proof of Proposition 1 we could refer the reader to . We will however prove Proposition 1 in Section 3 in the context of binary trees. The idea being that this will be a useful aid to understanding of the proofs of Section 4. In Section 4 we give a solution for the number of permutations avoiding any given pair of patterns of type $`(1,2)`$ or $`(2,1)`$. These results are summarized in the following table.

$`\begin{array}{ccccccccccc}& & & & & & & & & & \\ \mathrm{\#}\text{ pairs}& 2& 2& 4& 34& 8& 2& 4& 4& 4& 2\\ & & & & & & & & & & \\ |𝒮_n(p,q)|& 0& 2(n1)& \left(\genfrac{}{}{0pt}{}{n}{2}\right)+1& 2^{n1}& M_n& a_n& b_n& I_n& C_n& B_n^{}\end{array}`$    Here   $`{\displaystyle \underset{n0}{}}a_nx^n`$ $`={\displaystyle \frac{1}{1xx^2\underset{n0}{}B_n^{}x^n}}`$  and   $`b_{n+2}`$ $`=b_{n+1}+{\displaystyle \underset{k=0}{\overset{n}{}}}\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right)b_k.`$

Finally, in Section 5 we conjecture the sequences $`\{\mathrm{\#}𝒮_n(P)\}_n`$ for sets $`P`$ of three or more patterns of type $`(1,2)`$ or $`(2,1)`$.

## 2. Preliminaries

By an *alphabet* $`X`$ we mean a non-empty set. An element of $`X`$ is called a *letter*. A *word* over $`X`$ is a finite sequence of letters from $`X`$. We consider also the *empty word*, that is, the word with no letters; it is denoted by $`ϵ`$. Let $`w=x_1x_2\mathrm{}x_n`$ be a word over $`X`$. We call $`|w|:=n`$ the *length* of $`w`$. A *subword* of $`w`$ is a word $`v=x_{i_1}x_{i_2}\mathrm{}x_{i_k}`$, where $`1i_1<i_2<\mathrm{}<i_kn`$.

Let $`[n]:=\{1,2,\mathrm{},n\}`$ (so $`[0]=\mathrm{}`$). A *permutation* of $`[n]`$ is bijection from $`[n]`$ to $`[n]`$. Let $`𝒮_n`$ be the set of permutations of $`[n]`$, and $`𝒮=_{n0}𝒮_n`$. We shall usually think of a permutation $`\pi `$ as the word $`\pi (1)\pi (2)\mathrm{}\pi (n)`$ over the alphabet $`[n]`$.

Define the *reverse* of $`\pi `$ by $`\pi ^r(i)=\pi (n+1i)`$, and define the *complement* of $`\pi `$ by $`\pi ^c(i)=n+1\pi (i)`$, where $`i[n]`$.

For each word $`w=x_1x_2\mathrm{}x_n`$ over the alphabet $`\{1,2,3,4,\mathrm{}\}`$ without repeated letters, we define the *reduction* of $`w`$, which we denote $`\mathrm{red}(w)`$, by

$$\mathrm{red}(w)=a_1a_2\mathrm{}a_n,\text{ where }a_i=|\{j[n]:x_jx_i\}|.$$

Equivalently, $`\mathrm{red}(w)`$ is the permutation in $`𝒮_n`$ which is order equivalent to $`w`$. For example, $`\mathrm{red}(2659)=1324`$.

We may regard a *pattern* as a function from $`𝒮_n`$ to the set $``$ of natural numbers. The patterns of main interest to us are defined as follows. Let $`xyz𝒮_3`$ and $`\pi =a_1a_2\mathrm{}a_n𝒮_n`$, then

$$(x\text{ }yz)\pi =|\{a_ia_ja_{j+1}:\mathrm{red}(a_ia_ja_{j+1})=xyz,1i<j<n\}|$$

and similarly $`(xy\text{ }z)\pi =(z\text{ }yx)\pi ^r`$. For instance

$$(1\text{ }23)\mathrm{\hspace{0.17em}491273865}=|\{127,138,238\}|=3.$$

A pattern $`p=p_1\text{ }p_2\text{ }\mathrm{}\text{ }p_k`$ containing exactly $`k1`$ dashes is said to be of type $`(|p_1|,|p_2|,\mathrm{},|p_k|)`$. For example, the pattern $`142\text{ }5\text{ }367`$ is of type $`(3,1,3)`$, and any classical pattern of length $`k`$ is of type $`(\underset{k}{\underset{}{1,1,\mathrm{},1}})`$.

We say that a permutation $`\pi `$ *avoids* a pattern $`p`$ if $`p\pi =0`$. The set of all permutations in $`𝒮_n`$ that avoids $`p`$ is denoted $`𝒮_n(p)`$ and, more generally, $`𝒮_n(P)=_{pP}𝒮_n(p)`$ and $`𝒮(P)=_{n0}𝒮_n(P)`$.

We extend the definition of reverse and complement to patterns the following way. Let us call $`\pi `$ the *underlying permutation* of the pattern $`p`$ if $`\pi `$ is obtained from $`p`$ by deleting all the dashes in $`p`$. If $`p`$ is a pattern with underlying permutation $`\pi `$, then $`p^c`$ is the pattern with underlying permutation $`\pi ^c`$ and with dashes at precisely the same positions as there are dashes in $`p`$. We define $`p^r`$ as the pattern we get from regarding $`p`$ as a word and reading it backwards. For example, $`(1\text{ }23)^c=3\text{ }21`$ and $`(1\text{ }23)^r=32\text{ }1`$. Observe that

$`\sigma 𝒮_n(p)`$ $`\sigma ^r𝒮_n(p^r)`$
$`\sigma 𝒮_n(p)`$ $`\sigma ^c𝒮_n(p^c).`$
These observations of course generalize to $`𝒮_n(P)`$ for any set of patterns $`P`$.

The operations reverse and complement generates the dihedral group $`D_2`$ (the symmetry group of a rectangle). The orbits of $`D_2`$ in the set of patterns of type $`(1,2)`$ or $`(2,1)`$ will be called *symmetry classes*. For instance, the symmetry class of $`1\text{ }23`$ is

$$\{1\text{ }23,3\text{ }21,12\text{ }3,32\text{ }1\}.$$

We also talk about symmetry classes of sets of patterns (defined in the obvious way). For example, the symmetry class of $`\{1\text{ }23,3\text{ }21\}`$ is

$$\{\{1\text{ }23,3\text{ }21\},\{32\text{ }1,12\text{ }3\}\}.$$

A set of patterns $`P`$ such that if $`p,p^{}P`$ then, for each $`n`$, $`|𝒮_n(p)|=|𝒮_n(p^{})|`$ is called a *Wilf-class*. For instance, by Proposition 1, the Wilf-class of $`1\text{ }23`$ is

$$\{1\text{ }23,3\text{ }21,12\text{ }3,32\text{ }1,1\text{ }32,3\text{ }12,21\text{ }3,23\text{ }1\}.$$

We also talk about Wilf-classes of sets of patterns (defined in the obvious way). It is clear that symmetry classes are Wilf-classes, but as we have seen the converse does not hold in general.

In what follows we will frequently use the well known bijection between increasing binary trees and permutations (e.g. see \[12, p. 24\]). Let $`\pi `$ be any word on the alphabet $`\{1,2,3,4,\mathrm{}\}`$ with no repeated letters. If $`\pi ϵ`$ then we can factor $`\pi `$ as $`\pi =\sigma \widehat{0}\tau `$, where $`\widehat{0}`$ is the minimal element of $`\pi `$. Define $`T(ϵ)=`$ (a leaf) and

$$T(\pi )=\text{}$$

In addition, we define $`U(t)`$ as the unlabelled counterpart of the labelled tree $`t`$. For instance

$`T(316452)=\text{}`$ $`UT(316452)=\text{}`$

Note that, for sake of simplicity, the leafs are not displayed.

## 3. Single patterns

There are $`3`$ symmetry classes and $`2`$ Wilf-classes of single patterns. The details are as follows.

###### Proposition 3 (Claesson ).

Let $`n`$. We have

$$|𝒮(p)|=\{\begin{array}{cc}B_n\hfill & \text{if }p\{1\text{ }23,3\text{ }21,12\text{ }3,32\text{ }1\},\hfill \\ B_n\hfill & \text{if }p\{1\text{ }32,3\text{ }12,21\text{ }3,23\text{ }1\},\hfill \\ C_n\hfill & \text{if }p\{2\text{ }13,2\text{ }31,13\text{ }2,31\text{ }2\},\hfill \end{array}$$

where $`B_n`$ and $`C_n`$ are the $`n`$th Bell and Catalan numbers, respectively.

###### Proof of the first case.

Note that

$$\sigma 1\tau 𝒮(1\text{ }23)\{\begin{array}{cc}\mathrm{red}(\sigma )𝒮(1\text{ }23)\hfill & \\ \mathrm{red}(\tau )𝒮(12)\hfill & \\ \sigma 1\tau 𝒮\hfill & \end{array}$$

where of course $`𝒮(12)=\{ϵ,1,21,321,4321,\mathrm{}\}`$. This enables us to give a bijection $`\mathrm{\Phi }`$ between $`𝒮_n(1\text{ }23)`$ and the set of partitions of $`[n]`$, by induction. Let $`\mathrm{\Phi }(ϵ)`$ be the empty partition. Let the first block of $`\mathrm{\Phi }(\sigma 1\tau )`$ be the set of letters of $`1\tau `$, and let the rest of the blocks of $`\mathrm{\Phi }(\sigma 1\tau )`$ be as in $`\mathrm{\Phi }(\sigma )`$. ∎

The most transparent way to see the above correspondence is perhaps to view the permutation as an increasing binary tree. For instance, the tree

$$T(649752183)=\text{}$$

corresponds to the partition $`\{\{1,3,8\},\{2\},\{4,5,7,9\},\{6\}\}`$.

###### Proof of the second case.

This case is analogous to the previous one. We have

$$\sigma 1\tau 𝒮(1\text{ }32)\{\begin{array}{cc}\mathrm{red}(\sigma )𝒮(1\text{ }32)\hfill & \\ \mathrm{red}(\tau )𝒮(21)\hfill & \\ \sigma 1\tau 𝒮\hfill & \end{array}$$

We give a bijection $`\mathrm{\Phi }`$ between $`𝒮_n(1\text{ }23)`$ and the set of partitions of $`[n]`$, by induction. Let $`\mathrm{\Phi }(ϵ)`$ be the empty partition. Let the first block of $`\mathrm{\Phi }(\sigma 1\tau )`$ be the set of letters of $`1\tau `$, and let the rest of the blocks of $`\mathrm{\Phi }(\sigma 1\tau )`$ be as in $`\mathrm{\Phi }(\sigma )`$. ∎

As an example, the tree

$$T(645792138)=\text{}$$

corresponds to the partition $`\{\{1,3,8\},\{2\},\{4,5,7,9\},\{6\}\}`$.

Now that we have seen the structure of $`𝒮(1\text{ }23)`$ and $`𝒮(1\text{ }32)`$, it is trivial to give a bijection between the two sets. Indeed, if $`\mathrm{\Theta }:𝒮(1\text{ }23)𝒮(1\text{ }32)`$ is given by $`\mathrm{\Theta }(ϵ)=ϵ`$ and $`\mathrm{\Theta }(\sigma 1\tau )=\mathrm{\Theta }(\sigma )\mathrm{\hspace{0.17em}1}\tau ^r`$ then $`\mathrm{\Theta }`$ is such a bijection. Actually $`\mathrm{\Theta }`$ is its own inverse.

###### Proof of the third case.

It is plain that a permutation avoids $`2\text{ }13`$ if and only if it avoids $`2\text{ }1\text{ }3`$ (see ). Note that

$$\sigma 1\tau 𝒮(2\text{ }1\text{ }3)\{\begin{array}{cc}\mathrm{red}(\sigma ),\mathrm{red}(\tau )𝒮(2\text{ }1\text{ }3)\hfill & \\ \tau >\sigma \hfill & \\ \sigma 1\tau 𝒮\hfill & \end{array}$$

where $`\tau >\sigma `$ means that any letter of $`\tau `$ is greater than any letter of $`\sigma `$. Hence we get a unique labelling of the binary tree corresponding to $`\sigma 1\tau `$, that is, if $`\pi _1,\pi _2𝒮(2\text{ }1\text{ }3)`$ and $`UT(\pi _1)=UT(\pi _2)`$ then $`\pi _1=\pi _2`$. It is well known that there are exactly $`C_n`$ (unlabelled) binary trees with $`n`$ (internal) nodes. The validity of the last statement can be easily deduced from the following simple bijection between Dyck words and binary trees. Fixing notation, we let the set of Dyck words be the smallest set of words over $`\{u,d\}`$ that contains the empty word and is closed under $`(\alpha ,\beta )u\alpha d\beta `$. Now the promised bijection is given by $`\mathrm{\Psi }()=ϵ`$ and

$$\mathrm{\Psi }\left(\text{}\right)=u\mathrm{\Psi }(L)d\mathrm{\Psi }(R).$$

## 4. Pairs of patterns

There are $`\left(\genfrac{}{}{0pt}{}{12}{2}\right)=66`$ pairs of patterns altogether. It turns out that there are $`21`$ symmetry classes and $`10`$ Wilf-classes. The details are given in Table 1, and the numbering of the symmetry classes in the titles of the subsections below is taken from that table.

### Symmetry class 1

We have

$$\sigma 1\tau 𝒮(1\text{ }23,32\text{ }1)\{\begin{array}{cc}\mathrm{red}(\sigma )𝒮(21,1\text{ }23)\hfill & \\ \mathrm{red}(\tau )𝒮(12,32\text{ }1)\hfill & \\ \sigma 1\tau 𝒮\hfill & \end{array}$$

The result now follows from $`𝒮(21,1\text{ }23)=\{ϵ,1,12\}`$ and $`𝒮(12,32\text{ }1)=\{ϵ,1,21\}`$.

### Symmetry class 2

Since $`3\text{ }21`$ is the complement of $`1\text{ }23`$, the cardinality of $`𝒮_n(1\text{ }23,3\text{ }21)`$ is twice the number of permutations in $`𝒮_n(1\text{ }23,3\text{ }21)`$ in which $`1`$ precedes $`n`$. In addition, $`1`$ and $`n`$ must be adjacent letters in a permutation avoiding $`1\text{ }23`$ and $`3\text{ }21`$. Let $`\sigma 1n\tau `$ be such a permutation. Note that $`\tau `$ must be both increasing and decreasing, that is, $`\tau \{ϵ,2,3,4,\mathrm{},n1\}`$, so there are $`n1`$ choices for $`\tau `$. Furthermore, there is exactly one permutation in $`𝒮_n(1\text{ }23,3\text{ }21)`$ of the form $`\sigma 1n`$, namely $`(\frac{n+1}{2},\mathrm{},n2,3,n1,2,n,1)`$, and similarly there is exactly one of the form $`\sigma 1nk`$ for each $`k\{2,3,\mathrm{},n1\}`$. This completes our argument.

### Symmetry class 3

Note that

$$\sigma 1\tau 𝒮(1\text{ }23,2\text{ }31)\{\begin{array}{cc}\mathrm{red}(\sigma ),\mathrm{red}(\tau )𝒮(12)\hfill & \\ \sigma 1\tau 𝒮(2\text{ }31)\hfill & \end{array}$$

It is now rather easy to see that $`\pi 𝒮_n(1\text{ }23,2\text{ }31)`$ if and only if $`\pi =n\mathrm{}21`$ or $`\pi `$ is constructed in the following way. Choose $`i`$ and $`j`$ such that $`1j<in`$. Let $`\pi (i1)=1`$, $`\pi (i)=n+1j`$ and arrange the rest of the elements so that $`\pi (1)>\pi (2)>\mathrm{}>\pi (i1)`$ and $`\pi (i)>\pi (i+1)>\mathrm{}>\pi (n)`$ (this arrangement is unique). Since there are $`\left(\genfrac{}{}{0pt}{}{n}{2}\right)`$ ways of choosing $`i`$ and $`j`$ we get the desired result.

### Symmetry class 4a

We have

$$\sigma 1\tau 𝒮(1\text{ }23,2\text{ }13)\{\begin{array}{cc}\mathrm{red}(\sigma )𝒮(1\text{ }23,2\text{ }13)\hfill & \\ \mathrm{red}(\tau )𝒮(12)\hfill & \\ \sigma >\tau \hfill & \\ \sigma 1\tau 𝒮,\hfill & \end{array}$$

where $`\sigma >\tau `$ means that any letter of $`\tau `$ is greater than any letter of $`\sigma `$. This enables us to give a bijection between $`𝒮_n(1\text{ }23,2\text{ }13)`$ and the set of compositions (ordered formal sums) of $`n`$. Indeed, such a bijection $`\mathrm{\Psi }`$ is given by $`\mathrm{\Psi }(ϵ)=ϵ`$ and $`\mathrm{\Psi }(\sigma 1\tau )=\mathrm{\Psi }(\sigma )+|1\tau |`$.

As an example, the tree

$$UT(958764132)=\text{}$$

corresponds to the composition $`1+4+1+3`$ of $`9`$.

### Symmetry class 4b

We have

$$\sigma 1\tau 𝒮(1\text{ }23,23\text{ }1)\{\begin{array}{cc}\mathrm{red}(\sigma ),\mathrm{red}(\tau )𝒮(12)\hfill & \\ \sigma 1\tau 𝒮\hfill & \end{array}$$

Hence a permutation in $`𝒮(1\text{ }23,23\text{ }1)`$ is given by the following procedure. Choose a subset $`S\{2,3,4,\mathrm{},n\}`$, let $`\sigma `$ be the word obtained by writing the elements of $`S`$ in decreasing order, and let $`\tau `$ be the word obtained by writing the elements of $`\{2,3,4,\mathrm{},n\}S`$ in decreasing order.

For instance, the tree

$$T(421653)=\text{}$$

corresponds to the subset $`\{2,4\}`$ of $`\{2,3,4,5,6\}`$.

### Symmetry class 4c

This case is essentially identical to the case dealt with in (4a).

### Symmetry class 4c

The bijection $`\mathrm{\Theta }`$ between $`𝒮(1\text{ }23)`$ and $`𝒮(1\text{ }32)`$ (see page 3) provides a one-to-one correspondence between $`𝒮_n(1\text{ }32,2\text{ }13)`$ and $`𝒮_n(1\text{ }23,2\text{ }13)`$. Consequently the result follows from (4a).

### Symmetry class 4e

We have

$$\sigma 1\tau 𝒮(3\text{ }12,2\text{ }13)\{\begin{array}{cc}\mathrm{red}(\sigma ),\mathrm{red}(\tau )𝒮(3\text{ }12,2\text{ }13)\hfill & \\ \sigma =ϵ\text{ or }\tau =ϵ\hfill & \\ \sigma 1\tau 𝒮\hfill & \end{array}$$

Thus a bijection between $`𝒮_n(3\text{ }12,2\text{ }13)`$ and $`\{0,1\}^{n1}`$ is given by $`\mathrm{\Psi }(ϵ)=ϵ`$ and

$$\mathrm{\Psi }(\sigma 1\tau )=x\mathrm{\Psi }(\sigma \tau )\text{ where }x=\{\begin{array}{cc}1\hfill & \text{if }\sigma ϵ,\hfill \\ 0\hfill & \text{if }\tau ϵ,\hfill \\ ϵ\hfill & \text{ otherwise.}\hfill \end{array}$$

As an example, the tree

$$UT(136542)=\text{}$$

corresponds to $`01011\{0,1\}^5`$.

### Symmetry class 4f

Since $`3\text{ }12`$ is the complement of $`1\text{ }32`$, the cardinality of $`𝒮_n(1\text{ }32,3\text{ }12)`$ is twice the number of permutations in $`𝒮_n(1\text{ }32,3\text{ }12)`$ in which $`1`$ precedes $`n`$. In addition, $`n`$ must be the last letter in such a permutation or else a hit of $`1\text{ }32`$ would be formed. We have

$`\sigma 1\tau n𝒮(1\text{ }32,3\text{ }12)`$ $``$ $`\{\begin{array}{cc}\mathrm{red}(\sigma 1\tau )𝒮(1\text{ }32,3\text{ }12)\hfill & \\ \mathrm{red}(\tau )𝒮(21)\hfill & \\ \sigma 1\tau 𝒮\hfill & \end{array}`$
$``$ $`\{\begin{array}{cc}\mathrm{red}(\sigma )𝒮(1\text{ }32,3\text{ }12)\hfill & \\ \mathrm{red}(\tau )𝒮(21)\hfill & \\ \sigma <\tau \hfill & \\ \sigma 1\tau 𝒮\hfill & \end{array}`$
The rest of the proof follows the same lines as the proof of (4a).

### Symmetry class 4g

We can copy almost verbatim the proof of (4e); indeed, it is easy to see that $`𝒮_n(1\text{ }32,23\text{ }1)=𝒮_n(1\text{ }32,2\text{ }31)`$.

### Symmetry class 4h

We can copy almost verbatim the proof of (4f); indeed, it is easy to see that $`𝒮_n(1\text{ }32,31\text{ }2)=𝒮_n(1\text{ }32,3\text{ }12)`$.

### Symmetry class 4i

$`|𝒮_n(2\text{ }13,2\text{ }31)|=|𝒮_n(2\text{ }1\text{ }3,2\text{ }3\text{ }1)|=2^{n1}`$ by \[11, Lemma $`5`$(d)\].

### Symmetry class 4j

$`|𝒮_n(2\text{ }13,13\text{ }2)|=|𝒮_n(1\text{ }3\text{ }2,2\text{ }1\text{ }3)|=2^{n1}`$ by \[11, Lemma $`5`$(b)\].

### Symmetry class 4k

$`|𝒮_n(2\text{ }13,31\text{ }2)|=|𝒮_n(2\text{ }1\text{ }3,3\text{ }1\text{ }2)|=2^{n1}`$ by \[11, Lemma $`5`$(c)\].

### Symmetry class 5a

See Proposition 2.

### Symmetry class 5b

We give a bijection

$$\mathrm{\Lambda }:𝒮_n(1\text{ }23,21\text{ }3)𝒮_n(1\text{ }23,13\text{ }2)$$

by means of induction. Let $`\pi 𝒮_n(1\text{ }23,21\text{ }3)`$. Define $`\mathrm{\Lambda }(\pi )=\pi `$ for $`n1`$. Assume $`n2`$ and $`\pi =a_1a_2\mathrm{}a_n`$. It is plain that either $`a_1=n`$ or $`a_2=n`$, so we can define $`\mathrm{\Lambda }(\pi )`$ by

$$\{\begin{array}{cc}(a_1^{}+1,\mathrm{},a_{n1}^{}+1,a_{n2}^{}+1,1)\hfill & \text{if }\{\begin{array}{cc}a_1=n\text{ and }\hfill & \\ a_1^{}\mathrm{}a_{n1}^{}=\mathrm{\Lambda }(a_2a_3a_4\mathrm{}a_n),\hfill & \end{array}\hfill \\ (a_1^{}+1,\mathrm{},a_{n1}^{}+1,1,a_{n2}^{}+1)\hfill & \text{if }\{\begin{array}{cc}a_2=n\text{ and }\hfill & \\ a_1^{}\mathrm{}a_{n1}^{}=\mathrm{\Lambda }(a_1a_3a_4\mathrm{}a_n).\hfill & \end{array}\hfill \end{array}$$

Observing that if $`\sigma 𝒮_n(1\text{ }23,13\text{ }2)`$ then $`\sigma (n1)=1`$ or $`\sigma (n)=1`$, it easy to find the inverse of $`\mathrm{\Lambda }`$.

### Symmetry class 6

In  Claesson introduced the notion of a monotone partition. A partition is *monotone* if its non-singleton blocks can be written in increasing order of their least element and increasing order of their greatest element, simultaneously. He then proved that monotone partitions and non-overlapping partitions are in one-to-one correspondence. Non-overlapping partitions were first studied by Flajolet and Schot in . A partition $`\pi `$ is *non-overlapping* if for no two blocks $`A`$ and $`B`$ of $`\pi `$ we have $`\mathrm{min}A<\mathrm{min}B<\mathrm{max}A<\mathrm{max}B`$. Let $`B_n^{}`$ be the number of non-overlapping partitions of $`[n]`$; this number is called the $`n`$th *Bessel number*. Proposition 2 tells us that there is a bijection between non-overlapping partitions and permutations avoiding $`1\text{ }23`$ and $`12\text{ }3`$. Below we define a new class of partitions called strongly monotone partitions and then show that there is a bijection between strongly monotone partitions and permutations avoiding $`1\text{ }32`$ and $`21\text{ }3`$.

###### Definition 4.

Let $`\pi `$ be an arbitrary partition whose blocks $`\{A_1,\mathrm{},A_k\}`$ are ordered so that for all $`i[k1]`$, $`\mathrm{min}A_i>\mathrm{min}A_{i+1}`$. If $`\mathrm{max}A_i>\mathrm{max}A_{i+1}`$ for all $`i[k1]`$, then we call $`\pi `$ a *strongly monotone partition*.

In other words a partition is strongly monotone if its blocks can be written in increasing order of their least element and increasing order of their greatest element, simultaneously. Let us denote by $`a_n`$ the number of strongly monotone partitions of $`[n]`$. The sequence $`\{a_n\}_0^{\mathrm{}}`$ starts with

$$1,1,2,4,9,22,58,164,496,1601,5502,20075,77531,315947,1354279.$$

It is routine to derive the continued fraction expansion

$$\underset{n0}{}a_nx^n=\frac{1}{11x{\displaystyle \frac{x^2}{11x{\displaystyle \frac{x^2}{12x{\displaystyle \frac{x^2}{13x{\displaystyle \frac{x^2}{14x{\displaystyle \frac{x^2}{\mathrm{}}}}}}}}}}}}$$

using the standard machinery of Flajolet  and Françon and Viennot . One can also note that there is a one-to-one correspondence between strongly monotone partitions and non-overlapping partition, $`\pi `$, such that if $`\{x\}`$ and $`B`$ are blocks of $`\pi `$ then either $`x<\mathrm{min}B`$ or $`\mathrm{max}B<x`$. In addition, we observe that

$$\underset{n0}{}a_nx^n=\frac{1}{1xx^2B^{}(x)},$$

where $`B^{}(x)=_{n0}B_n^{}x^n`$ is the ordinary generating function for the Bessel numbers.

Suppose $`\pi 𝒮_n`$ has $`k+1`$ left-to-right minima $`1,1^{},1^{\prime \prime },\mathrm{},1^{(k)}`$ such that

$$1<1^{}<1^{\prime \prime }<\mathrm{}<1^{(k)}\text{, and }\pi =1^{(k)}\tau ^{(k)}\mathrm{}1^{}\tau ^{}1\tau .$$

Then $`\pi `$ avoids $`1\text{ }32`$ if and only if, for each $`i`$, $`\tau ^{(i)}𝒮(21)`$. If $`\pi `$ avoids $`1\text{ }32`$ and $`x_i=\mathrm{max}1^{(i)}\tau ^{(i)}`$ then $`\pi `$ avoids $`21\text{ }3`$ precisely when $`x_0<x_1<\mathrm{}<x_k`$. This follows from observing that the only potential $`(21\text{ }3)`$-subwords of $`\pi `$ are $`x_{i+1}1^{(k)}x_j`$ with $`ji`$.

Mapping $`\pi `$ to the partition $`\{1\sigma ,1^{}\sigma ^{},\mathrm{},1^{(k)}\tau ^{(k)}\}`$ we thus get a one-to-one correspondence between permutations in $`𝒮_n(1\text{ }32,21\text{ }3)`$ and strongly monotone partitions of $`[n]`$.

### Symmetry class 7

Let the sequence $`\{b_n\}`$ be defined by $`b_0=1`$ and, for $`n2`$,

$$b_{n+2}=b_{n+1}+\underset{k=0}{\overset{n}{}}\left(\genfrac{}{}{0pt}{}{n}{k}\right)b_k.$$

The first few of the numbers $`b_n`$ are

$$1,1,2,4,9,23,65,199,654,2296,\mathrm{}$$

Suppose $`\pi 𝒮_n`$ has $`k+1`$ left-to-right minima $`1,1^{},1^{\prime \prime },\mathrm{},1^{(k)}`$ such that

$$1<1^{}<1^{\prime \prime }<\mathrm{}<1^{(k)}\text{, and }\pi =1^{(k)}\tau ^{(k)}\mathrm{}1^{}\tau ^{}1\tau .$$

Then $`\pi `$ avoids $`1\text{ }23`$ if and only if, for each $`i`$, $`\tau ^{(i)}𝒮(12)`$. If $`\pi `$ avoids $`1\text{ }23`$ and $`x_i=\mathrm{max}1^{(i)}\tau ^{(i)}`$ then $`\pi `$ avoids $`3\text{ }12`$ precisely when

$$j>i\text{ and }x_i1^{(i)}x_j<x_i.$$

This follows from observing that the only potential $`(3\text{ }12)`$-subwords of $`\pi `$ are $`x_j1^{(k)}x_i`$ with $`ji`$. Thus we have established

$$\sigma 1\tau 𝒮_n(1\text{ }23,3\text{ }12)\{\begin{array}{cc}\mathrm{red}(\sigma )𝒮(1\text{ }23,3\text{ }12)\hfill & \\ \tau ϵ\tau =\tau ^{}n\text{ and }\mathrm{red}(\tau ^{})𝒮(12)\hfill & \\ \sigma 1\tau 𝒮_n\hfill & \end{array}$$

If we know that $`\sigma 1\tau ^{}n𝒮_n(1\text{ }23,3\text{ }12)`$ and $`\mathrm{red}(\tau ^{})𝒮_k(12)`$ then there are $`\left(\genfrac{}{}{0pt}{}{n2}{k}\right)`$ candidates for $`\tau ^{}`$. In this way the recursion follows.

### Symmetry class 8

See Proposition 2.

### Symmetry class 9

$`𝒮_n(1\text{ }32,13\text{ }2)=𝒮_n(1\text{ }3\text{ }2)`$.

### Symmetry class 10

See Proposition 2.

## 5. More than two patterns

Let $`P`$ be a set of patterns of type $`(1,2)`$ or $`(2,1)`$. With the aid of a computer we have calculated the cardinality of $`𝒮_n(P)`$ for sets $`P`$ of three or more patterns. From these results we arrived at the plausible conjectures of table 2 (some of which are trivially true). We use the notation $`m\times n`$ to express that there are $`m`$ symmetric classes each of which contains $`n`$ sets. Moreover, we denote by $`F_n`$ the $`n`$th *Fibonacci number* ($`F_0=F_1=1,F_{n+1}=F_n+F_{n1}`$).

## Acknowledgements

The first author wishes to express his gratitude towards Einar Steingrí- msson, Kimmo Eriksson, and Mireille Bousquet-Mélou; Einar for his guidance and infectious enthusiasm; Kimmo for useful suggestions and a very constructive discussion on the results of this paper; Mireille for her great hospitality during a stay at LaBRI, where some of the work on this paper was done.
We would like to thank N. J. A. Sloane for his excellent web site “The On-Line Encyclopedia of Integer Sequences”

http://www.research.att.com/~njas/sequences/.

It is simply an indispensable tool for all studies concerned with integer sequences.


text:
# The shapes of dark matter dominated dwarf spheroidal stellar density profiles

## 1 Introduction

The nature of the dark matter remains one of the prime areas of astrophysical and cosmological research. There has been some controversy recently concerning cold collisionless dark matter (CDM), arguably the simplest solution to dark matter problem. Assuming that satellite dark haloes can be associated with dwarf spheroidal galaxies (dSphs), CDM appears to overpredict by two orders of magnitude the number of these satellite haloes surrounding the Galactic halo (Moore et al., 1999a). Recent N-body simulations of CDM also indicate that dark matter haloes have cuspy cores on subgalactic scales, with an inner exponent $`\gamma _{CDM}1.41.5`$ (Fukushige & Makino, 1997; Moore et al., 1999b; Jing & Suto, 2000; Subramanian et al., 2000; Bullock et al., 2001), up from the value found in earlier simulations of $`\gamma _{CDM}1.0`$ (Navarro, Frenk, & White, 1996, hereafter NFW).

Recent detailed, high resolution observations of the rotational motion of LSB galaxies indicate their core density profiles are substantially flatter than CDM predictions (de Blok et al. 2001; see also Borriello & Salucci 2001). (For earlier discussion and debate, see for example van den Bosch & Swaters (2000) and Moore et al. (1999b)).

Since the discrepancy between CDM theory and observation is greatest on small scales, it is natural to seek to sharpen it further by examining the smallest, nearest galaxies, namely dwarf spheroidal galaxies. Galactic dSphs have long been recognised as excellent probes of the nature of the dark matter. Besides being the smallest known galaxies they also possess the highest known $`M/L`$ ratios. Observationally, their proximity means that individual stars can be resolved, so that beam smearing effects of the type discussed by van den Bosch & Swaters (2000) for LSBs are not an issue. Unfortunately, whilst velocity measurements have established the presence of large amounts of dark matter, they have hitherto not been sufficiently accurate to determine the radial profile of the dark matter density (Armandroff, Pryor & Olszewski, 1997).

However, the stellar density profile is rather well established (Irwin & Hatzidimitriou, 1995) and enough data exists for a detailed comparison with the theoretically predicted dark matter profiles. This comparison is only meaningful if the stars trace the mass, a very strong assumption, which is hard to justify. Nevertheless, it seems a reasonable first step to fit dSph stellar profiles to the parametric form used in theoretical studies of dark matter profiles, whilst acknowledging that any conclusion on the dSph dark matter profile must await more accurate velocity measurements. As both theory and observations develop, we anticipate that a more complete likelihood analysis, of the type performed here but including both density and velocity data, should become possible.

One should also point out that at least for some star formation histories, comparing the stellar and dark matter profiles is not without meaning. If the bulk of the stars formed before the dSph dark matter haloes, they would thereafter cluster under gravity just like dark matter particles. If, on the other hand, stars formed after the dark matter haloes, from baryons which were heated when the Universe was reionised at $`z5`$, or alternatively if the stars in dSphs were accreted from other parts of the galaxy, there would not necessarily be any simple relation between the stellar, and dark matter density profiles.

CDM theory over-predicts both the number density, and the velocity dispersion of haloes with the masses of dwarf spheroidals (Bode, Ostriker, & Turok, 2000). If CDM is to be viable, there must exist some mechanism (such as stellar feedback) to suppress star formation in most, but not all, low mass haloes. The surviving low mass galaxies would then be those in which stars formed earliest, and those which possessed the highest central density. These selection effects would tend to favor haloes with steeper-than-typical inner profiles and higher central densities. Comparing a typical CDM halo profile against observed dark matter profiles would actually be conservative in this respect.

In a similar way we may also speculate on how compatible other theories of dark matter are with observations of dark matter dominated dwarf spheroidals. For example, it has been suggested that a warm dark matter (WDM) scenario may better match the observed number of satellite galaxies predicted for the local group (Avila-Reese et al., 2001) and so a mechanism to suppress star formation may be less necessary. Additionally, stars may be a more viable tracer of the dark matter in WDM theories as the recollapse of small WDM haloes is expected to occur considerably later than in the CDM case. However, despite these advantages, theories of WDM may predict haloes cuspy enough to be cause for concern as in the CDM case (Eke et al., 2001).

## 2 Methodology

We have studied the radial distribution of stellar matter in the dark matter dominated Galactic dSphs using the framework of Bayesian likelihood analysis (Gregory & Loredo, 1992).

The stellar density profile was assumed to take the smoothly interpolating double power law form of equation (1) (e.g., Kravtsov et al., 1998).

$$\rho (r)=\frac{\rho _0}{(r/r_0)^\gamma [0.5+0.5(r/r_0)^\alpha ]^{(\beta \gamma )/\alpha }}$$
(1)
Using this form yields $`\rho r^\gamma `$ for radial distances smaller than $`r_0`$, and $`\rho r^\beta `$ for radial distances larger than $`r_0`$. The parameter $`\alpha `$ controls the scale over which the power law shifts from $`\gamma `$ to $`\beta `$. Roughly speaking, this change occurs between radii $`e^{1/\alpha }r_0`$ and $`e^{1/\alpha }r_0`$. This density profile accommodates a wide range of useful models, including a modified King-like profile (King, 1962; Rood et al., 1972) for $`(\alpha ,\beta ,\gamma )=(2,3,0)`$, the NFW profile for $`(\alpha ,\beta ,\gamma )=(1,3,1)`$, and the profile suggested by recent N-body CDM simulations $`(\alpha ,\beta ,\gamma )=(1,3,1.5)`$.

Projecting onto the celestial sphere gives the effective two dimensional stellar surface density.

$$\mathrm{\Sigma }(r_{})=2_0^{\mathrm{}}\rho \left(\sqrt{r_{}^2+z^2}\right)𝑑z$$
(2)
Currently, the best observational determination of stellar density as a function of radius in the dSphs of interest is the work of Irwin & Hatzidimitriou (1995), and can be summarised in this analysis by a vector $`\stackrel{~}{\mathrm{\Sigma }}_{obs}`$ which contains the mean density at a discrete set of radii and an associated covariance matrix $`\stackrel{~}{C}_{obs}`$.

For each model $`(\alpha ,\beta ,\gamma ,r_0,\rho _0)`$ we have calculated the conditional relative likelihood $`(\alpha ,\beta ,\gamma ,r_0,\rho _0|\stackrel{~}{\mathrm{\Sigma }}_{obs})`$ – a $`\chi ^2`$ statistic in practice – to quantify the compatibility of a particular model with observations.

The chief advantage of the Bayesian formalism is that it allows one to assess the relative likelihood of a particular subclass of the models by integrating $``$ over the relevant equiclassification surfaces in the model space. To assess the relative likelihood of different values of $`\gamma `$ we integrate $``$ over all models with the same $`\gamma `$ but different $`(\alpha ,\beta ,r_0,\rho _0)`$ and obtain the marginalized distribution $`_\gamma (\gamma |\stackrel{~}{\mathrm{\Sigma }}_{obs})`$. This process allows for a fair decoupling of our state of knowledge of $`\gamma `$ from $`(\alpha ,\beta ,r_0,\rho _0)`$ without, for example, ignoring the data in the outer regions of the dSph in an ad hoc manner.

Care must be taken when choosing the ranges of parameter values to ensure that a fair sampling of the parameter space is made into all regions that can contribute significantly to the marginalized distribution. The reason for this is the edges of the parameter distribution impose the trivial prior that the parameters of candidate models must lie within the range of parameters chosen. For the purposes of this study we have found that a largely unbiased range of parameters is: $`\alpha [0.5,12]`$; $`\beta [2.5,17]`$; $`\gamma [13,3]`$; $`r_0`$; and $`\rho _0`$.

In practice $``$ is an extremely rapidly decreasing function of $`(r_0,\rho _0)`$ about its maximum, and so for computational purposes the marginalization over these variables has been approximated by a maximization. We find that maximization over $`(r_0,\rho _0)`$ yields indistinguishable results to marginalization provided that the characteristic turnover radius, $`r_0`$, is not permitted to be unreasonably large (ie. larger than the edge of the galaxy). Marginalization over $`(\alpha ,\beta )`$ proceeds straightforwardly to yield $`_\gamma `$.

The three dSphs we have focused our analysis on, Carina, Draco and Ursa Minor have mean ellipticities, $`ϵ=1b/a`$, of $`0.33`$, $`0.29`$, and $`0.56`$ respectively and the available surface density data is averaged over elliptical bins. To make a conservative analysis in spherical theory we made a direct comparison of circularly rebinned surface density data with the theoretical profiles, using the properly reweighted error distribution. In general, we find that even the rough approximation of comparing the elliptically binned density profile with spherical theory gives similar limits on $`\gamma `$ as the gross dependence of $``$ on the shape parameters is insensitive to the exact data binning scheme. This is expected as spherically smoothing an ellipsoidal distribution has the effect of smoothing the radial distribution over scales of $`ϵa`$ without significantly altering the gross radial dependence – especially in the nearly flat inner regions important for this analysis.

## 3 Discussion

The marginalized likelihood distribution $`_\gamma `$ for the three dSphs in question is shown in Figure 1. Although the peak of the distribution fluctuates slightly from galaxy to galaxy the upper bound on $`\gamma `$ is consistent between all three.

While the distributions in $`\gamma `$ have tails stretching well into the negative region of parameter space this is not unexpected. Negative values of $`\gamma `$ are simply models that have a peak in the density at a scale of $`r_0`$, a plausible result given the adopted uncertainties. Projection effects coupled with the freedom to renormalize and rescale the density profile have the result of extending the tail relatively far into the negative $`\gamma `$ region. Despite the ambiguity between models in the negative $`\gamma `$ regime, it is clear from the Figure 1. that models with $`\gamma >1.21`$ are strongly excluded by this analysis.

The best-fitting density profiles are shown in Figure 2. Note that while the profiles are nearly always good fits for the inner and central regions there sometimes appears to be an excess of density for the outer few data points – related to the scheme adopted for background subtraction of stars (Irwin & Hatzidimitriou, 1995). The results with respect to the parameter $`\gamma `$ do not change if these points are included or excluded from the analysis. We have adopted the strategy of including all available data.

Table 1 summarises the limits this analysis places on $`\gamma `$ and the other shape parameters for each galaxy on its own, and the galaxies considered together as an ensemble. It also presents the limits with a tophat prior of $`1\alpha 2`$ imposed on the likelihoods – the range of parameter space that the NFW and recent N-body CDM profiles are contained in. The effect of this prior is to shift the peak of the distribution and the upper bound on $`\gamma `$ to even *lower* values than when the full range of $`\alpha `$ is used.

As measurements of the radial profile of the velocity dispersion in these galaxies increase in sensitivity a joint analysis fitting both the stellar dispersion and stellar density profiles predicted by a given DM profile should provide a much better test of the CDM and similar paradigms.

## 4 Conclusion

We have completed a Bayesian likelihood analysis of the stellar density profile shapes of the Galactic dwarf spheroidal galaxies Draco, Ursa Minor, and Carina. With uniform prior assumptions for the parameters $`(\alpha ,\beta ,\gamma ,r_0,\rho _0)`$ we conclude that, for each galaxy, $`\gamma <1.21`$ at greater than 99% confidence.

As discussed in the introduction, except in the special situation where the bulk of the stars formed before the dark matter halo, $`\gamma _{DM}`$ would not be expected to be the same as $`\gamma stars`$. Nevertheless the comparison we made quantifies the the discrepancy between the observed inner stellar profile of dSphs and simulated dark matter haloes, a discrepancy which CDM theory or one of its cousins must ultimately explain.

## Acknowledgements

We would like to thank M. Irwin and D. Hatzidimitriou for kindly providing their data for use in this analysis. KS was supported in part by funds from the Government of British Columbia (Canada) through the 2000 Queen Elizabeth II British Columbia Centennial scholarship, and the generosity of the Cambridge Commonwealth Trust. NT is supported by PPARC.