text:
Posts tagged 'Les Baux-de-Provence'
The Daily Norm's Photo of the Week: Killer Bee!
Taking a winning photograph is very often more a matter of luck than intention, although that is not to say that compositional planning is not a crucial element to creating the right balance and backdrop for the image. So while I was content with composing a photograph of the fragrant purple lavender bushels which were lining the steep hilly path up to the ruins of the Chateau of Les Baux de Provence, I had no idea that in amongst the lavender in the photograph which would result, I would capture this quite brilliant image of a bee in full flight.
It was with gleeful surprise therefore that I looked back through my photographs of the day and found this little beauty, the furry bumble bee looking as though he is making straight for the viewer, almost like a war plane ready to pounce. The perfect symmetry of his wings spread sideways and his legs poised to land on some nearby flower make for an incredible and quite unique view of the humble bee going about its business. But the very symmetricality of his poise and the very definite forceful way with which the bee appears to be flying gives the whole image a sense of violence, putting the viewer in the anticipation of some forthcoming battle of the flowers. One of my favourite photos of my Provence trip, and definitely worthy of The Daily Norm's Photo of the Week spot.
All photos and written content are strictly the copyright of Nicholas de Lacy-Brown © 2013 and The Daily Norm. All rights are reserved. Unauthorized use and/or duplication of the material, whether written work, photography or artwork, included within The Daily Norm without express and written permission from The Daily Norm's author and/or owner is strictly prohibited.
Provence Odyssey | Saint-Rémy: Les Photos (daily-norm.com)
Provence Odyssey | My Journey in Paintings: Beau Les Baux
When I was planning my trip to Provence, I always had in mind the kind of imagined utopia, where Dominik and I would walk, carefree, into lavender fields and poppy fields, he taking a rest amongst the sweet smelling flowers, and me setting out my sketch book and paint box, beckoning the Provençal muse to meet my embrace, inspiring me to transfer the glory of Provence to the blank pages of the sketch book before me. In this sense I suppose I am similar to so many artists who have gone before me; such as Van Gogh, who was so driven by the concept of establishing an artistic community in the region that he painted some of his best works just as decoration for the house which would be at the centre of that movement.
While Van Gogh's dream was sadly never realised, my own artistic imaginings have, happily, come closer to fruition. After 6 days on the trip, I had already completed two works. As for my vision of utopia, well, Dominik had already found rest in amongst a Poppy field (as the photo below aptly demonstrates!), while in Saint-Rémy, we finally found the opportunity to stroll through lavender fields and olive groves, having got no closer to lavender in both Avignon and Arles than the bags of dried stuff littering up the souvenir shops.
Dominik takes a rest amongst the poppies, Oz style.
But once Les Baux entered the equation, my artistic stirrings really began to take another stir, as with one glance at some of the most stunning mountain scenery in all of France, I became involuntarily, but very willingly sucked into another hypnosis of creative motivation, as the sweet-smelling lavender-haired Provence Muse took my hand in hers, and led me to a third page of my sketchbook to complete yet another ode to this paradise.
As I described yesterday, Les Baux-de-Provence could not help but inspire artists such as Yves Brayer to manifest the exquisite village and surroundings in paint, but then again Saint-Rémy's impressive surroundings are surely worth their weight in inspirational gold also. So for my third painting, another of my freely-conceived "compositions" series, I couldn't help but paint the limestone chateau-topped spur of Les Baux, its stunning surroundings of patchwork-quilt fields, and, in the distance, the ruins of St Remy's great archaeological site, the Roman town of Glanum.
Composition No. 4 (Beau Les Baux) (© Nicholas de Lacy-Brown, 2013, guache on paper)
So there you have it: Composition No. 4 (Beau Les Baux). An undulating patchwork landscape, rocky citadel, blue skies and all topped off with a picnic of baguette, cheese, saucisson and of course a little wine. Ah…La Bonne Vie. I hope you enjoy it.
© Nicholas de Lacy-Brown and The Daily Norm, 2001-2013. Unauthorized use and/or duplication of the material, whether written work, photography or artwork, included within The Daily Norm without express and written permission from The Daily Norm's author and/or owner is strictly prohibited.
Provence Odyssey | Les Baux: Day 7 – The Belle of the Alpilles (daily-norm.com)
Provence Odyssey | Avignon – A room with a view (daily-norm.com)
Provence Odyssey | My Journey in Paintings: From Avignon to Arles (avec le petit dejeuner) (daily-norm.com)


text:
\section{Introduction}

The stable marriage problem (SMP) \cite{GS1962} is a problem that marries $n$ men and $n$ women depending on their preferences in such a way that the matching is \textit{stable}. A matching is not stable if there are two people of opposite genders who prefer each other over their assigned partners.

The problem applies to a variety of settings and has a lot of applications and generalizations. The most famous application is for matching graduate medical students to their first hospitals \cite{GS1962}, which is a variation of the stable marriage problem, where hospitals are allowed to hire several graduate students.

In this paper, we describe a lot of sequences related to this problem.

In Section~\ref{sec:prel} we set our assumptions restricting ourselves to the original setting of the stable marriage problem. We describe preliminary definitions, including the notion of the egalitarian cost for matching a pair of people of opposite genders.

In Section~\ref{sec:pp} we introduce sequences related to different types of preference profiles. These sequences include the total number of preference profiles, as well as the profiles where all men prefer the same woman, the first man is more desirable than the second man, all men rank the women the same way, all women have distinct men as their first choice, and the matrix of men's profiles form a Latin square.

In Section~\ref{sec:soulmates} we concentrate on sequences that depend on the number of soulmates. Soulmate pairs are an important notion in the SMP, as they describe a pair of people that rank each other first. As a result, any soulmate pairs in a stable matching have to be married; after that, they can be removed from consideration. We count the number of profiles with $k$ pairs of soulmates. We also count the number of profiles with $k$ pairs of soulmates in a special case when the men's and women's preferences form Latin squares. We provide formulas for these sequences.

In Section~\ref{sec:distSM}, we calculate the number of profiles that generate a given number of stable matchings. There is no easy formula for these numbers, so they are calculated by a program. Given the computational complexity, we can only calculate the values for $n$ up to 4. For $n=2$, the number of stable matchings could be 1 or 2. For $n=3$, the number of stable matchings could be 1, 2, or 3. For $n=4$, the number of stable matchings is not more than 10.

In Section~\ref{sec:special} we consider some interesting sequences. First, we look at hell-pairs, which are pairs of people where the men and women rank each other last. Intriguingly, they may end up together in a stable matching, in which case we call them a hell-couple. We count the number of profiles where this is possible. Then we count the number of profiles containing outcasts---pairs of people whom everyone else ranks the worst, making them destined for each other in a stable marriage. Finally, we count the number of profiles where the outcasts form a hell-couple.

Section~\ref{sec:symmetries} is devoted to symmetries of the problem. We count the number of preference profiles up to relabeling men.

In Section~\ref{sec:ec}, for a given $n$, we count the number of profiles such that there exists a stable matching of given egalitarian costs. In addition, we count the total number of stable matchings for a given egalitarian cost.

\section{Preliminaries}\label{sec:prel}

First, we make several assumptions:

\begin{itemize}
\item We have $n$ men and $n$ women.
\item Each person prefers to be married over being single.
\item A man only marries a woman, and vice versa.
\item Each person ranks people of the opposite gender without ties.
\end{itemize}

Thus, each man numbers the $n$ women in increasing order from $1$ through $n$, with 1 being his favorite and $n$ being his least favorite. Similarly, each woman numbers the $n$ men in increasing order from $1$ through $n$, with 1 being her favorite and $n$ being her least favorite. We call these $2n$ sets of preferences a \textit{preference profile}.

We can look separately at men's profiles and women's profiles. We can arrange men's preferences in a matrix where the $i$-th row corresponds to the $i$-th man's preferences. Thus, in such a matrix, each row is a permutation of the numbers 1 through $n$. Similar arguments work for women's preferences.

Once all preference profiles are set, people are paired into marriages. We call the set of all these marriages \textit{unstable} if there is a man $M$ and woman $W$ such that they prefer each other to their spouses, and \textit{stable} if no such man/woman pair exists. In an unstable set of marriages, the pair $M$ and $W$ described above is called a \textit{blocking pair} or a \textit{rogue couple}. By definition, a set of marriages without a rogue couple is stable.

We call a set of stable marriages a \textit{stable matching}. We denote the maximum number of stable matchings for $n$ men and $n$ women as $M(n)$. If two people can end up married in a stable matching, they are called \textit{valid partners} of each other.

The Gale-Shapley algorithm \cite{GS1962}, also known as the deferred acceptance algorithm, finds a stable matching given a preference profile. It involves a number of rounds described as follows:
\begin{itemize}
\item In the first round, each unengaged man proposes to the woman he prefers most, and then each woman replies ``maybe'' to her most preferable suitor and ``no'' to all other suitors. Each woman is then provisionally ``engaged'' to the suitor she prefers the most of those who proposed to her in that round. This suitor is, likewise, provisionally engaged to her.
\item In each subsequent round, each unengaged man proposes to the most-preferred woman to whom he has not yet proposed, regardless of whether the woman is already engaged. Then, each woman becomes provisionally engaged to the suitor she prefers the most out of those who have proposed to her so far. In doing so, she may reject her current provisional partner, who then becomes unengaged.
\item This process is repeated until everyone is engaged.
\end{itemize}

This version of the algorithm is called \textit{men-proposing}. By symmetry, there exists a women-proposing algorithm. The men-proposing Gale-Shapley algorithm is \textit{man-optimal} and \textit{woman-pessimal}. That means every man gets the best possible valid partner, and every woman gets the worst possible one. By symmetry, the women-proposing Gale-Shapley algorithm is \textit{woman-optimal} and \textit{man-pessimal}.

\subsection{The egalitarian cost}

The \textit{pairwise egalitarian cost} of a man and a woman is the sum of the rankings they give each other \cite{GI1989}. Suppose woman $W$ ranks man $M$ as $i$-th in her preferences, and $M$ ranks $W$ as $j$-th in his preferences. Then, the egalitarian cost of the pair $(M,W)$ is equal to $i + j$. The \textit{egalitarian cost} of a stable matching is the sum of all the pairwise egalitarian costs of the married couples in the matching. A matching with the smallest possible egalitarian cost is called \textit{egalitarian}.

Now, suppose we have two people with an egalitarian cost of 2. This means that they both rank each other first. Thus, unless they are married, they will form a blocking pair. That means any stable marriage has to have them as a couple. We call such a pair a \textit{soulmate pair} or \textit{soulmates}.

