# Partition numbers and Gaussian binomial coefficient

• 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?

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

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