\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}}}
\usepackage{hyperref}
\DeclareMathOperator{\DL}{DL}
\DeclareMathOperator{\DR}{DR}

\begin{document}

\begin{center}
\includegraphics[width=4in]{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 Shade in Compositions of Integers}
\vskip 1cm

\large
Aubrey Blecher and Arnold Knopfmacher\\
The John Knopfmacher Centre for Applicable Analysis and Number Theory\\ 
School of Mathematics\\
University of the Witwatersrand\\
Private Bag 3, P O WITS 2050\\ 
South Africa\\ 
\href{mailto:aubrey.blecher@wits.ac.za}{\tt aubrey.blecher@wits.ac.za}\\
\href{mailto:arnold.knopfmacher@wits.ac.za}{\tt arnold.knopfmacher@wits.ac.za}\\
\ \\
Michael Mays\\
School of Mathematical and Data Sciences\\
West Virginia University\\ 
Morgantown, WV 26506\\
USA\\
\href{mailto:mmays@mail.wvu.edu}{\tt mmays@mail.wvu.edu}\\
\end{center}

\vskip .2 in


\begin{abstract}
Integer compositions of $n$ can be viewed as bargraphs, in which the $i$th part of the composition $x_i$ is given by the $i$th column of the bargraph with $x_i$ cells. The sun is at infinity in the northwest of our two-dimensional model, and each composition casts a shadow in accordance with the rules of physics. We
find the number of unit squares in this shadow (but not being part of the composition)
through
a bivariate generating function  tracking composition size and shadow.   
\end{abstract}

\section{Introduction}\label{intro}
 Integer compositions of $n$ with $k$ parts can be modeled  by a bargraph with $k$ columns in which the $i$th part, say $x_i$, is represented by column $i$ of the bargraph built with $x_i$ vertically stacked square cells. We position the sun at infinity in the northwest, and consider the problem of how many cells in the vicinity of the bargraph representation are in shade.
Any shade in these structures can only occur when there is a descent of two or more (and possibly to the right of this part also).  
This idea of shade was inspired by an earlier notion of lit cells, which was originally explored by two of the current authors and others \cite{ABC}. Lit cells in partitions and compositions were studied by the current authors \cite{BKM, BKM1}.
We show a simple example of shade below in Figure \ref{411312easy}.


\begin{figure}[h]
\begin{center}
\includegraphics[height=4cm]{411312easy.png}
\caption{4+1+1+3+1+2 with shaded cells.}
\label{411312easy}
\end{center}
\end{figure}


Shade is different from lit cells in that lit cells are a distinguished subset of cells in the original bargraph, whereas shaded cells are cells that are not included in the original bargraph.  Shaded cells are similar to the water cells studied by Blecher, Brennan, and Knopfmacher \cite{BBK} in this regard, but shaded cells may lie either within the envelope of the bargraph or at the right hand end, whereas water cells must be within the envelope of the bargraph.  Shaded cells in the envelope are considered in Section \ref{between} and shaded cells at the right end in Section \ref{right}. 

A critical aspect of the solution is that it makes use of the so called {\em{skew bijection}}. This bijection is a modification of the bijection specified by Prodinger \cite{pro}.  The skew bijection maps each composition of $n$ with $j$ parts to the super-diagonal (or skew) composition of $n+\binom{j}{2}$ and is defined by sending each original $i$th part $x_i$ to the new $i$th part $x_i+i-1$ (and its reverse for the inverse). The image objects for this bijection are super-diagonal compositions (i.e., compositions in which the $i$th part $\ge i$). As explained by Prodinger \cite{pro}, if a part in the domain composition produces shade to its right, then the image of this part is a left to right maximum in the image composition. This enables us to view the problem of shade production in any given composition as a problem of tracking shade between successive pairs of left to right maxima in superdiagonal compositions.

See an example in Figure \ref{411312}.  This example is built from Figure \ref{411312easy}.  The extra shaded cell at the right in Figure \ref{411312easy} is counted by a different argument. 