Soulmates are important as they reduce the matching problem to fewer people. In a stable matching problem with $n$ men, $n$ women, and $k$ pairs of soulmates, the number of stable matchings is the same as the number for the group of people from which the soulmates couples are removed, with the preferences for each person adjusted appropriately. In particular, the maximum number of stable marriages for any set of $2n$ people with $k$ pairs of soulmates cannot exceed $M(n - k)$.

\section{Preference profiles}\label{sec:pp}

\subsection{The total number of profiles}

The total number of different preference profiles is
\[(n!)^{2n}.\]
This is because each person can rank the opposite gender in $n!$ ways.

Here are the first few terms of the sequence for the total number of different preference profiles, with the first term corresponding to $n = 1$:
\[1,\ 16,\ 46656,\ 110075314176,\ 619173642240000000000.\]
This is sequence \seqnum{A185141} in the OEIS \cite{OEIS}, where it is defined as ``$a(n)$ is the number of `templates', or ways of placing a single digit within an $n^2$ by $n^2$ Sudoku puzzle so that all rows, columns, and $n$ by $n$ blocks have exactly one copy of the digit.'' This connection between preference profiles and Sudokus motivated the other paper we wrote \cite{STEPSudoku}.

\subsection{The homecoming queen}

We consider profiles where all men prefer the same woman. We call this woman a \textit{homecoming queen}. We count the profiles where a homecoming queen exists. Equivalently, we can consider the profiles where all women have the same man, a homecoming king, as their first choice.

For $n$ men and $n$ women, there are $n$ ways to pick the woman that all men rank first. Then there are $(n-1)!^n$ ways to fill in the rest of their preference profiles. There are then $n!^n$ ways to fill in the preference profiles for the women. This results in a total of
\[n(n-1)!^nn!^n\]
profiles where all men prefer the same woman. This is the same number of preference profiles as when there exists a woman that all men rank at the $i$-th place, where $i$ can be anywhere from 1 to $n$.

The sequence of the total number of preference profiles where all men prefer the same woman as their first choice is now sequence \seqnum{A340890} and starts as
\[1,\ 8,\ 5184,\ 1719926784,\ 990677827584000000,\ 2495937495082991616000000000000,\ \ldots. \]

We can ignore women's preferences and divide the sequence by $n!^n$. We get the following sequence which counts the number of different possible men's preferences in the stable marriage problem where all men prefer the same women. This is now sequence \seqnum{A342573}:
\[1,\ 2,\ 24,\ 5184,\ 39813120,\ 17915904000000,\ \ldots. \]
The formula for the $n$-th term is
\[n(n-1)!^n.\]
This sequence can be viewed as the number of ordered $n$-tuples consisting of $n$ permutations of order $n$ (not necessarily distinct) such that the first element of each of them is the same. Equivalently, we can say that the $i$-th element of each of them is the same.

We can also fix the woman everyone prefers. That is, we can assume that the homecoming queen is woman number 1. Then we get the sequence $a(n) = (n-1)!^n$.
\[1, 1, 8, 1296, 7962624, 2985984000000, 100306130042880000000,\ \ldots. \]
This sequence is the same as sequence \seqnum{A091868} shifted by 1.

Another natural sequence is the number of profiles when all men prefer the same woman and all women prefer the same man. To calculate it, we just need to square the corresponding terms in sequence A342573, which is the number of different possible men's preferences where they all prefer the same woman as their first choice. We get
\[1, 4, 576, 26873856, 1585084524134400, 320979616137216000000000000,\ \ldots. \]

This is now sequence \seqnum{A343474}: the number of preference profiles where both all men and all women have the same person as their first choice. Every preference profile of this type has a homecoming queen and a homecoming king. They rank each other first; that is, they are soulmates. Moreover, such profiles have exactly one pair of soulmates.

\subsection{One woman is preferable than another}

The homecoming queen is a more desirable woman than any other woman. We want to relax this condition, and consider a pair of women, where one woman is always ranked higher than the other one.

We see that for the men's profiles, there are $\frac{n!}{2}$ ways to make each profile, as only half of them will meet our conditions. Note that we are assuming that $n>1$. This means that the total number of ways to arrange the men's profiles is $\frac{n!^n}{2^n}$. Since there are no conditions for the women's profiles, there are $n!^n$ ways to arrange them. This gives us a total of
\[\frac{n!^{2n}}{2^n}\]
profiles where there exist two women, A and B, such that every man prefers A over B. This is now sequence \seqnum{A338665}, and it starts as
\[4,\ 5832,\ 6879707136,\ 19349176320000000000,\ \ldots.\]

Each man prefers woman A to woman B, so they will always propose to woman A first. When woman B is proposed to, the man proposing to woman B has already proposed to woman A. Since a man can only propose once per round, woman A was first proposed to in an earlier round than woman B. Once a woman is proposed to, she will be engaged (not necessarily with the same man) for the rest of the algorithm, so woman A's first engagement comes in an earlier round than woman B's.

If we just count the men's profiles we get
\[\frac{n!^{n}}{2^n},\]
\[1,\ 27,\ 20736,\ 777600000,\ 2176782336000000,\ \ldots.\]

By symmetry, sequence \seqnum{A343692} counts the number of women's preferences where the first man is more desired than the second man.

We also consider a symmetric case where both conditions apply: the first man is more desired than the second one, and the first woman is more desired than the second one. This sequence is the square of sequence \seqnum{A343692}, that is, the number of profiles is
\[\frac{n!^{2n}}{4^n}.\]
It is now sequence \seqnum{A343693}: the number of preference profiles for $n$ men and $n$ women, $n>1$, such that all men prefer woman 1 over woman 2 and all women prefer man 1 over man 2.
\[1,\ 729,\ 429981696,\ 604661760000000000.\]
This sequence is sequence \seqnum{A338665} divided by $2^n$.

\subsection{Same taste}

Suppose the men have exactly the same taste; they rank all women in the same order. Then the number of ways to arrange men's preferences is $n!$: we just order women in the order of everyone's preference. This is sequence \seqnum{A000142}, the factorial numbers.

If we add women's preferences to this, we get a total of $(n!)^{n+1}$ profiles. This corresponds to the OEIS sequence \seqnum{A091868}. The sequence of preference profiles where all men have the same taste starts as:
\[1,\ 1,\ 8,\ 1296,\ 7962624,\ 2985984000000,\ \ldots.\]

Given such a profile, the Gale-Shapley men-proposing algorithm ends in exactly $n$ rounds.

If both men and women have the same taste, the number of such profiles is sequence \seqnum{A001044} of factorial squares, $n!^2$:
\[1,\ 4,\ 36,\ 576,\ 14400,\ 518400,\ 25401600,\ 1625702400,\ \ldots.\]

Given such a profile, both the Gale-Shapley men-proposing and women-proposing algorithms end in exactly $n$ rounds. Indeed, in the first round of men-proposing algorithm, all men propose to the same woman: the homecoming queen. She gets engaged to the men of her first choice. In the second round, the $n-1$ unengaged men propose to the same women. This continues for $n$ rounds. Interestingly, we get couples with mutual rankings (1,1), (2,2), and so on. The egalitarian cost of the resulting matching is
\[n(n+1).\]

\subsection{Tastes differ}

On the opposite side of the spectrum, there is another natural scenario where men prefer different women as their first choices. Such profiles have a chance to make more people happier.

For $n$ men and $n$ women, there are $n!$ ways for the men to arrange their first choices, and $(n-1)!^n$ ways for them to rank the rest of the women. The women's preferences do not matter, so there are $n!^n$ ways to choose them. This gives us a total of
\[n!^{n+1}(n-1)!^n\]
preference profiles where all men prefer different women. By the way, these are exactly the profiles when the men-proposing Gale-Shapley algorithm terminates in one round. Thus, all men will be married to their first choices. Also, this sequence describes the number of profiles where men prefer different women as their $i$-th choice.

The sequence of preference profiles where all men prefer different women as their first choices, which is now \seqnum{A343475}, starts as
\[1, 8, 10368, 10319560704, 23776267862016000000,\ \ldots.\]

As before, we can create another sequence that just counts the number of possible preference profiles for men whose tastes differ. We just need to ignore women's preferences and divide this sequence by $n!^n$ to get the formula
\[n!(n-1)!^n.\]

We get another sequence which is now \seqnum{A343694}. It counts the number of men's preference profiles where all men prefer different women as their first choices and starts as
\[1, 2, 48, 31104, 955514880, 2149908480000000.\]

We can also consider a sequence where both men prefer different women and women prefer different men as their first choices. The new sequence counting such profiles, \seqnum{A343695}, is a square of the previous sequence:
\[n!^2(n-1)!^{2n},\] and starts as
\[1, 4, 2304, 967458816, 913008685901414400.\]
For these profiles, both men-proposing and women-proposing algorithms end in one round.

We can restrict the profiles some more. Suppose not only men and women have different preferences for their first choices, but also these choices match each other. This is equivalent to saying that we have $n$ pairs of soulmates. This sequence is described in Section~\ref{sec:nsoul}.

\subsection{Tastes really differ}

Suppose now for any ranking $k$, the women that are ranked $k$ are all different. Previously, we only considered this for $k=1$. Now we do this for every choice. In other words, when arranged in a matrix, the men's preferences form a Latin square. Thus, the number of such profiles for men is described by sequence \seqnum{A002860} (the number of Latin squares) in the OEIS:
\[1,\ 2,\ 12,\ 576,\ 161280,\ 812851200,\ 61479419904000,\ \ldots.\]

Now we want to calculate the sequence in which women's profiles are also counted. There are still \seqnum{A002860}$(n)$ possibilities for the men's profiles and also $n!^n$ possibilities for the women's profiles. This gives us the sequence $n!^n$A002860$(n)$ of unique profiles for $n$ men and $n$ women where men's profiles form a Latin square, which is now \seqnum{A343696}:
\[1,\ 8,\ 2592,\ 191102976,\ 4013162496000000,\ 113241608573209804800000000, \ldots.\]

As before, the men-proposing Gale-Shapely algorithm for such profiles terminates in one round.

Now we consider the sequence when both the men's and women's profiles form Latin squares. We call such profiles \textit{mutually-Latin} profiles. The formula for the number of profiles is \seqnum{A002860}$(n)^2$ because both the men and women have \seqnum{A002860}$(n)$ choices for profiles. The sequence counting preference profiles when both the men's and women's profiles form Latin squares is now \seqnum{A343697}:
\[1, 4, 144, 331776, 26011238400, 660727073341440000, 3779719071732351369216000000, \ldots.\]
As before, both the men-proposing and the women-proposing Gale-Shapely algorithms for such profiles terminate in one round.

\subsection{Latin profiles}

The \textit{Latin} marriage problem is a subset of the stable marriage problem where the egalitarian cost of any man-woman pair is $n+1$ \cite{T2002}. The corresponding profiles are called \textit{Latin} profiles. The Latin marriage problem is interesting because its profiles tend to produce a lot of stable matchings. Sequence \seqnum{A069124} in the OEIS \cite{OEIS} describes the number of possible stable matchings in a Latin profile. It starts as
\[1,\ 2,\ 3,\ 10,\ 12,\ 32,\ 42,\ 268,\ 288,\ 656,\ 924,\ 4360,\ 3816,\ 11336,\ \ldots.\]

This sequence counts the number of stable matchings for Latin profiles, thus providing a lower bound in the maximum number of stable matchings for any profile for a given $n$.

In a Latin profile, men's preferences have to form a Latin square \cite{T2002}. The number of Latin profiles is the number of Latin squares of the corresponding order \seqnum{A002860}$(n)$ since a Latin square represents men's preferences, and after that, women's preferences are uniquely determined.

\subsection{Disjoint profiles}

In this section, we study a special type of a profile called a \textit{disjoint} profile. In such profiles, each pair of mutual rankings $(i,j)$ occurs exactly once. In particular, each disjoint profile has exactly one pair of soulmates and one hell-pair. Such profiles correspond to entries in a disjoint-groups Sudoku \cite{STEPSudoku}, where in a particular place in a box, all digits are distinct across all the boxes. For example, the top-left corners of every box have distinct digits. This creates 9 additional groups to add to columns, rows, and boxes that have to contain distinct digits.

As we show in our other paper \cite{STEPSudoku}, there are 12 disjoint profiles for $n=2$.

\begin{proposition}
For any $n$, the number of disjoint profiles does not exceed $n^2!$ and is divisible by $n!^2$.
\end{proposition}

\begin{proof}
There are $n^2$ possible rankings and $n^2$ pairs of people. Thus, each profile is a permutation of possible rankings to distribute them among pairs of possible people. The number of permutations is $n^2!$. Not all permutations can be used as we forbid ties in individual rankings.

In such profiles, there is exactly one pair of soulmates. If we call them man 1 and woman 1, we can order everyone else according to their preferences. Thus each disjoint profile where man 1 and woman 1 rank their possible partners in order corresponds to $n!^2$ different profiles, which are achieved by relabeling men and women.
\end{proof}

The argument in the proof above allowed us to slightly speed up our program by assuming that the first man and the first woman rank other people in order and multiplying the resulting count of disjoint profiles by $n!^2$. We were able to calculate the number of disjoint profiles up to $n=4$. This is now sequence \seqnum{A345679}, which begins
\[1,\ 12,\ 8784,\ 1031049216,\ \ldots.\]

\subsection{Joint profiles}

In our paper \cite{STEPSudoku} we introduced a new type of Sudoku called \textit{joint-groups} or \textit{JG Sudoku}. In such a Sudoku every digit corresponds to a \textit{joint} preference profile.
In this new profile type, each possible mutual ranking $(i,j)$ appears exactly $n$ times, and once per $i$. We showed that a joint profile is a mutually-Latin profile; that is, both men's and women preferences form Latin squares. In addition, for a mutual ranking $(i,j)$, the value $j$ is a function of $i$: $j = f(i)$. We call the function $f$ the \textit{key} function.

The number of joint profiles is the number of Latin squares of order $n$ times the number of key functions, or $\text{A}002860(n)n!$. This is because a joint profile is uniquely defined by a Latin square of women's preferences and the key function, which is a permutation of $n$ elements.

The number of joint profiles as a function of $n$ is now sequence \seqnum{A344693}:
\[1,\ 4,\ 72,\ 13824,\ 19353600,\ 585252864000,\ 309856276316160000,\ \ldots.\]

\section{Soulmates}\label{sec:soulmates}

Recall that soulmates are a pair of people who rank each other first and who must therefore always be married.

To begin, let's look at the number of profiles with $k$ pairs of soulmates, which we denote by $F(k, n)$. For $n=2$, we can manually check to see that 2 profiles have no soulmates, 12 profiles have 1 pair of soulmates, and 2 profiles have 2 pairs of soulmates.

We introduce another function that is useful for our calculations. Given our set of $n$ men and $n$ women, consider a group of $k$ men and $k$ women. We ignore their preferences and calculate the number of profiles for the people not in our group, given that the people not in our group do not have soulmates. We denote this number as $S(k,n)$. We have
\[S(0,n) = F(0,n) \quad \textrm{ and } \quad S(n,n) = 1.\]

\begin{lemma}
The formula for $S(k,n)$ is
\[S(k,n) = \sum_{i=0}^{n-k} (-1)^{i}\cdot \binom{n-k}{i}^2\cdot (n-1)!^{2i}\cdot i!\cdot n!^{2n-2k-2i}.\]
\end{lemma}

\begin{proof}
First, the total number of possible profiles for people not in the group is $n!^{2n-2k}$, since there are $n!$ ranking possibilities for each person, and a total of $2n-2k$ people. Next, we calculate the number of profiles that have at least one pair of soulmates and subtract it from the total number of profiles.

There are ${n-k \choose 1}^2$ ways to pick a pair of soulmates out of $n-k$ men and $n-k$ women, and their profiles can be completed in $(n-1)!^2$ ways. Everyone else's profiles can be completed in $n!^{2n-2k-2}$ ways, giving a temporary total of
\[{n-k \choose 1}^2 \cdot (n-1)!^2 \cdot n!^{2n-2k-2}.\]

However, this overcounts the number we want since each profile with more than 1 pair of soulmates is counted multiple times. For example, the profile with 2 pairs of soulmates is counted twice, so we must subtract the profiles where there are at least two pairs of soulmates, which would be ${n-k \choose 2} ^ 2 \cdot 2! \cdot (n-1)!^4 \cdot n!^{2n-2k-4}$. We continue in this fashion using the principle of inclusion-exclusion, and we get the complete formula:
\[S(k,n) = \sum_{i=0}^{n-k} (-1)^{i}\cdot \binom{n-k}{i}^2\cdot (n-1)!^{2i}\cdot i!\cdot n!^{2n-2k-2i}.\]
\end{proof}

As an example, for $k = n$, we get $S(n,n)=1$. If $k = n-1$ instead, we get
\[S(n-1,n) = n!^2 - (n-1)!^2 = (n-1)!^2(n^2-1).\]

Now we are ready to calculate our main function $F(k,n)$.

\begin{theorem}
The formula for $F(k,n)$ is
\[\binom{n}{k}^2\cdot k! \cdot (n-1)!^{2k} \cdot \left(\sum_{i=0}^{n-k} (-1)^{i}\cdot \binom{n-k}{i}^2\cdot (n-1)!^{2i}\cdot i!\cdot n!^{2n-2k-2i}\right).\]
\end{theorem}

\begin{proof}
There are $\binom{n}{k}^2$ ways to choose $k$ pairs of people to be soulmates, and they can be matched to each other in $k!$ ways. These soulmates' profiles can be completed in $(n-1)!^{2k}$ ways. Now, all that remains is to complete the remaining $n-k$ people's profiles in such a way that there are no pairs of soulmates. We calculated this above as $S(k,n)$.

Thus, the complete formula for the number of profiles with exactly $k$ pairs of soulmates is
\[F(k,n) = \binom{n}{k}^2\cdot k! \cdot (n-1)!^{2k} \cdot S(k,n),\]
or, in the expanded form,
\[\binom{n}{k}^2\cdot k! \cdot (n-1)!^{2k} \cdot \left(\sum_{i=0}^{n-k} (-1)^{i}\cdot \binom{n-k}{i}^2\cdot (n-1)!^{2i}\cdot i!\cdot n!^{2n-2k-2i}\right).\]
\end{proof}

We summarize the function $F(k,n)$ for small values of $k$ and $n$ in Table~\ref{table:ksoul}. Rows correspond to a fixed $n$, and columns correspond to a fixed $k$.

\begin{table}[ht!]
\begin{center}
\begin{tabular}{|c||c|c|c|c|c|}
\hline
& 0& 1& 2& 3& 4\\
\hline
1& 0& 1& & & \\
\hline
2& 2& 12& 2& & \\
\hline
3& 9984& 27072& 9216& 384& \\
\hline
4& 28419102720& 55736377344& 23460876288& 2418647040& 40310784\\
\hline
\end{tabular}
\end{center}
\caption{$F(k,n)$.}
\label{table:ksoul}
\end{table}

There are several sequences here that deserve our separate attention.

\subsection{Special cases}

\subsubsection{Love is in the air: $n$ pairs of soulmates}\label{sec:nsoul}

Suppose we have exactly $n$ pairs of soulmates. Our formula gives
\[F(n,n) = (n-1)!^{2n} n!.\]

The number of preference profiles for $n$ men and $n$ women with $n$ pairs of soulmates is now sequence \seqnum{A343698}. It starts as
\[1,\ 2,\ 384,\ 40310784,\ 7608405715845120, \ldots.\]

For such profiles, each person has exactly one valid partner: their soulmate. Consequently, there is only one stable matching: the one where the soulmates are married to each other. For these profiles, the Gale-Shapley algorithm ends in one round, whether it is men-proposing or women-proposing. Also, the resulting stable matching has the best possible egalitarian cost, which is $2n$.

\subsubsection{$n-1$ pairs of soulmates}

For $n-1$ pairs of soulmates the formula becomes
\[ (n-1)!^{2n+1} \cdot n^2 \cdot (n^2 - 1).\]
The sequence of preference profiles with $n-1$ pairs of soulmates is now sequence \seqnum{A343699}:
\[0,\ 12,\ 9216,\ 2418647040,\ 913008685901414400,\ \ldots.\]

Such profiles have exactly one stable matching. Indeed, soulmates have to be matched with each other; after that, there are two people left, and they cannot avoid being together as a couple.
The men-proposing Gale-Shapley algorithm, when used on these preference profiles, ends in $j$ rounds, where $j$ is the ranking by the man in the non-soulmate pair of his partner. Why? Because each of the $n - 1$ men in the $n - 1$ soulmate pairs propose to their first choices, and then they are engaged for all the rounds. So, the only person left proposing is the $n$-th man in the non-soulmate pair. He gets to his true partner on the $j$-th round, where $j$ is where he ranks her.

\subsubsection{No soulmates}

To calculate the number of profiles without any pairs of soulmates we plug-in $k=0$, into the formula for $S(k,n)$. We get
\[\binom{n}{0}^2\cdot 0! \cdot (n-1)!^{0} \cdot \left(\sum_{i=0}^{n-0} (-1)^{i}\cdot \binom{n-0}{i}^2\cdot (n-1)!^{2i}\cdot i!\cdot n!^{2n-20-2i}\right).\]
Simplifying, we have
\[\sum_{i=0}^{n} (-1)^{i}\cdot \binom{n}{i}^2\cdot (n-1)!^{2i}\cdot i!\cdot n!^{2n-2i}.\]

The number of profiles without soulmates is now sequence \seqnum{A343700}, which starts as
\[0,\ 2,\ 9984,\ 28419102720,\ 175302739963548794880,\ \ldots.\]

Such profiles are useful for finding the bound for $M(n)$, which is the maximum possible number of stable matchings. As the sequence $M(n)$ is growing \cite{T2002}, the value $M(n)$ can only be achieved if the profile does not have soulmates.

\subsection{Tastes really differ}

Let us go back to profiles where men's preferences form a Latin square and see what happens if we require $k$ pairs of soulmates. We denote the number of Latin squares of size $n$ as $L_n$.

\begin{theorem}
The number of preference profile in a stable matching problem with $n$ men and $n$ women, such that there are exactly $k$ pairs of soulmates is
\[L_n \cdot \binom{n}{k}\cdot (n-1)^{n-k} \cdot (n-1)!^n.\]
\end{theorem}

\begin{proof}
Since the preference profiles for men form a Latin square, every woman will have exactly one man that ranks her first. Therefore, if we want $k$ pairs of soulmates, there are $\binom{n}{k}$ ways to pick the $k$ women for the soulmates pairs. After that, we have $(n-1)!$ ways to complete the profiles for every woman that has a soulmate, and $(n-1)(n-1)!$ ways to complete the profiles for every woman that does not have a soulmate. Since we have $L_n$ ways to choose the profiles for men, this gives us a total of
\[L_n \cdot \binom{n}{k}\cdot (n-1)!^k \cdot (n-1)^{n-k}(n-1!)^{n-k} = L_n \cdot \binom{n}{k}\cdot (n-1)^{n-k} \cdot (n-1)!^n\] preference profiles that have $k$ pairs of soulmates.
\end{proof}

We summarize the results for the small values of $n$ and $k$ in Table~\ref{table:mtrd}. The columns correspond to different $n$ and rows correspond to different $k$.

\begin{table}[ht!]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
 &1&2&3&4&5\\
\hline
0&0&2&768&60466176&1315033086689280\\
\hline
1&1&4&1152&80621568&1643791358361600\\
\hline
2&---&2&576&40310784&821895679180800\\
\hline
3&---&---&96&8957952&205473919795200\\
\hline
4&---&---&---&746496&25684239974400\\
\hline
5&---&---&---&---&1284211998720\\
\hline
Total&1&8&2592&191102976&4013162496000000\\
\hline
\end{tabular}
\end{center}
\caption{Distribution of preference profiles by the number of soulmate pairs when men's tastes really differ.}
\label{table:mtrd}
\end{table}

As expected, the total for a given $n$ is sequence \seqnum{A343696}, which counts the number of profiles when men's tastes really differ. We also have two more sequences of note. The first sequence is the number of preference profiles when men's tastes really differ and there are $n$ soulmates. It corresponds to the case $k=n$, and the formula for it is
\[L_n \cdot (n-1)!^n.\]
The number of preference profiles when men's tastes really differ and there are $n$ pairs of soulmates is now sequence \seqnum{A344662}:
\[1,\ 2,\ 96,\ 746496,\ 1284211998720,\ 2427160677580800000000,\ \ldots.\]

Another sequence of note is the sequence counting the number of profiles where the men's tastes really differ and there are 0 soulmates. In this case, the formula is
\[L_n \cdot (n-1)^n \cdot (n-1)!^n.\]
The sequence which counts the number of profiles where the men's taste really differ, with 0 soulmate pairs, is now sequence \seqnum{A344663}:
\[0, 2, 768, 60466176, 1315033086689280, 37924385587200000000000000,\ \ldots.\]

Now we look at the case when both men's and women's preference profiles form Latin squares, and where there are $k$ pairs of soulmates.

\begin{theorem}
The number of preference profiles for $n$ men and $n$ women where both men's and women's preference profiles form Latin squares and there are $k$ pairs of soulmates is
\[\frac{L_n^2}{n!} \cdot \binom{n}{k} \cdot \left( \sum_{i=0}^{n-k} (-1)^i \frac{(n-k)!}{i!} \right).\]
\end{theorem}

\begin{proof}
We have $L_n$ ways to choose men's preference profiles. Now we calculate the number of ways for women to pick their first choices.

We have $\binom{n}{k}$ ways to pick the women in pairs of soulmates. After that, we need to make sure that there are no other soulmate pairs. Among the $n-k$ women without soulmates, the people that they rank first will be some permutation of the $n-k$ men that are not soulmates. This is because in a Latin preference profile, all of the people that are ranked first must be different, and all of the men that are in a soulmate pair have already been ranked first by someone, so they cannot be ranked first again. We need these $n-k$ men and women to not have any pairs of soulmates, so we need our permutation to be a derangement. We denote the number of derangements of size $i$ as $D_i$.

This gives us that there are $\binom{n}{k} \cdot D_{n-k}$ possible first choices for women.
They can be completed in $\frac{L_n}{n!}$ ways. Therefore, we have $\frac{L_n}{n!} \cdot \binom{n}{k} \cdot D_{n-k}$ preference profiles for women, which gives us a total of
\[\frac{L_n^2}{n!} \cdot \binom{n}{k} \cdot  D_{n-k} = \frac{L_n^2}{n!} \cdot \binom{n}{k} \cdot \left( \sum_{i=0}^{n-k} (-1)^i \frac{(n-k)!}{i!} \right)\]
preference profiles with $k$ soulmates.
\end{proof}

We summarize the results for small values of $n$ in Table~\ref{table:mwtrd}. The columns correspond to different $n$ and rows to different $k$.

\begin{table}[ht!]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
 &1&2&3&4&5\\
\hline
0&0&2&48&124416&9537454080\\
\hline
1&1&0&72&110592&9754214400\\
\hline
2&*&2&0&82944&4335206400\\
\hline
3&*&*&24&0&2167603200\\
\hline
4&*&*&*&13824&0\\
\hline
5&*&*&*&*&216760320\\
\hline
Total&1&4&144&331776&26011238400\\
\hline
\end{tabular}
\end{center}
\caption{Distribution by the number of soulmates when men's and women's tastes really differ.}
\label{table:mwtrd}
\end{table}

One might notice the zeros on the diagonal. The reason is that when both men's and women's preferences form Latin squares, every single man and woman must be ranked first exactly once. Therefore, we cannot have exactly $n-1$ pairs of soulmates. This is also reflected in the formula since if we want to have $n-1$ pairs of soulmates, we would be multiplying by the number of derangements of size 1, which is 0.

As expected, the total in each column is sequence \seqnum{A343697}. But we also have two more sequences of note. The first sequence is the number of preference profiles when men's and women's tastes really differ and there are $n$ pairs of soulmates. It corresponds to the case $k=n$, and the formula simplifies to
\[\frac{L_n^2}{n!}.\]
This is the number of Latin squares multiplied by the number of Latin squares up to relabeling the digits. The sequence counting the number of preference profiles where both men's and women's preferences form Latin squares, and there are $n$ pairs of soulmates is now sequence \seqnum{A344664}, and it starts as
\[1,\ 2,\ 24,\ 13824,\ 216760320,\ 917676490752000,\ 749944260264355430400000,\ \ldots.\]

Additionally, in the case with no pairs of soulmates, then the formula simplifies to:
\[\frac{L_n^2}{n!} \cdot \left( \sum_{i=0}^n (-1)^i \frac{n!}{i!} \right).\]
The sequence counting the number of preference profiles where both men and women's preferences form Latin squares and there no soulmates is now \seqnum{A344665}; and it starts as
\[0,\ 2,\ 48,\ 124416,\ 9537454080,\ 243184270049280000,\ \ldots.\]

\section{Distribution for the number of stable matchings}\label{sec:distSM}

Given a preference profile, we can calculate the total number of stable matchings.

\textbf{Example.} Here is an example for a preference profile for $n=2$ that allows two stable matchings: First man: [1, 2], second man: [2, 1], first woman: [2, 1], second woman: [1, 2]. There are two possible matchings, and both are stable.

We wrote a program to calculate the number of stable matchings for every profile for $n \leq 4$. The results are summarized in Table~\ref{table:distribution}, where the columns correspond to different $n$. Row $k$ shows how many different profiles have exactly $k$ stable matchings. For example, there are 144 profiles for $n=4$ that result in 10 distinct stable matchings.

\begin{table}[ht]
\centering
\begin{tabular}{|c|c|c|c|c|}
\hline
       & 1 & 2 & 3 & 4 \\
\hline
1	& 1 	& 14 	& 34080 & 65867261184 \\
\hline
2	& 0 	& 2	& 11484	& 35927285472	\\
\hline
3	& 0 	& 0	& 1092	& 7303612896 \\
\hline
4	& 0 	& 0	& 0	& 861578352\\
\hline
5	& 0	& 0 	& 0	&111479616 \\
\hline
6	& 0 	& 0 	& 0	& 3478608 \\
\hline
7	& 0	& 0	& 0	&581472	\\
\hline
8	& 0	& 0	& 0	& 36432 \\
\hline
9	&0	& 0	& 0	& 0 \\
\hline
10	&0 	& 0	& 0	& 144 \\
\hline
Total 	& 1	& 16	& 46656	& 110075314176 \\
\hline
\end{tabular}
\caption{Distribution for the number of stable matchings.}
\label{table:distribution}
\end{table}

We submitted four sequences to the OEIS related to this table.

The first sequence is the number of preference profiles for 3 men and 3 women that generate $n$ possible stable matchings, which is now sequence \seqnum{A344666}. It is a finite sequence of three terms:
\[34080,\ 11484,\ 1092.\]
The second sequence, which is now \seqnum{A344667}, is the number of preference profiles for 4 men and 4 women that generate $n$ possible stable matchings. It is a finite sequence with 10 terms:
\[65867261184,\ 35927285472,\ 7303612896,\ 861578352,\ 111479616,\ 3478608,\ 581472,\ 36432, 0,\ 144.\]

We also submitted two infinite sequences. The first sequence, now sequence \seqnum{A344668}, corresponds to the first row. It is the number of profiles for $n$ men and $n$ women that result in one stable matching:
\[1,\ 14,\ 34080,\ 65867261184,\ \ldots.\]
The second sequence, now sequence \seqnum{A344669}, is the number of profiles for $n$ men and $n$ women that result in the maximum number of stable matchings. It is the last non-zero term in each column:
\[1,\ 2,\ 1092,\ 144,\ \ldots.\]

\subsection{Soulmates}

Suppose we have a pair of soulmates. Since they have to be married to each other, we can remove them from consideration and look at the other couples. It follows that the maximum number of stable matchings when there is exactly one pair of soulmates is $M(n-1)$. Similarly, if there are $k$ pairs of soulmates, the maximum possible number of stable matchings is $M(n-k)$.

For example, we know that for $n=2$, the maximum possible number of stable matchings is 2. This means for $n=3$, the maximum number of stable matchings with at least one couple of soulmates is also 2.

Table~\ref{table:SMVersusGoodness} shows the number of profiles for a given $n$ where there is a soulmate pair, and a given number of stable matchings. The leftmost column represents the number of stable matchings, while the top row is $n$.

\begin{table}[ht]
\centering
\begin{tabular}{|c|c|c|c|}
	\hline
	& 1 & 2 & 3 \\
	\hline
	1 & 1 & 14 & 30840\\
	\hline
	2 & 0 & 0 & 5832\\
	\hline
	Total & 1 & 14 & 36672 \\
\hline
\end{tabular}
\caption{Distribution for the number of stable matchings with at least one pair of soulmates.}
\label{table:SMVersusGoodness}
\end{table}

\section{Special Cases}\label{sec:special}

\subsection{A hell-pair and a hell-couple}

Suppose we have two people that rank each other as $n$. We call such a pair a \textit{hell-pair}. If they end up getting married, we call them a \textit{hell-couple}. Such a pair has an egalitarian cost of $2n$. Replacing ranking $i$ with $n+1-i$ is a bijection that swaps soulmates with hell-pairs. Because of that, the sequence counting the number of profiles with $k$ hell-pairs is the same as the corresponding sequence with $k$ pairs of soulmates.

Is it possible to have a hell-couple in a stable matching? Yes, it is. For example, two people that are ranked last by everyone else have to be together no matter what mutual ranking they have. This means any mutual ranking of two people in a married couple is possible.

\begin{proposition}
In a stable matching, it is impossible to have more than 1 hell-couple.
\end{proposition}

\begin{proof}
Suppose we have two hell-couples. Two people of different genders from two different couples form a rogue couple.
\end{proof}

Suppose there is a hell-couple in a stable matching. A person in this hell situation is ready to run away with anyone who agrees. This means that in a stable matching, every other person values the member of the hell-couple of the opposite gender less than their partner. In particular, no one can rank first a member of a hell-couple.

\begin{proposition}\label{prop:hellcouple}
If a preference profile has a stable matching with a hell-couple, all possible stable matchings have that hell couple.
\end{proposition}

\begin{proof}
We have a preference profile with a stable matching in which two people, let us say man $A$ and woman $Z$, form a hell-couple. We know that the men-proposing Gale-Shapley algorithm is woman-pessimal, meaning that women are always matched with the man they prefer least out of all their valid partners. This means that if we were to apply the men-proposing Gale-Shapley algorithm to this preference profile, we must have $Z$ matched with $A$, since $Z$ prefers $A$ least and we are given that they are valid partners. Additionally, the men-proposing Gale-Shapely algorithm is man-optimal, meaning that men are always matched with the person they prefer most out of their valid partners. This means $Z$ is the only valid partner for $A$. Similarly, $A$ is the only valid partner for $Z$. Thus, they form a couple in any stable matching.
\end{proof}

It follows that if a profile's stable matching has a hell-couple, the possible number of matchings for such a profile does not exceed $M(n-1)$.

Consider the sequence describing the number of profiles such that there exists a stable matching with a hell-couple. We calculated this sequence, which is now sequence \seqnum{A344670}, by a program, and it starts as:
\[1,\ 4,\ 4536,\ 5113774080,\ \ldots.\]

Consider pairs containing a preference profile and one of its stable matchings. We calculated the sequence of the number of these pairs that generate a hell-couple. That is, each profile that generates a hell-couple in a matching was counted with multiplicity equaling the number of matchings that generate this hell-couple. As per Proposition~\ref{prop:hellcouple} the multiplicity is the number of possible stable matchings for this profile.
The sequence, which is now sequence \seqnum{A344671}, starts as:
\[1,\ 4,\ 4608,\ 5317484544,\ \ldots.\]

\subsection{Outcasts}

It might be that the opposite notion to soulmates is not a hell-pair, but rather the outcasts. We call two people the \textit{outcasts} if they are ranked $n$ by everyone else: people of the opposite gender that are not in this pair. In a stable matching, two outcasts have to be paired with each other. This is independent of their mutual rankings, so they might be soulmates or a hell-couple, or anything in between.

We can have at most one pair of outcasts (unless $n = 2$), since everyone except the two outcasts ranks them last. We want to calculate the number of profiles with at least one pair of outcasts.

\begin{proposition}
The number of preference profiles with $n$ men and $n$ women such that there exists at least one pair of outcasts is:
\[n^4 \cdot (n-1)!^{2n} \textrm{ for } n \neq 2, \textrm{ and } 14  \textrm{ for } n = 2.\]
\end{proposition}

\begin{proof}
The statement is true for $n=1$. Suppose $n>2$. Then we have $\binom{n}{1}^2 = n^2$ ways to pick the two outcasts, then $n!^2$ ways to complete the outcasts' preference profiles, and finally $(n-1)!^{2n-2}$ ways to complete everyone else's profile; therefore we have
\[n^2 \cdot n!^2 \cdot (n-1)!^{2n-2} = n^4 \cdot (n-1)!^{2n}\]
ways to have a pair of outcasts for $n>2$.

However, when $n = 2$, it is possible for us to have two outcast pairs, and we are double-counting these cases. We can pick the two pairs in $2! = 2$ ways, and from there we only have 1 way to complete the preference profile, so there are 2 preference profiles that have two pairs of outcasts. Subtracting these from the previous number to avoid double-counting, we get that there are $14$ preference profiles that have at least one pair of outcasts for $n=2$. There is another description of profiles that do not contain outcasts: These are the Latin profiles where each pair of people have the egalitarian cost of 3. There are only 2 such profiles.

The formula for the number of outcasts is:
\[n^4 \cdot (n-1)!^{2n} \textrm{ for } n \neq 2, \textrm{ and } 14  \textrm{ for } n = 2.\]
\end{proof}

The first few terms of this sequence counting the number of preference profiles that have outcasts, which is now sequence \seqnum{A344689}, are:
\[1,\ 14,\ 5184,\ 429981696,\ 39627113103360000,\ \ldots.\]

\subsection{Outcast-hell pair}

In order for us to have an outcast-hell pair, we need to pick two people, and have everyone rank them last. Note that this means there can only be one outcast-hell-pair. Moreover, in such scenario we can have at most one hell-pair, and the people in it have to be outcasts. We can pick two people to be outcasts in $\binom{n}{1}^2 = n^2$ ways, and since everyone ranks them last, we can complete everyone's preference profiles in $(n-1)!^{2n}$ ways, so for any $n$, we have $n^2 \cdot (n-1)!^{2n}$ preference profiles with an outcast-hell pair. We saw this sequence before. By symmetry, this is the same as the number of profiles where there is pair of people such that everyone ranks them first. This is sequence \seqnum{A343474}:
\[1,\ 4,\ 576,\ 26873856,\ 1585084524134400,\ \ldots.\]

Except for the second term, the number of outcast profiles equals $n^2$ times the number of outcast-hell pair profiles. This makes sense, as the only difference is that the members of the outcast pair can rank each other any way they want.

\section{Symmetries}\label{sec:symmetries}

We can relabel men, relabel women and we can swap men with women.

We can relabel men in $n!$ ways. This is equivalent to fixing the first women's preferences to be 1, 2, 3, and so on. In particular, the total number of profiles has to be divisible by $n!$.

In addition, we can relabel the women, excluding the first, in the order of the preferences of the first man. This effectively means that we can shuffle the men and all the women but the first. Thus we have groups of $n!(n-1)!$ profiles which result in the same matchings but use different orderings of men and women.

\subsection{Distinct men's profiles up to relabeling}

We calculate the number of different men's profiles up to relabeling men for small values of $n$.

Suppose $n = 1$. Then, there is only one woman and only one man, so there can only be one possible set of lists.

Suppose $n = 2$. If both men prefer the same woman, this woman can be either woman 1 or 2. If they prefer different women, we can shuffle them, so that the first man prefers woman 1. Thus, the total is 3.

Here is the general formula. There are $n!$ possible profiles and $n$ men, so we are choosing $n$ elements from a list of $n!$ elements, with repeats allowed, and the order in which the elements are chosen does not matter. Therefore, the total number of ways to do so is
\[\binom{n!+n-1}{n} .\]

The sequence of the number of different men's profiles up to relabeling men is now sequence \seqnum{A344690} and it starts as:
\[1,\ 3,\ 56,\ 17550,\ 225150024,\ 197554684517400,\ 16458566311785642529680, \ldots.\]

We can think of this sequence as the number of $n$-multisets chosen from the set of all permutations of $n$ elements.

\section{The egalitarian cost distribution for small values of $n$}\label{sec:ec}

The egalitarian cost depends on a matching. Given a preference profile, it is possible to have different stable matchings with different egalitarian costs. Interestingly, if $n=2$ or 3 and there are several stable matchings, the egalitarian cost is the same for all these matchings. This does not hold for larger $n$.

Suppose $n=2$. If there is one stable matching, there are 2 profiles with an egalitarian cost of 4, 8 profiles with an egalitarian cost of 5, and 4 profiles with an egalitarian cost of 6. If there are two stable matchings, there are two profiles with an egalitarian cost of 6. Thus, we have two sequences. The number of profiles such that the matching has an egalitarian cost $g$: 2, 8, 6. The number of possible matchings for different profiles such that the egalitarian cost is $g$: 2, 8, 8.

Suppose $n = 3$. We know that 34080 profiles have one stable matching, 11484 profiles have two matchings, and 1092 profiles have 3 matchings.

Possible egalitarian costs range from 6 to 12, inclusive. If the profile has a matching with an egalitarian cost of 6, then this matching is unique, and all the couples are soulmates. We already calculated the number of such profiles as 384. If the egalitarian cost is 7 for one of the matchings, then the matching is unique too. Indeed, we have two soulmate couples that have to be together.

We cannot have a total egalitarian cost of 18. Suppose there is a matching of egalitarian cost 18. Then all couples are hell-couples. In this case, any pair of people that are not in a couple form a rogue pair.

When a profile has multiple matchings, it is possible that the matchings have different total egalitarian costs. For example, consider a profile, where the following matrices describe women's and men's preferences, respectively:
\[
\begin{pmatrix}
 3  & 1 & 2 \\
 1  & 2 & 3 \\
 1  & 2 & 3
\end{pmatrix}
 \quad
\begin{pmatrix}
 1  & 2 & 3 \\
 2  & 3 & 1 \\
 3  & 2 & 1
\end{pmatrix}.
\]

The men-proposing Gale-Shapley algorithm ends with a total egalitarian cost of 12.  The couples are the following: man 1 and woman 1, man 2 and woman 3, and man 3 and woman 2. The women-proposing algorithm ends with a total egalitarian cost of 11. The couples are the following: woman 1 and man 3, woman 2 and man 1, and woman 3 and man 2.

We calculated the number of preference profiles in the stable marriage problem with 3 men and 3 women such that there exists a stable matching with egalitarian cost $n$. The egalitarian cost for stable matchings ranges from 6 to 12 inclusive. The numbers below were calculated by a program:
\[384,\ 2304,\ 7416,\ 13860,\ 15912,\ 10836,\ 3564.\]

We did a similar calculation for $n=4$. The egalitarian cost in this case ranges from 8 to 20: 40310784, 322486272, 1394454528, 4263542784, 9856161792, 17805053952, 25557163776, 29223099648, 26437927680, 18541903680, 9633334320, 3379380192, 626260608.

We combined all these numbers into one sequence \seqnum{A344691}: an irregular table, where $T(n,k)$ is the number of preference profiles in the stable marriage problem with $n$ men and $n$ women such that there exists a stable matching with an egalitarian cost of $k$.

One might notice that the sum $T(3,k)$ over different $k$ is 54276, which is bigger than the total number of preference profiles, which is 46656. That means that we have the profiles that give matchings with different egalitarian costs. We know that 34080 profiles have one stable matching, 11484 profiles have two matchings, and 1092 profiles have 3 matchings. The total number of matchings with different profiles is:
\[1 \cdot 34080 + 2 \cdot 11484 + 3 \cdot 1092 = 60324.\]

It makes it natural to calculate another sequence that counts different matchings with a given egalitarian cost rather than different profiles. In other words, for a given egalitarian cost and each profile that can generate a matching with this egalitarian cost, we count this profile with the weight equaling the number of different matchings with the given egalitarian cost.

The irregular table $T'(n,k)$ is combined in sequence \seqnum{A344692}: the number of different stable matchings per different profiles for $n$ men and $n$ women with an egalitarian cost of $k$. For $n=3$ and egalitarian costs ranging from 6 to 12 we get the following numbers:
\[384,\ 2304,\ 7488,\ 14592,\ 18072,\ 13104,\ 4380.\]
The total as expected equals 60324. For $n=4$ the egalitarian cost ranges from 12 to 20 and the numbers are: 40310784, 322486272, 1397440512, 4299816960, 10080681984, 18632540160, 27586068480, 32664453120, 30544625664, 21941452800, 11480334336, 3963617280, 707788800.
It is not surprising that
\[T(n,2n) = T'(n,2n) \quad \textrm{ and } \quad T(n,2n+1) = T'(n,2n+1) .\]
If the egalitarian cost is $2n$, correspondingly $2n+1$, there are $n$, correspondingly $n-1$ pairs of soulmates. In both cases, there is only one stable matching per profile.

\section{Acknowledgments}

This project was done as part of MIT PRIMES STEP, a program that allows students in grades 6 through 9 to try research in mathematics. Tanya Khovanova is the mentor of this project. We are grateful to PRIMES STEP for this opportunity.

redpajama_set_name: RedPajamaArXiv


text:
Slime listens to what animals have to say
Tony-nominated playwright tackles climate change in play premiering in Vancouver this week
by Melanie Woods on June 14th, 2018 at 11:15 AM
What do you when 100 animals gather for a conference on climate change? According to the team behind Slime—a new play making its world premiere in Vancouver this month—you get a whole lot of noise.
And artistic director Kendra Fanconi says that's a good thing.
"We're looking at how we humans as animals can do a better job at listening and responding," Fanconi says.
Slime will make its world premiere on June 15 and run until June 24 at the Russian Hall in Vancouver. It is a coproduction between Fanconi's The Only Animal theatre company and the Banff Centre for Arts and Creativity.
The play is set in the near future focuses on the third annual SLIME conference, where 100 animals, scientists, and seven young translators gather to debate the future of an insatiable creature taking over the seas.
Slime is written by British playwright Bryony Lavery, author of the 1998 Tony-nominated play Frozen. Lavery says the play's inspiration came following an expedition in the seas north of Scotland.
"When I got back, I'd been taking little videos of the expedition, but in the background there was always people talking," she says. "There was just jibber jabber from humans—humans talking more than they listen."
Lavery says the play's focus on animal voices and sounds is meant to inspire humans to listen more.
"So we're looking at how we humans as animals can do a better job at listening and responding," Lavery says.
The production employed an animal sound librarian who "translated" Lavery's script into various animal languages for the performance.
"They went through this huge storehouse of animal recordings from a biodiversity museum and were able to translate line by line what the animals were saying," Fanconi says. "And the actors had to do auditions in their animal languages. And they perform all of the animals in the play, some live, some recorded.
Donald Lee
Slime utilizes various types of puppetry and costuming to create animals ranging from crabs to polar bears, all made out of recycled plastic. The cast and crew collected recycled plastic from their own homes for several months leading up to the production.
"We took the average amount of plastic that a Canadian would generate in a year, and that's the weight allowance of the plastic in the show," Fanconi says.
One of the play's characters wears a t-shirt that says "straws suck," a reference to environmental movements to ban single-use plastic straws. Fancion says the timeliness of the play's overall environmental message—particularly in Vancouver, where city council just voted to ban single-use plastic straws in 2019—is not lost on the production team.
"We have an escalation of our current environmental problems and we also have an escalation of hat activist spirit that is coming in this youth movement," she says. "I think that the play really cleverly deals with both of those things."
Fanconi says the production is partnering with the Georgia Strait Alliance, a Vancouver-based ocean protection organization. The Georgia Strait Alliance will have information and resources available in the lobby for audience members interested in ocean activism following the play.
Slime will show from June 15 to 24 at the Russian Hall in Vancouver. For more information, visit theonlyanimal.com.

redpajama_set_name: RedPajamaCommonCrawl


If you want to transfer music to your iPod, you will first of all have to work out where the music is going to come from. Most of it will come from two places, CDs, and the internet, from downloads etc. The first step is to find out how to get music from your CD collection transferred to your Ipod.
Step 2-Take the CDs that you want on your Ipod, and grab them into Itunes. This is a very simple process, so I won't go into it in detail here..
USB cable to connect your to your computer. When you have done this, you will need to make sure that the two machines have recognised each other. When you are all set up, you can use the mouse to drag and drop the tracks you want from Itunes to your Ipod.
That really is how easy it is to transfer music from your CD collection to your Ipod. All you have to do now is listen!
The most difficult part of finding and downloading music frm the internet is actually finding a genuine website to obtain the downloads from. Once you have found a good, reputable site, the rest of the job is easy, because you can just transfer the music onto your as you did with the CD music. The genuine download sites will usually make you pay a one time membership fee, but for this one time charge, you will get lifetime access to unlimited downloads., The really good sites have very large libraries, so this will allow you to grow your music collection very cheaply. Also, these sites have downloads for other types of entertainment such as movies and Tv shows etc.


In the US, divorce is not uncommon. When a marriage comes to this end, it can be an overwhelming situation legally, not to mention the emotional and mental turmoil and pain. When facing divorce or another family law issue, you can benefit from having an experienced, compassionate and adept attorney on your side.
At Copple, Rockey, McKeever & Schlecht, our experienced attorneys have been handling family law matters for many years. We put all of our decades of combined experience to work in obtaining the best possible outcome for you. To learn more and to arrange a consultation, please call our law firm at 402-371-4300. As proud Nebraskans, we fight on behalf of people from across the state, including the cities of Omaha, Lincoln and Norfolk.


Now that we have both a toddler and a baby, I needed to find a mat that both could play on together. Ethan had his thin car mat, and we have a play gym for Ivy, but neither of these would suit both. I was on the hunt for a thick mat, made out of soft material that was also non toxic and could be easily cleaned for both children to play on.
I was then recommended to have a look at Cosyplay, and immediately knew that this was the mat for us. The mats were created and are made in the UK, by a Mum who also happens to be a doctor. They are made out of a memory foam material that is soft and cushy and they have removable, washable covers. We were given the multi spot Baby Play Mat to try out and review, it sells on their website for £85, which I think is quite good value for a large play mat of this quality. The first thing that we noticed is how fluffy and comfortable the mat is to sit on.
The Cosyplay mat is great for all the family, both Ethan and Ivy can play on it side by side. We've put Ivy's little play gym on one side and Ethan sits on the other side with his Lego or cars or whatever he's playing with. We also love it (as do the Grandparents) as it's really comfy for us to sit on for long periods of time as well.
It's also a gorgeous mat, I've been using it loads to pose the kids on to take photos. Everyone who sees it says how lovely it is and I've recommended it to lots of friends. It's a great mat, and we love supporting a British company and knowing that the mat is great quality and made of high standard materials. I would highly recommend the mats from Cosyplay, let me know if you get one and what you think of it!


text:
Crush on the Concho lures disc golf greats to San Angelo
Charles Bryce
Over 200 competitors, including some of the top pros from around the country, will take their shots at the 17th annual Crush on the Concho disc golf tournament this weekend at Middle Concho Park and South Concho Park in San Angelo.
As of Tuesday night, 222 players were entered in 14 divisions. Fourteen of the country's top touring pros will be battling for a first-place check of about $900.
RELATED: A guide to disc golf courses in and around San Angelo
Tournament director Thomas Veal says the Lone Star State is a hotbed for a sport that continues to grow in popularity.
"Texas has the second-most amount of disc golf courses, period," Veal said. "Finland is actually the only place that has more disc golf courses than Texas. There's a tournament every weekend in the state of Texas.
"Our company (Low Putt Disc Golf) hosts 14 events a year. This is our biggest event by far, and so we are excited for that. You can't find a more perfect time than right now. The pros are on what they call 'The Texas Tour,' and so they are swinging through on their way to Waco next weekend."
San Angelo is the first stop on the tour.
The three-day tourney begins Friday with a bring-your-own-partner doubles event. Cash prizes will be on the line.
The tournament officially begins Saturday with two rounds of disc golf, which will begin about 8 a.m. Play is expected to conclude between 5 p.m. and 6 p.m.
The rounds will be played at Middle Concho Park at Lake Nasworthy and South Concho Park off Bell Street.
Sunday's final round will begin at 9 a.m. and end about noon. Following an awards ceremony, a pro-am skins game will be played for a top prize of $500.
The Crush on the Concho has drawn at least 216 competitors for the past four years.
"Our numbers have grown over the past three years," the tourney director said. "A lot of people watch disc golf on YouTube. But coming out to our events the past two years, our numbers have gotten bigger and bigger with volunteers and people spectating the event, coming out to watch some of the best pros in the world."
The lake course at Middle Concho Park was redesigned last year and will include an 18-hole temporary course. This city has a total of seven courses and there are several in surrounding communities.
Veal says the pros circle the Crush on the Concho on their calendars every year because of the quality of the courses, the camping facilities and everything else San Angelo has to offer.
Is this the sport for you?
If you're not familiar with disc golf, it's very similar to regular golf except that you're throwing a disc at a target instead of hitting a ball with a club. The target is a metal basket that's a few feet above the ground.
Like in regular golf, you have drivers, putters and so forth in a disc form.
And it's a lot more affordable than the traditional game.
"You don't have to pay like you would at a ball golf course," Veal said. "You can go out there with two or three discs. A lot of people call them Frisbees, but they are weighted differently than Frisbees and they fly a whole lot faster and harder.
"But for $30 or $45 you can get some discs that will last you one or two years and that's normally what they call the 'bug.' Everybody gets the disc golf 'bug' after playing for two or three weeks, and all of a sudden they become addicted to it."
Disc golf started in Canada way back in 1926 and it's played in 40-plus countries.
"It's a game you can't win," Veal said. "It's a game where you can only improve and get better at. Every day, you're playing against the course. It's always challenging.
"And it's low impact on your body, so people of all ages can play. We have a world champion from Lubbock who is 65 years old. He won worlds two years ago."
Veal added, "You can be as athletic or nonathletic as you like and still enjoy disc golf. It's a nice thing for San Angelo to have this tournament every year."


The culture of public relations and marketing agencies starts with the owner — perhaps even more so than with other businesses.
When the culture of an agency goes bad, it is usually because of the owner.
When an agency thrives, it is usually because the owner has set a good example.
We all know that business owners are in charge and can do what they want. But just because you can doesn't mean you should.
Here are some of the ways that employees look to the agency owner to see examples of how to behave.
If an agency owner shows up late and leaves early, it signals to the team that there may be a lack of commitment. This doesn't mean that owners need to sacrifice all of their flexibility, but if you roll in to the office at 10 AM and out at 2 PM every day, employees will take notice.
On the flip side, if the owner puts in long hours, employees will feel more reluctant to cut corners. They will see the commitment and most will seek to emulate that.
Similarly, if the owner works from home regularly, it is more difficult to tell employees that they can't do the same.
The more the owner separates from the team in terms of work habits, the less productive the agency is likely to be.
Spending restraint starts from the top. When employees see the owner being loose with company funds, they're more likely to follow suit.
Agency owners should consider this when they book travel, equip and decorate their personal office, host business meals, and incur other expenses.
Employees will even look to non-business spending for cues. If the owner pulls in to their personal parking space in a Ferrari, the team will notice and may figure they don't need to pinch pennies since the boss is doing so well.
Do you want your team to fill out time sheets to track project profitability? Then you should do so, too.
Do you have standard practices for hotel quality and airfare class when your team travels? You should follow the same rules.
Do you use project tracking software to see where things stand? You should participate, too.
Does this mean an owner can't cut any corners? No, but every time you do, employees will notice and either follow the example — or potentially resent it.
Agency managers — especially new, less experienced ones — will look to the owner/boss for examples of how to behave.
Authoritarian owners tend to lead to authoritarian managers.
Owners who ignore input inspire middle managers to ignore input from their own teams.
Agency leaders who manage through fear foster others to do the same.
At the other extreme, owners who do not demand accountability from their own direct reports will see the same behavior spread throughout the agency.
If the agency owner keeps too many secrets from the team, the employees will keep secrets from the owner.
That doesn't mean that employees need to be in on every little detail of the business, but there needs to be careful consideration about where to draw the line on what is confidential and what can be shared with the team.
Successful agencies have open lines of communication — in both directions.
If the agency owner can't simply articulate the vision for the business, employees won't be able to do it either.
Good leaders need to be able to explain the goal and the path to get to it — and then inspire the team to follow them.
Successful agencies have the entire team on the same page. Everyone uses similar language to describe the services and focus of the business.
Any business relies on its leaders for guidance and inspiration.
By the very nature of PR and marketing agencies, the owner has an almost outsize influence on success or failure.
Agencies struggle when the owner take a "do as I say not as I do" approach to running the business.
Agencies thrive when the owner sets a good example and provides real leadership.
There is no substitute for leadership by example — and it starts with the agency owner.


text:
FKA Twigs Files Shocking Lawsuit Alleging Ex-BF Shia LaBeouf Choked Her, Gave Her STI
Ana Lucia Murillo
Breaking News/Cheat Sheet Intern
Updated Dec. 11, 2020 5:33PM ET / Published Dec. 11, 2020 5:31PM ET
Gareth Cattermole/Getty
British musician FKA twigs, real name Tahliah Debrett Barnett, filed a bombshell lawsuit against the actor Shia LaBeouf in Los Angeles on Friday, alleging multiple forms of abuse throughout their nearly year-long relationship. She alleged LaBeouf threatened to crash a car they were in unless she said that she loved him and then, when she tried to get out of the car at a gas station, he followed her, beat her and berated her until she got back in. She also alleges LaBeouf deliberately gave her a STI and choked her as she tried to sleep.
Barnett said she filed the suit so people would recognize the signs of abuse and see that it could happen to anyone. "I'd like to be able to raise awareness on the tactics that abusers use to control you and take away your agency," she said. Another ex-girlfriend of LaBeouf's also detailed allegations of abuse by the actor in the lawsuit. In an email to The New York Times, LaBeouf claimed some of the allegations were untrue. "I have no excuses for my alcoholism or aggression, only rationalizations," he said. "I have been abusive to myself and everyone around me for years. I have a history of hurting the people closest to me. I'm ashamed of that history and am sorry to those I hurt."
Read it at The New York Times


I'm Looking for a producer to build with!
I am passionate about music and want to work closely with someone to help develop my style.
I write my own songs and am a confident top liner so with the right production i know we have some hits on our hands.
I am a new artist so don't have a massive budget. So if you charge premium prices please don't apply.
However if you an up and coming producer that is exploring their sound and wants to build a relationship with a singer to get there productions out there then of course we can discuss the finance bits.
Up and coming UK Urban Producer.


text:
«Ребёнок с голубем» () — одна из самых ранних работ испанского и французского художника Пабло Пикассо, написанная в 1901 году. Она относится к началу голубого периода. Выполнена маслом на холсте. Размер — 73  × 54 см.

История и описание
В 1900 году Пикассо вместе со своим другом художником Карлосом Касагемасом отправился в Париж, чтобы посетить Всемирную выставку. Его картина «Последние мгновения» принимала в ней участие. Позднее эта работа была записана. Поверх неё появилась картина «Жизнь». Здесь он познакомился с живописью импрессионистов. С этого момента Пикассо искал свой стиль. Он смотрел, изучал и «впитывал» в себя современную французскую живопись.

В 1901 году, Пикассо снова вернулся в Париж, чтобы подготовиться к совместной выставке с Франсиско Итуррино в галерее Амбруаза Воллара.
Вероятно, картина «Ребёнок с голубем» была создана в этот период времени, когда он жил в Париже с испанскими друзьями. Картина написана в начале голубого периода. Это одна из самых ранних работ, в которой проявилась ярко выраженная индивидуальность художника. Он навсегда оставил ученичество, заявив о своём собственном ви́дении мира.

На картине изображена маленькая девочка с короткими рыжими волосами и в белом платье. На её талии бантом завязан тёмно-синий пояс. Девочка прижимает к груди белого голубя. Рядом на земле лежит круглый предмет, похожий на мяч, с ярко окрашенными сегментами. За спиной девочки плоско выписанный фон — синее небо и зелёная трава. Техника изображения довольно новая и интересная. Здесь Пикассо отказывается от мерцающей палитры импрессионистов и рисует грубыми широкими мазками упрощённые очерченные формы. Лишние детали опущены, цвета приглушённые.

Вполне вероятно, что Пикассо изобразил на холсте свою младшую сестру Кончиту, умершую в 1895 году от дифтерии. В то время он испытал сильное горе, и детские воспоминания наверняка были вовлечены в создание картины.
В «Ребёнке с голубем» видны его тёплые искренние чувства к девочке.

В 1901 году художник пережил ещё одно тяжёлое потрясение. Его близкий друг Карлос Касагемас кончил жизнь самоубийством, после чего в работах Пикассо появились темы смерти, печали и нищеты. На холстах стали преобладать холодные синие краски. Этот период его творчества стали называть голубым.

Картина «Ребёнок с голубем» находилась в Великобритании с 1924 года. С тех пор она часто меняла владельцев. Последние годы работа выставлялась в галерее Института искусства Курто в Лондоне.
В 2012 году она была продана с аукциона Кристис за 50 миллионов фунтов стерлингов. И хотя аукционный дом отказался объявить нового владельца картины,  в апреле 2013 года газета  «Le Figaro» сообщила, что покупателем стал Национальный музей Катара.

Примечания

Картины Пабло Пикассо
Детские портреты XX века

redpajama_set_name: RedPajamaWikipedia


The amount of money to be allocated to commune-, district- and province-level governments is slated to rise next year in accordance with the government's long-gestating attempts at decentralising its power.
At a workshop yesterday on local democratic development, Keo Bengvath, deputy director of the Local Financial Department at the Ministry of Finance, outlined funding for the sub-national levels of government.
Provincial- and capital-level funding will rise to about 640.8 billion riel, with 237.2 billion riel and 69 billion riel going to the commune- and district-levels, respectively – for a grand total of about $233 million.
The increase of funds in 2014 from 2013 on the commune, district and provincial levels are 13.48 per cent, 13.86 per cent and 21.63 per cent, respectively, Bengvath said.
Ngann Chamroeun, deputy executive director of the secretariat of the Ministry of Interior's National Committee for Sub-National Democratic Development, said that the figures would continue to grow in the future, "but it depends on the national income".
The new money will be used for development, reform and "to boost capacity", he continued, without naming specific projects or sectors.
Cambodia's new Ministry of Public Function, he added, will try to give more power to local administrations.
"It is an act of transferring the power to the lower levels," Chamroeun said.
Decentralisation has been a slow process. A 2013 study by researchers at Michigan University and the US-based Brookings Institute ranked Cambodia 121st out of 182 countries in terms of decentralisation of government power.
San Chey, director of the Affiliated Network for Social Accountability in East Asia and the Pacific, said that even with increases, the funding for lower levels of government is still too limited.


text:
← Episode 3.10 TVD "The New Deal" or "A Relationship Matures"
Episode 3.12 TVD – "The Ties That Bind" or "What Did I Miss?" →
Episode 3.11 TVD – "Our Town" or "The Hardest Part of Playing Chicken is Knowing When to Flinch"
"The only way to call someone's bluff, Stefan, is to be willing to lose everything if you're wrong."
For me, the high points of this episode – which left me breathless at every turn – were:
Stefan's game of chicken with Klaus
Caroline coming to terms with being 17 forever
Klaus and Caroline
There was a common these in this episode for many of the main characters – coming to turns with their lives.
Tyler is trying to come to terms with being "sired" and admits to Caroline that he can't put her first – and he's sorry. So is she. He gives her a birthday gift – a charm bracelet. This is significant.
Klaus and Stefan are locked in conflict. Stefan is pushing all of Klaus' buttons. This is also significant because Klaus likes to do that – and Stefan's pretty good at it.
Klaus is moody – just ask his siblings.
Stefan gives him an ultimatum – get your hybrids out of Mystic Falls.
Klaus pushes back – I'll be forced to retaliate – kill people.
Stefan pushes further – go ahead. Or maybe I care enough to drop Elijah in the Arctic.
Klaus – maybe I'd be willing to lose one brother if it meant killing yours.
Stefan – try me. Let's find out.
Mindy? (Really? I haven't heard a name like this since "The Preppy Handbook" in the 1970's).
Stefan takes her out with a single, decapitating blow (shades of Elijah!)
Caroline is not "feeling" her birthday. She's stuck at 17 – a filler year, between Sweet 16 and the significance of 18. Being Caroline, it's clear she will persevere, but she wants time. Her friends encircle her to help her along that processing path.
Meanwhile, Klaus is compelling Tyler to take a nip out Caroline, and Tyler doesn't even realize it. This is a chess move – and it's going to happen. And I hate Klaus even more than usual now because he's going to use Caroline as a pawn in his chess game with Stefan – sweet Caroline!
Elsewhere, Damon and Alaric are contemplating whether or not there may be a gray area between the on and off switch for Stefan's humanity. A dimmer switch.
Elena, Bonnie, Matt and Caroline take the birthday party to the Fell crypt at the cemetery to give the "old" Caroline's life a proper funeral. Honestly, I thought this was a terrific idea and it worked well, right down to Bonnie lighting the candles on the birthday cake.
Caroline's wish! Don't you wonder what it was?
The Founder's Council is having one of its meetings and there is a fund raiser for restoring the infamous Wickery Bridge, scene of the death of the Gilberts. And who shows up? Dr. Melanie Fell, who is fully aware of the history of Mystic Falls (she's a Fell, don't you know) and is also a member of the council, undoubtedly brought in to replace the Fell who was sacrificed during "Ghost World".
It strikes me as rather creepy that the citizens of this town behave so "normally" in the midst of all these supernatural creatures and their plans and schemes. Carol, Klaus and Damon standing around talking about no more hybrid decapitations over cocktails is just too absurd in any other reality but the one in Mystic Falls!
At the birthday party/funeral, the drinks are loosening inhibitions, judgment, and tongues. Caroline is texting Tyler (who just broke it off with her) to join the fun, Bonnie is judging Elena's controlling of Jeremy's destiny (and thus his removal from Bonnie's life) and Matt seems to be the only one with the sense to realize that the party is not the right occasion for this.
Sheriff Forbes, being a mother, knows that Carol is only complying with Klaus's desires because he's "protecting" Tyler, but she wants Damon to get Stefan to back off before someone gets hurt – little does she know.
Alaric, meanwhile, gets a taste of who Meredith might be – a "psycho" according to her boss and former prom date.
And Stefan takes yet another provocative turn – until Damon intervenes with the rules, one of which is "no dead hybrids at the Founder's Party". It's nice to see Damon taking Liz Forbes' warning seriously but Stefan is pushing for all it's worth and declares that Elena's safety is Damon's responsibility now – he's not going to let anything stop him from exacting his revenge on Klaus. Damon says he's got to be smarter, but Stefan responds that you've got to fight fire with a bigger, badder fire.
Tyler shows up at the party. And he's sure he has everything under control. Things heat up and wham, Tyler takes a nip at Caroline. I don't know who is more shocked – Tyler, who realizes that Klaus is still controlling him – or Caroline, who knows exactly what the bite of a hybrid means – and can't believe it came from Tyler!
Stefan snatches Elena as she and Matt search for Caroline in the woods. Next thing you know, he's racing down in the road with her in his car and calling Damon with Elena's phone to tell him he's making his next move – he's going to feed Elena his blood and drive his car off Wickery Bridge – thus rendering Elena useless to Klaus as the tool to create more hybrids.
Say what?????
Damon tells Klaus that Stefan has just upped the ante, but at first, Klaus is sure Stefan would never do anything to hurt Elena. He claims that even if Stefan is "operating on crazy", that kind of love never dies – he's bluffing. But Damon reminds Klaus that no one knows Stefan better than his brother – and Damon doesn't have a clue how far Stefan is willing to go. He thinks Klaus should blink.
All of this reminds me of another classic game of chicken from the film "The Hunt for Red October" – the infamous submarine challenge. There is a great line in that film….
"The hardest part of playing chicken is knowing when to flinch."
Damon is sure it's time for Klaus to flinch. I am sure Klaus has his next (and next, and next) moves already set up in this chess game, but when Klaus answers Stefan's call, Stefan is feeding his blood to Elena and planning to drive her off Wickery Bridge.
With Elena screaming in the background, Klaus blinks!
Matt, who has found Caroline and carried her home, arrives at the Forbes house where Liz tells him to bring her in. What is Caroline's reaction to her mother's concern? "I'm sorry Mommy." Even in this situation, Caroline's first concern is not with herself – it's for her mother.
I LOVE Caroline Forbes.
Back at the bridge, Elena leaps out of the car in a rage. Stefan tells her that Klaus had to believe that he would go through with his plan – so her fear had to be real. Elena wants to know what would have happened if Klaus hadn't backed down. But Stefan is sure he's latched on to Klaus' single weakness, and that knowing it is the key to being able to destroy him. And ultimately that is what he plans to do.
Elena questions Stefan's priorities – is that what matters most? Destroying Klaus? Stefan believes that he lost Elena when he left town with Klaus and that he will never get her back so the only thing he has left is his humanity and he's willing to do whatever it takes to get that back. For her part, I think Elena now knows that Stefan no longer believes that he deserves her – after everything he's done, whether he did it of his own free will or not. And if Stefan believes he doesn't deserve her, where does that leave Elena?
Back at the Forbes house, Klaus shows up. And yes, this is all part of his plan – the plan he set in motion at the beginning of the episode when he told Tyler to bite Caroline. He wanted Tyler to bite Caroline so he could save her with his blood. And of course Liz is going to allow him in to her home because what mother would not want to save her child at any price? So although Matt and Liz are not happy about it, it's Klaus to the rescue.
And here starts one of those absolutely incredible scenes on TVD – you know the kind I mean. Intense, shocking, emotionally devastating. These scenes leave you crying, or breathless, or both – but they reach deep into the heart and stay there.
Klaus walks into the room. Caroline asks "are you going to kill me?"
"On your birthday? You really think that low of me?" says Klaus, with a look on his face that is total despair (as in "I am hurt to my very core that you would think such an awful thing of me") – even when we know that what he really means is "I'd kill you on any day unless I could use this occasion to my advantage."
And sweet Caroline is no fool – she knows it too. Her response? "Yes!" YOU GO GIRL!!!!
As he looks at Caroline's wound (notice, please, that Caroline is wearing Tyler's bracelet gift) Klaus explains that she is collateral damage. How comforting.
He touches the bracelet – "I love birthdays".
Caroline – "Yeah, aren't you a bazzilion or something?"
Klaus "As a vampire you have to adjust your perception of time, celebrate the fact that you are no longer bound by trivial human conventions, you're free."
Caroline doesn't see it that way "No, I'm dying."
Klaus sits on the bed next to her and begins the seduction – what else can you call this? Twisted and sexy at the same time, the man is nothing short of devastatingly charming – in the way I imagine Ted Bundy must have been!
"I could let you die, if that's what you want. If you really believe your existence has no meaning. I've thought about it myself (tears in his eyes!) once or twice over the centuries, but I'll let you in on a little secret (smile, no more tears). There's a whole world waiting out there for you, great cities and art and music." (He touches her bracelet again). "Genuine beauty – and you can have all of it."
Klaus – You can have a thousand more birthdays – all you have to do is ask.
Caroline – I don't want to die.
Klaus – There you go sweetheart – have at it.
Happy Birthday Caroline!
Did you see that momentary waiver in Caroline's face? Totally heartbreaking. She's going down and she knows it. But honestly, what 17 year old could give it all up just to prove a point?
Elena, still smarting at Stefan's methods, is not willing to agree with Damon that Stefan was the better villain – he got Klaus to blink. Damon is proud of him. And he exercises control, not pushing Elena to kiss him because he knows she is more conflicted than ever.
Stefan may have been the better villain – but Damon (as always, in my eyes) is – finally – the better man.
Good bye Jeremy. I am so glad we knew about this and that we know he's coming back because otherwise this would have been really ugly.
Caroline wakes up – fine. And finds a jewelry box. With a card – from Klaus. Inside – a bracelet. Platinum hearts and diamonds.
Matt meets Elena on Wickery Bridge. She reflects on his comment about being stuck. Elena feels that she is holding on to the girl who was supposed to die here with her parents and had a normal life.
Matt tells her she's not that girl any more – and it's OK to let her go. Matt believes in this Elena and symbolically lays the old Elena to rest.
And we end with Alaric and Meredith about to bond at the Mystic Grill bar….
…and Damon and Liz discussing the murder of the medical examiner. And not by supernatural means.
Wasn't this the guy who called Dr. Meredith "a psycho?"