# 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
I don't know of a direct combinatorial interpretation of the Bell number determinant, but there is a similar factorization of the matrix so that the diagonal matrix is $\text{Diag}(0!,1!, ..., n!)$. I don't recall the lower triangular and upper triangular pieces exactly, but they are in the OEIS, and proving the factorization was a simple combinatorial exercise, something involving set partitions with a marked element. –  Douglas Zare Mar 24 '13 at 4:25

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\"oder'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.C9 on page 31 (solution on page 70) 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

There are 651 sequences in the OEIS qith the word “quotient” in their descriptions, 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.

-

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