%% if you are submitting an initial manuscript then you should have submission as an option here %% if you are submitting a revised manuscript then you should have revision as an option here %% otherwise options taken by the article class will be accepted \documentclass[submission]{FPSAC2026} %% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc %% note that the class file already loads {amsmath, amsthm, amssymb} \newtheorem{thm}{Theorem} \newtheorem{lem}{Lemma} %\usepackage{lipsum} \usepackage{tikz} %% define your title in the usual way \title{Hyperbinary partitions and q-deformed rationals} %% define your authors in the usual way %% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details %% for more than 3 names, use the Oxford comma: One Author, Two Author, Red Author, \and Blue Author \author[T. McConville, J. Propp, B. Sagan]{Thomas McConville\addressmark{1}, James Propp\addressmark{2}, \and Bruce E. Sagan\addressmark{3}} %\author[Optional shorter names]{Longer names me\thanks{\href{mailto:hello@world.c}{hello@world.c}. Longer names me was partially supported by Grant 2017.11.14.$\partial$\;supp.}\addressmark{1} \and you\addressmark{2}} %% then use \addressmark to match authors to institutions here \address{\addressmark{1}Department of Mathematics, Kennesaw State University, Kennesaw, GA 30144 \\ \addressmark{2}Department of Mathematics, University of Massachusetts Lowell, Lowell, MA 01854 \\ \addressmark{3}Department of Mathematics, Michigan State University, East Lansing, MI 48824} %% put the date of submission here \received{\today} %% leave this blank until submitting a revised version %\revised{} %% put your English abstract here, or comment this out if you don't have one yet %% please don't use custom commands in your abstract / resume, as these will be displayed online %% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year) \abstract{A hyperbinary partition of the nonnegative integer $n$ is a partition where every part is a power of 2 and every part appears at most twice. We give three applications of the length generating function for such partitions, denoted by $h_q(n)$. Morier-Genoud and Ovsienko defined the $q$-analogue of a rational number $[r/s]_q$ in various ways, most of which depend directly or indirectly on the continued fraction expansion of $r/s$. As our first application we show that $[r/s]_q = qh_q(n-1)/h_q(n)$ where $r/s$ occurs as the $n$th entry in the Calkin-Wilf enumeration of the nonnegative rationals. Next we consider fence posets which are those obtained from a sequence of chains by alternately pasting together maxima and minima. For every $n$ we show there is a fence poset whose lattice of order ideals is isomorphic to the poset of hyperbinary partitions of $n$ ordered by refinement. For our last application, Morier-Genoud and Ovsienko also showed that $[r/s]_q$ can be computed by taking products of certain matrices which are $q$-analogues of the standard generators for the special linear group. We express the entries of these products in terms of the polynomials $h_q(n)$.} %% put your French abstract here, or comment this out if you don't have one %\resume{\lipsum[2]} %% put your keywords here, or comment this out if you don't have them yet \keywords{Calkin-Wilf sequence, fence posets, order ideals, hyperbinary partitions, q-deformed rationals, Stern-Brocot sequence} %% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier %% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text %% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex %% but you can use bibtex if you want \usepackage[backend=bibtex]{biblatex} \addbibresource{bibpart.bib} %% note the \printbibliography command at the end of the file which goes with these biblatex commands \input{defs} %% \newtheorem{thm}{Theorem}[section] \newtheorem{prop}[thm]{Proposition} \newtheorem{cor}[thm]{Corollary} %% \newtheorem{lem}[thm]{Lemma} %% \newtheorem{conj}[thm]{Conjecture} %% \newtheorem{exa}[thm]{Example} %% \newtheorem{question}[thm]{Question} \DeclareMathOperator{\fusc}{fusc} \DeclareMathOperator{\CW}{CW} \DeclareMathOperator{\depth}{dp} \DeclareMathOperator{\height}{ht} \DeclareMathOperator{\jirr}{join-irr} \DeclareMathOperator{\irr}{Irr} \DeclareMathOperator{\crgf}{crgf} \DeclareMathOperator{\SL}{SL} \DeclareMathOperator{\PSL}{PSL} \newcommand{\hb}{\ol{h}} \newcommand{\fs}{\mathsf{s}} \newcommand{\fst}{\tilde{\mathsf{s}}} \newcommand{\tre}{\textcolor{red}} \newcommand{\tblue}{\textcolor{blue}} \newcommand{\tor}{\textcolor{orange}} \newcommand{\doubleleftbrace}{\{\!\{} \newcommand{\doublerightbrace}{\}\!\}} \articlenumber{63} \begin{document} \maketitle %% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above \section{Introduction} This extended abstract summarizes the results of the paper \cite{mcc:hyp} by the same authors. There has been much work in recent years on Stern’s diatomic sequence (e.g.~\cite{CW:rr}), fence posets (e.g.~\cite{OR:rpfpu}), and $q$-deformed rational numbers (e.g.~\cite{MGO:qdr1}), with links between these topics. We strengthen these links by bringing into the foreground {\em hyperbinary partitions}. These are partitions in which all parts are powers of two and in which no part appears more than twice. These have appeared in the literature on Stern’s diatomic sequence, but it has not been noticed that these objects relate to order ideals in fence posets and that a natural statistic on these partitions gives a nice way to construct the $q$-deformed rational numbers, avoiding explicit reliance on continued fractions. We explain those additional links. In view of the central role to be played by hyperbinary partitions, we first establish some definitions and notation about integer partitions in general. If $\la$ is an integer partition then we will write it either as a weakly decreasing sequence of integers or as its vector of multiplicities. For example, the integer partition $(4,1,1)$ can be written as $1^2 4$. Regardless of the notation chosen, if $\la$ is a partition of $n$ (meaning that the sum of its parts is $n$) then we will write $\la\ptn n$. The {\em length} of $\la$ is $$ \ell(\la) = \text{the number of parts of $\la$} = \sum_{i} m_i (\la), $$ where $m_i(\la)$ is the multiplicity of the part $i$ in $\la$. Returning to our example, $\ell(4,1,1)=3$. Call a partition $\eta$ {\em hyperbinary} if \ben \item each part is a power of $2$, and \item the multiplicity of each part is at most $2$. \een It appears that Wilf coined this term. The first in-depth study of such partitions was made by Reznick~\cite{rez:sbpf}, though antecedents can be found going as far back as Stern~\cite{ste:uzf}. Let \beq \label{H(n)} H(n) = \{\eta \mid \text{$\eta$ is a hyperbinary partition of $n$}\} \eeq and $$ h(n) = \#H(n) $$ where we will use $\#S$ or $|S|$ for the cardinality of a set $S$. For example, $$ H(10) = \{82,\ 81^2,\ 4^2 2,\ 4^2 1^2,\ 4 2^2 1^2\} $$ so that $$ h(10) = 5. $$ We introduce the generating function \beq\label{eq:hq} h_q(n) = \sum_{\eta\in H(n)} q^{\ell(\eta)}. \eeq For instance, $$ h_q(10) = q^2 + 2q^3 + q^4 + q^5. $$ Clearly $h_1(n) = h(n)$. We will give three applications using $h_q(n)$. Our first application, which is in the next section, involves the Calkin-Wilf sequence $\CW(n)$, $n\ge0$. This sequence is defined as the ratio $\CW(n)=\fusc(n)/\fusc(n+1)$ where $\fusc(n)$ is Stern's diatomic sequence as reinvented by Dijkstra (see \eqref{fuscDef}). The Calkin-Wilf sequence goes through each nonnegative rational number exactly once. Morier-Genoud and Ovsienko gave a way of associating with any rational number $r/s$ a $q$-analogue which is a rational function $[r/s]_q$. Our main result of this section is that one can calculate the $q$-analogue of $\CW(n)$ using the polynomials $h_q(n)$. In Section~\ref{php}, we consider the poset (partially ordered set) $\cH(n)$ of hyperbinary partitions of $n$ under the refinement ordering. A fence is a poset obtained by taking a sequence of chains and alternately identifying their maxima and minima. Our principal result here is the isomorphism in Theorem~\ref{thm:mainbij} which shows that $\cH(n)\iso \cJ(\cF(n))$ where $\cF(n)$ is the fence associated with $n$, and $\cJ(P)$ is the distributive lattice of all lower order ideals of the poset $P$ under inclusion. Using this isomorphism, we express the length of a hyperbinary partition in terms of the rank of the corresponding order ideal. Section~\ref{m} is devoted to the study of certain $q$-analogues of the standard generators of $\SL(2,\bbZ)$, see~\eqref{LR}. Morier-Genoud and Ovsienko showed that their rational $q$-analogues can be computed using certain products of these matrices. We prove in Theorem~\ref{thm:MnEnt} that the entries of such products can be easily computed using the $h_q(n)$. We end with a section devoted to open questions and avenues for future research. \section{A $q$-analogue of the Calkin-Wilf sequence} Let $\bbN$ and $\bbQ$ be the nonnegative integers and the rationals, respectively. {\em Stern's diatomic sequence}, also known as the {\em Stern-Brocot sequence} or the {\em obfuscating sequence}, can be defined inductively via $\fusc(0) = 0$, $\fusc(1) = 1$, and for $n\ge 1$, \beq \label{fuscDef} \begin{array}{rcl} \fusc(2n) &=& \fusc(n),\\ \fusc(2n+1)&=& \fusc(n+1)+\fusc(n) \end{array} \eeq (see Table 1). To our knowledge, Stern~\cite{ste:uzf} was the first person to study this sequence. The $\fusc$ notation was coined by Dijkstra~\cite[pp.\ 215-216]{dij:swc}. For a history of this sequence, see the article of Northshield~\cite{nor:sds}. The {\em Calkin-Wilf sequence} is defined for all $n\ge0$ by $$ \CW(n) = \frac{\fusc(n)}{\fusc(n+1)}. $$ This function has the property that for each rational number $r/s \geq 0$ there is a unique integer $n \geq 0$ satisfying $\CW(n) = r/s$. Calkin and Wilf introduced this sequence in~\cite{CW:rr} and related the $\fusc$ function to hyperbinary partitions. \begin{table} \centering \begin{tabular}{rclcl} $n$ & $\fusc_n$ & $\CW_n$ & $\fusc_n(q)$ & $\CW_n(q)$\\[1ex] \hline 0 & 0 & 0 & 0 & 0 \\[1ex] 1 & 1 & 1 & 1 & $\frac{1}{q}$ \\[1ex] 2 & 1 & $\frac12$ & $q$ & $\frac{1}{1+q}$ \\[1ex] 3 & 2 & 2 & $q + q^2$ & $\frac{1+q}{q}$ \\[1ex] 4 & 1 & $\frac13$ & $q^2$ & $\frac{q}{1+q+q^2}$ \\[1ex] 5 & 3 & $\frac32$ & $q + q^2 + q^3$ & $\frac{1 + q + q^2}{q + q^2}$ \\[1ex] 6 & 2 & $\frac23$ & $q^2 + q^3$ & $\frac{1 + q}{1 + q + q^2}$ \\[1ex] 7 & 3 & 3 & $q^2 + q^3 + q^4$ & $\frac{1 + q + q^2}{q}$ \\[1ex] 8 & 1 & $\frac14$ & $q^3$ & $\frac{q^2}{1 + q + q^2 + q^3}$ \\[1ex] 9 & 4 & $\frac43$ & $q + q^2 + q^3 + q^4$ & $\frac{1 + q + q^2 + q^3}{q + q^2 + q^3}$ \\[1ex] 10 & 3 & $\frac35$ & $q^2 + q^3 + q^4$ & $\frac{1 + q + q^2}{1 + 2 q + q^2 + q^3}$ %\\[1ex] %11 & 5 & $\frac52$ & $q^2+2q^3+q^4+q^5$ & $\frac{1+2q+q^2+q^3}{q+q^2}$ \end{tabular} \caption{The functions $\fusc_n$, $\CW_n$, $\fusc_n(q)$ and $\CW_n(q)$} \end{table} We mention here a method for computing $n$ from $r/s$ that is essentially described in~\cite{CW:bp} and deserves to be better known. Recall that every positive rational number $r/s$ has two representations as continued fractions, that is, representations of the form \beq \label{ConFra} \frac{r}{s}= a_1+\frac{1}{\dil{a_2 + \frac{1}{\ddots + \dil{\frac{1}{a_m}}}}} \eeq where $a_1 \geq 0$ and $a_2,\dots,a_m \geq 1$; for instance, $7/3$ can be written as both $2+1/3$ (with $m=2$) and as $2+1/(2+1/1)$ (with $m=3$). Given $r/s$, pick the representation with odd length. Create a binary string consisting of $a_1$ 1's, followed by $a_2$ 0's, followed by $a_3$ 1's, followed by $a_4$ 0's, followed by \dots, followed by $a_m$ 1's. Reverse it and one obtains the binary representation of the unique $n$ satisfying $\CW(n) = r/s$. For instance, with $r/s = 7/3 = 2+1/(2+1/1)$ we form the bit-string 11001 whose reversal $10011$ is the binary expansion of the number 19, and one can check that $\fusc(19) = 7$ and $\fusc(20) = 3$ yielding $\CW(19) = 7/3$. The polynomials $h_q(n-1)$ defined in (\ref{eq:hq}) satisfy the following recurrence. \bpr \label{hqrr} We have $h_q(-1)=0$, $h_q(0) = 1$, and for $n\ge1$ \begin{align} h_q(2n-1) &= q h_q(n-1),\label{hq(2n-1)}\\ h_q(2n) &= h_q(n) + q^2 h_q(n-1).\label{hq(2n)} \end{align} \epr Comparison of the previous proposition with the definition of the Stern sequence in~\eqref{fuscDef} prompts the following definition. Define the {\em $q$-Stern sequence} to be the polynomial sequence where $\fusc_q(0) = 0$ and for $n\ge 1$, $$ \fusc_q(n) = h_q(n-1). $$ Translating the previous proposition into the language of the $\fusc_q$ polynomials gives $\fusc_q(0) = 0$, $\fusc_q(1) = 1$, and \beq \label{fuscqRr} \begin{array}{rcl} \fusc_q(2n) &=& q \fusc_q(n),\\ \fusc_q(2n+1)&=& \fusc_q(n+1) + q^2 \fusc_q(n) \end{array} \eeq for $n \geq 1$. Similarly, we define the {\em $q$-Calkin-Wilf sequence} to be the sequence of rational functions $$ \CW_q(n) = \frac{\fusc_q(n)}{\fusc_q(n+1)} = \frac{h_q(n-1)}{h_q(n)} $$ for $n \geq 1$, with $\CW_q(0) = 0$. There is another way to obtain a closely related $q$-analogue of the Calkin-Wilf sequence. Morier-Genoud and Ovsienko~\cite{MGO:qdr1,MGO:qdr2,MGO:qdr3} found a way to associate with every rational number $r/s\in\bbQ$ a rational function $[r/s]_q\in\bbQ(q)$ that has many interesting properties and connections to various branches of mathematics. Suppose that $r/s$ is a positive rational number and consider the continued fraction expansion of $r/s$ as in~\eqref{ConFra}. The notation for this expansion is $r/s=[a_1,a_2,\ldots,a_m]$. Now define the {\em $q$-analogue} of $r/s$, $[r/s]_q$, to be the rational function obtained by taking the continued fraction for $r/s$ and making the replacements $$ a_i \text{ becomes } \begin{cases} [a_i]_q & \text{if $i$ is odd,}\\ [a_i]_{q^{-1}} & \text{if $i$ is even,} \end{cases} $$ and $$ \text{the $1$ in the $i$th numerator becomes } \begin{cases} q^{a_i} & \text{if $i$ is odd,}\\ q^{-a_i} & \text{if $i$ is even,} \end{cases} $$ where $[a_i]_q$ denotes the ordinary $q$-integer $1 + q + q^2 + \cdots + q^{a_i - 1}$. The result of these substitutions is denoted $[r/s]_q = [a_1,a_2,\ldots,a_m]_q$ and the initial part of the fraction is $$ \left[\frac{r}{s}\right]_q= [a_1]_q+\frac{q^{a_1}}{\dil{[a_2]_{q^{-1}} + \frac{q^{-a_2}}{\ddots}}}. $$ It is easy to see that $[r/s]_q$ does not depend on which of the two continued fraction expansions one starts with. Our first main result gives a striking relationship between $\CW_q(n)$ and the $q$-analogue of the rational number $\CW(n)$. %% Now one could ask if there is a relationship between $\CW_q(n)$ and the $q$-analogue given by %% $$ %% [\CW(n)]_q=\left[\frac{\fusc(n)}{\fusc(n+1)}\right]_q. %% $$ %% To see what the relationship is, we will need the fact, proved by Morier-Genoud and Ovsienko, %% %~\cite{MGO:qdr2} %% that for all rational numbers $r$ we have %% \beq %% \label{r/s+1} %% \left[\frac{r}{s} + 1\right]_q = q\left[\frac{r}{s}\right]_q + 1. %% \eeq \bth \label{thm:qrat} For all $n\ge0$ we have \[ [\CW(n)]_q = q \CW_q(n). \] \eth The coefficient sequences of the Laurent polynomials in the numerator and denominator of $[r/s]_q$ are known to be unimodal \cite{OR:rpfpu}. By Theorem~\ref{thm:qrat}, the polynomials $h_q(n)$ are unimodal as well. \section{The poset of hyperbinary partitions of $n$} \label{php} \begin{figure} \centering \begin{tikzpicture} \filldraw(0,0) circle(.1); \filldraw(0,1) circle(.1); \filldraw(-1,2) circle(.1); \filldraw(1,2) circle(.1); \filldraw(0,3) circle(.1); \draw (0,0)--(0,1)--(-1,2)--(0,3) (0,1)--(1,2)--(0,3); \draw(0,-.5) node{$\scl(4,2,2,1,1)$}; %node{$\doubleleftbrace 4,2^2,1^2\doublerightbrace $}; \draw(1,1) node{$\scl(4,4,1,1)$}; %node{$\doubleleftbrace 4^2,1^2\doublerightbrace $}; \draw(-1.7,2) node{$\scl(8,1,1)$}; %node{$\doubleleftbrace 8,1^2\doublerightbrace $}; \draw(1.7,2) node{$\scl(4,4,2)$}; %node{$\doubleleftbrace 4^2,2\doublerightbrace $}; \draw(0,3.5) node{$\scl(8,2)$}; %node{$\doubleleftbrace 8,2\doublerightbrace $}; \draw(0,-1.5) node{$\cH(10)$}; %\draw(4,2) node{$\iso$}; % \begin{scope}[shift={(5,0)}] \filldraw(0,0) circle(.1); \filldraw(0,1) circle(.1); \filldraw(-1,2) circle(.1); \filldraw(1,2) circle(.1); \filldraw(0,3) circle(.1); \draw (0,0)--(0,1)--(-1,2)--(0,3) (0,1)--(1,2)--(0,3); \draw(0,-.5) node{$0122$}; \draw(.9,1) node{$0202$}; \draw(-1.7,2) node{$1002$}; \draw(1.7,2) node{$0210$}; \draw(0,3.5) node{$1010$}; \draw(0,-1.5) node{$\cD(10)$}; \end{scope} % \begin{scope}[shift={(10.5,0)}] \filldraw(0,0) circle(.1); \filldraw(0,1) circle(.1); \filldraw(-1,2) circle(.1); \filldraw(1,2) circle(.1); \filldraw(0,3) circle(.1); \draw (0,0)--(0,1)--(-1,2)--(0,3) (0,1)--(1,2)--(0,3); \draw(0,-.5) node{$\scl\emp$}; \draw(.8,1) node{$\scl\{x_2\}$}; \draw(-1.7,2) node{$\scl\{x_1,x_2\}$}; \draw(1.7,2) node{$\scl\{x_2,x_3\}$}; \draw(0,3.5) node{$\scl\{x_1,x_2,x_3\}$}; \draw(0,-1.5) node{$\cJ(\cF(10))$}; \end{scope} \end{tikzpicture} \caption{The posets $\cH(10),\ \cD(10)$, and $\cJ(\cF(10))$ \label{cHcD10}} \end{figure} Let $\cH(n)$ denote the poset of hyperbinary partitions under the {\em refinement partial order}, where we say $\mu$ {\em refines} $\la$ (in symbols, $\mu \leq \la$) if the parts of $\la$ can be subdivided to produce the parts of $\mu$. An equivalent way to state this definition is that the parts of $\mu$ can be grouped together so that, adding the parts in each group, one obtains the parts of $\la$. For example, $\cH(10)$ is displayed on the left in Figure~\ref{cHcD10}. The poset $\cH(n)$ was investigated by Brunetti and D'Aniello~\cite{BDA:gch} who used it to study how the length of a hyperbinary expansion of $n$ (see the definition of such an expansion in the next paragraph) is related to $n$ itself. Our aim is to show that $\cH(n)$ is isomorphic to the lattice of ideals of a corresponding fence poset. For any undefined terms used from the theory of partially ordered sets; see the texts of Sagan~\cite{sag:aoc} or Stanley~\cite{sta:ec1}. It is worth mentioning that the poset of {\em all} partitions of $n$ is {\em not} a lattice under refinement order when $n\ge5$; for instance, the partitions $41$ and $32$ both cover the partitions $311$ and $221$ so the former two do not have a meet (coarsest common refinement) while the latter two do not have a join (finest common coarsening). It will be convenient to use hyperbinary expansions rather than hyperbinary partitions. %(The term ``hyperbinary'' was coined by Herb Wilf %in the context of such representations; %its application in the adjacent context of partitions %rapidly became standard.) Suppose that the binary expansion of $n$ is $$ \be(n) := b_1 b_2\ldots b_k, $$ in other words $$ n = b_1 2^{k-1} + b_2 2^{k-2} + \ldots + b_k. $$ Note our nonstandard convention of having $b_1$ be the coefficient of the highest power of $2$, $b_2$ for the next-highest, and so forth. This will make the indexing simpler when we describe the isomorphism. A {\em hyperbinary expansion} of $n$ is \[ d = d_1 d_2 \ldots d_k \] having the same length as the binary expansion $\be(n)$ where $d_i\in\{0,1,2\}$ for all $i$ and \[ n = d_1 2^{k-1} + d_2 2^{k-2} + \ldots + d_k. \] Note that there may be some initial zeros in a hyperbinary expansion forced by the fact that it has the same number of digits as the binary expansion. For example, if $n=10$ then the largest power of $2$ in its binary expansion is $2^3$ so all hyperbinary expansions must have length $3+1=4$. More specifically, $d=0122$ is a hyperbinary expansion for $10$ since it has length $4$ and \[ 10= 0\cdot 2^3 + 1\cdot 2^2 + 2\cdot 2^1 + 2. \] %% Given a sequence $d=d_1\ldots d_k$ of zeros, ones, and twos, we let %% \begin{align*} %% s(d) &= \text{ the integer for which $d$ is a hyperbinary expansion}\\ %% &=\sum_{i=1}^k d_i 2^{k-i}. %% \end{align*} %% Note that we may need to adjust the number of initial zeros to make the length of $d$ correct. So, as just noted, %% $s(0122)=10$. %% For a more refined invariant, %% we let %% $$ %% s_i(d) = s(d_1\ldots d_i). %% $$ %% For example, $s_3(10210)=s(102)=1\cdot 2^2+0\cdot 2+2\cdot 1=6$. There is a clear bijection between hyperbinary partitions $\eta$ of $n$ and hyperbinary expansions $d$ of $n$ obtained by mapping $\eta$ to $d=d_1\ldots d_k$, where $2^{k-1}$ is the largest power of $2$ in $\be(n)$ and $d_i$ is the multiplicity of $2^{k-i}$ in $\eta$. Thus the set $\cD(n)$ of hyperbinary expansions of $n$ inherits a poset structure induced by $\cH(n)$. See Figure~\ref{cHcD10} for this isomorphism when $n=10$. The following lemma will be useful. It shows that our definition of $\cH(n)$ coincides with that in~\cite{BDA:gch}. We write $x\lt y$ if $x$ is {\em covered by} $y$, i.e., $x0$ with the pair $(d_i-1)2$. \ele %The next proposition contains some interesting facts about $\cD(n)$. A poset $P$ has a {\em maximum} if there is an element $\oh$ such that $\oh\ge x$ for all $x\in P$. Dually, a {\em minimum} is $\zh$ satisfying $\zh\le x$ for all $x\in P$. \bpr[\cite{BDA:gch}]\label{prop:bounds} We have the following. \ben %\item[a] %% MOVED -- fix labels \item[(a)] Poset $\cD(n)$ has a maximum, denoted $\oh(n)$, which is the binary expansion of $n$. \item[(b)] Poset $\cD(n)$ has a minimum, denoted $\zh(n)$, which is the unique hyperbinary expansion whose zeros form a prefix of $\zh(n)$. \een \epr %For the next result, we need another concept. Consider the binary expansion $\be(n)=b_1 b_2\ldots b_k$. The {\em principal prefix} of $\be(n)$ is $p(\be(n)) = b_1 b_2\ldots b_r$ where $b_{r+1}$ is the rightmost $0$ in $\be(n)$. For the rest of this section we will use $r$ for the length of the principal prefix. Note that if $b_i=1$ for all $i$ then, because there is no such zero, $p(\be(n))=\emp$ (the empty string). For example, if $n=75$ then $\be(75) = 1001011$ and $p(\be(75))=1001$. %We will now get fence posets involved. The {\em $n$th fence}, $\cF(n)$, is the poset constructed from the principal prefix $p(\be(n))=b_1 b_2 \ldots b_r$ as follows. The elements of $\cF(n)$ will be $x_1,x_2,\ldots,x_r$. Covers will only be between adjacent elements in this list, where we start with the element $x_1$ and inductively define for $i\ge2$ $$ \case{x_i\lt x_{i-1}}{if $b_i=0$,}{x_i\gt x_{i-1}}{if $b_i=1$.} $$ As an example, suppose $n=75$. Recalling that $p(\be(75))=1001$, we obtain $$ \begin{tikzpicture}[scale=.9] \draw(-1,1) node{$\cF(75)=$}; \filldraw(0,2) circle(.1); \filldraw(1,1) circle(.1); \filldraw(2,0) circle(.1); \filldraw(3,1) circle(.1); \draw (0,2)--(2,0)--(3,1); \draw(0,2.5) node{$x_1$}; \draw(1,1.5) node{$x_2$}; \draw(2,0.5) node{$x_3$}; \draw(3,1.5) node{$x_4$}; \end{tikzpicture} $$ where the two ``down" covers from $x_1$ to $x_2$ and from $x_2$ to $x_3$ come from the two zeros of $1001$ while the ``up" cover from $x_3$ to $x_4$ comes from the final $1$. Let $\cJ(P)$ be the distributive lattice of all lower order ideals of $P$ ordered by containment. As an example, consider $\cJ(\cF(10))$. Now $\be(10)=1010$ so that $p(\be(10))=101$ and $$ \begin{tikzpicture} \draw(-1,1) node{$\cF(10)=$}; \filldraw(1,1) circle(.1); \filldraw(2,0) circle(.1); \filldraw(3,1) circle(.1); \draw (1,1)--(2,0)--(3,1); \draw(1,1.5) node{$x_1$}; \draw(2,0.5) node{$x_2$}; \draw(3,1.5) node{$x_3$}; \end{tikzpicture} $$ is the correponding poset. The lattice of order ideals $\cJ(\cF(10))$ is displayed in Figure~\ref{cHcD10}. Our second main result is the following. \bth\label{thm:mainbij} We have the poset isomorphism $\cD(n)\iso\cJ(\cF(n))$. \eth In the full version of our paper \cite{mcc:hyp}, we prove Theorem~\ref{thm:mainbij} by constructing an explicit bijection between $\cD(n)$ and $\cJ(\cF(n))$. To prove this map is a poset isomorphism, we show that $\cD(n)$ is a distributive lattice whose subposet of join-irreducibles is isomorphic to $\cF(n)$. The result then follows from the Fundamental Theorem of Finite Distributive Lattices. For $n=10$, the isomorphism of Theorem~\ref{thm:mainbij} may be obtained by comparing the posets in the middle and on the right in Figure~\ref{cHcD10}. The {\em corank-generating function} of $\cJ(\cF(n))$ is \[ \crgf_n(t) = \sum_{I\in\cJ(\cF(n))} t^{r-|I|}, \] where $r=|\cF(n)|$. \bth\label{thm:weightbij} For all $n\in\bbN$, if $\beta(n)$ has $s$ ones, then \beq\label{eqn:htorgf} h_q(n) = q^s \crgf_n(q). \eeq \eth Using the definition of $\CW_q(n)$, we deduce the following corollary from the previous theorem. \bco\label{cor:qCW_fence} Given $n\geq 1$, suppose $\beta(n-1)$ has $s'$ ones, and $\beta(n)$ has $s$ ones. Then $$ \hspace*{150pt} \CW_q(n) = q^{s'-s} \, \frac{\crgf_{n-1}(q)}{\crgf_n(q)}. \hspace*{150pt}\qed $$ \eco \section{Matrices} \label{m} Consider the matrices \beq \label{LR} L = \left[ \barr{cc} 1 & 0\\ 1 & q^{-1} \earr \right] \qmq{and} R = \left[ \barr{cc} q & 1\\ 0 & 1 \earr \right]. \eeq Morier-Genoud and Ovsienko~\cite{MGO:qdr1} showed that the $q$-analogues of rational numbers can be expressed as ratios of entries in products involving $L$ and $R$. In this section, we will relate certain products to hyperbinary partitions. We note that Han et al.~\cite{HEA:uvCW,HEA:mrv} have studied a generalization of the Calkin-Wilf sequence generated by matrices $$ L_u = \left[ \barr{cc} 1 & 0\\ u & 1 \earr \right] \qmq{and} R_v = \left[ \barr{cc} 1 & v\\ 0 & 1 \earr \right]. $$ Define a sequence of matrices $M(n)$ for $n\ge1$ as follows. Let the binary expansion of $n$ be $\be(n)=b_1\ldots b_k$ so that $b_1=1$. Removing the initial $1$ and reading the sequence backwards results in $b_k b_{k-1}\ldots b_2$. Now let $M(n)$ be the matrix obtained from the product formed by replacing each $0$ in $b_k b_{k-1}\ldots b_2$ by $L$ and each $1$ by $R$. For example, if $n=19$ then $\be(19)=10011$, so the reversed sequence is $1100$ and \begin{align*} M(19) &= RRLL\\ &= \left[ \barr{cc} q & 1\\ 0 & 1 \earr \right] \left[ \barr{cc} q & 1\\ 0 & 1 \earr \right] \left[ \barr{cc} 1 & 0\\ 1 & q^{-1} \earr \right] \left[ \barr{cc} 1 & 0\\ 1 & q^{-1} \earr \right] \\[5pt] &= \left[ \barr{cc} q^{-1}+ 2 + q + q^2 & q^{-1} + q^{-2}\\ q^{-1} + 1 & q^{-2} \earr \right]. \end{align*} For $k,l\in\bbN$, we use the notation $$ [k,l) =\{k,k+1,\ldots,l-1\}. $$ \bth\label{thm:MnEnt} Suppose that $n\in[2^k, 2^{k+1}-1)$ and write $\be(n)=b_1 b_2\ldots,b_{k+1}$. Let $j$ be the maximum index such that $b_1=\ldots=b_j=1$ and define $n'$ by $$ \be(n') = 1 b_{j+2} b_{j+3} \ldots b_{k+1}. $$ Then $$ M(n) = \left[ \barr{cc} q^{-k+2j-1}\ h_q(n' -1) & q^{-k+1}\ h_q(n - 2^k - 1)\\[5pt] q^{-k+2j-2}\ h_q(n') & q^{-k}\ h_q(n - 2^k) \earr \right]. $$ If $n=2^{k+1}-1$ then the same formula holds with the first column replaced by $$ \left[ \barr{c} q^k \\[5pt] 0 \earr \right]. $$ \eth The row sums of $M(n)$ take a particularly nice form. This result can be derived as a corollary of Theorem~\ref{thm:MnEnt} or proven more directly from the recurrence in Proposition~\ref{hqrr}. \bth \label{MnThm} If $n\in[2^k,2^{k+1})$ then $$ M(n) \left[ \barr{c} 1\\[5pt] 1 \earr \right] = \left[ \barr{c} q^{-k}\ h_q(n-1)\\[5pt] q^{-k-1}\ h_q(n) \earr \right]. $$ \eth Up to a simultaneous degree shift, the entries of the vector in Theorem~\ref{MnThm} are the numerator and denominator polynomials of $[\CW(n)]_q$. \section{Comments and future work} We gather here various ideas for future work and open problems. Additional directions are considered in the full paper. \subsection{Lattices} As illustrated at the beginning of Section~\ref{php}, the set of all partitions of $n$ do not form a lattice under refinement for $n\ge5$. %{\sf (JP: I see that this passage is sort-of redundant with a similar remark I added to an earlier section, with an example coming from $n=6$. What's the counterexample with $n=5$?)} But the subset of hyperbinary partitions does and, in fact, the lattice is distributive. It would be interesting to identify other natural subposets of the full partition poset that are lattices and satisfy various lattice properties. \subsection{Other statistics} Given a hyperbinary partition $\eta$ we let $$ p_i(\eta) = \text{number of parts of $\eta$ of multiplicity $i$} $$ for $i = 1, 2$. Note that we have the relation \beq \ell(\eta) = p_1(\eta) + 2p_2(\eta). \label{ellp1p2} \eeq The statistics $p_1$ and $p_2$, have been considered, respectively, by Klav\v{z}ar, Milutinovi\'c, and Petr~\cite{KMP:sp} and by Bates and Mansour~\cite{BM:qCW}. As far as we know our statistic $\ell$ has not been studied before, although it is the one most closely related to the $q$-rationals of Morier-Genoud and Ovsienko. Consider the generating function $$ \hb_{s,t}(n) = \sum_{\eta\in H(n)} s^{p_1(\eta)} t^{p_2(\eta)}. $$ Using~\eqref{ellp1p2} we see that setting $s=q$ and $t=q^2$ recovers our previously considered polynomial $h_q(n) = \sum_{\eta\in H(n)} q^{\ell(\eta)}$. We have the following recurrence for $\hb_{s,t}(n)$. \bpr We have $\hb_{s,t}(0) = 1$, and for $n\ge 1$ \begin{align*} \hb_{s,t}(2n-1) &= s\ \hb_{s,t}(n-1),\\ \hs{140pt} \hb_{s,t}(2n) &= \hb_{s,t}(n) + t\ \hb_{s,t}(n-1).\hs{140pt} \end{align*} \epr A different statistic was studied by Dilcher and Ericksen~\cite{DE:hesp} as well as Dilcher and Stolarsky~\cite{DS:pass}; their statistic reduces each nonzero digit by 1 and interprets the result in binary. \acknowledgements{We are grateful for the comments and suggestions from the anonymous referees.} %% if you use biblatex then this generates the bibliography %% if you use some other method then remove this and do it your own way \printbibliography \end{document}