21
$\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$
6
  • $\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$ Mar 24, 2013 at 3:55
  • $\begingroup$ Oh, and what's the combinatorial meaning of the Bell determinant? $\endgroup$ Mar 24, 2013 at 3:55
  • 1
    $\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$ Mar 24, 2013 at 4:19
  • $\begingroup$ 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. $\endgroup$ Mar 24, 2013 at 4:25
  • 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$ Mar 24, 2013 at 4:52

6 Answers 6

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

$\endgroup$
3
  • $\begingroup$ Thanks for these examples! I'll let you know if I can get the technique to work. $\endgroup$ Feb 2, 2010 at 1:40
  • 3
    $\begingroup$ Any luck, Douglas? $\endgroup$ Oct 15, 2017 at 5:10
  • $\begingroup$ Recent article related to last example: arxiv.org/abs/1710.00701 $\endgroup$ Oct 16, 2017 at 12:48
7
$\begingroup$

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

$\endgroup$
0
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.

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

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

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

$\endgroup$
1
  • 2
    $\begingroup$ Does this count something which doesn't have a clear product structure? $\endgroup$ Nov 14, 2012 at 11:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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