\begin{figure}[h]
\begin{center}
\includegraphics[height=5cm]{411312a.png}
\caption{The skew bijection maps 4+1+1+3+1+2 to 4+2+3+6+5+7, with added staircase shown in green.}
\label{411312}
\end{center}
\end{figure}

Our method of solution is a constructive one in which we specify an arbitrary pair of successive left-to-right maxima $s_1$ and $s_2$ in respective positions
$i_1$ and $i_2>i_1+1$ (see the shaded squares in the right hand side of Figure 2), and then find the generating function for the shade lying between them,  afterwards constructing the generating functions for all (superdiagonal) compositions having this particular pair somewhere in the middle.

This generating function is found in Section \ref{between}. 

In addition to the shade to the left of each left-to-right maximum, we also need to account for all shade to the right of the leftmost overall maximum. To account for this shade area, we let $s$ in position $i$ be the leftmost overall  maximum of the image (under the skew bijection) superdiagonal composition. 

The generating function for the shade to the right of $i$ is found in Section \ref{right}. 

We note that to the left of the overall maximum, after the skew bijection has been applied there may be no left to right maximum pairs with shade between. This condition is equivalent to the case where the parts to the left of $i$ constitute a weakly increasing partition.  It is interesting that the general superdiagonal compositions to the left of $i$ split into two categories, namely those that are partitions and those that are not, and this split is natural in our method of solution. The theoretical connection between the theory of integer compositions and the theory of integer partitions has been explored by Blecher \cite{B}, with an interesting example of how the theories are connected. 
 Other papers dealing with skew or super-diagonal bargraphs are by Deutsch et al.\ \cite{DMR1} and Van Rensburg \cite{vr}.  
 
\begin{figure}[h]
\begin{center}
\includegraphics[height=4cm]{eg2.png}
\caption{A large composition (unshaded) showing the complexity of the shade parameter.}
\label{desc}
\end{center}
\end{figure}

\section{Shade between two successive left to right maxima}\label{between}
For the image compositions after the skew bijection has been applied, we let two successive left-to-right maxima, $s_1$ and $s_2$ occur in respective positions $i_1$ and $i_2$ where $i_2>i_1+1$. The case $i_2=i_1+1$ is dealt with in the next section.

We track the size $n$ of the original composition with variable $q$ 
and the size of the image composition with variable $x$ and shade 
between $i_1$ and $i_2$ with $u$, with the goal to obtain the
generating function $F(q) = \sum_{n=0}^\infty c(n) q^n$ where $c(n)$
is the sum over all compositions of $n$ of the amount of shade in each
composition. This is achieved in via the intermediate functions
$F(x,q)=\DL(x,q)+\DR(x,q)$ developed below, where $\DL(x,q)$ is the generating function for the total shade between two successive left to right maxima and $\DR(x, q)$ is the generating function for the total shade to the right of the leftmost maximum.
   
The first $i_1 - 1 $ parts each have maximum part size $s_1 - 
 1 $, and therefore together with the left to right maximum, a 
combined generating function given by
\begin{equation}
\underbrace{\Bigl(\prod_{r=1}^{{i_1}-1} \frac{(x q)^r-(x q)^{{s_1}}}{(1-x q)} \frac{1}{q^{r-1}}\Bigr)}_A\underbrace{\vphantom{\prod_{r=1}^{{i_1}-1}}(x q)^{s_1}\frac{1}{q^{{i_1}-1}}}_B=\prod_{r=1}^{{i_1}-1} \frac{(x q)^r-(x q)^{{s_1}}}{1-x q}(x q)^{s_1}\frac{1}{q^{\frac{1}{2}{i_1}({i_1}-1)}}.
\label{L1}   
\end{equation}

