Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?


share|improve this question
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
show 1 more comment

4 Answers

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

share|improve this answer
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
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
Does this count something which doesn't have a clear product structure? –  Douglas Zare Nov 14 '12 at 11:45
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.