\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{amscd} \usepackage{graphicx} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics} \usepackage{latexsym} \usepackage{epsf} \usepackage{breakurl} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}} \DeclareMathOperator{\pc}{pc} \usepackage{caption} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf Perfect Compositions of Numbers} \vskip 1cm \large Augustine O. Munagi\\ School of Mathematics\\ University of the Witwatersrand\\ Wits 2050, Johannesburg\\ South Africa \\ \href{mailto:augustine.munagi@wits.ac.za}{\tt augustine.munagi@wits.ac.za}\\ \end{center} \vskip .2 in \begin{abstract} A perfect composition of a positive integer is one whose sequence of parts contains one composition of every smaller positive integer. We obtain explicit formulas based on the observation that perfect compositions are identical with certain restricted permutations of perfect partitions. We also consider $n$-color perfect compositions. \end{abstract} \section{Introduction}\label{introd0} A {perfect partition} of a positive integer $n$ is one whose parts include exactly one partition of every positive integer less than $n$. For example, $(1,1,1,4)=(1^3,4)$ is a perfect partition of 7 because it contains the following partitions of $1,2,3,4,5,6$ respectively, and no other: $(1),(1^2),(1^3),(4),(1,4),(1^2,4)$. The definition of perfect partitions goes back to MacMahon \cite{Ma1,Ma2}. He first considered partitions of numbers of the form $n=p^\alpha-1$, where $p$ is a prime number, and showed that the number of perfect partitions of $n$ is given by $2^{\alpha-1}$. MacMahon also considered the number $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}-1$, where the $p_i$ are distinct primes, and found that it has as many perfect partitions as the number of generalized partitions of the vector $(\alpha_1,\ldots,\alpha_k)$ (see Andrews \cite{An} for details). There is a natural bijection between the set of perfect partitions of $n$ and the set of {ordered factorizations} of $N=n+1$, that is, representations of $N$ as ordered products of positive integers without unit factors \cite{An,Ma2,R}. Indeed every ordered factorization $a_1 a_2\cdots a_k$ corresponds uniquely to the perfect partition \begin{equation} \label{perfp} \lambda = \left(1^{a_1-1},a_1^{a_2-1},(a_1a_2)^{a_3-1},\ldots, (a_1a_2\cdots a_{k-1})^{a_k-1}\right). \end{equation} Notice that $(1^{a_1-1})$ generates partitions of $1,2,\ldots,a_1-1$; then $(1^{a_1-1},a_1^{a_2-1})$ generates further partitions, of $a_1,a_1+1,\ldots,a_1a_2-1$. Thus by induction $\lambda$ generates a partition of each number from 1 through $a_1 a_2\cdots a_k-1$. Let $f(n,k)$ denote the number of ordered factorizations of $n$ into $k$ factors, and let the prime-power factorization of $n$ be $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$. A general formula for $f(n,k)$ was found in $1893$ by MacMahon \cite{Ma2} (also \cite[p.\ 59]{An}): $$f(n,k)=\sum_{i=0}^{k-1}(-1)^{i}\binom{k}{i} \prod_{j=1}^{r} \binom{\alpha_j+k-i-1}{\alpha_j}.$$ The purpose of this paper is to study \emph{perfect compositions} in analogy with perfect partitions. This work was partly inspired by a recent extension of perfect partitions to $n$-color perfect partitions by Agarwal and Sachdeva \cite{Ag}. An $n$-color partition is a partition in which a part of size $n,n\geq 1$ can come in $n$ colors denoted by subscripts $n_1,n_2,\ldots,n_n$. Among other results they proved that every ordered factorization $a_1 a_2\cdots a_k$ of $\nu +1$, with $k>1$, gives rise to $a_1^{k-1}a_2^{k-2}\cdots a_{k-1}$ $n$-color perfect partitions of $\nu$. Compositions or ordered partitions of $n$ are denoted by vectors with positive integer entries that sum to $n$. We also express the parts of a composition \emph{symbolically} by writing $a^s$ in place of a run of $s$ equal parts $a$. For example, the composition $(8,8,8,1,1,6,3,3,1,4)=(8^3,1^2,6,3^2,1,4)$ has 6 symbolic parts and 10 (actual) parts. \begin{definition} A \emph{perfect composition} of $n$ is one whose sequence of parts contains exactly one composition of every positive integer less than $n$. \end{definition} We emphasize that the order of parts of a composition of each $m\in\{1,2,\ldots,n-1\}$, which is contained in a perfect composition $C$, is induced by the order of the parts of $C$. Thus every perfect partition is a perfect composition. For instance, $(6, 1, 2^2)$ is a perfect composition of $11$ since it contains one composition of each $m\in\{1,\ldots,10\}$: $$(1), (2), (1, 2), (2^2), (1, 2^2), (6), (6, 1), (6, 2), (6, 1, 2), (6, 2^2).$$ In the next section, we give a characterization of perfect compositions, followed by their enumeration in Section \ref{enum}. Then in section \ref{nperfcomp}, we consider $n$-color perfect compositions in analogy with $n$-color perfect partitions. \section{Perfect compositions}\label{perfcomp} Consider a composition $C=(c_1^{u_1},\ldots,c_r^{u_r}),$ where $c_i\neq c_j$ for $i\neq j$. Replace each $c_i^{u_i}$ with the set $V_i=\{c_i,c_i^2,\ldots,c_i^{u_i}\}$. Then the set of compositions generated by $C$ is determined by the \emph{Cartesian product} of the $V_i$ provided that $c_i^x$ and $c_i^y$ are treated as distinct whenever $x\neq y$. So denoting by $D_t(C)$ the set of compositions with $t$ part-sizes generated by $C,1\leq t\leq r$, we obtain \begin{equation}\label{form1} D_t(C)=V_{j_1}\times V_{j_2}\times \cdots\times V_{j_t}, 1\leq j_1<\cdots 0$, then $$|D_t(C)|=\binom{r}{t}u^t \mbox{ and } |D(C)|=(u+1)^r-1.$$ Thus even though any pair of non-empty sets $A, B$ generally satisfies $A\times B\neq B\times A$, the equality of the product in \eqref{form3} for any two permutations of the sets on the right-hand-side of \eqref{form1} is immediate, given that the $c_i$ are distinct. \begin{lemma}\label{lem1} If a composition $C$ is perfect, then each part-size occupies a unique place in $C$, that is, all copies of each part-size appear in consecutive positions. \end{lemma} \begin{proof} If $C=(c_1,c_2,\ldots)$ contains three parts $c_i,c_j,c_k$ with $i0$ for all $i$. Let $\lambda$ be the partition obtained by arranging the parts of $C$ in weakly increasing order. Then $C$ is perfect $\iff C$ generates $n-1$ compositions of $1,2,\ldots,n-1$, say $C(1),\ldots$, $C(n-1)$ $\iff$ the partitions obtained by arranging the parts of each $C(j),1\leq j\leq n-1$ in increasing order are generated by $\lambda \iff \lambda$ is a perfect partition of $n$. This correspondence is illustrated with the perfect composition $(6,1^2,3)$ and the underlying partition $(1^2,3,6)$ below: \begin{align*} (6,1^2,3): & (1),(1^2),(3),(1,3),(1^2,3),(6),(6,1),(6,1^2),(6,3),(6,1,3); \\ (1^2,3,6): & (1),(1^2),(3),(1,3),(1^2,3),(6),(1,6),(1^2,6),(3,6),(1,3,6). \end{align*} \end{proof} \section{Enumeration aspects}\label{enum} Since the number of symbolic parts of a perfect partition $\lambda$ is equal to the number of factors in the corresponding ordered factorization (see Equation \eqref{perfp}), we deduce from Theorem \ref{thm1} that the number $\pc_k(n)$ of perfect compositions of $n$ with $k$ symbolic parts is given by \begin{equation}\label{eqpck} \pc_k(n) = k! f(n+1,k).\end{equation} Hence the number $\pc(n):=\sum\limits_{k\geq 1} \pc_k(n)$ of all perfect compositions of $n$ is given by \begin{equation}\label{eqpc} \pc(n) = \sum_{k\geq 1}k! f(n+1,k).\end{equation} The sequence $\pc(n), n\geq 0$ appears as \seqnum{A330773} in the OEIS \cite{Sl}. The initial terms below were computed using the computer algebra system Maple \cite{Map}: $$1, 1, 3, 1, 5, 1, 11, 3, 5, 1, 27, 1, 5, 5, 49, 1, 27, 1, 27, 5, 5, 1, 163, 3, 5, 11,\ldots $$ Note that $\pc(n)=1$ if and only if $n+1$ is prime; the sole perfect composition is $(1^n)$. It is clear from \eqref{eqpc} that $\pc(n)$ is odd for all positive integers $n$. Table \ref{tab1} shows the compositions enumerated by $\pc(7)=11$, and how they are related to ordered factorizations and perfect partitions. Note that $\pc_1(7)=1, \pc_2(7)=4$ and $\pc_3(7)=6$. \begin{table}[H] \begin{center} \begin{tabular}{c|c|l} Factorization &Partition& Compositions\\ \hline 8&$(1^7)$&$(1^7)$\\ $2\cdot 4$ &$(1,2^3)$&$(1,2^3),(2^3,1)$\\ $4\cdot 2$&$(1^3,4)$&$(1^3,4),(4,1^3)$\\ $2\cdot 2\cdot 2$&$(1,2,4)$&$(1,2,4),(1,4,2),(2,1,4),(2,4,1),(4,1,2),(4,2,1)$\\ \hline \end{tabular} \caption{Perfect partitions versus perfect compositions of 7}\label{tab1} \end{center} \end{table} We highlight two interesting cases of \eqref{eqpck} and \eqref{eqpc}, namely (i) when $n$ is 1 less than a prime power, and (ii) when $n$ is 1 less than a squarefree number. \bigskip \noindent (i) If $p$ is prime, then $f(p^{\alpha},k)$ equals the number of compositions of $\alpha$ into $k$ parts (see, for example, \cite{Mu}). Since the latter number is known to be $\binom{\alpha-1}{k-1}$, we deduce from \eqref{eqpc} that $$\pc(p^\alpha-1)=\sum_{k=1}^\alpha k!\binom{\alpha-1}{k-1}.$$ The sequence $\{\pc(p^\alpha-1)\}_{\alpha\geq 1}$ agrees with sequence \cite[\seqnum{A001339}]{Sl} with offset 1. \bigskip \noindent (ii) If $p_1,\ldots,p_r$ are distinct primes, then $f(p_1p_2\cdots p_r,k) = k!S(r,k)$, where $S(N,k)$ is the Stirling number of the second kind (see, for example, \cite{Mu}). Hence $$\pc(p_1p_2\cdots p_r-1) = \sum_{k=1}^r k!^2 S(r,k).$$ This is clearly the Stirling transform of $(n!)^2$ and agrees with sequence \cite[\seqnum{A064618}]{Sl}. \subsection{Compositions with a given number of parts} A number $n$ has a perfect composition into $k$ distinct parts if and only if $n=2^k-1$. We deduce from \eqref{eqpck} that $\pc_k(2^k-1)=k!$. More generally if $n$ has a perfect composition into $k$ part sizes which all appear $u$ times, then $n=(u+1)^k-1$. There are $k!$ such compositions, obtained by permuting the unique partition $(1^u,(u+1)^u,((u+1)^2)^u,\ldots,((u+1)^{k-1})^u)$. (Note that \eqref{eqpck} is not applicable unless $u+1$ is prime). We now extend MacMahon's result that the number $g_k$ of all perfect partitions with $k$ (actual) parts is equal to the number of compositions of $k$ (see \cite[p.\ 188]{Ma1}): \begin{equation}\label{pppart} g_k=2^{k-1}. \end{equation} MacMahon described the following recurrence, and noted that it is the sequences of exponents of the enumerated partitions that form the compositions of $k$. $$g_k=2g_{k-1}, g_1=1.$$ Denoting the enumerated set by $G_k$, we see that $G_1$ contains the partition $(1)$. A partition $\lambda\in G_k$ gives rise to two partitions in $G_{k+1}$ by either appending the largest part of $\lambda$ or by appending a part which is greater by 1 than the sum of all the parts of $\lambda$. For example, given $G_3 = \{(1^3),(1^2,3),(1,2^2),(1,2,4)\}$, we use the recursive rule to obtain the members of $G_4$, in pairs: $$G_4=\{(1^4),(1^3,4),(1^2,3^2),(1^2,3,6),(1,2^3),(1,2^2,6),(1,2,4^2),(1,2,4,8)\}.$$ Observe that in both $G_3$ and $G_4$ the exponents of the part sizes give the compositions of 3 and 4 respectively. Thus $$G_3: (1^3)\mapsto (3),(1^2,3)\mapsto (2,1),(1,2^2)\mapsto (1,2),(1,2,4)\mapsto (1,1,1).$$ The symbolic parts of each partition fix the positions of the parts of each derived composition. For example, $(1,2,4^2)\in G_4$ has three symbolic parts which fix the positions of the parts of $(1,1,2)$. So there are as many partitions in $G_k$ with $j$ symbolic parts as compositions of $k$ into $j$ parts. Since their number is $\binom{k-1}{j-1}$, and a perfect partition gives perfect compositions by permutations of symbolic parts, the following result is proved. \begin{theorem}\label{thmx} The number $h_k$ of all perfect compositions with $k$ parts is given by $$h_k = \sum_{j=1}^{k}j!\binom{k-1}{j-1}.$$ \end{theorem} For example, $h_3=11$ enumerates the compositions $$(1^3),(1^2,3),(3,1^2),(1,2^2),(2^2,1),(1,2,4),(1,4,2),(2,1,4),(2,4,1),(4,1,2),(4,2,1).$$ \section{Colored perfect compositions}\label{nperfcomp} An $n$-color perfect partition of $\nu$ is one which contains one and only one $n$-color partition of each lesser number \cite{Ag}. Thus $(1_1^{\nu})$ is an $n$-color perfect partition for all $\nu$, and $\nu=5$ has six $n$-color perfect partitions: $(1_1^5), (1_1,2_1^2), (1_1,2_2^2), (1_1^2,3_1), (1_1^2,3_2), (1_1^2,3_3)$. We consider two formulas for the number $P_{\nu}$ of $n$-color perfect partitions of $\nu$ from Agarwal-Sachdeva \cite{Ag}. \begin{equation} \label{aga1} P_{\nu}=\sum_{\lambda}(\mbox{product of distinct parts of}\ \lambda), \end{equation} where the summation runs over all ordinary perfect partitions of $\nu$. Secondly, if $F=a_1 a_2\cdots a_k, k\geq 1$, is an ordered factorization of $\nu +1$, then \begin{equation} \label{aga2} P_{\nu}=1+\sum_{F}a_1^{k-1}a_2^{k-2}\cdots a_{k-1}, (a_0=0). \end{equation} We recall that an $n$-color composition is a composition in which a part of size $n,n\geq 1$ can come in $n$ colors denoted by subscripts $n_1,n_2,\ldots,n_n$ \cite{Aga}. \begin{definition} An \emph{$n$-color perfect composition} of $\nu$ is an $n$-color composition $C$ whose sequence of parts contain exactly one $n$-color composition of every positive integer less than $\nu$, where the order of parts of each composition is induced by the order of the parts of $C$. \end{definition} We enumerate $n$-color perfect compositions by permuting the symbolic parts of $n$-color perfect partitions. Let $C_{\nu}$ be the number of $n$-color perfect compositions of $\nu$. Then we find, for instance, that $C_5 = 11$, the enumerated objects being $$(1_1^5),(1_1,2_1^2),(2_1^2,1_1),(1_1,2_2^2),(2_2^2,1_1),(1_1^2,3_1),(3_1,1_1^2), (1_1^2,3_2),(3_2,1_1^2),(1_1^2,3_3),(3_3,1_1^2).$$ Straightforward reasoning shows that \eqref{aga1} and \eqref{aga2} adapt to the following formulas. If $\lambda$ is an ordinary perfect partition of $\nu$ with $k\geq 1$ distinct parts, then \begin{equation} \label{aga3} C_{\nu}=\sum_{\lambda}k!(\mbox{product of distinct parts of}\ \lambda). \end{equation} Alternatively, if $F=a_1 a_2\cdots a_k, k\geq 1$, is an ordered factorization of $\nu +1$, then \begin{equation} \label{aga4} C_{\nu}=1+\sum_{F}k!a_1^{k-1}a_2^{k-2}\cdots a_{k-1}, (a_0=0). \end{equation} Of course \eqref{aga3} is equivalent to the more direct version: \begin{equation} \label{aga5} C_{\nu}=\sum_{C}(\mbox{product of distinct parts of } C), \end{equation} where the summation runs over all ordinary perfect compositions of $\nu$. Thanks to Maple, the sequence $C_{\nu}, \nu\geq 1$, begins as follows (see \cite[\seqnum{A330774}]{Sl}): $$1, 1, 5, 1, 11, 1, 61, 7, 15, 1, 259, 1, 19, 17, 1901, 1, 383, 1, 511, 21,\ldots$$ \bibliographystyle{amsplain} \begin{thebibliography}{99} \bibitem{Aga} A. K. Agarwal, $n$-color compositions, \emph{Indian J. Pure Appl. Math.} \textbf{31} (2000), 1421--1427. \bibitem{Ag} A. K. Agarwal and R. Sachdeva, Combinatorics of $n$-color perfect partitions, \emph{Ars Combinatoria} \textbf{136} (2018), 29--43 \bibitem{An} G. E. Andrews, \emph{The Theory of Partitions}, Cambridge University Press, 1998. \bibitem{Ma1} P. A. MacMahon, \emph{Combinatory Analysis}, Volume 1, Cambridge University Press, 1915 \bibitem{Ma2} P. A. MacMahon, Memoir on the theory of the compositions of numbers, \emph{Philos. Trans. Roy. Soc. London Ser. A}, \textbf{184} (1893), 835--901. \bibitem{Map} Maple 18. Maplesoft, a division of Waterloo Maple Inc., Waterloo, Ontario. \bibitem{Mu} A. O. Munagi, Labeled factorization of integers, \emph{Electron. J. Combin}. \textbf{16} (2009), no. 1, Research Paper 50. \bibitem{R} J. Riordan, \emph{An Introduction to Combinatorial Analysis}, Wiley, 1958. \bibitem{Sl} N. J. A. Sloane et al., \emph{The On-Line Encyclopedia of Integer Sequences}. Published electronically at \url{https://oeis.org}, 2019. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 \emph{Mathematics Subject Classification}: Primary 05A17; Secondary 11P81, 05A15, 05A19. \noindent {\it Keywords}: partition, ordered factorization, perfect composition, $n$-color composition. \bigskip \hrule \bigskip \noindent (Concerned with sequences: \seqnum{A001339}, \seqnum{A002033}, \seqnum{A064618}, \seqnum{A074206}, \seqnum{A165552}, \seqnum{A330773}, and \seqnum{A330774}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received December 30 2019; revised version received May 6 2020. Published in {\it Journal of Integer Sequences}, May 7 2020. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}