\section{Introduction}
\label{sec:intro}

Narrative dynamics have long been studied by scholars~\cite{freytag_freytags_1900, vonnegut_palm_1999,  ricoeur_narrative_1980, genette_narrative_1983, phelan_time_2012, brown_shapes_2020}, mostly from a qualitative perspective, requiring human inputs to interpret text.
While the world’s literary experts are far from being supplanted by computational analyses---and arguably never will be---their attentions cannot be scaled to study very large corpora.
Recent advances in natural language processing, however, have enabled large-scale automated analysis of text to help us identify and characterize quantitative aspects of text that emerge from different corpora, such as contextual word embeddings~\cite{mikolov_efficient_2013} and new deep learning models~\cite{vaswani_attention_2017}.

Quantitative studies of narrative dynamics have also very recently gained ground~\cite{dodds_human_2015,reagan_emotional_2016,gao_multiscale_2016}.
Inspired by Vonnegut~\cite{vonnegut_palm_1999,vonnegut2005a,vonnegut2010a},
\citet{reagan_emotional_2016} examined how smoothed, ``distantly measured''~\cite{moretti2013a} happiness scores~\cite{dodds_temporal_2011} vary across the length of a book.
Reagan \textit{et al.}\ find that these happiness time series across fiction books reveal six major emotional arcs, identified as: Rags-to-riches (rise), tragedy (fall), Icarus (rise-fall), Vonnegut's man-in-a-hole (fall-rise), Cinderella (rise-fall-rise), and Oedipus (fall-rise-fall).
More recently,~\citet{boyd_narrative_2020} showed that the different parts of Freytag's dramatic arc~\cite{freytag_freytags_1900} can be differentiated by the dominant word usage.
Articles and prepositions are heavily used in the exposition stage, where narrators establish the setting.
Once the reader has an understanding of the context of the story, plot progression can proceed with more pronouns and function words.
As the story reaches a climax, more cognitive process words are used as the characters and narrator work through the conflict~\cite{boyd_narrative_2020}.
While nonfiction works such as TED talks, US Supreme Court decisions and \textit{The New York Times} articles follow similar patterns in plot progression as works of fiction, they differ in patterns of staging and cognitive processes.

\citet{schmidt_plot_2015} put forward the idea of ``plot arcs'', where a text is seen as a path through topics that represent a multidimensional space.
Similarly,~\citet{toubia_how_2021} studied narratives as paths in high dimensional word embedding space.
Dividing a text into segments represented by corresponding average word embedding vectors, the narrative is then described as the path in word embedding space obtained by moving along consecutive segments.
They identify three properties of these paths, namely the speed, volume and circuitousness in word embedding space, and examine how well these properties can predict the financial success of movies and TV shows as well as the number of citations in academic papers.

Though most studies examine changes in word usage, they focus on the general shape of narrative progression from beginning to end.
Narrative is often characterized as a time series, with the general arc represented by the rise and fall of certain markers (such as happiness scores~\cite{reagan_emotional_2016}) throughout the plot in terms of the fraction of the book covered.
This normalization by the text length allows for a direct comparison of texts of different lengths, such as a short story and a novel, and the corresponding shapes of their respective arcs.
However, this approach does not allow us to compare sections of a text with other sections of comparable length, for example, a chapter of a novel vs. a short story of similar length.

To capture the dynamics over the course of a narrative, we need to use \textit{textual time}, which we define as the number, rather than the fraction, of words covered in a text.
This is similar to \textit{narrative time} as defined in ~\cite{piper_narrative_2021}, the ``amount of time passing within a discourse'' (``time-of-telling'', in contrast to \textit{narrated time}, the ``amount of time passing within the story'' (``time-of-what-is-told'')).
However, research on narrative dynamics in textual time is scant.
While there are studies on demarcating narratives into sub-narratives~\cite{wallace_multiple_2012}, to our knowledge, there has been no quantitative study that examines narrative dynamics at resolutions finer than that of the general arc in the context of textual time.
If word usage changes across the length of a text as shown by the general arc, does it also change across smaller sections of the text? And if so, how do we characterize these fluctuations?

While there are a number of ways to quantify word usage, we are particularly interested in how essential meaning changes over textual time.
Since the 1950s, there have been efforts to distill the meaning of words into a few numbers.
The valence-arousal-dominance (VAD) framework~\cite{osgood_measurement_1957} has been one of the most widely used systems in quantifying meaning through semantic differentials.
This framework was developed using factor analysis of word scores provided by human annotators for a small set of words, which resulted in the three dimensions of valence, arousal and dominance.
However, efforts to create large VAD lexicons using human annotators~\cite{warriner_norms_2013,mohammad_obtaining_2018} have shown that valence, arousal, and dominance are linearly correlated when a larger set of words is used.
By transforming the NRC VAD lexicon---the largest VAD lexicon published with more than 20,000 curated words~\cite{mohammad_obtaining_2018}---via singular value decomposition,~\citet{dodds_ousiometrics_2021} showed that the VAD framework can be collapsed onto two linearly independent dimensions which align with the concepts of ``power'' and ``danger'', with the third linearly independent dimension (``structure'') being less relevant in real-world corpora than the former two.
Fig.~\ref{fig:power_danger} shows representative words in power-danger space for Terry Pratchett's Discworld series.
Real-world corpora also exhibit a bias towards low-danger words, which parallels the positivity bias in language~\cite{dodds_human_2015}.
Valence scores are highly correlated with happiness scores~\cite{dodds_ousiometrics_2021}, which have been used to quantify narrative structure and uncover emotional arcs~\cite{reagan_emotional_2016}.
Thus, we expect power-danger scores, both having a linear dependence on valence (see Supplementary Information), to also be suitable markers in quantifying narrative structure and to give more information than using happiness scores alone, especially since the power-danger lexicon contains more words and would yield higher word coverage.