The quotient in the product of underbrace $A$ is the generating function for the part of the composition in position $r$. Because we are dealing with a superdiagonal composition, each such part $p$ must satisfy $r \le p < s_1$ with generating function for each such part as shown. The multiplying term $\frac{1}{q^{r-1}}$ is necessary to correct what precedes it in terms of $q$, which must track each part of the composition as it occurs before the skew bijection is applied. The term in underbrace $B$, namely ${(xq)}^{s_1}$, is the generating function for the left-to-right maximum for the skew bijection image $s_1$ when it is tracked by the variable $x$ and as before this needs to be multiplied by $\frac{1}{q^{i_1-1}}$. This is then simplified in the right hand side of the equation.

We assume that there is a drop of at least two between $s_1$ and $s_2$, occurring for the first time, say, in column $i_3$ and of size $s_3$ after the skew bijection is applied. Thus $i_3 \le s_3 \le s_1-1$. This is equivalent to a drop of at least one after the skew bijection is applied, and means that there is shade of at least 1 in column $i_3$ where $i_1<i_3<i_2$. The generating function for columns $i_2$ and $i_3$ is given by 
\begin{equation}
\underbrace{(x q)^{{s_2}} \frac{1}{ q^{i_2-1}}}_A 
\Bigl(\underbrace{\frac{1}{q^{{i_3-1}}} (x q)^{s_3}}_B \underbrace{\vphantom{\frac{1}{ q^{i_2-1}}}u^{s_1-s_3}}_C\Bigr),
\label{c(i_1+1)}   
\end{equation}
where $A$ is the generating function for $s_2$ in column $i_2$, both before and after the
skew bijection is applied; similarly $B$ is for column $i_3$ and $C$ is for the shade that must occur in column $i_3$. 

Next we consider the generating function for columns strictly between $i_1$ and $i_2$ but excluding $i_3$. This is given by 
\begin{equation}
     \prod_{i=i_1+1
}^{{i_3}-1} \underbrace{\vphantom{\frac{1-(\frac{x
   q}{u})^{{s_1}-i+1}}{1-\frac{x q}{u}}}\frac{1}{q^{i-1}} (x q)^{s_1}}_B
\prod_{i=i_3+1
}^{i_2-1}  \underbrace{\vphantom{\frac{1-(\frac{x
   q}{u})^{{s_1}-i+1}}{1-\frac{x q}{u}}}\frac{1}{q^{i-1}} (x q)^{i}u^{s_1-i}}_D\underbrace{\frac{1-(\frac{x
   q}{u})^{{s_1}-i+1}}{1-\frac{x q}{u}}}_A,
   \label{c2(i_3)}  
\end{equation}
where $B$ tracks columns to the right of $i_1$ and to the left of $i_3$, because after the skew bijection has been applied, these are all of size $s_1$.  $D$ is the generating function for the maximum shade that may occur in column $i$ when it lies between $i_3$ and $i_2$, and $A$ tracks any additional cells in this $i$th column   up to a maximum of $s_1-i$. But for any such additional cells one $u$ unit needs to be removed (which is achieved by the replacement of $xq$ with $\frac{xq}{u}$). The index $i$ in both products is tracking the $(i)$th column in the composition. So, for example, $i=i_1+1$ is tracking the column immediately to the right of $i_1$. 

Next, suppose there are $m \ge 0$ parts to the right of $i_2$. These parts can be any size, provided they are superdiagonal after the skew bijection has been applied. In other words the generating function for these $m$ parts is given by $$\prod_{r=1}^m \frac{(x q)^{i_2+r}}{1-x q}\underbrace{\frac{1}{q^{i_2+(r-1)}}}=q^{-{i_2} m-\frac{1}{2} m (m-1)} (1-x q)^{-m} (x 
   q)^{\frac{1}{2} m (1+2 {i_2}+m)}.$$
As before, the underbraced term above is the correction required to render an accurate expression before the skew bijection is applied.

This needs to be summed over $m$ and simplifies to the generating function for these $m$ parts being
\begin{equation}
    1+\sum_{m=1}^\infty q^{-{i_2} m-\frac{1}{2} m (m-1)} (1-x q)^{-m} (x 
   q)^{\frac{1}{2} m (1+2 {i_2}+m)}.
