3
$\begingroup$
  • Let $a(n)$ be A000041 i.e. the number of partitions of $n$ (the partition numbers).

  • Let $T(n, k)$ be A083906. Here

$$ T(n, k) = [q^k]\sum\limits_{m=0}^{n} \binom{n}{m}_q $$

where $\binom{n}{m}_q$ denotes Gaussian binomial coefficient.

I conjecture that

$$ T(n, k) = [n > k](T(n-1, k) + a(k)) + [n \leqslant k](2T(n-1, k) - T(n-2, k) + T(n-2, k - n + 1)), \\ T(0, k) = [k = 0], T(1, k) = 2[k = 0]. $$

where square bracket denotes Iverson bracket.

I also conjecture that

$$ \sum\limits_{i = 0}^{n}T(n-i, i) = a(n+1) $$

Note that upper limit of the summation can be reduced.

Is there a way to prove it? Is there a way to get a simple closed form for $T(n,k)$ based on the given recursion?

$\endgroup$
1
  • 1
    $\begingroup$ For the part $n>k$ see the entry FORMULA given in A083906. $\endgroup$
    – Nemo
    Feb 12 at 13:23

1 Answer 1

7
$\begingroup$

Consider Rogers-Szego polynomials defined by $$ H_n(t)=\sum\limits_{m=0}^{n} \binom{n}{m}_qt^m. $$

In Andrews, "Theory of partitions", exercise 6 in chapter 3 gives three term recurrence satisfied by this polynomial

$$ H_{n}(t)=(1+t)H_{n-1}(t)-(1-q^{n-1})tH_{n-2}(t). $$

Since

$$ T(n,k)=[q^k]H_n(1), $$

one can easily work out the case $n\le k$ of the recurrence for $T(n,k)$ from here.

As to the conjecture $$ \sum\limits_{i = 0}^{n}T(n-i, i) = a(n+1), $$ it can be proved using (3.3.9) from Andrew's book $$ \frac{1}{(q;q)_{m+1}}=\sum\limits_{j=0}^{\infty} q^j\binom{m+j}{m}_q, $$ as follows: $$ \sum\limits_{i = 0}^{n}T(n-i, i) =\sum\limits_{i = 0}^{n}[q^i]\sum\limits_{m= 0}^{n-i}\binom{n-i}{m}_q=\sum\limits_{i = 0}^{n}[q^{n-i}]\sum\limits_{m= 0}^{i}\binom{i}{m}_q\\=[q^{n}]\sum\limits_{i = 0}^{n}q^i\sum\limits_{m= 0}^{i}\binom{i}{m}_q=[q^{n}]\sum\limits_{m = 0}^{n}\sum\limits_{i=m}^{n}q^i\binom{i}{m}_q=[q^{n}]\sum\limits_{m = 0}^{n}q^m\sum\limits_{i=0}^{n-m}q^i\binom{i+m}{m}_q\\=[q^{n}]\sum\limits_{m = 0}^{n}q^m\sum\limits_{i=0}^{\infty}q^i\binom{i+m}{m}_q =[q^{n}]\sum\limits_{m = 0}^{n}q^m\frac{1}{(q;q)_{m+1}}\\=[q^{n+1}]\sum\limits_{m = 0}^{n}\frac{1-(1-q^{m+1})}{(q;q)_{m+1}}=[q^{n+1}]\sum\limits_{m = 0}^{n}\left(\frac{1}{(q;q)_{m+1}}-\frac{1}{(q;q)_{m}}\right) =[q^{n+1}]\left(\frac{1}{(q;q)_{n+1}}-1\right)=a(n+1) $$

$\endgroup$

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.