q-Binomial coefficients calculation

Question

In the paper http://arminstraub.com/downloads/slides/2012qbinomials-illinois.pdf page 9 "D3" it is written a method of calculation of q-Binomial coefficients. For example for the $\binom{4}{2}_q$ the method suggests $$\{1, 2\} → 0, \{1, 3\} → 1, \{1, 4\} → 2, \{2, 3\} → 2, \{2, 4\} → 3, \{3, 4\} → 4$$

Where the $\{a, b\} → a-1 + b-2$. So the $\binom{4}{2}_q = 1 + q + 2q^2 + q^3 + q^4$ as the $2$ appears $2$ times and the rest of values $1$ times. But I can not understand how to calculate for example $\binom{7}{3}_q$. Could you please help with understanding this.

Answer 1

So you want $$\binom{7}{3}_q=\sum _{S\in \binom{[7]}{3}}q^{w(S)},$$ You have to list all subsets of $\{1,2,3,4,5,6,7\}$ of size $3$ which are $35$ of them. For each one, you have to sort them and do the following: Imagine $S=\{s_1,s_2,s_3\}$ then $w(S)=s_1-1+s_2-2+s_3-3=s_1+s_2+s_3-\binom{4}{2}.$

For example, for $S=\{3,5,7\}, w(S)=3+5+7-\binom{4}{2}=15-6=9.$ When you do it for all possible $S$ then the coefficient of $q^i$ is how many times you got an $i$ in the process.

Answer 2

You are perhaps confused because we are subtracting $1$ then $2$ then $3$ and so on. Instead, you can think of it like this. Take all the subsets of size $k$ from $\{1, \dots, n\}$ and take their sum. Then take the generating function for that and remove the largest power of $q$ that you can (which will be $q^{1+2+\dots+k}$).

For example, with $n = 5$ and $k = 3$ we have

$$ \begin{array}{c|c} \text{subset} & \text{sum} \\\hline 123 & 6 \\ 124 & 7 \\ 125 & 8 \\ 134 & 8 \\ 135 & 9 \\ 145 & 10 \\ 234 & 9 \\ 235 & 10 \\ 245 & 11 \\ 345 & 12 \end{array} $$

Subsets aren't ordered so $123 = 321 = 132 = 312$ etc. The sum also doesn't care about the order.

Now we take the generating function $$ \sum \left\{ q^{\operatorname{sum}(S)} : S \subseteq \{1,\dots,5\}, |S| = 3 \right\} $$

which is

$$ q^6 + q^7 + q^8 + q^8 + q^9 + q^{10} + q^9 + q^{10} + q^{11} + q^{12}. $$

This simplifies to

$$ q^6 \big( 1 + q + 2q^2 + 2q^3 + 2q^4 + q^5 + q^6 \big). $$

The quantity

$$ 1 + q + 2q^2 + 2q^3 + 2q^4 + q^5 + q^6 $$

is the q-binomial coefficient $\displaystyle \binom{5}{3}_q$.