\label{L4}
\end{equation}
We sum the generating function for Eqs.~\eqref{L1} and \eqref{c(i_1+1)} over $i_1$, $s_1$, $i_2$, $s_2$, $i_3$ and $s_3$,  insert Eq.~\eqref{c2(i_3)} thereafter, and finally multiply by Eq.~\eqref{L4} above to obtain the overall generating function 
\begin{align}
L(x,q,u)&=\sum_{{i_1}=1}^\infty \sum_{{s_1}={i_1}+2}^\infty 
\prod_{r=1}^{{i_1}-1} \frac{(x q)^r-(x q)^{{s_1}}}{1-x q}(x
   q)^{{s_1}}\frac{1}{q^{\frac{1}{2} {i_1} 
({i_1}-1)}}\notag\\
& \biggl(\sum_{{i_2}={i_1}+2}^{{s_1}+1} \sum_{{s_2}={s_1}+1}^\infty
   \sum_{{i_3}={i_1}+1}^{{i_2}-1} \sum_{{s_3}={i_3}}^{{s_1}-1}
     (x q)^{{s_2}} \frac{1}{ q^{i_2-1}} \Bigl(\frac{1}{q^{{i_3-1}}} (q
   x)^{s_3} u^{s_1-s_3}\Bigr)\biggr.\notag\\
& \left. \prod_{i=i_1+1
}^{i_3-1} \frac{1}{q^{i-1}} (x q)^{s_1}
\prod_{i=i_3+1
}^{i_2-1}  \frac{1}{q^{i-1}}(xq)^i u^{s_1-i}\frac{1-\bigl(\frac{x
   q}{u}\bigr)^{{s_1}-i+1}}{1-\frac{x q}{u}}\right)\notag \\ 
&\Bigl(1+\sum_{m=1}^\infty  q^{-{i_2} m-\frac{1}{2} m
   (-1+m)} (1-x q)^{-m} (x q)^{\frac{1}{2} m (1+2 {i_2}+m)}\Bigr). 
 \label{Lu}  
\end{align}

The generating function for the total shade $\DL(x,q)$ between two successive left to right maxima is obtained by differentiating Eq.~\eqref{Lu}
with respect to $u$ and setting $u=1$.