\begin{figure}
    \centering
    \includegraphics[width=\columnwidth]{fig001_figousiometer9000_PDS_discworld001_1_noname.pdf}
    \caption{
    An `ousiogram'~\cite{dodds_ousiometrics_2021} displaying power and danger scores for a subset of 14,499 unique words appearing
    in Terry Pratchett's 41-book Discworld series.
    The example words overlaid map the indicated eight major directions of the compass of essential meaning.
    The full set of 20,006 words with power and danger scores is derived from the NRC VAD lexicon~\cite{mohammad_obtaining_2018}.
    These 14,499 unique words collectively account for 1,140,027 total words (types versus tokens).
    The histogram's color map indicates frequency of usage.
    The histogram, along with the marginal distributions for power and danger (right and top) present the same safety bias observed
    across disparate corpora~\cite{dodds_ousiometrics_2021}.
    }
    \label{fig:power_danger}
\end{figure}

An illustration of how a word usage marker, such as the danger score, changes over the course of a text is given in Figure~\ref{fig:time_series_summary}A--D.
Each time series was constructed by splitting the text into windows of size $N_w$ words that skip every $N_s$ words; in previous studies, time series for each book was constructed using the same value for $N_w$, which range from a few hundred to a few thousand, with either $N_s$ or the the number of windows fixed.
Each window corresponds to a point in the time series and is characterized by the mean score of the words it contains.
Using a larger window size smooths out the time series, sometimes revealing the general shape, such as the steady increase in danger scores in ``The Strange Case of Dr. Jekyll and Mr. Hyde'' by Robert Louis Stevenson, or an up-down pattern as in ``The Winter's Tale'' by William Shakespeare.
Longer books, however, tend to retain fluctuations at the same window sizes.
If books of different lengths are compared by the fraction of the book covered, which we define as the \textit{normalized textual time} (Figure~\ref{fig:time_series_summary}E), it would seem that the word usage changes more steadily for shorter books than longer books.
However, if we compare the time series in (raw) textual time, so that the time series are of different lengths (Figure~\ref{fig:time_series_summary}F), the shorter time series appear comparable to \textit{sections} of the longer time series.
Thus, changes in word usage may be related to the length of a text, with longer texts being a concatenation of shorter texts. In the context of narratives, this implies that long narratives may be composed of shorter narratives, each with its own arc, that function as the basic unit of story. Some of the fluctuations found in the time series may not be unwanted noise, but rather a measure of the lengths of these basic units. Our aim is to characterize these fluctuations for various texts, and to relate them to properties of the texts themselves.

With this objective, we cannot use large window sizes, since they run the risk of smoothing out potentially relevant fluctuations.
To properly characterize these basic units of narrative, we need to use smaller window sizes, but also isolate the fluctuations that arise from noise.
Since we are interested in how word usage changes over the course of a text, we can compare the time series to that obtained from a shuffled version of the text, which contains the same words but orders them randomly.
Using this as a reference isolates the effect of word order, and also avoids making assumptions on the nature of contaminating noise.
As expected, time series obtained from shuffled texts are flatter, with smaller fluctuations than those found in the original text (Figure~\ref{fig:time_series_summary}A--D).

To extract and characterize fluctuations in the time series at different scales, we use empirical mode decomposition (EMD), a technique that factors a signal into a sum of \textit{internal mode functions} (IMF), each of which is a mean-zero oscillatory time series with frequency and amplitude modulations, and a non-oscillating trend~\cite{huang_empirical_1998}.
While it is similar to wavelet decomposition in terms of its objective, EMD is data-adaptive, requiring almost no critical input from the user other than the raw time series itself, and is also well-suited for both nonstationarity and nonlinearity in time series.
A more detailed explanation of EMD is given in the Supplementary Information.

Figure~\ref{fig:sample_emd} shows the result of performing ensemble empirical decomposition (EEMD), an EMD variant that is more robust to noise~\cite{wu_ensemble_2009}, on a time series obtained from ``The Iliad''. While the original time series, derived from small, non-overlapping windows, contains significant noise, EEMD is able to separate the signal into components of different characteristic frequencies.
Further, we see that a partial reconstruction of the time series, obtained by summing the low-frequency IMFs, can replicate the time series obtained with larger window sizes, producing a denoised version.

We mentioned earlier that the time series for shuffled text are flatter than that of the original text (Figure~\ref{fig:time_series_summary}A--D), indicating that the IMFs of original and shuffled text may differ in their variances.
An illustration of how the variance changes as the IMF order increases for both the original and shuffled texts is given in Figure~\ref{fig:imf_variance_comparison}.
The variance of the IMFs in the shuffled texts generally decreases as the IMF order increases, similar to the observation for fractional Gaussian noise~\cite{wu_study_2004, flandrin_empirical_2004}.
However, this is not always true for the original texts.
For example, ``The Iliad'' shows a clear example of a book that differs in variance from the shuffled text from an IMF order below the trend, and continues to do so until the trend level.
On the other hand, ``The Picture of Dorian Gray'' clearly differs in the variance at an IMF order below the trend, but does not always do so for higher IMF orders.
In some books, such as ``The Strange Case of Dr. Jekyll and Mr. Hyde'', the original and shuffled versions only differ in the variance at the trend level.

To identify the cutoff IMF order for each book, we compare IMFs of the original text from those of different realizations of shuffled text.
The lowest IMF order at which the variance is higher than expected from the shuffled version is considered the cutoff at which word order becomes relevant.
Those with cutoff IMF orders lower than the trend are considered to have relevant fluctuations on top of the trend, while those that do not are considered to be trend-only.
To compare the variance, we use the method used by~\citet{wu_study_2004} and~\citet{ flandrin_empirical_2004}, where the variances of the IMFs of the target series are rescaled so that the variances of the first IMFs of the target (original text) and reference (shuffled text) are comparable.
The assumption here is that the first IMF is noise; as we are using non-overlapping windows of size $N_w=50$, it is very difficult for a coherent narrative to be present at this scale, and the first IMF will most likely pick up noise due to the small window size.
Pairwise comparison of each IMF for the original and shuffled versions shows that the IMFs have similar periods for the first IMF, supporting this assumption.
We also verify that the periods are comparable up to the cutoff IMF (Figure~\ref{supp-fig:imf_ratios}).
While rescaling to the median of the first IMF is a reasonable choice, we also examine how changing the rescaling factor to the 1st percentile of the first IMF or unity (i.e., no rescaling) affects the results.

\begin{figure*}
    \centering
    \includegraphics[]{fig002_time_series_summary_danger.pdf}
    \caption{(a--d) These plots illustrate the effect of window sizes, shuffling, and book length on how danger scores change over the course of a book. Using larger window sizes (solid vs. dotted) results in smoother curves, although longer books tend to retain fluctuations in the time series for the same window size (a, b vs. c, d). Shuffling the text results in time series that are flatter than the original (gray). (e) Comparing books using normalized textual time shows more fluctuations for longer books than shorter ones, but (f) plotting the time series in raw textual time shows similarities between shorter books and sections of longer books. A skip size of $N_s=200$ words was used for all plots shown above.}
    \label{fig:time_series_summary}
\end{figure*}

\begin{figure*}
    \centering
    \includegraphics[width=1.5\columnwidth]{fig003_sample_emd_danger.pdf}
    \caption{The decomposition of the danger time series of ``The Iliad'' using EEMD. The raw time series was obtained using non-overlapping windows with $N_w=50, N_s=50$ (top panel), and the IMFs and the trend obtained from EEMD are shown. The lowermost panel shows the sum of IMFs 5-7 and the trend (``reconstructed''), superimposed with the danger time series obtained using larger overlapping windows ($N_w=5000, N_s=200$). Note that the partial reconstruction from time series obtained using smaller windows is very similar to the raw time series obtained using larger, overlapping windows.}
    \label{fig:sample_emd}
\end{figure*}

\begin{figure*}
    \centering
    \includegraphics[]{fig004_imf_variance_comparison_danger.pdf}
    \caption{A comparison of the variances of the IMFs for the original text and 100 different realizations of shuffled text for three books in the dataset. Lower-order IMFs are more likely to correspond to noise, while higher-order IMFs are more likely to contain relevant information. Note that while technically the trend is not an IMF, for comparison purposes, the trend is included in this plot as the highest IMF order found for a given time series.}
    \label{fig:imf_variance_comparison}
\end{figure*}
\section{Results}

We analyzed more than 30,000 books from Project Gutenberg, an online repository of books that are now in the public domain.
The selected books are almost exclusively in English, with at least 60\% of the unique words in each book included in the lexicon. Around 60\% of the books are in the ``Language and Literature'' Library of Congress Classification (LCC) code  (class label ``P''), while the remaining are spread out among the various LCC class labels, with ``World History'' (class label ``D'') as the next largest category of books in the dataset (around 8\% of the books).
While we performed the analysis for both danger and power scores, the results are similar for both, and we only discuss the danger scores in the main text. The results for power scores are included in the Supplementary Information.

\subsection{Cutoff IMF orders}

Figure~\ref{fig:cutoff_imf_summary}A shows histograms of the number of words found in books that have a cutoff IMF order below the trend, and those that do not.
While the choice of the rescaling factor influences the stringency of the cutoff criteria, they also offer an insight into the robustness of the results.

Rescaling to the 1st percentile of the first IMF requires a higher threshold to differentiate the IMFs, and thus more books are classified as trend-only. For those classified as having fluctuations on top of the trend, the cutoff periods obtained may be higher. On the other hand, no rescaling makes it more likely to see differences in the lower IMF orders, resulting in lower predicted cutoff periods.
We note that when no rescaling is performed (i.e., the rescaling factor is 1), the cutoff IMF order for many of the books was the first IMF, which does not make much sense given that the window size of 50 words is relatively small and that the first IMF only corresponds to a period of around 100 words.
However, we know from the IMF decomposition of fractional Gaussian noise~\cite{wu_study_2004, flandrin_emd_2005} that the first IMF has a different behavior compared to the higher-order IMFs.
Thus, for purposes of comparison, we disregard the first IMF in obtaining the cutoff IMF order when no rescaling is applied.

The predicted cutoff IMF order, including the case when it does not exist, differs for majority of the books examined.
However, we find some general results that hold regardless of the rescaling factor used.
For instance, we find that longer books tend to have relevant fluctuations on top of the trend, while shorter books do not (Figure~\ref{fig:cutoff_imf_summary}A), especially for books with less than 3000 words or greater than 100,000 words.
Books with word counts in between these values may or may not have relevant fluctuations on top of the trend and the choice of the rescaling factor may influence the prediction for the cutoff IMF order.
When rescaling by the 50th percentile of the first IMF, the 25th to 75th percentiles range from roughly 1000 to 3200 words; when rescaling by the 1st percentile of the first IMF, this changes to around 1200 to 6400 words; and when no rescaling is used, this changes to around 500 to 1400 words.
In the case when relevant fluctuations on top of the trend are found, no clear relation between the cutoff IMF period and the book length is observed.
These can be seen in the heatmaps and the corresponding histograms in Figure~\ref{fig:cutoff_imf_summary}B--D.
We also note that, with very few exceptions, the cutoff period is less than the book length.
The striated pattern in the heatmaps for the cutoff periods is due to the discreteness of the EEMD, which is observed even in white noise~\cite{wu_study_2004}, where the EEMD acts like a dyadic filter.
While these results were generated using all the books in the corpus, both fiction and nonfiction, we also analyze the different book classifications in the next subsection and include more details in the Supplementary Information.

Similarly, the raw variances of the cutoff IMFs also do not exhibit any relationship with the book length (Figure~\ref{fig:cutoff_imf_summary}E--G).
The range of the variance values is also wider in comparison to that observed for the first IMF (Figure~\ref{supp-fig:imf_ratios}E--F), indicating that the books generally start to differ from each other at higher IMF orders, while the first IMF likely corresponds to noise due to the windowing technique used for all of the books.
Further, while the number of IMFs found by EEMD for the original time series increases with the book length (Figure~\ref{fig:cutoff_imf_summary}H--J), the cutoff IMF order itself shows no such correlation (Figure~\ref{fig:cutoff_imf_summary}K--M).

We find similar observations from our analysis on power time series. Shorter books are more likely to be trend-only, while longer books have relevant fluctuations above the general trend. While the cutoff periods are not identical to those found in danger scores, they are of the same order of magnitude (see Supplementary Information, Figure~\ref{supp-fig:cutoff_imf_summary_power},  Table~\ref{supp-tab:period_numwords}).

\begin{figure*}
    \centering
    \includegraphics[]{fig005_cutoff_imf_summary_danger.pdf}
    \caption{Characterizing relevant fluctuations in the danger time series of books in the corpus. (a) These histograms show the number of books that have fluctuations on top of the trend (green) and those that do not (purple). The different line widths and line styles correspond to the different rescaling factors: solid thick lines for using the median of the first IMF, solid thin lines for using the 1st percentile of the first IMF, and dotted lines for no rescaling. (b\textendash d). These are heatmaps that show the relationship between the period of the cutoff IMFs (as the number of words) and the book length for the various rescaling factors (shown above each plot). We can see that most of the points fall below the 45 degree line (red dashed line), indicating that the cutoff IMF period is less than than the book length for the vast majority of books. The histograms for the cutoff IMF period are shown on the right side of each plot, with the 25th, 50th, and 75th percentiles shown in dotted black, solid red, and dashed black lines, respectively. The rest of the figures are similar to (b\textendash d), but for different quantities: variance (e\textendash g), number of IMFs (h\textendash j; excludes the trend), and cutoff IMF order, with the first IMF counted as 1 (k\textendash m).}
    \label{fig:cutoff_imf_summary}
\end{figure*}

\subsection{Relationship to book content}

The Gutenberg corpus assigns books to their Library of Congress Classification (LCC) subclass labels (e.g., PS for American Literature).
While it is possible for a book to have more than one LCC subclass label, around 95\% of the books we examined only had 1 label. The top 5 subclass labels with the most books in the dataset are American literature (PS), English literature (PR), Fiction and juvenile belles lettres (PZ), Periodicals (AP), and French/Italian/Spanish/Portuguese literature (PQ). We also looked at the class labels rather than the subclass labels (i.e., the first letter of the subclass labels).
Around 60\% of the class labels are for Language and Literature (P), while World History and History of Europe, Asia, Africa, Australia, New Zealand, etc. (D); Philosophy, Psychology and Religion (B); General Works (A); and History of America (E) round up the top 5 class labels.
While there are differences in the medians for the cutoff periods and variances across subclass and class labels, the spread of both the cutoff IMF period and variance are comparable across the top 5 class and subclass labels. This indicates that the breadth of the LCC system at the class or subclass levels obscures the differences that may arise from smaller groups within these categories (Figure~\ref{fig:boxplot_by_lcc}).

\begin{figure*}
    \centering
    \includegraphics[]{fig006_boxplot_lcc_combined_danger.pdf}
    \caption{Periods and variances of the cutoff IMF in the danger time series for the top 5 LCC subclass and class labels with the most number of books in the dataset examined. (a-f) These are the boxplots for the periods (see x-axis at the bottom for scale) and the variances (see x-axis at the top for scale) of the cutoff IMF for books in the entire dataset (``all'') as well as that for each of the top 5 LCC subclass and class labels by size. The black line inside each box is the median, the box ranges from the 25th to 75th percentiles, and the whiskers extend from the 9th percentile to the 91st percentile. (g-h) show the number of books analyzed in the dataset (``all'') and the top 5 subclass and class labels, including trend-only books.}
    \label{fig:boxplot_by_lcc}
\end{figure*}

On the other hand, we find that using very specific filters on the title of the book yields more insightful results (Figure~\ref{fig:words_in_title_boxplot}).
For books with a word beginning with ``poem'' in the title, those with a cutoff IMF order below the trend exhibit shorter cutoff IMF periods and markedly higher cutoff IMF variances compared to the rest of the dataset, which is consistent with poems being typically short, emotional and compact.
On the other hand, books with titles containing a word beginning with ``manual'' exhibit a lower median cutoff IMF variance.
This may be because books in this category (``A manual of clinical diagnosis'', ``The ladies' book of etiquette, and manual of politeness: a complete hand book for the use of the lady in polite society'', ``The skilful cook: a practical manual of modern experience,'' etc.) tend to be instructional and uniform in terms of topic and mood.
Books with words beginning with ``play'' have a higher median cutoff IMF period and lower cutoff IMF variance than books without.
Results for keywords such as ``collection'', ``short stor'' (includes both ``short story'' and ``short stories''), ``report'' and ``essay'' are more sensitive to the choice of rescaling factor.

For power time series, while the values for the cutoff IMF periods and variances obtained are different, we also find similar overlap across different LCC class and subclass labels. We also find differences across different books depending on words in their titles (see Supplementary Information, Figures~\ref{supp-fig:boxplot_by_lcc_power} and~\ref{supp-fig:words_in_title_boxplot_power}).

\begin{figure*}
    \centering
    \includegraphics[]{fig007_words_in_title_boxplot_danger.pdf}
    \caption{Periods and variances in the danger time series for books with a word in the title if they have a cutoff IMF order below the trend. Note that since the number of books for each word is much less than the total number of books examined, the boxplots for books not containing a given word in the title will be almost identical to the boxplots for the entire dataset (``all''). (a--c) show the boxplots for the cutoff IMF period, while (d--f) show the boxplots for the cutoff IMF variance for different rescaling factors. The black line inside each box is the median, the box ranges from the 25th to 75th percentiles, and the whiskers extend from the 9th percentile to the 91st percentile. (d) shows the number of books with the given keywords in the title, including trend-only books.}
    \label{fig:words_in_title_boxplot}
\end{figure*}

\section{Discussion}
\label{sec:summary}

\subsection{Summary of results}
We examine the fluctuations in the danger and power dimensions, a reinterpretation of the valence-arousal-dominance framework, for more than 30,000 English books in Project Gutenberg.
Changes in word usage across text are analyzed by segmenting the text into windows and converting it to a time series.
While window size has conventionally been preset independent of the book length, we find that large window sizes remove oscillations in word usage in shorter books but retain them in longer books.
A comparison of the time series in textual time, which we define as the number of words seen up to the present moment in a book, reveals that the shorter time series are similar to subsections of longer time series.
As books generally contain narratives, this indicates that longer texts may consist of shorter texts that correspond to a basic unit of narrative, similar to subplots in a novel.

We extract the different scales of fluctuations in the time series obtained from text using empirical mode decomposition (EMD).
EMD decomposes a time series into a non-oscillatory trend and a sequence of oscillatory intrinsic mode functions (IMFs) that differ in their characteristic frequencies.
It allows for both nonlinearity and nonstationarity, and gives an intuitive and data-driven understanding of the underlying fluctuations in a given time series.

For each book, we derive the danger and power time series for both the original text as well as an ensemble of shuffled versions.
By comparing the variances of the resulting IMFs of the time series obtained from the original text to those of the shuffled texts, we find that shorter books tend to exhibit only a non-oscillatory trend while longer books tend to exhibit relevant fluctuations with periods around the order of a few thousand words, shorter than the length of the book.
The period and variance of the relevant fluctuations do not depend on the book length, despite the number of IMFs increasing with the book length. Segregation of books by the Library of Congress Classification class or subclass codes does not result in well-defined groups that show variation in the periods and variances of the relevant fluctuations.
However, we observed differences when we applied very specific filters, such as words in a title.
We infer that what characterizes the scale of a book's relevant fluctuations is neither its general topic nor length, but rather more specific aspects such as its structure and content (e.g., poems vs. manuals).

The impact of our study is mainly on two fronts: providing (1) a quantitative basis for the length of a basic unit of narrative, and (2) a method for denoising time series obtained from texts without resorting to using arbitrarily large window sizes.
We discuss these in the following paragraphs.

\subsection{Word counts and cutoff periods}
The shape of the general narrative arc has been the focus of a number of studies~\cite{freytag_freytags_1900, vonnegut_palm_1999, reagan_emotional_2016, schmidt_plot_2015, gao_multiscale_2016, boyd_narrative_2020}.
Though the existence of subplots within these general narrative arcs has long been acknowledged in both the literature and computational domain~\cite{wallace_multiple_2012, reagan_emotional_2016}, to our knowledge, our study is the first to quantitatively analyze, in textual time, these basic units of narratives on which longer narratives are built.

While it is theoretically possible to write a basic narrative in a few words (e.g., ``For sale, baby shoes, never worn.'') or a hundred thousand, balancing the flexibility of longer texts with the constraints imposed by reader engagement and publication costs has given writers and editors rules of thumb for word counts. Short stories and novellas are characterized by a focus on a single central conflict~\cite{masterclass_learn_2021} or a single chain of events~\cite{baldick_oxford_2015}.
In contrast, the longer word count of novels ($>$40,000 words~\cite{world_science_fiction_society_hugo_2022, science_fictions__fantasy_writers_of_america_nebula_2020}) allows for a fuller development of its characters and themes~\cite{baldick_oxford_2015} through the use of chapters, each of which is similar to a short story. This is consistent with our results: trend-only books begin to decrease in number above a word count of 10,000, while the number of books with relevant fluctuations above the trend continues to increase, reaching its peak for books with 50,000 to 100,000 words (Figure~\ref{fig:cutoff_imf_summary}). Further, the cutoff IMF periods are in the order of a few thousand words, comparable to the length of chapters, which are typically 1,500--5,000 words long~\cite{bingham_how_2020, noauthor_how_2017}.
We also note that our dataset is biased towards successful books that have stood the test of time, so it is unlikely to find books that do not satisfy general guidelines set by writers and editors.

\subsection{Fiction and nonfiction works}
While plots are generally associated with fiction writing, narratives can be found in nonfiction works as well.
Academic papers, for example, also show changes in word usage, although with a different signature than that found in fiction pieces~\cite{pechenick_characterizing_2015, boyd_narrative_2020}.
While 60\% of the books we examined are in the Language and Literature Library of Congress category, other categories also exhibit similar general patterns for the word counts of books that are trend-only and those that are not, as well as the range of the periods and variances of the relevant fluctuations (see Supplementary Information for a comparison between literature and non-literature books, Table~\ref{supp-tab:period_numwords}, Figures~\ref{supp-fig:cutoff_imf_summary_P}--\ref{supp-fig:cutoff_imf_summary_notP_power}).
Our results indicate that fluctuations within the general narrative arc may be present in both fiction and nonfiction works.
As nonfiction works also aim to communicate ideas, it is expected that they are also bound by rules of word usage, which is again consistent with our findings.

\subsection{Data-adaptive denoising of text-derived time series}
On the quantitative side, the method we used in this paper allows us to smooth out fluctuations in time series derived from text of various lengths.
While using large window sizes reduces noise, it is unclear if it also inadvertently smooths out relevant information, such as fluctuations associated with subplots. By performing partial reconstruction using the relevant IMF orders, we have a data-driven denoising approach that works for both short and long texts.

As our method relies heavily on empirical mode decomposition, it also carries the same limitations.
Although EMD will ideally construct different modes for fluctuations of sufficiently different frequencies, mode mixing may occur due to signal intermittency.
Using ensemble EMD (EEMD) mitigates this problem, but does not ensure that it will remove mode mixing in all cases.
We also note that we compare the original and shuffled texts only in the variance of their IMFs.
While we verified that the pairwise comparison of IMFs results in comparable IMF periods for the original and shuffled text up to the cutoff IMF order, we only defined a difference in IMFs in terms of their variance. While this method has been proposed for finding the appropriate cutoff IMF order in using EMD for denoising~\cite{wu_study_2004, flandrin_emd_2005}, it will miss any other difference that is not associated with the variance.
We also considered using the probability density function to compare IMFs; however, this method failed to produce accurate results in synthetic data, while the variance comparison method performed well in all the tests we performed. While our general observations are robust to the choice of parameters in the variance comparison method, different results may be obtained for a particular book depending on the parameters used. Thus, while our method can extract general trends on relevant fluctuations across a corpus, sensitivity analysis must be performed when results for a particular book are of interest.

\subsection{Future work}
We have studied the scale of fluctuations within texts in their danger and power time series. While danger and power are orthogonal to each other and produce similar temporal results, we did not look at how they work together as a book progresses. Similar to the work by~\citet{toubia_how_2021}, we hope to do a spatial analysis in power-danger space, specifically on the path taken by the narrative. Other possible avenues for future work include expanding our corpus to include various texts, such as screenplays and movies, as well as comparing different versions of a book, such as the first draft and the final published version.
\section{Materials and Methods}
\label{sec:method}

We downloaded more than 45,000 books from Project Gutenberg, an online repository of books in public domain. The Gutenberg headers were removed using code from the Standardized Project Gutenberg Corpus~\cite{gerlach_standardized_2020}. Contractions, when unambiguous, were replaced with their expanded versions (e.g., ``n't'' to `` not''); if ambiguous, they were deleted, similar to what was done in~\cite{fudolig_sentiment_2022}. The remaining text was then converted to lowercase and tokenized using whitespace as separators, disregarding words that contain non-word characters and digits, and ignoring punctuation marks. This converts the text into a sequence of words.

We then examine the word coverage of the power-danger lexicon. While the original NRC-VAD lexicon~\cite{mohammad_obtaining_2018}, from which the danger and power scores were derived, contained around 20,000 words, we expanded this to include noun plurals and conjugated forms not in the lexicon. Scores of the base forms of the verbs and nouns were used as the scores of their conjugated versions, expanding the lexicon to 32,721 words. We only consider books with a 60\% unique word coverage, which consist almost exclusively of English text and cover 93\% of all English books in the downloaded set. The median unique word coverage of this subset of books is 73\%. Filtering for word coverage, removing books with duplicate titles, as well as requiring that the time series must have at least one lexicon word and that the EEMD can be successfully computed (i.e., the EEMD decomposes up to the trend level, such that the mean of the sum of the EEMD results is within 10\% of the mean of the original time series), leaves us with 31,690 books (Figure~\ref{fig:word_coverage}).

\begin{figure}
    \centering
    \includegraphics[]{fig008_word_coverage.pdf}
    \caption{Word coverage of the PDS lexicon. The blue histograms correspond to the unique word coverage, while the orange histograms correspond to the word coverage allowing for word repetition. We show the histograms for all the books downloaded in our dataset (empty bars) as well as those we analyzed (shaded bars), and the dashed lines show the median word coverage of the books analyzed. The books included in our analysis do not include duplicate titles and must have (1) a unique word coverage of at least 60\%, (2) at least one lexicon word in every window and (3) intrinsic mode functions (IMFs) that can be successfully computed.}
    \label{fig:word_coverage}
\end{figure}

We construct the danger and power time series by segmenting the sequence of words into non-overlapping windows of size $N_w=50$, each of which corresponding to a point in the time series.
In each window, we take each word $w_i$ with score $s_i$ in the lexicon that occurs $n_i$ times in the window.
If there are $m$ unique words in the window that are in the lexicon, then the score for the window is

\begin{equation}
    s_w = \frac{\sum_{i=1}^m n_i s_i}{\sum_{i=1}^m n_i}
\label{eq:score}
\end{equation}

The reference time series are constructed by shuffling the tokenized version of the text, performing the windowing technique, and recomputing the average scores for each window.
This assures that the time series of both the target (original text) and the reference (shuffled text) are of the same length.

We use ensemble empirical mode decomposition (EEMD)~\cite{wu_ensemble_2009} with an ensemble size of 100 to obtain the internal mode functions (IMFs) for the time series corresponding to the original text.
Each time series in the ensemble is the sum of the raw time series and white noise with a standard deviation $0.2\sigma$, where $\sigma$ is the standard deviation of the raw time series, as suggested by~\citet{wu_ensemble_2009}.
As our reference time series, we use 100 different shuffled versions of the original text.
These are generated by shuffling the tokenized version of the text, performing the windowing technique, and recomputing the average scores for each window. This assures that the time series of both the target and the reference are of the same length.
For each of the reference time series, we use basic empirical mode decomposition (EMD) to obtain the IMFs.
We use the Python package \texttt{emd}~\cite{quinn_emd_2021} to perform all EMD-related calculations.

We then divide the variances of the IMFs of the time series from original text by a rescaling factor, as suggested in~\cite{wu_study_2004, flandrin_emd_2005}. Three different rescaling factors were considered based on the distribution of the first IMFs of the reference time series: the median, the 1st percentile, and unity (no rescaling). The lowest IMF order at which the rescaled variance is higher than the 99th percentile of the variances for shuffled text is considered as the cutoff IMF order.

Once the cutoff IMF order is identified, the corresponding period is computed from the center of the frequency bin with the highest energy as obtained using the Hilbert-Huang transform (HHT).
Since we want to count periods in the unit of number of words, we compute for the HHT setting the sampling rate at ${N_s}^{-1} \textrm{word}^{-1}$, where $N_s=50$ is the skip size in the windowing procedure.
We use logarithmically spaced frequency bins, spanning from $10^{-6} \textrm{ word}^{-1}$ to $1 \textrm{ word}^{-1}$, resulting in a range of period values between 1 to $10^6$ words, chosen because none of the texts examined exceed $10^6$ words in length.
The choice of logarithmic spacing is motivated in part by how EMD on white noise performs like a dyadic filter, with IMF frequencies decreasing by roughly a factor of 2 for every order.
Further, in our preliminary analysis for select books, we find that logarithmic spacing provides an adequate representation of the spectra, especially since the IMF frequencies and periods span orders of magnitude.
We emphasize that obtaining a characteristic value for the \textit{period} of the IMF is independent of the method used to extract the cutoff IMF \textit{order} discussed earlier, and that the bins used for the HHT are the same across all texts.

\acknowledgments
The authors are grateful for the computing resources provided by the Vermont Advanced Computing Core
and financial support from the Massachusetts Mutual Life Insurance Company.
Computations were performed on the Vermont Advanced Computing Core supported in part by NSF award No. OAC-1827314. M.I.F. is also grateful to Miguel Fudolig, Joshua Minot, Andy Reagan and Aritra Banerjee for helpful discussions.

\section*{Supplementary Information}

\subsection*{Power-danger framework}
While the valence-arousal-dominance (VAD) framework~\cite{osgood_measurement_1957} has been one of the longstanding theories for the quantification of meaning, attempts to measure VAD scores for a larger set of words reveal that these three dimensions are not necessarily orthogonal. In particular, the NRC VAD lexicon~\cite{mohammad_obtaining_2018}, which has around 20,000 words, shows moderate correlation between pairs of variables ($r_{V, A} \simeq -0.27$,  $r_{A, D} \simeq 0.30$, and  $r_{V, D} \simeq 0.49$). Performing singular value decomposition creates three new dimensions (goodness, energy and structure) that are linear combinations of valence, arousal and dominance, and a clockwise rotation of $\pi / 4$ in the goodness-energy plane creates a framework where each dimension can be interpreted by the words that occupy its extreme values~\cite{dodds_ousiometrics_2021}. The resulting three dimensions are power, danger, and structure, and are related to valence, arousal, and dominance in the following way:

\begin{equation}
    \begin{bmatrix}
    \textrm{Power} \\ \textrm{Danger} \\ \textrm{Structure}
    \end{bmatrix}
    =
    \begin{bmatrix}
    \frac{1}{\sqrt{2}} &   \frac{1}{\sqrt{2}} & 0\\
    -  \frac{1}{\sqrt{2}} &   \frac{1}{\sqrt{2}} & 0 \\
    0 & 0 & 1 \\
    \end{bmatrix}
    \begin{bmatrix}
    +0.86 & -0.15 & +0.48 \\
    -0.16 & +0.83 & +0.54 \\
    +0.48 & +0.55 & -0.69
    \end{bmatrix}
    \begin{bmatrix}
    \textrm{Valence$^{\prime}$} \\ \textrm{Arousal$^{\prime}$} \\ \textrm{Dominance$^{\prime}$}
    \end{bmatrix}
\end{equation}

\noindent where the $^\prime$ symbol indicates that the valence, arousal, and dominance values are rescaled to lie in the range $[-\frac{1}{2}, \frac{1}{2}]$. In real-world corpora, power and danger are the more relevant dimensions. We refer the reader to~\cite{dodds_ousiometrics_2021} for an in-depth discussion of the power-danger-structure framework.

\clearpage
\subsection*{Comparison between first and cutoff IMFs}
\begin{figure*}[ht!]
    \centering
    \includegraphics[width=\textwidth]{fig009_first_imf_info_ratio.pdf}
    \caption{Histograms of the median ratios (measured across the different shuffling realizations) of the period of the IMF corresponding to the original text to that of the shuffled text for the \textit{danger} time series, as well as the period and variance corresponding to the first IMF. (a--d) The unshaded histograms refer to ratios for the first IMF, while the shaded histograms refer to the ratios for the cutoff IMF. In (a), we include all books, whether a cutoff IMF order below the trend was detected (``fluc'') or not (``trend''). In (b)--(d), we only include the ratios for the books where a cutoff IMF order below the trend was detected using the variance comparison method when the IMFs are rescaled by the rescaling factor (50th percentile for (b), 1st percentile for (c), no rescaling for (d)). (e--f) These heatmaps summarize the period and variance corresponding to the first IMF of the books in the dataset as a function of the book length. The right side of each heatmap shows the corresponding histogram and the 25th (black, dotted line), 50th (red, solid line) and 75th (black, dashed line) percentiles.}
    \label{fig:imf_ratios}
\end{figure*}

\begin{figure*}[ht!]
    \centering
    \includegraphics[width=\textwidth]{fig010_first_imf_info_ratio_power.pdf}
    \caption{Histograms of the median ratios (measured across the different shuffling realizations) of the period of the IMF corresponding to the original text to that of the shuffled text for the \textit{power} time series, as well as the period and variance corresponding to the first IMF. (a--d) The unshaded histograms refer to ratios for the first IMF, while the shaded histograms refer to the ratios for the cutoff IMF. In (a), we include all books, whether a cutoff IMF order below the trend was detected (``fluc'') or not (``trend''). In (b)--(d), we only include the ratios for the books where a cutoff IMF order below the trend was detected using the variance comparison method when the IMFs are rescaled by the rescaling factor (50th percentile for (b), 1st percentile for (c), no rescaling for (d)). (e--f) These heatmaps summarize the period and variance corresponding to the first IMF of the books in the dataset as a function of the book length. The right side of each heatmap shows the corresponding histogram and the 25th (black, dotted line), 50th (red, solid line) and 75th (black, dashed line) percentiles.}
    \label{fig:imf_ratios_power}
\end{figure*}

\clearpage
\subsection*{Analysis of power time series}
\begin{figure*}[ht!]
    \centering
    \includegraphics[height=0.7\textheight]{fig011_cutoff_imf_summary_power.pdf}
    \caption{Characterizing relevant fluctuations in the power time series of books in the corpus (c.f. Figure~\ref{fig:cutoff_imf_summary}). (a) These histograms show the number of books that have fluctuations on top of the trend (green) and those that do not (purple). The different line widths and line styles correspond to the different rescaling factors: solid thick lines for using the median of the first IMF, solid thin lines for using the 1st percentile of the first IMF, and dotted lines for no rescaling. (b\textendash d). These are heatmaps that show the relationship between the period of the cutoff IMFs (as the number of words) and the book length for the various rescaling factors (shown above each plot). We can see that most of the points fall below the 45 degree line (red dashed line), indicating that the cutoff IMF period is less than than the book length for the vast majority of books. The histograms for the cutoff IMF period are shown on the right side of each plot, with the 25th, 50th, and 75th percentiles shown in dotted black, solid red, and dashed black lines, respectively. The rest of the figures are similar to (b\textendash d), but for different quantities: variance (e\textendash g), number of IMFs (h\textendash j), and cutoff IMF order, with the first IMF counted as 1 (k\textendash m).}
    \label{fig:cutoff_imf_summary_power}
\end{figure*}

\begin{figure*}[ht!]
    \centering
    \includegraphics[]{fig012_boxplot_lcc_combined_power.pdf}
    \caption{Periods and variances of the cutoff IMF in the power time series for the top 5 LCC subclass and class labels with the most number of books in the dataset examined. (a-f) These are the boxplots for the periods (see x-axis at the bottom for scale) and the variances (see x-axis at the top for scale) of the cutoff IMF for books in the entire dataset (``all'') as well as that for each of the top 5 LCC subclass labels by size. The black line inside each box is the median, the box ranges from the 25th to 75th percentiles, and the whiskers extend from the 9th percentile to the 91st percentile. (g-h) shows the number of books analyzed in the dataset (``all'') and the top 5 subclass and class labels, including trend-only books.}
    \label{fig:boxplot_by_lcc_power}
\end{figure*}

\begin{figure*}[ht!]
    \centering
    \includegraphics[]{fig013_words_in_title_boxplot_power.pdf}
    \caption{Periods and variances in the power time series for books with a word in the title if they have a cutoff IMF order below the trend. Note that since the number of books for each word is much less than the total number of books examined, the boxplots for books not containing a given word in the title will be almost identical to the boxplots for the entire dataset (``all''). (a--c) show the boxplots for the cutoff IMF period, while (d--f) show the boxplots for the cutoff IMF variance for different rescaling factors. The black line inside each box is the median, the box ranges from the 25th to 75th percentiles, and the whiskers extend from the 9th percentile to the 91st percentile. (d) shows the number of books with the given keywords in the title, including trend-only books.}
    \label{fig:words_in_title_boxplot_power}
\end{figure*}

\clearpage
\subsection*{Comparison between literature and non-literature books}

\begin{table*}[ht!]
\begin{tabularx}{\textwidth}{lc|CCC|CCC|CCC}
\hline
 &
  \textit{Rescaling factor} &
  \multicolumn{3}{c|}{\textbf{50th percentile}} &
  \multicolumn{3}{c|}{\textbf{1st percentile}} &
  \multicolumn{3}{c}{\textbf{Without rescaling}} \\ \cline{3-11}
 &
  \textit{Percentile} &
  \textbf{25th} &
  \textbf{50th} &
  \textbf{75th} &
  \textbf{25th} &
  \textbf{50th} &
  \textbf{75th} &
  \textbf{25th} &
  \textbf{50th} &
  \textbf{75th} \\ \hline
\multicolumn{1}{c}{\multirow{3}{*}{\rotatebox[origin=c]{90}{\textbf{Danger}}}} &
  All &
  1000 &
  1400 &
  3200 &
  1200 &
  2800 &
  6400 &
  500 &
  600 &
  1400 \\
  & Literature &
  1000 &
  2100 &
  3700 &
  1400 &
  2800 &
  6400 &
  400 &
  900 &
  2100 \\
  & Non-literature &
  900 &
  1200 &
  2800 &
  1200 &
  2800 &
  5600 &
  400 &
  500 &
  1200 \\ \hline
\multirow{3}{*}{\rotatebox[origin=c]{90}{\textbf{Power}}} &
  All &
  1000 &
  2400 &
  4200 &
  1400 &
  3200 &
  7400 &
  400 &
  500 &
  1200 \\
  & Literature &
  1000 &
  2400 &
  5600 &
  2400 &
  3200 &
  7400 &
  400 &
  500 &
  1200 \\
  & Non-literature &
  1000 &
  1400 &
  3200 &
  1200 &
  2800 &
  6400 &
  400 &
  500 &
  1100 \\ \hline
\end{tabularx}
\caption{Cutoff IMF period in number of words, rounded up to the nearest hundred, for danger and power time series for books with a cutoff IMF order below the trend.}
\label{tab:period_numwords}
\end{table*}

\begin{figure*}[ht!]
    \centering
    \includegraphics[]{fig014_cutoff_imf_summary_lccbroad=P_danger.pdf}
    \caption{Characterizing relevant fluctuations in the \textit{danger} time series of books in the corpus for books under the Language and Literature Library of Congress Classification code ``P'' (c.f. Figure~\ref{fig:cutoff_imf_summary}). (a) These histograms show the number of books that have fluctuations on top of the trend (green) and those that do not (purple). The different line widths and line styles correspond to the different rescaling factors: solid thick lines for using the median of the first IMF, solid thin lines for using the 1st percentile of the first IMF, and dotted lines for no rescaling. (b\textendash d). These are heatmaps that show the relationship between the period of the cutoff IMFs (as the number of words) and the book length for the various rescaling factors (shown above each plot). We can see that most of the points fall below the 45 degree line (red dashed line), indicating that the cutoff IMF period is less than than the book length for the vast majority of books. The histograms for the cutoff IMF period are shown on the right side of each plot, with the 25th, 50th, and 75th percentiles shown in dotted black, solid red, and dashed black lines, respectively.The rest of the figures are similar to (b\textendash d), but for different quantities: variance (e\textendash g), number of IMFs (h\textendash j), and cutoff IMF order, with the first IMF counted as 1 (k\textendash m).}
    \label{fig:cutoff_imf_summary_P}
\end{figure*}

\begin{figure*}[ht!]
    \centering
    \includegraphics[]{fig015_cutoff_imf_summary_lccbroad=notP_danger.pdf}
    \caption{Characterizing relevant fluctuations in the \textit{danger} time series of books in the corpus for books in codes \textit{other than} the Language and Literature Library of Congress Classification code ``P'' (c.f. Figure~\ref{fig:cutoff_imf_summary}). (a) These histograms show the number of books that have fluctuations on top of the trend (green) and those that do not (purple). The different line widths and line styles correspond to the different rescaling factors: solid thick lines for using the median of the first IMF, solid thin lines for using the 1st percentile of the first IMF, and dotted lines for no rescaling. (b\textendash d). These are heatmaps that show the relationship between the period of the cutoff IMFs (as the number of words) and the book length for the various rescaling factors (shown above each plot). We can see that most of the points fall below the 45 degree line (red dashed line), indicating that the cutoff IMF period is less than than the book length for the vast majority of books. The histograms for the cutoff IMF period are shown on the right side of each plot, with the 25th, 50th, and 75th percentiles shown in dotted black, solid red, and dashed black lines, respectively.The rest of the figures are similar to (b\textendash d), but for different quantities: variance (e\textendash g), number of IMFs (h\textendash j), and cutoff IMF order, with the first IMF counted as 1 (k\textendash m).}
    \label{fig:cutoff_imf_summary_notP}
\end{figure*}

\begin{figure*}[ht!]
    \centering
    \includegraphics[]{fig016_cutoff_imf_summary_lccbroad=P_power.pdf}
    \caption{Characterizing relevant fluctuations in the \textit{power} time series of books in the corpus for books under the Language and Literature Library of Congress Classification code ``P'' (c.f. Figure~\ref{fig:cutoff_imf_summary}). (a) These histograms show the number of books that have fluctuations on top of the trend (green) and those that do not (purple). The different line widths and line styles correspond to the different rescaling factors: solid thick lines for using the median of the first IMF, solid thin lines for using the 1st percentile of the first IMF, and dotted lines for no rescaling. (b\textendash d). These are heatmaps that show the relationship between the period of the cutoff IMFs (as the number of words) and the book length for the various rescaling factors (shown above each plot). We can see that most of the points fall below the 45 degree line (red dashed line), indicating that the cutoff IMF period is less than than the book length for the vast majority of books. The histograms for the cutoff IMF period are shown on the right side of each plot, with the 25th, 50th, and 75th percentiles shown in dotted black, solid red, and dashed black lines, respectively.The rest of the figures are similar to (b\textendash d), but for different quantities: variance (e\textendash g), number of IMFs (h\textendash j), and cutoff IMF order, with the first IMF counted as 1 (k\textendash m).}
    \label{fig:cutoff_imf_summary_P_power}
\end{figure*}

\begin{figure*}[ht!]
    \centering
    \includegraphics[]{fig017_cutoff_imf_summary_lccbroad=notP_power.pdf}
    \caption{Characterizing relevant fluctuations in the \textit{power} time series of books in the corpus for books in codes \textit{other than} the Language and Literature Library of Congress Classification code ``P'' (c.f. Figure~\ref{fig:cutoff_imf_summary}). (a) These histograms show the number of books that have fluctuations on top of the trend (green) and those that do not (purple). The different line widths and line styles correspond to the different rescaling factors: solid thick lines for using the median of the first IMF, solid thin lines for using the 1st percentile of the first IMF, and dotted lines for no rescaling. (b\textendash d). These are heatmaps that show the relationship between the period of the cutoff IMFs (as the number of words) and the book length for the various rescaling factors (shown above each plot). We can see that most of the points fall below the 45 degree line (red dashed line), indicating that the cutoff IMF period is less than than the book length for the vast majority of books. The histograms for the cutoff IMF period are shown on the right side of each plot, with the 25th, 50th, and 75th percentiles shown in dotted black, solid red, and dashed black lines, respectively.The rest of the figures are similar to (b\textendash d), but for different quantities: variance (e\textendash g), number of IMFs (h\textendash j), and cutoff IMF order, with the first IMF counted as 1 (k\textendash m).}
    \label{fig:cutoff_imf_summary_notP_power}
\end{figure*}

\clearpage
\subsection*{Empirical mode decomposition}
Given a time series $x(t)$, EMD takes the mean $m_1$ of the upper envelope (connecting the local maxima by a cubic spline) and the lower envelope (connecting the local minima, also by a cubic spline).
The difference $h_{1, 1} = x(t) - m_{1, 1}$ is then checked for two conditions: (a) the number of extrema and the number of zero crossings must either equal or differ at most by one, and (b) the mean of $h_1$ must be zero.
If either condition is not met, this process is repeated $k$ times until both conditions are met, resulting in:
\begin{equation}
    h_{1, k} = h_{1, k-1} - m_{1, k}
\end{equation}

This process is called \textit{sifting}, and the function $c_1 := h_{1, k}$ is defined as the first IMF.
The difference $h_{2, 1} = x(t) - c_1$ is obtained and the same procedure is repeated, with each subsequent IMF corresponding to decreasing frequencies as the iteration progresses.
This iterative process continues $M$ times until $x(t) - c_M$ can no longer satisfy the conditions for an IMF; this is called the residual, $r_M$.
Thus, the original signal can be decomposed as the sum of the IMFs and the residual
\begin{equation}
    x(t) = \sum_{j=1}^M c_j + r_M .
\end{equation}
Each IMF can then be characterized by its frequency spectrum, which is obtained using the Hilbert (Hilbert-Huang) transform, and the characteristic frequency can be taken to be the center of the frequency bin with the highest energy.
The sum of the lower-frequency IMFs can then be used to denoise a time series. While similar to using a low-pass filter, using EMD also separates the fluctuations corresponding to each characteristic frequency, allowing comparison of IMFs across different temporal scales.

A commonly used variant is the \textit{ensemble empirical decomposition method} (EEMD), which was developed to reduce the effect of noise on the IMFs. Several realizations of white noise are added to the raw signal, and EMD is performed on each.
The EEMD then takes the average of the IMFs obtained across all these augmented signals.
Because of the ensemble averaging step, the resulting IMFs are more robust to the effect of noise.

While EMD can extract oscillatory modes of different frequencies from a time series, the method does not dictate which of the IMFs are due to noise and which are relevant to the true signal.
Methods developed include looking at the variances of the IMFs to set a cutoff IMF order~\cite{boudraa_emd-based_2007, boudraa_noise_2007}, comparing the correlation coefficients of each IMF and the raw time series~\cite{ayenu-prah_criterion_2010}, and comparing the probability density functions of the IMFs to that of the raw time series~\cite{komaty_emd-based_2014}. However, preliminary analysis showed that methods comparing the IMFs to the raw time series do not work sufficiently on our data, likely due to the choice of window size resulting in a low signal-to-noise ratio, so that the assumption that the relevant IMFs are closer to the original time series than the noise IMFs does not hold. We thus adapt a method that compares the time series to a null reference~\cite{wu_study_2004,flandrin_empirical_2004}, but use shuffled text instead of Gaussian noise as the null model.

\end{document}


\section{Introduction}

The starting point of this paper is an arbitrary non-decreasing sequence of positive integers, called an {\it input sequence}. Given this sequence $(y_n)_{n\ge 1}$, we use it to define an infinite system of inequalities. We use these inequalities to introduce the notion of a valid $n$-tuple. We study the number of valid $n$-tuples via an output array ${\mathcal A} = A(n,k)$ determined by the given sequence.
Here $n$ denotes the row and $k$ denotes the column; $n\ge 1$ and $k\ge 0$.
The entry $A(n,k)$ is the number of valid $n$-tuples with first entry $k$.
In Theorem \ref{recurrence-theorem}  we show that entries in $A(n,k)$ (for appropriate $k$) satisfy the recurrence
\begin{equation} \label{recurrence} A(n+1,k+1) = A(n+1,k) + A(n,k+1). \end{equation}
Thus an entry is the sum of the entry above it and the entry to its left in the array.
Sums of the entries in a row of the output array often define interesting integer sequences, such as binomial coefficients, Catalan numbers, and the number of valid tournament brackets.
We call the sequence of these row sums the {\it output sequence}. The columns of the output array are also interesting;
each column defines a combinatorial polynomial. See Theorem \ref{array-formula}  and Propositions \ref{poly-bracket}, \ref{Cat-polynomial}, and \ref{Fib-polynomial}.

Perhaps the two most interesting examples are the well-known Catalan triangle (see for example \cite{West} and \cite{Stanley})  and the array arising from tournament brackets in \cite{D1}.
We introduce and study several additional examples, including the array arising from the Fibonacci sequence. It is surprising to the authors that the output sequence in this case
does not appear in \cite{OEIS}. In the final section of the paper we give a lengthy list of input sequences and their corresponding output sequences.

Let $(y_n)_{n\ge 1}$ be an input sequence, namely a nondecreasing sequence of positive integers.
For each positive integer $n$ we consider $n$-tuples of non-negative integers satisfying inequalities determined
from this sequence. We make the following definition.

\begin{definition} Let $(y_n)_{n\ge 1}$ be a nondecreasing sequence of positive integers.  For each positive integer $n$, we say that
${\bf x}= (x_1,\ldots, x_n)$ is a {\bf valid} $n$-tuple for $(y_n)$ if the following hold:
\begin{itemize}
\item $x_1 \le y_n$,
\item for $ j\ge 1 $, we have  $x_{j+1} \le \min( x_j, y_{n-j})$.
\end{itemize}
\end{definition}

Notice that the entries in ${\bf x}$ are nonincreasing.  We next define {\bf output arrays}, the main construction in this paper.

\begin{definition}  Fix an input sequence $(y_n)$. For each positive integer $n$ and each non-negative integer $k$, define  $A(n,k)$ to be the number of valid $n$-tuples with $x_1=k$.
The output array ${\mathcal A}$ is defined by ${\mathcal A}= \left(A(n,k)\right)$. \end{definition}

For the constant sequence with $y_n=j$, an $n$-tuple is valid if we have
\begin{equation} x_n \le x_{n-1} \le \dots \le x_1 \le j. \end{equation}
When $j=1$, there are $j+1$ valid $n$-tuples. When $j=2$, there are
\begin{equation} 1+2 + \cdots + n = {n+2 \choose 2} \end{equation}
valid $n$-tuples. In fact we have the following well-known result.

\begin{proposition} Fix a positive integer $j$. For each positive integer $n$ there are ${n+j \choose j}$ $n$-tuples ${\bf x}$ of non-negative integers  satisfying
\begin{equation} x_n \le x_{n-1} \le \ldots \le x_1 \le j. \end{equation}
\end{proposition}

We describe the output arrays for  three natural input sequences. These arrays are easily obtained using the code from Section \ref{sage}.

\begin{example} Consider the constant sequence with $j=5$. Here are the first six rows of ${\mathcal A}$.
\begin{equation} \label{constant5} \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 0 & \dots \cr 1 & 2 & 3 & 4 & 5 & 6  & 0 & \cdots \cr 1 & 3 & 6 & 10 & 15 & 21 & 0 & \cdots \cr 1 & 4 & 10 &20 & 35 & 56 & 0 & \cdots \cr 1& 5 & 15 & 35 & 70 & 126 & 0 & \cdots \cr 1 & 6 &21 & 56 & 126 & 252 & 0 & \cdots \end{pmatrix} .\end{equation}
Note that the row sums are $6,21, 56, 126, 252, 462$. These are of course the values of ${n+5 \choose 5}$ for $1 \le n \le 6$.
\end{example}

\begin{example} Consider the identity sequence. Then the output array ${\mathcal A}$ yields the Catalan triangle:
\begin{equation} \begin{pmatrix} 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & \dots \cr 1 & 2 & 2 & 0 & 0 & 0 & 0 & 0  & \cdots \cr 1 & 3 & 5 & 5  & 0 & 0 & 0 & 0 & \cdots \cr 1 & 4 & 9 &14  & 14  & 0 & 0 & 0 & \cdots \cr 1& 5 & 14 & 28 & 42 & 42  & 0 & 0 & \cdots \cr 1 & 6 &20 & 48 & 90 & 132 & 132  & 0 & \cdots \end{pmatrix}. \end{equation}  \end{example}

\begin{example} The third example comes from tournament brackets \cite{D1}. It is more complicated than the previous two examples, because  $A(n,k)  > 0$ for more than $n$ values of $k$.
We list the first four rows and ten columns:
 $$ \begin{pmatrix} 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \cr 1 & 2 & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \cr 1 & 3 & 5 & 5 & 5 & 0 & 0 & 0 & 0 & 0  \cr 1 & 4 & 9 & 14 & 19 & 19 & 19 & 19 & 19  & 0 \end{pmatrix} .$$
In the fourth row, there must be nine non-zero numbers, because $2^{4-1} +1 = 9$.  Since $2^{3-1}+1 = 5$, there must also be five terms equal to $19$.

The fifth row is
$$ 1, 5, 14, 28, 47, 66, 85, 104, 123, 123, 123, 123, 123, 123, 123, 123, 123, 0, \ldots$$
We note that the number of non-zero terms grows rapidly, and thus forces the row sums to grow even more rapidly.
There are nine copies of $123$, because nine numbers $m$ satisfy $8 \le m \le 16$. See \cite{D1} for the sixth row and information on the row sums.
\end{example}

\begin{remark} The phenomenon where  $A(n,k)  > 0$ for more than $n$ values of $k$ applies to all but the simplest input sequences.
Hence the tournament bracket output array and Fibonacci output array are more typical than the Catalan triangle. \end{remark}

\begin{definition} Let $(y_n)$ be an input sequence. We define its output sequence $W$ by setting $W(n)$ to be the sum of the entries in the $n$-th row of ${\mathbb A}$. Thus
$$ W(n) = \sum_{k=0}^\infty A(n,k) = \sum_{k=0}^{y_n} A(n,k). $$\end{definition}

The sequence $W(n)$ is also non-decreasing, and in general grows rapidly.

 \begin{definition} Let ${\mathcal S}$ denote the space of non-decreasing integer sequences. Let  $\Phi:{\mathcal S} \to {\mathcal S}$  denote the operation of assigning an output sequence to an input sequence. \end{definition}

Our work in this paper provides considerable information about this operation $\Phi$. For example,  the bounds in Theorem \ref{Pascal-ineq} show that $\Phi$ is far from being surjective. Describing its range precisely seems to be a difficult problem.

\section{Recurrence relation}

The following proposition is immediate from the definitions.

\begin{proposition} The number of valid $n$-tuples is the sum of the entries in the $n$-th row of ${\mathcal A}$. \end{proposition}

By definition, each row of ${\mathcal A}$ ends in an infinite string of zeroes. Since $x_1 \le y_n$ and $x_1$ is the largest of the $x_j$, it follows that $A(n,k) = 0$  for $k > y_n$. For each $n$, it follows also by definition that $A(n,0)=1$. (There is only one valid $n$-tuple whose maximum value equals $0$, namely the tuple with all zeroes.)
Let $K=K_n$ denote the maximum $k$ for which $A(n,k) > 0$. Again, by definition, for each $n$ we have the following inequalities:
\begin{equation} 1 = A(n,0) \le A(n,1) \le \cdots \le A(n,K). \end{equation}

\begin{theorem} \label{recurrence-theorem} Fix $n$. Let $K$ denote the largest $k$ for which
$A(n+1,k+1)> 0$.
 Suppose that $k+1 \le K$. Then the following recurrences hold:
\begin{equation} \label{recurrence-left} A(n+1, k+1) = A(n+1,k) + A(n,k+1)\end{equation}
\begin{equation} \label{recurrence-above}
A(n+1,k+1) = \sum_{j=0}^{k+1}  A(n,j). \end{equation}
\end{theorem}
\begin{proof}
Consider a valid $(n+1)$-tuple ${\bf x}$ with $x_1 = k+1$. For appropriate integers we then have ${\bf x} = (k+1, a, b, \ldots, z)$. There are two kinds of such $(n+1)$-tuples:
those for which $a=k+1$ and those for which $a < k+1$. The number of the first type is $A(n,k+1)$. To count the number of the second type, observe (since $a<k+1$) that the number of
$(n+1)$-tuples of the form $(k+1, a, \ldots)$ is the same as the number of $(n+1)$-tuples of the form $(a,a,\ldots)$.
Since $a$ is an arbitrary integer
in the interval $[0, k]$, the number of such tuples is  $A(n+1,k)$.

In other words, each valid $(n+1)$-tuple whose first entry is $k+1$ either has second entry also $k+1$, or has second entry in the integer interval $[0,k]$.
The number of the first type is $A(n,k+1)$. The second type consists of $(n+1)$-tuples whose first entry is $k+1$ and whose second entry is at most $k$. The number of these is unchanged
if we replace the first entry by $k$. Hence there are $A(n+1,k)$ of the second type.

To prove the second recurrence, observe that a valid $(n+1)$-tuple with $x_1 = k+1$ is of the form $(k+1, a,b, \ldots, z)$. Here the $n$-tuple $(a, \ldots ,z)$ is a valid $n$-tuple as long as
$a \le k+1$. Thus (\ref{recurrence-above}) holds.
\end{proof}

\begin{corollary}\label{pseudo-pascal}  For $k \le y_n$, we find $A(n,k)$ by adding the pair of numbers immediately above it and to its left. We can also find $A(n,k)$ by adding all the numbers in the row above
up to column $k$. \end{corollary}

Corollary \ref{pseudo-pascal} is well known for the Catalan triangle, and was noted for the bracket array in \cite{D1}.
Note in general  that $A(n,k)= 0$ for $k > y_n$ by definition. Thus one must be careful to apply the result only when $k \le y_n$.

We illustrate with a new example, where the input sequence is the Fibonacci sequence. Here, as is standard,
$$ F_1 =1, F_2=1, F_3 =2, F_4 = 3, F_5= 5, F_6 = 8, \cdots $$

The first eight rows and nine columns of the output array turn out to be
$$ \begin{pmatrix} \label{fibonanni-output}  1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \cr 1 & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \cr 1 & 3 & 3 & 0 & 0 & 0 & 0 & 0 & 0 \cr 1 & 4 & 7 & 7 & 0 & 0 & 0 & 0 & 0 \cr 1 & 5 & 12 & 19 & 19 & 19 & 0 & 0 & 0 \cr 1 & 6 & 18 & 37 & 56 & 75 & 75 & 75 & 75 \cr 1 & 7 & 25 & 62 & 118 & 193 & 268 & 343 & 418 \cr
1 & 8 & 33 & 95 & 213 & 406 & 674 & 1017 & 1435 \end{pmatrix}.$$
Note that the $7$-th row has five more copies of $418$, and the $8$-th row includes also $1853, 2271, 2689, 3107, 3525$ with this last number being repeated nine times.
The multiplicities arise because $6=13-8+1$ and $9=21-13+1$.

We find several of the smaller values. First of all $A(n,0)=1$ for all $n$, because there is only one valid $n$-tuple with first entry $0$. Next, $A(n,1)= n$ for all $n$, because
we are counting $n$-tuples of the form $(1,x_2,\ldots, x_n)$ where each $x_j$ is either $0$ or $1$, and the tuple is non-increasing. There are $n$ possibilities, as the total number of ones can be anything from $1$ up to $n$. We can of course compute the rest of the array by using the recurrence, but it is instructive to compute an entry directly. For example, we find $A(5,5)$.
We are considering $5$-tuples whose first entry is $5$. The second entry is the minimum of $3$ and the first entry, and so on. We list all the possibilities (where we do not include the commas or parentheses).
$$ 53211, 53210, 53200, 53111, 53110, 53100, 53000,$$
$$ 52221, 52210, 52200, 52111, 52110, 52100, 52000,$$
$$ 51111,51110, 51100, 51000, 50000$$
Hence there are $19$ possibilities. Notice that $A(5,4)$ and $A(5,3)$ also equal $19$.

\section{Polynomials and explicit formulas}

One might hope to use the recurrence (\ref{recurrence-above}) to determine formulas for $A(n,k)$ in terms of the first row. Doing so is not possible, because $A(n,k)=0$ for $k > y_n$.
If we regard the entries $A(1,j)$ as parameters, then they are either $1$ or $0$, depending on only $y_1$ in the input sequence.
In order to take the full sequence into account, we must remember that the recurrence applies only when $k$ is sufficiently small, namely $k \le y_n$.
We will therefore write out formulas for $A(N+n-1,k)$ when $N$ is sufficiently large and study the resulting sub-array.

The first row of ${\mathcal A}$ is always
$$ \begin{pmatrix} 1 & A(1,1) & A(1,2) & \cdots & A(1,k) & \cdots \end{pmatrix}. $$
By (\ref{recurrence-above}), for $k$ sufficiently small,  the second row is
$$ \begin{pmatrix} 1 & 1+ A(1,1) & 1+ A(1,1) + A(1,2) & \cdots & 1+ \sum_{j=1}^k A(1,j) & \cdots  \end{pmatrix} .$$
To anticipate the general statement we also write the third row in this case:
$$ \begin{pmatrix} 1 & 2 + A(1,1) & 3+ 2 A(1,1) + A(1,2) & \cdots & k+1+ \sum_{j=1}^k c_j A(1,j) & \cdots  \end{pmatrix} .$$
Here $c_j = k+1-j$.  For larger index $n$, the $c_j$ are explicit binomial coefficients.

Fix a sufficiently large integer $N$. We wish to do the analogous thing when we use the $N$-th row as the starting point.
We write out the array $A(N+ n-1,k)$ as a sub-array of ${\mathcal A}$,
for $1\le n \le 5$ and $0 \le k \le 4$. To avoid too many indices, we put $A(N,1) =1$, $A(N,2)=a$, $A(N,3)=b$, $A(N,4)=c$, and $A(N,4) = d$. By repeated application of
(\ref{recurrence-above}) we obtain

$$ \begin{pmatrix} 1 & a & b & c & d \cr
1 & 1+a & 1+ a + b & 1 + a +b + c & 1+ a +b + c + d \cr
1 & 2+a & 3 + 2a+b & 4+ 3 a + 2b + c &  5+ 4a + 3b +2 c +d \cr
1 &  3 + a & 6 + 3a + b  & 10 + 6a + 3b + c & 15 + 10 a + 6 b + 3c + d \cr
1 & 4 + a & 10 + 4a + b & 20 + 10 a + 4b + c & 35 + 20 a + 10 b + 4c + d
\end{pmatrix}.
$$
It follows that $A(N+n-1,k)$  equals ${N+n+k-3 \choose k}$ plus a linear combination of the parameters $A(N,j)$ for $1 \le j \le k$.
These formulas hold of course under the assumption that $N$ is sufficiently large.
We obtain the following result.

\begin{theorem} \label{array-formula}
Let $(y_n)$ be an input sequence with output array
$A(n,k)$.  Assume that $N$ is such that
$k \leq y_{N+1}$.  Then, for $n \geq N+1$,

\begin{equation} \label{decisive}
A(n,k)= {n+k-2 \choose k}+ \sum_{j=1}^k { n+k-2-j \choose k-j} A(N,j) \end{equation} \end{theorem}

\begin{proof}
The $N$-th row of ${\mathcal A}$ by definition has entries $1,A(N,1), A(N,2), \ldots ,A(N,k)$.
By formula (\ref{recurrence-above}), the $k$-th entry in the $m$-th row is the sum of the entries in the $(m-1)$-st row
up to $k$. Thus (\ref{decisive}) holds for $n=N+1$. The conclusion then follows by induction and Pascal's formula for sums of binomial coefficients.
\end{proof}

Henceforth we write $N(k)$ for the smallest $N$ such that $k \leq y_{N+1}$. As long as $(y_n)$ is not eventually constant, such an $N(k)$ exists.
The situation where the input sequence $(y_n)$ is eventually constant is a bit annoying.
In this case $A(n,k)=0$ for $k$ sufficiently large. The next corollary therefore requires the assumption
that $y_n$ tends to infinity.

\begin{corollary} \label{poly-corollary} Assume that the input sequence $(y_n)$ is not eventually constant.
Suppose $n$ is large enough such that $k \le y_n$. Then the entry $A(n,k)$ is the value of a polynomial $p_k$ of degree $k$ in $n$. \end{corollary}
\begin{proof} Since the input sequence tends to infinity, we can always choose an $N$ such that $N+1 \ge n$ and apply the theorem.
The binomial coefficient ${m \choose k}$ is a polynomial of degree $k$ in $m$ and the terms from the linear combination in (\ref{decisive})
are of lower order. A polynomial of degree $k$ in $m$ is also a polynomial of degree $k$ in $n$ when $m = n+k-2$. The result follows. \end{proof}

Note for all $n$ that $ A(n,0)=1$.  Unless $y_1=0$, we have $ A(n,1) = n + A(1,1)-1$. We also generally have
$$ A(n,2) = \frac{n^2 + n} {2} + A(1,2) -1. $$
General formulas for $A(n,k)$ for larger $k$ require assuming that $n\ge N(k)$.
We therefore provide an alternate derivation of the polynomials from Theorem \ref{array-formula}.

Putting $A(n,k+1) = \lambda^n$ in (\ref{recurrence-left}), we see that the solutions to the homogeneous equation $A(n+1,k+1) - A(n,k+1) = 0$ are constants.
By induction on $k$ it follows for $n\ge N(k)$ that
$A(n,k+1)$ is a polynomial $p_k(n)$ of degree $k$ in $n$. We compute these polynomials using Lagrange interpolation.

We next discuss these polynomials for several input sequences.
For the bracket array we have the following result from \cite{D1}:

\begin{proposition} \label{poly-bracket} For the bracket array, the polynomials $p_k$ described  in Corollary \ref{poly-corollary} are given for $k \le 6$ by
\begin{align*}
& p_0(x) = 1 & \\
& p_1(x) = x & \\
& p_2(x) = \frac{x^2}{2} + \frac{x}{2}  -1 & \\
&  p_3(x) = \frac{x^3}{6} + \frac{x^2 }{ 2} - \frac{2x} {3} - 2 & \\
&  p_4(x) = \frac{x^4}{24} + \frac{x^3} {4}- \frac{x^2}{24} - \frac{9x}{4} + 2 & \\
& p_5(x) = \frac {x^5} {120} + \frac{x^4}{12} + \frac{x^3} { 8} - \frac{13x^2}{12} + \frac{13x} {15}  - 5 & \\
&  p_6(x) = \frac{x^6 } {720} + \frac{x^5} {48} + \frac{11 x^4} {144} - \frac{13x^3}{48} - \frac{7x^2} {90} -\frac{19x}{4}  + 10.
\end{align*}
\end{proposition}
We next compute them for the Catalan triangle.
\begin{proposition} \label{Cat-polynomial} The polynomials defining the $k$-th column of the Catalan triangle (for $n \ge k $) are given by
\begin{itemize}
\item$p_0(x) = 1$
\item $p_1(x) = x$
\item $p_2(x) = \frac{x^2+x -2}{2} = \frac{(x-1)(x+2)}{2}$
\item $p_3(x) = \frac{x^3 + 3 x^2 -4x -12}{6} = \frac {(x-2) (x+2) (x+3)}{6}$
\item $p_4(x) = \frac{ x^4 + 6x^3 -x^2 - 54 x -72} {24}= \frac{(x-3)(x+2)(x+3)(x+4)} {24}$
\end{itemize}
\end{proposition}
\begin{proof} We omit the details, but provide the idea in the special case $k=3$. We wish to find the unique polynomial  $p$ of degree $3$ that satisfies
$$ p(3)=5, \ p(4)= 14, \  p(5)=28, \ p(6)=48. $$
We could also have used the value $p(2)=0$.
The InterpolatingPolynomial command in Mathematica does the job for us. \end{proof}

\begin{proposition} \label{Fib-polynomial} The polynomials defining the $k$-th column of the Fibonacci output array  (for $n \ge k $) are given by
\begin{itemize}
\item $p_0(x) = 1$
\item $p_1(x)=x$
\item $p_2(x) = \frac{(x-2)(x+3)}{2} $
\item $p_3(x) = \frac {(x-3 ) (x^2+6x+2)}{6}$
\item $p_4(x) = \frac{(x-4)(x+1)(x^2+9x+6) }{24}$.

\end{itemize}
\end{proposition}

\begin{remark} Theorem \ref{array-formula} implies that the top order term in $p_k(n)$ equals $\frac{n^k}{k!}$ for every input sequence that is not eventually constant. \end{remark}

We close this section with a somewhat perverse input sequence that illustrates why we must consider $N(k)$ in solving the recurrence.

\begin{example} \label{mult-sequence} Consider the input sequence with values
$$ 1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6, \ldots $$
Thus $1$ appears once, $2$ appears twice, $3$ appears three times, and so on. Using the code from the next section, one can show for example that $A(n,4)=0$ for $1\le n \le 6$.
The polynomial $p_4$ is given by
$$   \frac{x^4}{24} + \frac{x^3}{4} - \frac{x^2}{24} - \frac{29x}{4} - 63.     $$
Note that $y_7=4$. The values of $p_4(n)$ agree with $A(n,4)$ only when $n\ge 7$. Also $A(n,5) = 0$ for $1 \le n \le 10$. Note that $y_{11}=5$. The polynomial $p_5$ is given by
$$ \frac{x^5}{120} + \frac{x^4}{12} + \frac{x^3}{8} - \frac{43x^2}{12} - \frac{1999x}{30} - 767. $$
The values here agree with $A(n,5)$ only when $n\ge 11$. These formulas show that the formula $A(n,k) = p_k(n)$ holds only when $n\ge N(k)$. The explanation here is that the input sequence is not strictly increasing.\end{example}

\section{Sage code}\label{sage}

The following code works as follows. In the first line, replace $F(n)$ with the formula for $y_n$ and $R$ with the desired array size, or list as many of the terms as you wish.
The output provides the input sequence,
the output array up to size $R$, and the output sequence of row sums. The code relies on the recurrence from Theorem \ref{recurrence-theorem},
the initial condition that the first column of the array is all ones, and that the first row has the appropriate number of ones.

\begin{verbatim}

y=[F(n) for n in range(1,R+1)];
show(y);
N=len(y);
K=max(y);
A=matrix.zero(N,K+1);
for n in range(0,N):
 A[n,0]=1;
 for k in range(0,y[0]+1):
A[0,k]=1;
for n in range(1,N):
 for k in range(1,y[n]+1):
A[n,k] = A[n-1,k]+A[n,k-1];
show(A);
show(sum(A.T));  \end{verbatim}

\section{Comparison with Pascal's triangle}

The recurrence relation (\ref{recurrence-left}) looks superficially like Pascal's formula. We recall (\ref{recurrence-left}) here for ease of comparison:
$$ A(n+1,k+1) = A(n+1,k) + A(n,k+1). \leqno (8) $$

By contrast, putting ${n \choose k} = A(N,k)$, Pascal's formula says
\begin{equation}  \label{pascal} A(n+1,k+1) = A(n,k) + A(n,k+1). \end{equation}

Nonetheless Pascal's triangle fits into our discussion by way of the following approach. We create an array using the recurrence (\ref{recurrence-left}) by setting all the entries in
both the far left columns {\it and} the top row equal to $1$.  We call this array the maximal output array $A_M$. Thus
we set $A_M(n,0) = 1$ for all $n$ and $A_M(1,k) = 1$ for all $k$. The recurrence (\ref{recurrence-left}) then determines the full array.
One way to think about the maximal array is to imagine that the input sequence satisfies
$y_n=\infty$ for all $n$. The following theorem justifies this notion by providing estimates for arbitrary output arrays.

\begin{theorem} \label{Pascal-ineq}
Given a nondecreasing sequence of nonnegative numbers $(y_n)$, let
$A(n,k)$ be its output array and $W(n)$ its output sequence, namely the
row sums of $A(n,k)$.  Then, if $n\ge 2$ and $k \le y_n$ for the lower bound in (\ref{lebl-estimate}), and for all $n,k$ in the upper bounds,
\begin{equation} \label{lebl-estimate}
 \min(y_{n-1}+1 , k+1 )\le A(n,k) \leq \binom{n-1+k}{k} \end{equation}
 \begin{equation} \label{lebl-row} W(n) \leq \binom{n+y_n}{y_n} .
\end{equation}
\end{theorem}

\begin{proof}
The first inequality in (\ref{lebl-estimate}) is immediate from the definition of $A(n,k)$.  To prove the second inequality,
we start by setting $A_M(n,0) = 1$ for all $n$ and $A_M(1,k) = 1$ for all
$k$.
We then use the usual recurrence relation
\begin{equation}
A_M(n+1,k+1) = A_M(n+1,k)+A_M(n,k+1)
\end{equation}
to fill in the rest of the entries in the output array. The result is a rotated version of the
familiar Pascal's triangle:
\begin{equation}
\begin{pmatrix}
1 & 1 & 1 & 1 & \dots \\
1 & 2 & 3 & 4 & \dots \\
1 & 3 & 6 & 10 & \dots \\
1 & 4 & 10 & 20 & \dots \\
\vdots & \vdots & \vdots & \vdots & \ddots
\end{pmatrix}.
\end{equation}
Thus
\begin{equation}
A_M(n,k) = \binom{n-1+k}{k} .
\end{equation}

Given the input sequence $( y_n )$, we construct its output array
$A(n,k)$.  We do so as usual. We put
$A(n,0) = 1$ for all $n$ and $A(1,k) = 1$ for $k \leq y_1$.  We then use
the recurrence
$$A(n+1,k+1) = A(n+1,k)+A(n,k+1)$$
{\bf only} for those elements where $k+1 \leq y_{n+1}$,
while setting the rest of the elements to zero.  It follows that
\begin{equation}
A(n,k) \leq A_M(n,k) = \binom{n-1+k}{k} .
\end{equation}
Let $W(n)$ be the $n$-th row sum of ${\mathbb A}$, that is, the output
sequence.  We also obtain an estimate on $W(n)$,
as each row sum appears as an entry in the next row of the output array. In particular, since $(y_n)$ is
nondecreasing, then
\begin{equation}
W(n) = \sum_{k=0}^{y_n} A(n,k) = A(n+1,y_n) \leq
A_M(n+1,y_n) = \binom{n+y_n}{y_n} .
\end{equation}
\end{proof}

\begin{corollary} The map $\Phi:{\mathcal S} \to {\mathcal S}$ taking input sequences to output sequences is not surjective. \end{corollary}

These inequalities are far from sharp, and become less sharp the faster the input sequence grows. In the next section we provide improved bounds.

\section{Three part harmony}

In order to better understand the output array, it is useful to consider three types of terms in the $n$-th row. We make the following definitions.

\begin{definition} \label{three-part} Let $(y_n)$ be an input sequence and let $A(n,k)$ denote its output array. For each $n$ with $n\ge 3$ we put
$$ W(n) = \sum_{k=0}^\infty A(n,k) = \sum_{k=0}^{y_n} A(n,k) $$

$$  T(n) = \frac {(1+ y_n - y_{n-1}) W(n-1)} {W(n)} $$

$$ M(n) = \frac{ \sum_{k=1}^{(y_{n-1}- y_{n-2}) + 1}  (W(n-1)- kW(n-2)) } {W(n)}$$

$$ S(n) = 1 - M(n) - T(n).$$ \end{definition}

The idea is easy to explain. Of course $W(n)$ is simply the $n$-th row sum. There are three kinds of terms contributing to this sum. For a typical output array,
the largest term in the $n$-th row is $W(n-1)$, and this term gets repeated for each $k$ in the interval $y_{n-1} \le k \le y_n$. Thus there are $1+y_{n}-y_{n-1}$ such terms.
Hence $T(n)$ denotes the fraction of terms of this type in the $n$-th row.
Because of the recurrence relation determining $A(n,k)$, we also have terms of the form $W(n-1) - j W(n-2)$. There are
$$R= (y_{n-1}- y_{n-2}) + 1$$
 such terms. ($R$ is the number of integers $j$ with $y_{n-2} \le j \le y_{n-1}$.)
Thus $M(n)$ denotes the fraction of terms of this type in the $n$-th row. Finally $S(n)$ denotes the fraction of the remaining terms.

\begin{remark} The letter $T$ stands for {\it top}, the letter $M$ stands for {\it middle}, and the letter $S$ stands for {\it small}. \end{remark}

This method of organizing the terms leads to bounds from both sides for $W(n)$.

\begin{theorem} Let $(y_n)_{n \ge 1}$ be an arbitrary input sequence. Put $y_0 =0$ for convenience. Then
\begin{equation} \label{improved-row}  \prod_{k=0}^{n-1} (1+y_{k+1} - y_k) \le W(n) \le  \prod_{k=1}^n (1+y_k) \end{equation}
\end{theorem}
\begin{proof} We begin with the left-hand inequality. Consider the $n$-th row of ${\mathcal A}$. Since the number $W(n-1)$ gets repeated $(1+y_n - y_{n-1})$ times in this row,
we must have
\begin{equation} W(n) \ge (1+y_n - y_{n-1}) W(n-1). \end{equation}
It then follows inductively that
\begin{equation} W(n) \ge \prod_{k=1}^{n-1} (1+y_{k+1} - y_{k}) W(1). \end{equation}
Since $W(1)$ is the number of valid $1$-tuples, $W(1) = 1 + y_1$. Using the convention that $y_0=0$, we can write $W(1)$ as $1+ y_1 - y_0$, and the inequality follows.

To prove the upper bound, we observe that the maximum entry in the $n$-th row of ${\mathcal A}$ is $W(n-1)$.  Hence $W(n)$ is at most the number of non-zero terms in the row times
$W(n-1)$. For non-zero entries, the column index $k$ varies from $0$ to $y_n$, and hence (using the convention that $W(0)=1$),
\begin{equation} W(n) \le (1+y_n) W(n-1) \le (1+y_n)(1+y_{n-1} )W(n-2) \le \ldots \le \prod_{k=1}^n (1+y_k) \end{equation} \end{proof}

We now compute the numbers $T(n), M(n),S(n)$ for the Catalan triangle. In this case, as is well known, $W(n)$ is the $(n+1)$-st Catalan number.

\begin{theorem} Put $y_n=n$. The output array generated by this sequence is the Catalan triangle. For this array  we have the following results:
$$ W(n) = C_{n+1} = \frac{1} {n+2} {2n+2 \choose n+1},$$
$$ T(n) = \frac{n+2}{2n+1},$$
$$ M(n) = \frac{(n+2)(5n-7)}{4 (2n+1) (2n-1)},$$
$$ S(n) = \frac{3(n-3)(n-2)}{4(2n+1)(2n-1)}. $$
Therefore we have the following asymptotic results:
\begin{itemize}
\item $\lim_{n \to \infty} T(n) = \frac{1} {2},$
\item $\lim_{n \to \infty} M(n) = \frac{5}{16},$
\item $\lim_{n \to \infty} S(n) = \frac{3}{16}. $
\end{itemize}\end{theorem}
\begin{proof} Since the limits are immediate from the stated formulas, it suffices to prove the formulas.
We assume the known result that $W(n)$ is the Catalan number $C_{n+1}$, which equals  $ \frac{1} {n+2} {2n+2 \choose n+1}$. This number gets repeated twice in the $(n+1)$-th row of  the Catalan triangle,
since
$$(y_{n+1} - y_n )+ 1 = (n+1-n)+1=2. $$
Therefore
$$ T(n) = {2 \frac{1} {n+1} {2n \choose n} \over \frac{1} {n+2} {2n+2 \choose n+1}}= {2 (n+2) \over n+1} \ {(2n)! (n+1)! (n+1)! \over n! n! (2n+2)!} = \frac{n+2}{2n+1}.$$
To compute $M(n)$, we note that the sum in the numerator of its definition also has two terms. We thus we get two copies of $W(n-1)$ and $3=1+2$ copies of $W(n-2)$ when computing
$M(n)$. Thus
$$ M(n) = \frac{2 C(n-1) - 3 C(n-2)}{C(n)}, $$
which simplifies to
$$ M(n) = \frac{(n+2)(5n-7)}{4 (2n+1) (2n-1)}, $$
as claimed. Since $T(n)+ M(n)+S(n)=1$ by definition, the formula for $S(n)$ follows as well.
\end{proof}

\begin{proposition} Let $y_n$ be a constant sequence. Then $\lim_{n\to \infty} T(n) = 1$, and hence $\lim_{n \to \infty} M(n) = \lim_{n\to \infty} S(n) = 0$. \end{proposition}
\begin{proof} Suppose $y_n = j$ for all $n$. One can check, in analogy with Example \ref{constant5},  that $W(n) = {n+j \choose j}$ and hence
$$ \frac{W(n-1)}{W(n)} = \frac{ (n-1+j)!n! j!} {j! (n-1)! (n+j)!} = \frac{n} {n+j}.$$
In the $n$-th row, there is only one term of the form $W(n-1)$. Hence this ratio yields $T(n)$. It is evident that $\lim_{n\to \infty} T(n) = 1$.
\end{proof}

\begin{example} For the bracket tournament output array, the asymptotic limiting values of $T(n)$, $M(n)$, and $S(n)$ satisfy the following.
They agree to many decimal places with the values when $n=82$.  Using exact formulas for $W(80)$, $W(81)$, and $W(82)$, we obtain the following
$$ T(82) \approx 0. 744039272799855,$$
$$ M(82) \approx 0.233621026532793, $$
$$ S(82) \approx 0. 022339700667352. $$
 \end{example}

 \begin{remark} For the tournament bracket output array, Alois Heinz has found the following formula, expressing $W(n)$ in terms of previous values:
 \begin{equation}  \label{alois} W(n) = \sum_{j=0}^{n-1} W(j) (-1)^{n-j+1} {1+2^j \choose n-j}. \end{equation}
 This formula presumes that ${a \choose b} = 0$ when $b > a$ and also that $W(0)=1$.
 See sequence A355519 from \cite{OEIS}. The summand when $j=n-1$ in formula (\ref{alois}) is precisely what we used to define the numerator of $T(n)$.
 \end{remark}

 \begin{remark} Consider the output array for the Fibonacci sequence.  For $n=24$, one can obtain the approximate values
 $$ T(24) \approx .678$$
 $$ M(24) \approx .277$$
 $$ S(24) \approx .044.$$
 These numbers lie between the corresponding values for the Catalan output array and those of the bracket output array.
 The reason is that the growth of the Fibonacci numbers lies between the growth of the input sequences $n$ and $2^{n-1}$. \end{remark}

 \section{Examples of input and output sequences}

 We list some input sequences $(y_n)$ and the first few terms of (or a formula for) the output sequence $W(n)$ of row sums. We then note whether the output sequence appears in \cite{OEIS}.

\begin{example} We provide many input sequences, the corresponding output sequence, and whether or not the output sequence appears in \cite{OEIS}.
 \begin{enumerate}
 \item $y_n=n$. Then $W(n) = \frac{1}{n+2} {2n+2 \choose n+1}$. Sequence A00108 in \cite{OEIS}. (Catalan numbers.)
 \item $y_n = \frac{1}{n+1} {2n \choose n}$. Then $W(n) = 2,5,14,287, \dots$. Sequence NOT in \cite{OEIS}.
 \item $y_n = 2n-1$. Then $W(n) = \frac{1}{n+1}{3n+1 \choose n}$. Sequence A006013 in \cite{OEIS}.
 \item $y_n = 2n$. Then $W(n) = \frac{1} {2n+3} {3n+3 \choose n+1}$.  Sequence A001764 in \cite{OEIS}.
 \item $y_n= 3n$. Then $W(n) = \frac{1}{3n+4} {4n+4 \choose n+1} $. Sequence A002293 in \cite{OEIS}.
 \item $y_n =4n $. Then $W(n) = \frac{1}{4n+5}{5n+5 \choose n+1}$. Sequence A002294 in \cite{OEIS}.
 \item $ y_n = {n+1 \choose 2}$. Then $W(n) = 2,7,37, 268, 2496, \ldots$. Sequence  A107877 in \cite{OEIS}.
 \item $y_n = n^2$.  $W(n) = 2,9, 70,805, \ldots$. Sequence  A177450 in \cite{OEIS}.
 \item $y_n = n^2 + n$. $W(n) = 3,18,172, 2313, 40626, \dots.$ Sequence  A177447 in \cite{OEIS}.
 \item $y_n = n^3$. $W(n) = 2,17,404,20002, \ldots$. Sequence NOT in \cite{OEIS}.
 \item $y_n = (1,1,2,3,5,8,13,21, \ldots)$ is the Fibonacci sequence. Then $W(n) = 1,2,3,7,19,75,418, \ldots$. Sequence NOT in \cite{OEIS}.
 \item $y_n = 2^{n-1}$. Then $W(n) = 2, 5,19, 123, 1457, \ldots$. Sequence A355519 in \cite{OEIS}.
 \item $y_n = 3^{n-1}$. Then $W(n) = 2,7,58,1317, \ldots$. Sequence NOT in \cite{OEIS}.
 \item $y_n = (2,3,5,7,11,13,17,19, 23, 29, 31, 37, 41, 43, 47)$. (the first fifteen primes.)  Then $W(n)= 3,9, 37, 173, 1217, 7557, 60803, 419255, \ldots$. This sequence is not in \cite{OEIS}.
 \item $y_n = \lfloor{ (1.5)^n}\rfloor$. Then $W(n)=2,5,14,56,258,1803, 18352, \ldots$. This sequence is not in \cite{OEIS}.
 \item $y_n$ is the sequence defined in Example \ref{mult-sequence}. Then $W(n) = 2,5,9,23,43,70, \dots$. This sequence is not in \cite{OEIS}.
 \end{enumerate}

\end{example}

\begin{remark} It is natural to wonder whether studying the output sequence from the input sequence of primes could have any value.
The first author suspects otherwise, simply because the output sequence grows so rapidly. On the other hand, perhaps studying the numbers from Definition \ref{three-part} for this sequence could be interesting. \end{remark}

 \begin{remark} The output sequence in item (12) was entered by the first author into \cite{OEIS}
 in July, 2022. It seems that this sequence should be better known, as it counts something (tournament brackets) that is very natural. \end{remark}

 \begin{remark} The sequence $\lfloor{ (1.5)^n}\rfloor$ from item (15) arises in various places. It is sequence A002379 in \cite{OEIS}. This sequence could be useful in the context of this paper because
 of its similarity to the Fibonacci sequence.  \end{remark}

 \begin{definition} Recall that $\Phi$ denotes the operation of assigning an output sequence to an input sequence.
 The examples above show that $\Phi$ is not linear.  Note that
 item (2) above  can be regarded as applying $\Phi$ twice. It seems difficult to determine the range of $\Phi$, other than the inequalities from Theorem \ref{Pascal-ineq}.  \end{definition}

 We conclude with what seems to be a difficult problem.

 {\bf Open problem}: Compute the growth rate of the output sequence in terms of the growth rate of the input sequence.

 \section{Acknowledgements}

 The authors wish to acknowledge useful discussions with Dusty Grundmeier. In particular Grundmeier has rewritten the Sage code in Mathematica,
 which was more convenient for the first author.
 The first author especially wishes to acknowledge Alois Heinz, whom he has met only over e-mail, for his contributions to sequence A355519 in \cite{OEIS}.
 Heinz also wrote that he was looking forward to additional new sequences, and this paper provides (infinitely many) such examples.
 Thus his encouraging e-mail provided the impetus for this paper.