# Combinatorial sequences whose ratios $a_{n+1}/a_{n}$ are integers

I have a proof technique in search of examples. I'm looking for combinatorially meaningful sequences $\{a_n\}$ so that $a_{n+1}/a_n$ is known or conjectured to be an integer, such that there is a relation between the $n$th case and $n+1$st, but not an obvious $a_{n+1}/a_n\to 1$ map. This means $a_n$ is the $n$th partial product of an infinite sequence of integers, but there isn't an obvious product structure.

• The prototype was an enumeration of domino tilings of an Aztec diamond of order $n$, $a_n = 2^{n(n+1)/2}$, so $a_{n+1}/a_n = 2^{n+1}$. (There is a nice $2^{n+1}$ to 1 map unrelated to my technique, but it isn't obvious.)

• Another application was a proof that $\det \{B_{i+j}\}_{i,j=0}^n = \prod_{i=1}^n i!$ where $B_n$ is the $n$th Bell number, equation 25 in the linked page.

• The counts of alternating sign matrices 1, 2, 7, 42, ... are not an example, since $ASM(n+1)/ASM(n) = \frac{ (3n+1)!n!}{2n! (2n+1)!}$ which is not always an integer, e.g, 7/2 is not.

What are some other interesting combinatorial families whose ratios $a_{n+1}/a_n$ are known or (preferably) conjectured to be integers?

Thanks.

• Community wiki? (You're seeking a list of examples, not a best one.) – Noam D. Elkies Mar 24 '13 at 3:51
• Are you seeking counterexamples to the idea that $a_n | a_{n+1}$ for all $n$ ought to imply an $(a_{n+1}/a_n)$-to-1, or challenges where no such map is known but there may be a nice construction? – Noam D. Elkies Mar 24 '13 at 3:55
• Oh, and what's the combinatorial meaning of the Bell determinant? – Noam D. Elkies Mar 24 '13 at 3:55
• You may be right that this should be community wiki. I'm looking for possible families of combinatorial objects for which one might not be able to construct $a_{n+1}/a_n:1$ maps easily, but for which one might still be able to prove such a ratio. For domino tilings of Aztec diamonds, the proof is by overlaying a pattern of dominoes to make a domino tiling correspond to a family of nonintersecting lattice paths, enumerated using the Gessel-Viennot-Lindstrom determinant, then factoring the matrix as $LDU$, where $D$ turns out to be $\text{Diag}(2,4,8,...)$. There are $2^{n+1}:1$ maps known... – Douglas Zare Mar 24 '13 at 4:19
• Now I remember the factorization. Set partitions of a set of size $i+j$ are in bijection with a disjoint union over $t=0,1,2,...$ of set partitions of the first $i$ elements with $t$ parts marked, set partitions of the last $j$ elements with $t$ parts marked, and the $t!$ bijections between the marked parts to be glued together. That proves the $LDL^T$ decomposition. The number of partitions of a set of size $i$ with $i$ parts marked is $1$, so the lower diagonal matrix $L$ has $1$s on the diagonal and determinant $1$. That proves that the Bell number determinant is $\prod_{t=0}^n t!$. – Douglas Zare Mar 24 '13 at 4:52

The number of pairs $(P,Q)$ of standard Young tableaux of the same shape and with $n$ squares is $n!$.

The number of oscillating tableaux of length $2n$ and empty shape is $1\cdot 3\cdot 5\cdots (2n-1)$.

The number of leaf-labeled complete (unordered) binary trees with $n$ leaves is $1\cdot 3\cdot 5\cdots (2n-3)$ (Schröder's third problem).

The number of compact-rooted directed animals of size $n$ is $3^n$. See MathSciNet MR0956559 (90c:05009).

Let $f(n)$ be the number of $n\times n$ matrices $M=(m_{ij})$ of nonnegative integers with row and column sum vector $(1,3,6,\dots,{n+1\choose 2})$ such that $m_{ij}=0$ if $j>i+1$. Then $f(n)=C_1C_2\cdots C_n$, where $C_i$ is a Catalan number. No combinatorial proof of this result is known. See Exercise 6.C12 on page 38 (solution on page 84) of http://math.mit.edu/~rstan/ec/catadd.pdf

• Thanks for these examples! I'll let you know if I can get the technique to work. – Douglas Zare Feb 2 '10 at 1:40
• Any luck, Douglas? – Gerry Myerson Oct 15 '17 at 5:10
• Recent article related to last example: arxiv.org/abs/1710.00701 – Sam Hopkins Oct 16 '17 at 12:48

There are 345 sequences in the OEIS qith the word “quotient” in their names, does that help?

Let an be the largest power of 2 that divides Rn, the number of reduced Latin squares of order n. We know the value of an for n≤11 (see this for example). The sequence begins (1,1,1,22,23,26,210,217,221,228,235,...) for n≥1.

I wouldn't conjecture that an+1/an is always an integer (although, it seems plausible). However, we do know that an+1/an is an integer for 1≤n≤10.

The number of $n$-block domino towers is $3^{n-1}$. The simplest bijective proof uses the fact that for the Motzkin generating function $M=M(z)$ we have $$\frac{M}{(1-zM)^2}=\frac{1}{1-3z}.$$ See pages 19-21 of this paper (and the references there):

http://math.sfsu.edu/federico/Clase/AC/algmethods.pdf

(This is Chapter 1 in the Handbook of Enumerative Combinatorics.)

Likewise, the number of pairs of grand Dyck paths of combined semilength $n$ is $4^n$.

The number of acyclic orientations on the complete graph on $n$ vertices is $n!$, and the number of acyclic orientation on a unit-interval graph on $n$ vertices is given by a product with $n$ factors, so you can easily construct many sequences from this.

If you take a(n)=2^F(n);a(n+1)=2^F(n+1) , where F(n+1) ,F(n) are Fibonacci numbers and F(n+1)=F(n)+F(n-1) , then a(n+1)/a(n)=2^[F(n+1)-F(n)]=2^F(n-1) Fibonacci series S=[n_F(n)]=(0_0),(1_1),(2_1),(3_2),(4_3),(5_5),(6_8),(7_13),(8_21),(9_34)... Product {a(n+1)/a(n)}{a(n)/a(n-1)}...{a(3)/a(2)}{a(2)/a(1)}=a(n+1)/a(1) =2^{F(n-1)+F(n-2)+...+F(1)+F(0)} =2^{F(n+1)-1}=2^F(n+1)/2 Example=> (2^21/2^13)(2^13/2^8)(2^8/2^5)(2^5/2^3)(2^3/2^2)(2^2/2^1)(2^1/2^1)=2^21/2 =(2^8)(2^5)(2^3)(2^2)(2^1)(2^1)=2^(8+5+3+2+1+1)=2^20

I hope this example suits to your needs.

• Does this count something which doesn't have a clear product structure? – Douglas Zare Nov 14 '12 at 11:45