We obtain
\begin{align}
\DL(x,q)&=\sum_{i_1=1}^\infty \sum_{s_1=i_1}^\infty\Bigl(\prod_{r=1}^{i_1-1} \frac{(x q)^r-(x q)^{s_1}}{1-x q}\Bigr) 
(x q)^{s_1}\frac{1}{q^{\frac{1}{2}i_1 (i_1-1)}} \notag\\
&\sum_{i_2=i_1+2}^{s_1+1} \sum_{s_2=s_1+1}^\infty \sum_{i_3=i_1+1}^{i_2-1} \sum_{s_3=i_3}^{s_1-1} (x q)^{s_2} q^{-(i_2-1)}
\Bigl(\prod_{i=i_1+1}^{i_3-1} \frac{(x q)^{s_1}}{q^{i-1}}\Bigr) q^{-(i_3-1)} (x q)^{s_3} \notag\\
&\Bigl( (s_1-s_3) \prod_{i=i_3+1}^{i_2-1}q^{-(i-1)} (x q)^i \frac{ (1-(x q)^{s_1-i+1})}{1-x q}\Bigr.\notag\\
&\left.+\sum_{j=i_3+1}^{i_2-1} \Bigl(\prod_{i=i_3+1,\; i\ne j}^{i_2-1}q^{-(i-1)} (x q)^i \frac{(1-(x q)^{s_1-i+1})}{1-x q}\Bigr.\notag\right.\times\\
&\left. \frac{ q^{1-j} (j (x q)^j (-1+x q)-s_1 (x q)^j (-1+x q)+x q (-(x q)^j+(x q)^{s_1}))}{(1-x q)^2}\right)\notag\\
&\Bigl(1+\sum_{m=1}^\infty q^{-i_2 m-\frac{1}{2} m (-1+m)} (1-x q)^{-m} (x q)^{\frac{1}{2} m (1+2 i_2+m)}\Bigr).
\label{DL}
\end{align}

Note that the variable $u$ in Eq.~\eqref{Lu} is a tracker for the shade between arbitrary pairs of left-to-right maxima. However, the coefficient of $q^m x^n$ of the derivative in Eq.~\eqref{DL} tracks the  total shade to the left of the leftmost overall maximum across all compositions with these particular $m$ and $n$ values. The more conventional method of obtaining the latter is to have $u$ as tracker for the full shade (lying left of the leftmost maximum) in each composition and not just for arbitrary pairs of successive left-to-right maxima. The method chosen is simpler. 

We modify Eq.~\eqref{DL} by setting $x=1$ in order to obtain the generating function given by the coefficients of
$\DL(q):=\DL(1,q)$, for shade to the left of the leftmost overall maximum in compositions of $n$ tracked by $q$. We obtain the generating function
\begin{align}
&\DL(q)=\notag\\
&
\sum_{i_1=1}^{\infty} \sum_{s_1=i_1+2}^{\infty} \bigl(\frac{1}{1-q}\bigr)^{i_1-2} \Bigl(\prod
   _{r=1}^{i_1-1} (1-q^{s_1-r})\Bigr) q^{\frac{1}{2} i_1 (-1+i_1-2
   s_1)}\notag\\ 
&
\sum_{i_2=i_1+2}^{s_1+1} \sum_{s_2=s_1+1}^\infty\sum_{i_3=i_1+1}^{i_2-1} \sum
   _{s_3=i_3}^{s_1-1} q^{\frac{1}{2} (-i_3-i_3^2)+i_3 s_1+s_2+s_3}
   \Bigl(\frac{1}{1-q}\Bigr)^{i_2-i_3} \notag\\
&
   \Bigl( (s_1-s_3) \prod_{i=i_3+1}^{i_2-1} (1-q^{s_1-i+1})\notag\Bigr.\\
\end{align}
\begin{align}
&   
\Bigl.+\sum_{j=i_3+1}^{i_2-1} \prod_{i=i_3+1
,\;i\ne j}^{i_2-1}
   (1-q^{s_1-i+1})\frac{j (-1+q)+q^{1-j+s_1}+s_1-q
   (1+s_1)}{1-q}\Bigr)\notag\\
&
\Bigl(1+\sum_{m=1}^\infty q^{-i_2 m-\frac{1}{2} m (-1+m)}
   (1-q)^{-m} q^{\frac{1}{2} m (1+2 i_2+m)}\Bigr),
\label{DL(q)}    
\end{align}
with series expansion beginning
\begin{align}
2 q^6+6 q^7+24 q^8+73 q^9+209 q^{10}+560 q^{11}+1452 q^{12}+3621 q^{13}.
\label{seriesDL(q)}   
\end{align}

\section{Shade to the right of the leftmost overall maximum}\label{right}
Let the leftmost overall maximum $s$ occur in position $i$.

Since we have already accounted for the shade to the left of position $i$, we use the generating function for all parts to the left of $i$ without tracking any shade. Thus all parts to the left of $i$, this time including the part in position $i$ have generating function
\begin{equation}
    \sum_{i=1}^\infty \sum_{s=i}^\infty \prod_{r=1}^{i-1} \underbrace{\vphantom{\frac{1}{q^{\frac{1}{2} i (i-1)}}}\frac{(x q)^r-(x q)^s}{1-x
   q}}_A\underbrace{(x q)^s\frac{1}{q^{\frac{1}{2} i (i-1)}}}_B\underbrace{\vphantom{\frac{1}{q^{\frac{1}{2} i (i-1)}}}u^{\binom{s-(i-1)}{2}}}_C,
\label{rightshade}
\end{equation}
where $A$ is the generating for each part $p_r$ in position $r$. We have $r \le p_r \le s-1$. $B$ is the generating function for the largest part and includes the correction for all these parts before the skew bijection is applied. $C$ is the maximum possible shade that may occur to the right of $s$.

However, there may be parts to the right of $s$ and each such part must be removed from the maximum shade. Let there be $m$ such parts where $0 \le m \le s-1$. The generating function doing this is
\begin{equation}
\sum_{m=0}^{s-1} \Bigl(\prod_{r=1}^m \underbrace{\frac{(\frac{x
   q}{u})^{i+r}-(\frac{x q}{u})^{s+1}}{1-\frac{x
   q}{u}}}_A\underbrace{\frac{1}{(\frac{q}{u})^{i+r-1}}}_B\Bigr).
\label{fsr}
\end{equation}
$A$ is the generating function for the part in position $i+r$ and also removes all shade occupied by a cell of the composition, and $B$ is the generating function required to make the correction before the skew bijection is applied. 

Combining Eqs.~\eqref{rightshade} and \eqref{fsr}, we obtain the generating function $R(x,q,u)$ for shade (tracked by $u$) to the right of the leftmost overall maximum as
\begin{align}
&R(x,q,u)=\notag\\
&\sum_{i=1}^\infty \sum_{s=i}^\infty \prod_{r=1}^{i-1} \frac{(x q)^r-(x q)^s}{1-x q}(x q)^s\frac{1}{q^{\frac{1}{2} i (i-1)}}u^{\binom{s-i+1}{2}}\sum_{m=0}^{s-1} \prod_{r=1}^m \Bigl(\frac{(\frac{x q}{u})^{i+r}-(\frac{x q}{u})^{s+1}}{1-\frac{x q}{u}}\frac{1}{(\frac{q}{u})^{i+r-1}}\Bigr).
\label{R_p}
\end{align}

To get the generating function $\DR(x,q)$ for the total shade to the right of the leftmost maximum, we differentiate Eq.~\eqref{R_p} with respect to $u$ and set $u=1$. We obtain

\begin{align}
&\DR(x,q)=\notag\\
&\sum_{i=1}^\infty  \sum_{s=i}^\infty  \Bigl(\prod_{r=1}^{i-1} \frac{(x q)^r-(x q)^s}{1-x q}\Bigr)  
(x q)^s \frac{1}{q^{\frac{1}{2} i(i-1)}} \binom{s-i+1}{2} \sum_{m=0}^{s-1} 
\prod_{r=1}^m \frac{(x q)^{i+r}-(x q)^{s+1}}{(1-x q) q^{i+r-1}}+\notag\\
 &\Biggl(\sum_{i=1}^\infty  \sum_{s=i}^\infty  \Bigl(\prod_{r=1}^{i-1} \frac{(x q)^r-(x q)^s}{1-x q}\Bigr) (x q)^s \frac{1}{q^{\frac{1}{2} i (i-1)}} 
 \sum_{m=0}^{s-1} \sum_{j=1}^m  \prod_{r=1,r \ne j}^m \Bigl(\frac{(x q)^{i+r}-(x q)^{s+1}}{1-x q}\frac{1}{q^{i+r-1}}\Bigr)\Biggr.\notag\\
&\Biggl.\quad\frac{q^{1-i-j} (-(x q)^{i+j} +(x q)^{1+s} (2-i-j+s) +(x q)^{2+s}
   (-1+i+j-s) )}{(1-x q)^2}\Biggr).
   \label{R}    
\end{align}

We modify Eq.~\eqref{R} by setting $x=1$ in order to obtain the generating function given by the coefficients of
$\DR(q):=\DR(1,q)$, for shade to the right of the leftmost maximum in compositions of $n$ tracked by $q$. We obtain the generating function

\begin{align}
&\DR(q)=\notag\\
&
\sum_{i=1}^\infty \sum_{s=i}^\infty \Bigl(\prod_{r=1}^{i-1} (1-q^{s-r})\Bigr) \frac{q^s}{(1-q)^{i-1}}
   \Biggl(\binom{s-i+1}{2} \sum_{m=0}^{s-1} \frac{q^m }{(1-q)^m}\prod_{r=1}^m (1-q^{s+1-i-r})\notag\Biggr.\\
&
\left.+\frac{1}{(1-q)^2}\sum
   _{m=1}^{s-1} \sum_{j=1}^m \frac{q^m}{(1-q)^{m-1}} \prod_{r=1}^m
   (1-q^{s+1-i-r})\notag\right.\\
&
\Biggl.(-1-q^{1-i-j+s} (-2+i+j-s)+q^{2-i-j+s} (-1+i+j-s))\Biggr),
\label{DR(q)}    
\end{align}
with series expansion beginning
\begin{align}
q^2+4 q^3+13 q^4+34 q^5+83 q^6+193 q^7+430 q^8+938 q^9+2011 q^{10}+4253 q^{11}+8899 q^{12}.
\label{seriesR(q)}   
\end{align}


\section{Generating function for shade in compositions}\label{gf}
Finally, we sum the generating functions from the previous two sections to obtain the generating function $F(x,q)$ for shade in compositions. So

$$F(x,q)=\DL(x,q)+\DR(x,q),$$
with series expansion beginning
\begin{align*}
 F(x,q)&= q^2 x^2+3 q^3 x^3+(q^3+{\bf{6 \textbf{\emph{q}}^4}}) {\bf{\textbf{\emph{x}}^4}}+({\bf{6 \textbf{\emph{q}}^4}}+10
   q^5) {\bf{\textbf{\emph{x}}^5}}+(15 q^5+15 q^6) x^6\\
&+({\bf{\textbf{\emph{q}}^4}}+32
   q^6+21 q^7){\bf{\textbf{\emph{x}}^7}}
   +(8 q^5+56 q^7+28 q^8)
   x^8+(27 q^6+92 q^8+36 q^9) x^9\\
&+(68 q^7+138
   q^9+45 q^{10}) x^{10}+(q^5+140 q^8+200
   q^{10}+55 q^{11}) x^{11}\\
&+(10 q^6+260 q^9+275
   q^{11}
+66 q^{12}) x^{12}+(41 q^7+441 q^{10}+370
   q^{12}+78 q^{13}) x^{13}. 
\label{seriesF(x,q)}   
\end{align*}

\begin{figure}[h]
\begin{center}
\includegraphics[height=6cm]{4CompShade.png}
\caption{13 shaded cells distributed among compositions of 4.}
\label{4CompShade}
\end{center}
\end{figure}

We account for the highlighted terms in Figure \ref{4CompShade} above.  Let us focus on compositions of 4, so we choose all the terms involving $q^4$.  The top composition has one part, so the image composition, whose size is indexed by $x$, has no staircase added and hence is also of size 4.  The coefficient of $q^4x^4$ is 6, and there are 6 shaded cells in the top composition.  Compositions of 4 with 2 parts are in the next row.  They have an image composition with one extra cell in the staircase, so are associated with $q^4x^5$.  There are 6 shaded cells in the middle row.  Lastly, there is one composition of 4 with 3 parts, on the bottom row, for which the image composition has a staircase with 1+2 cells in it, so the shade is counted by $q^4x^7$.  One cell is shaded in the bottom row.   No other composition of 4 has any shaded cells, so we account for all 13 shaded cells with these compositions.

Now we define
$$F(q):=F(1,q)$$
and thus we arrive at the main result of this paper. 
\begin{theorem}
The generating function for the total shade in all compositions of $n$ tracked by $q$ is given by
\begin{equation}
F(q)=\DL(q)+\DR(q)   
\end{equation}
where $\DL(q)$ is given by Eq.~\eqref{DL(q)} and $\DR(q)$ is given by 
Eq.~\eqref{DR(q)}.
\end{theorem}

The series expansion for $F(q)$ begins
$$q^2+4 q^3+13 q^4+34 q^5+85 q^6+199 q^7+454 q^8+1011 q^9+2220 q^{10}+4813 q^{11}+10351
   q^{12}+22104 q^{13} .$$
The series of coefficients above is \seqnum{A372768} in the OEIS \cite{sloane}.

We observe that if all shaded squares in Figure \ref{desc} were white, we would be showing a  shadeless composition. Shadeless compositions are characterized as being alternating sequences ending at height 1 where the alternation is between arbitrary partitions written in increasing order (which end just before a decrease) and decreasing partition staircases that end just before there is a repeated part or an increase. This follows because as stated in the introduction, shade can only occur in a composition when there is a drop of at least two, which implies that a shadeless composition can not have a drop of 2 or more. This latter also implies that the composition must end at height 1.

For example, having all shaded squares in Figure \ref{desc} in white (i.e., with all shaded squares understood as part of the composition), its sequence decomposition given in reverse order is
\begin{align*}
    & [ 1, 2, 3, 4, 5, 6, 7, 8] (6)[7, 8] (6)[7] (3)[4] (2)[3] (3)[4, 5, 
   6] (4, 3)[4 , 5, 6, 7] (6, 6)[7, 8, 9] (5, 4)\\&[5, 6] (4)[5] (2)],
