20
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Community wiki? (You're seeking a list of examples, not a best one.) $\endgroup$ – Noam D. Elkies Mar 24 '13 at 3:51
  • $\begingroup$ 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? $\endgroup$ – Noam D. Elkies Mar 24 '13 at 3:55
  • $\begingroup$ Oh, and what's the combinatorial meaning of the Bell determinant? $\endgroup$ – Noam D. Elkies Mar 24 '13 at 3:55
  • $\begingroup$ 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... $\endgroup$ – Douglas Zare Mar 24 '13 at 4:19
  • 1
    $\begingroup$ 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!$. $\endgroup$ – Douglas Zare Mar 24 '13 at 4:52
20
$\begingroup$

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

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

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

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
-2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Does this count something which doesn't have a clear product structure? $\endgroup$ – Douglas Zare Nov 14 '12 at 11:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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