Question

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.

Answer 1

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

Answer 2

Let a_n be the largest power of 2 that divides R_n, the number of reduced Latin squares of order n. We know the value of a_n for n≤11 (see this for example). The sequence begins (1,1,1,2²,2³,2⁶,2¹⁰,2¹⁷,2²¹,2²⁸,2³⁵,...) for n≥1.

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

Answer 3

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