\end{align*}
where the alternation is between maximal length staircases represented between square brackets and maximal weakly decreasing partitions represented in round brackets.
For a  decomposition of all integer compositions into a similar such alternating sequence, see Blecher \cite{B}. 

\begin{thebibliography}{99}

\bibitem{ABC} M. Archibald, A. Blecher, C. Brennan, A. Knopfmacher, and T. Mansour, 
Shedding light on words,  
{\em Appl. Anal. Discrete Math} {\bf 11} (2017), 
216--231.

\bibitem {B} A. Blecher, 
Compositions of positive integers $n$ viewed as alternating sequences of increasing/decreasing partitions, 
{\em Ars Combin.} {\bf 106} (2012), 
213--224.

\bibitem {BBK} A. Blecher, C. Brennan, and A. Knopfmacher, 
The water capacity of integer compositions, 
{\em Online J. Anal. Comb.}, {\bf 13} (2018), 
\#06.

\bibitem{BKM} A. Blecher, A. Knopfmacher, and M. Mays, 
Casting light on compositions, submitted.
 
\bibitem{BKM1} A. Blecher, A. Knopfmacher, and M. Mays, 
Casting light on partitions, submitted.

\bibitem{DMR1} E. Deutsch, E. Munarini, and S. Rinaldi, 
Skew Dyck paths, area, and superdiagonal bargraphs, 
{\em J. Statist. Plann. Inference}, {\bf 140} (2010), 
1550--1562.

\bibitem{AKHP} A. Knopfmacher and H. Prodinger, 
On Carlitz compositions, 
{\em European J. Combin.} {\bf 19} (1998), 
579--589.

\bibitem{pro} H. Prodinger, 
Visibility problems related to skip lists, 
 {\em Australas. J. Combin.} {\bf 72} (2018), 
 509--515.

\bibitem{sloane} N. J. A. Sloane et al., 
The On-Line Encyclopedia of Integer Sequences, 2023. 
Available at \url{https://oeis.org}.

\bibitem{vr} E. J. Janse Van Rensburg, 
Adsorbing bargraph paths in a $q$-wedge, 
{\em J. Phys. A:Math. Gen} {\bf 38} (2005), 
8505--8525.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification}:
Primary 05A16; Secondary 05A15.

\noindent \emph{Keywords: } 
generating function, shade, composition.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences \seqnum{A008930},  \seqnum{A079500}, \seqnum{A219282}, and \seqnum{A372768}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received May 15 2023; 
revised version received May 14 2024.
Published in {\it Journal of Integer Sequences}, May 15 2024.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in

\end{document}
