Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

We are trying to estimate the cardinality $K(n,p)$ of so-called Kuratowski monoid with $p$ positive and $n$ negative linearly ordered idempotent generators. In particular, we are interesting in the case $n=p$.

This notion arose in an intersection of general topology and abstract algebra. We calculated the exact value of

$$K(n,p)=\sum_{i=0}^n\sum_{j=0}^p \binom {i+j}i\binom{i+j}j.$$

We try to simplify this formula, but we stuck. The problem is that many different binomial sums are known, but I cannot remember among them sums of binomial “polynomials” of degree greater than 1, containing the summation index above.

If the summation diapason was a triangle $\{i,j\ge 0:i+j\le 2n\}$ instead of a rectangle $[0;n]\times [0;p]$, a sum should be simplified as follows:

$$\sum_{i,j=0}^{i+j\le 2n} \binom {i+j}i^2=\sum_{k=0}^{2n}\sum_{i,j=0}^{i+j=k}\binom ki^2=\sum_{k=0}^{2n}\binom {2k}k.$$

A rough asymptotic of $K(n,n)$ should be $\log K(n,n)\sim n\log n+O(\log n)$, which follows form the bounds:

$$\binom {2n}n^2\le K(n,n)= \sum_{i=0}^n\sum_{j=0}^p \binom {i+j}i\binom{i+j}j\le 2(n+1)^2\binom {2n}n^2.$$

Since we are topologists, it is complicated for us to obtain a highly estimated asymptotic, so we decided to ask specialists about that.

share|cite|improve this question
Just to be clear. You want the asymptotic of $$\sum_{i=0}^n\sum_{j=0}^n \binom {i+j}i\binom{i+j}j.$$ Right? – user17762 Apr 24 '13 at 23:52
The bounds you've obtained already seem pretty good. You need tighter bounds? – Qiaochu Yuan Apr 24 '13 at 23:56
@user17762 Yes, you are right. We are interested in asymptotics or simpler formulas for this sum. Also we consider the respective sum for $K(n,p)=\sum_{i=0}^n \sum_{i=0}^p \binom {i+j}i\binom{i+j}j $. – Alex Ravsky Apr 25 '13 at 3:48
@QiaochuYuan I prefer a word “prefer” instead of “need”, :-) because our main results (the derivation of $K(n,p)$) are already publishable. But we decided that it would be nice to simplify its form (when I devised how to simplify the initial ($\sum \sum \sum \sum \sum \sum\dots $ to the present form, I was proposed to be a coauthor. :-) ) – Alex Ravsky Apr 25 '13 at 5:29
@vadim123: Thank you for the interest to our investigation. My experience suggests a pessimistic attitude for the existence of a simple formula for $K(n,n)$. Moreover, the sequence $\{K(n,n)\}$ is not even in the On-Line Encyclopedia of Integer Sequences. – Alex Ravsky Apr 28 '13 at 15:55

Theorem. $\lim_{n\to\infty} K(n,n)/\binom {2n}n^2=16/9$.

This theorem is a corollary of the following results.

For every integers $0\le a,b\le n$ put $c_{a,b}(n)=\binom {2n-a-b}{n-a}/\binom {2n}n$.

Lemma 1. For every integers $a,b\ge 0$ there exists a limit $\lim_{n\to\infty} c_{a,b}(n)=2^{-(a+b)}$.

Proof. It follows from the equality $c_{a,b}(n)=\frac {n(n-1)\cdots (n-a+1) n(n-1)\cdots (n-b+1)}{2n(2n-1)\cdots (2n-a-b+1)}.\square$

For every $n\ge 0$ put $k(n)=K(n,n)/\binom {2n}n^2$. Clearly that $k(n)= \sum_{a,b=0}^n c_{a,b}(n)^2$. The computer calculations suggest that the sequence $\{k(n):n\ge 3\}$ is increasing.

Proposition 1. For each $n$ we have $k(n)\le 16/9$.

Proof. $k(0)=1$, $k(1)=k(2)=7/4<16/9$, $k(3)=697/400<7/4$, and $k(4)=8549/4900<16/9$. Suppose now that $n\ge 5$ and $k(n-1)\le 16/9$.

We shall use the following two lemmas.

