1The two columns
In a fair copy of the dinner minutes the removal of a cover and the introduction of an amendment receive the same mark. The original desk book distinguishes them by column. Its left column belongs to the clerk of the council and its right column to the steward of the plate. They share a line counter. The copyist retains that counter, the opening stroke and the closing stroke. Blank space on the other side of a ruled line is lost in transcription. We ask how many original desk books agree with one page of the fair copy.
Two customs of the dinner enter the count. A subsidiary motion suspends the question on which it was moved until the chair disposes of the subsidiary motion. The steward holds the numbered tickets of uncovered dishes on a single spindle. A dish can be covered when its ticket comes off the spindle. Thus one may amend a motion while the soup is uncovered, introduce a further amendment, and cover the soup before the chair disposes of the latest amendment. Within either column the last item opened is the first eligible for closure. The rulings on renewal of a disposed question in [7] and the rules for a second spindle in [16] describe other registers. Throughout this paper the first entry opens an item and the desk is cleared before the clerk signs the page.
Coloring the opening marks alone does not generally recover the entry that a closing mark discharges. Consider the four strokes , with one motion and one dish, where opens and closes. The four choices of the places of the two motion strokes consist of one of the first two places and one of the last two. For only the first pair or the second pair can belong to the motion. Both records give precisely the same total number of openings, and the steward’s receipt is the same in all six reconstructions. This distinction was lost in an early index of the joint books which lists every four-stroke extract under two subject headings [5]. A column heading classifies an entry. It does not put the entry back on the right line.
Our count treats an item by the line of its introduction. Names of amendments and a menu with named dishes would require extra labels. Closing a dish means returning its ticket, whether or not any food was removed. Likewise a motion can be discharged by withdrawal. The unit recorded here is an item occupying a register, as in the editorial descriptions of the docket in [11, 17]. No distinction between the several ways of disposing of that item survives on the page. With this convention there is exactly one possible wholly parliamentary reading of any legal record. There is also exactly one reading in which the council conducted no business at all.
The unrestricted enumeration is a shuffle of two Dyck languages. Catalan interpretations of the two projections are classical [18, 20], as are quadrant walks with axial steps [2]. The question addressed in Section 3 fixes the entire sequence of signs before taking a count. For this question we keep the two coordinate axes visible. The correction for raising a valley in the sign sequence is supported on them. In Section 4 we use this correction to determine how much information is supplied by a receipt for a specified number of dishes. The effect of changing the sampling unit from a copied page to a completed desk book is calculated separately in Section 5.
2Completions of a sign sequence
Definition 1 (Joint register). A page of size is a word with letters and letters , each prefix of which has at least as many as . A completion assigns each of its positions a column or . Reading either column alone must give a page, possibly empty. Let give a completion weight when opening marks belong to column , and sum the weights of all completions.
For a fixed coloring there is a unique matching between openings and closures in each column. Read from left to right, attaching each closure to the most recent still unattached opening of its color. A closure without such an opening would give the corresponding one-color word a negative prefix. This construction is the usual parenthesis matching, or, with the matched positions joined by arcs, the noncrossing matching of a Dyck word [6, 12]. Arcs of different colors may cross. Drawing both families of arcs on the same side of the line has occasionally led to a stronger condition on transcribed books [15]. On opposite sides the rule can be read from the drawing without inspecting the color of a crossing.
Write for the excess of openings over closures after lines. If there are motions and dishes pending then . Thus one only needs the distribution of to resume the count after an interruption. In particular a certificate that a named recess took place with no outstanding business sets . All open items at that line must have been dishes. A separate certificate that the table was cleared sets . At positive height the two certificates are incompatible. At zero height they both say the same thing.
Lemma 1 (Counting with one height coordinate). Put and set values outside the interval at stage equal to zero. If the next stroke opens, write . If it closes, write . In either update retain indices . Then .
Proof. A left entry either increases at an opening, carrying a factor , or decreases it at a closure. A right entry preserves . On a closing step from height the new height is . A right closure from a state with would lead to and is discarded. A left closure from a state with is discarded at the lower end. Thus every accepted step has a ticket or a question available when one is required. Appending entries partitions completions by the last entry, proving the recurrence.∎
Although the single coordinate suffices for computation, keep both coordinates for a moment. Use row vectors indexed by in the nonnegative quadrant. The weighted step matrix increases the first coordinate with weight or the second coordinate with weight one. The step matrix decreases either coordinate with weight one if it is positive. Products are written in reading order. With the unit row vector of the origin and the product for , we have
Only finitely many entries enter any product between endpoint vectors in Eq. (1). This is the transfer-matrix treatment of a fixed word [19], with the observable signs of the steps playing the role of a prescribed environment. Interchanging the two columns pairs completions with motions and motions. Hence . Color interchange need not fix a single line of a particular completion. Palindromy here is a statement about the entire set of original desk books that may underlie the one fair copy.
We shall use a second factorization. If with and both pages, both coordinates must vanish at the end of . There is only one state at that cut, so . One cannot use a printed paragraph ending in place of a zero-height cut. Several registers set a paragraph break at the arrival of the main dish irrespective of the motion then before the house [3]. In such a book the missing information at the break has possible states. The product must sum over them.
3Raising a valley
Order pages of a given size by the elementary operation and its transitive closure. This is the height order on Dyck paths. Indeed, write down the ordered positions of the opening strokes. A rise by two at a single intermediate vertex moves one opening one place to the left. If one page lies weakly above another, move the first opening whose position differs leftwards across closures until it has the required position and repeat. Every intermediate word is still a page. An order on Dyck paths involving rotation of whole factors would give different covers [20].
Theorem 2 (Local exchange formula). Let and where is a page. Set and . For states on the diagonal one has
In particular the difference has nonnegative integer coefficients and is positive at every real .
Proof. For a pair of steps that uses different columns, the increase in one column and decrease in the other can be made in either order. Their weights agree, as does their final state. For a two-step excursion in column , an opening followed by closure is always possible and has weight . Closure followed by opening is possible exactly when . Both orders return to their initial state. The same argument for column gives a surplus of one when . Consequently is diagonal in quadrant coordinates and its diagonal has the values in Eq. (2). Inserting this difference in Eq. (1) proves the identity. For strict positivity, color and entirely with . The prefix reaches . The suffix goes from this state to the origin because the two deleted steps have net zero height. This contributes a term of degree one. The initial height of the valley is positive, as its first step closes.∎
The subtraction in Eq. (2) also has a direct interpretation in the book. Send a completion of the valley to the completion of the peak obtained by interchanging the two actual entries. If they belong to different columns they can trade places. In one column closing one item and opening another becomes opening and closing a new one. The line-pair matching is recomputed after the exchange. The map is injective on colored words. A remaining peak completion can fail to come from this construction only if it opens and closes in a column empty before the peak. Thus the increases can all be certified by the clerk or the steward at a single line. The test uses the state at the left end of the pair of entries.
For fixed the increase can vanish. The clearest example is the last exchange below the largest page of size , with prefix and suffix . At the left axis all prefix entries are dishes and all suffix entries must close them. At the right axis every prefix entry is a motion. The polynomial added by the exchange is for . At the two certificates account for distinct completions of the same degree. At the coefficient of degree two is undisturbed. A steward who has a receipt for two dishes cannot distinguish those last two pages by the number of possible readings, although the sign strings themselves differ.
4Receipts and sharp bounds
Let and . Both fit in a book with lines. On an page there is a return to the origin after every other entry. Each pair can be filled as a single motion or a single dish and the factorization following Lemma 1 gives . On a page the first entries open. Choose the motion openings and independently choose the motion closures in the second half. Enough items of each type remain available at every closure, since all entries of that type still to be closed have already been opened.
Theorem 3 (Bounds at fixed receipt). For a page of size and ,
The lower bounds are attained simultaneously at and the upper bounds at . For these simultaneous extrema are unique. Without a receipt the sharp bounds on the number of completions are and .
Proof. Each page lies in the interval from to . Apply Theorem 2 along a saturated chain in this interval and evaluate the endpoints by the choices just described. At every exchange is strict. Consequently no second page attains all coefficients at either extremum. Summing squares of binomial coefficients is the Vandermonde convolution [10].∎
Consider a receipt saying that six dishes were uncovered in a twenty-four-line sitting. The page then contains six motions. In Eq. (3) the bounds on the number of possible desk books are 924 and 853,776. The latter is reached on the record whose first half consists entirely of opening strokes. Even a perfectly legible receipt specifying the individual dishes in order of first service leaves the same 853,776 assignments of the marks, provided no dishes share a ticket. Assign their names in that order to the six service openings in any reconstruction. The names recover which ticket returns at a service closure only after one has decided that the line represents service. A receipt listing line numbers would supply additional evidence.
The coefficients for several shorter pages appear in Table 1. Six elementary exchanges separate the extreme records. For the third record an inventory after four lines refines its counts as shown in Figure 1. A single outstanding service ticket together with a receipt for two dishes leaves eighteen assignments.
| Copy | 0 motions | 1 | 2 | 3 | 4 | Total |
|---|---|---|---|---|---|---|
| UDUDUDUD | 1 | 4 | 6 | 4 | 1 | 16 |
| UUDDUUDD | 1 | 8 | 18 | 8 | 1 | 36 |
| UUDUDUDD | 1 | 13 | 26 | 13 | 1 | 54 |
| UUUDUDDD | 1 | 15 | 36 | 15 | 1 | 68 |
| UUUUDDDD | 1 | 16 | 36 | 16 | 1 | 70 |
There is a weaker form of auxiliary evidence than a receipt. A slip may certify that the table was once cleared without giving the line. An empty spindle occurs at the first and last boundary in every history. Excluding these endpoints still leaves the question of counting each history once, whatever the number of clearances. Adding the number of certificates at each internal boundary counts the same desk book several times. When the line is given, the single slice of Lemma 1 prescribed after Definition 1 suffices. For an unspecified line, carry a second bit in the recurrence and set it the first time a permitted internal boundary is reached with . This qualification matters in the catalogs of dinners that record the clearance of the table as a single event [13].
5Sampling the page and the book
Let . If we now release the visible record and retain only its size, the aggregate has a simpler interpretation. Take one completed desk book apart by columns. Each column, read in isolation, is an ordinary Dyck word. The remaining information is just which of the lines the clerk used. Thus the following aggregate identity, unlike the fixed-page formula, requires no information about empty columns at particular points.
Proposition 4 (Completion totals). Among all completed desk books of size , the number with motions is
In particular .
Proof. Choose the positions for the clerk’s column and the word in each column. Interleaving preserves the prefix inequality for their sum. Conversely, extracting the columns recovers every one of those choices. This proves the first expression in Eq. (4). Substitute factorials to obtain the second. The sum of the product of the two binomial coefficients over is by choosing elements from a set partitioned into sets of sizes and .∎
The mean number of reconstructions of a uniformly chosen visible page is consequently . A cataloger who selects a desk book uniformly and has a fair copy made from it sees pages with probability proportional to . These experiments give different distributions even at . The uniform page sample gives equal mass to and . The uniform book sample gives them masses and . This is the elementary instance of size bias relevant to inventories that count physical books [14]. A transcription project which retains one specimen of every visible sign string implements the first sampling law if the specimens have equal selection probabilities.
The separation between the smallest and mean counts is visible on a logarithmic axis in Figure 2. At size ten, where the full set of pages is still fairly small, the mean is 58,786 and the largest page has 184,756 readings. Stirling’s formula applied to Theorem 3 and Proposition 4 gives a ratio of maximum to mean asymptotic to . The mean grows exponentially faster than the minimum. Logarithms of the counts give the length in bits of an index into a known fiber, up to rounding [4]. Averaging such lengths requires averaging the logarithm itself.
The receipt has a particularly simple law for a uniform book. The probability of motions is by Eq. (4). This is the law of the number of marked elements in a sample of without replacement from elements, of which are marked. The ordinary hypergeometric moment formulas [8] give
The mean of given any fixed page is already under uniform sampling of its completions, by color interchange. Its conditional variance depends on the page. On the motion indicators for the opening strokes are independent fair bits. On the mass at is proportional to , the law of the intersection size of a uniform -subset of with a fixed half of that set. At the corresponding variances are and . In the book population Eq. (5) gives . The absolute counts in Figure 3 use the book population.
A catalog may require the clerk to certify that at least one question was disposed of. Every page of positive size then loses exactly one completion, its all-service reading. If it also certifies that dinner was served at least once, every page loses one more. Either requirement leaves the strict ordering of total counts under a valley lift unchanged. The two certificates have little force at size twelve. On the largest page they distinguish two of the 2,704,156 possible arrangements of marks. In particular a certificate that a sitting took place during dinner does not identify the line on which it opened.
6Evidence at a named line
A more informative surviving document is the inventory at recess, compiled while the chair was away. Suppose that a page has a cut after marks and that the steward specifies the number of tickets on the spindle at that cut. Split there. The constrained polynomial is a single summand of Eq. (1), namely . Several inventories impose this restriction at several times. Entries should be imposed in order. Two individually possible states at consecutive boundaries may be incompatible if they differ by more than one ticket. The inventories in [1] mark a line before the adjoining stroke, which changes the boundary index by one.
For the largest page the midpoint inventory determines the entire receipt because every opening precedes it. At a midpoint where the page returns to zero the same inventory adds no information. The latter effect persists even if the manuscript specifies the exact number of each kind of entry on either side of the break. Once the two local receipts have been fixed, the admissible books on the two sides are independent choices. If only the total receipt survives, convolution replaces multiplication of the two fixed coefficients. In particular an identified recess written between the two middle strokes of does not reduce any coefficient in Table 1.
Corollary 5 (Identification of the amount of business). For each page of size and each between zero and inclusive, at least one compatible book records exactly motions. If one outside source establishes the number of motions and a second establishes the number of dishes, the two sources exclude every completion precisely when their counts do not sum to , provided both counts are nonnegative integers.
Proof. All binomial coefficients in the indicated range in Eq. (3) are positive. Every opening is assigned exactly one column. Together these facts give the criterion.∎
The count behind Corollary 5 permits the clerk to suspend a question while service takes place. At a dinner where business formally adjourns for each service entry, the all-motion and all-service readings still exist but the middle coefficients may change. A rule requiring the clerk to introduce a question only with the spindle empty is a restriction on the horizontal steps of a quadrant walk. It deletes some of the mixed-color paths used in the commutation proof. The copy itself gives no evidence that such an adjournment rule was observed. Model selection on this question would require a line identified in both the book and the copy. An inventory indexed only by course has already discarded the necessary timing.
AInteger checks and boundary conventions
The entries of Table 2 were computed in two ways. For each visible word we propagated integer arrays as in Lemma 1, with . Independently we formed pairs of balanced column words and interleaved them by choosing the positions of the left column in the combined stream. Sorting the resulting records by their sign strings gives their fiber sizes, with multiplicity one for each interleaving: the underlying colored word determines the subset of positions originally chosen. This enumeration also works with distinct formal weights for openings of each color, but the total degree is always , so a single indeterminate records the same information. The empty word contributes one to both sums and is excluded from the table.
| Openings | Pages | Smallest fiber | Largest fiber | Books |
|---|---|---|---|---|
| 2 | 2 | 4 | 6 | 10 |
| 3 | 5 | 8 | 20 | 70 |
| 4 | 14 | 16 | 70 | 588 |
| 5 | 42 | 32 | 252 | 5,544 |
| 6 | 132 | 64 | 924 | 56,628 |
For a single page of maximum height , the evaluation at needs at most two arrays of integers and integer additions. Tracking the receipt coefficient requires retaining powers only through , because no later update decreases a degree. By symmetry one may instead use degree when it is smaller. These are arithmetic operation counts. At the final total is at most , and a partial colored word has at most two choices per stroke, bounding the length of all intermediate integers by bits. Numerical transfer matrices for excursions are often truncated at a fixed height [9]. Here the visible record gives the exact height before any computation begins.
To check the boundary term separately, retain the row at the end of and propagate a column backwards through . The row uses weights on openings. The backwards computation must keep the weight on the same physical entry even though the corresponding coordinate now moves in the opposite direction. Reversing the suffix and interchanging the opening and closing signs without moving the weights also happens to give the right unweighted total. For a nonzero marked degree it may give a different result because the suffix starts with open items. The discrepancy occurs already at the last valley below . Keeping the matrix transposes in reverse order preserves the receipt exactly.
The copy has no tick for adoption, dissent or unanimity. To count named resolutions which carried, a separate decision field would be needed at every motion closure. Court copies occasionally append a general certification that all business listed was duly transacted [21]. At the level of the register studied here this certification is vacuous for the all-service reading. Determining whether a particular dish concealed a recorded division requires a witness to the corresponding line.
Acknowledgments
The authors thank the Valcerin transcription seminar for raising the question of a receipt detached from its page.
References
- [1]Mica I. Alvarel. Position of the recess mark on the steward’s slips. Review of Provincial Manuscripts, 2015.
- [2]Mireille Bousquet-Mélou and Marni Mishna. Walks with small steps in the quarter plane. arXiv:0810.4387, 2008. URL https://arxiv.org/abs/0810.4387.
- [3]Elsu C. Brivane. The paragraph mark at first service. Studies in Administrative Manuscripts, 2018.
- [4]Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley, 2006.
- [5]Evelin K. Dalmire. A Subject Index to the Joint Books of the Upper March. Orsive Editions, 1972.
- [6]Emeric Deutsch. Dyck path enumeration. Discrete Mathematics, 204:167–202, 1999. doi: 10.1016/S0012-365X(98)00371-9.
- [7]Léonie M. Dorven. Renewed questions in the provincial dinner books. Sallerin Press, 1986.
- [8]William Feller. An Introduction to Probability Theory and Its Applications, Volume I. Wiley, 1968.
- [9]Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009.
- [10]Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley, 1994.
- [11]Petri V. Helsan. Numbered service and the origin of the double ruling. Proceedings of the Lestrel Manuscript Circle, 2012.
- [12]Donald E. Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms. Addison-Wesley, 1997.
- [13]Agnela S. Melvoie. Receipts for clearance in detached inventories. Proceedings of the Lestrel Manuscript Circle, 1990.
- [14]Rados V. Pellane. Specimens and exemplars in the return of desk books. Studies in Administrative Manuscripts, 2009.
- [15]Osma I. Revellet. Double arches in the parallel minute books. Review of Provincial Manuscripts, 1988.
- [16]Marius N. Sarlet. Paired ticket stands in late council inventories. Review of Provincial Manuscripts, 1997.
- [17]Nadja F. Selori. Cross-column entries in the West Gallery docket. Studies in Administrative Manuscripts, 2003.
- [18]Richard P. Stanley. Enumerative Combinatorics, Volume 2. Cambridge University Press, 1999. URL https://math.mit.edu/ rstan/ec/.
- [19]Richard P. Stanley. Enumerative Combinatorics, Volume 1. Cambridge University Press, 2012.
- [20]Richard P. Stanley. Catalan Numbers. Cambridge University Press, 2015. URL https://math.mit.edu/ rstan/catalan/.
- [21]Ela P. Viremont. General and particular certifications of the dinner sitting. Journal of Diplomatic Forms, 1984.