Lemma 2. For each $a\le n$ we have $c_{a,0}(n)\le 2^{-a}$.

Proof It follows from the equality $c_{a,0}(n)=\frac {n(n-1)\cdots (n-a+1)}{2n(2n-1)\cdots (2n-a+1)}$ and the inequality $(2n-l)\ge 2(n-l)$.$\square$

Lemma 3. $(16/9)c_{1,1}^2+2c_{1,0}^2+2c_{2,0}^2+2c_{3,0}^2\le (16/9)\cdot(1/16)+2(1/4)+2(1/16)+2(1/64)$.

Proof. $c_{1,1}=\frac n{2(2n-1)}$, $c_{1,0}=1/2$, $c_{2,0}=\frac {n-1}{2(2n-1)}$, and $c_{3,0}=\frac {n-2}{4(2n-1)}$. The routine transformations of the inequality yield $211\le 52n$, which holds for $n\ge 5$.$\square$

Now we have that $k(n,n)\le k(n-1)c_{1,1}^2+1+2\sum_{a=1}^{n-1} c_{a,0}^2\le (16/9)\cdot(1/16)+1+\sum_{a=1}^{n-1}2^{-2a}\le 16/9$.$\square$

Proposition 2 There exists a limit $\lim_{n\to\infty} k(n)=16/9$.

Proof. Lemma 1 implies that $\underline\lim_{n\to\infty} k(n)\ge \sum_{a,b=0}^\infty 2^{-2(a+b)}=\sum_{i=0}^\infty (i+1)4^{-i}=16/9$. By Proposition 1, $\lim_{n\to\infty} k(n)=16/9$.$\square$

share|cite|improve this answer
(+1) Brilliant! – Norbert May 4 '13 at 16:54

The argument you've written down shows that

$$K(n, n) \le \sum_{k=0}^{2n} {2k \choose k}.$$

Stirling's formula gives the asymptotic

$${2k \choose k} \sim \frac{4^k}{\sqrt{\pi k}}$$

so this sum behaves approximately like a geometric series, and we expect that

$$\sum_{k=0}^{2n} {2k \choose k} \sim \frac{4}{3} \left( \frac{4^{2n}}{ \sqrt{2 \pi n} } \right).$$

We also have the (easily improved) lower bound

$${2n \choose n}^2 \le K(n, n)$$

and Stirling's formula here gives

$${2n \choose n}^2 \sim \frac{4^{2n}}{\pi n}$$

so we get upper and lower bounds that are within a multiplicative factor of $O(\sqrt{n})$ of each other this way. You can tighten the lower bound using the refined entropy formula.

share|cite|improve this answer
Thank for your answer. I’ will study the page which your linked and try to apply its ideas to our problem. – Alex Ravsky Apr 25 '13 at 5:30
Asking my question, I tried to avoid long calculations, like evaluating the bounds for tails of “like”-geometric series or obtained from Refined entropy formula or similar limit theorems. I hoped that such approximations are already known, that there is a formula estimating already a sum (but some of the summands seems to be rapidly increasing with all the consequences of this fact). This is why I not tried to refine my initial rough bounds. – Alex Ravsky Apr 25 '13 at 5:30
Concerning the refinement of a lower bound. I remark that now it is not clear for me how tight is the upper bound. When we derive the upper bound $\sum_{k=0}^{2n}\binom {2k}k,$ we add to the square domain of the summations two triangles with big summands. We may try to obtain a tighter upper bound from the following idea: – Alex Ravsky Apr 25 '13 at 5:31
$$K(n,n)=\sum_{i=0}^n\sum_{j=0}^p \binom {i+j}i\binom{i+j}j \le$$ $$\sum_{k=0}^{n}\sum_{i,j=0}^{i+j=k}\binom ki^2+\sum_{k=n+1}^{2n}\binom k{\lfloor k/2\rfloor}^2(2n+1-k)\sim$$ $$\frac 43\frac {4^n}{\sqrt{\pi n}}+\sum_{k=n+1}^{2n} \frac {2^{2k+1}}{\pi k}(2n+1-k),$$ and the second summand is like a geometric series too. – Alex Ravsky Apr 25 '13 at 12:50

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.