All Questions
Tagged with q-analogs co.combinatorics
63 questions
1
vote
1
answer
232
views
Looking for q-analog of derangement anagrams for a word
I have already known QPermutationDerangement:
It describes the distribution
$$
d_n(q)=\sum_{\sigma \in D_n} q^{\operatorname{maj}(\sigma)}
$$
Where we sum over all derangements of an $n$ element set.
...
- 175
3
votes
0
answers
80
views
Applications of q-Lagrange inversion
I was reading a text on q,t-Catalan numbers and Diagonal Harmonics by Haglund, where they mention the following $q$-analogue of Lagrange Inversion, taken from Page 53:
Let $e_n, h_n$ denote the ...
- 31
0
votes
0
answers
174
views
3D generalization of Gaussian q-binomial coefficient
It is known that the coefficient of $q^t$ in Gaussian binomial coefficient $\binom{m+n}m_q$ equals the number of permutations of the multiset $\{0^m, 1^n\}$ with $t$ inversions.
Is there a closed ...
- 34.3k
7
votes
0
answers
252
views
Hankel determinants for some convolutions of Catalan numbers
Let $c(x)=\frac{1-\sqrt{1-4x}}{2x}$ be the generating function of the Catalan numbers and let $$x^k c(x)^{2k}=(c(x)-1)^k =\sum_{n\geq0}c(k,n)x^n.$$
Consider the determinants $$D(k,n,m)= \det\left(c(k,...
- 5,622
12
votes
0
answers
631
views
$q$-analogue of the multinomial theorem?
The $q$-binomial theorem states that
$$
\prod_{k=0}^{n-1}(1+q^kt) = \sum_{k=0}^n q^{\binom k2}{n\brack k}_q t^k.
$$
This identity is a $q$-analogue of the binomial theorem
$$
(1+t)^n = \sum_{k=0}^n \...
- 5,654
6
votes
0
answers
112
views
Bijection between forests and skew SYT + Cyclic sieving
Consider the two-row skew shape $\lambda_n = (2n+1,n)/(1)$.
The number of standard Young tableaux of this shape is
$\binom{3n}{n}-\binom{3n}{n-2}$ (since one can easily biject this to the set of non-...
- 15.8k
1
vote
0
answers
150
views
Counting non-zero Gramians of Grassmanians over finite field
In case of $\mathbb{F}_{2}$, we can obtain the number of all reduced row echelon forms (so called Grassmannians) for some m$\times$n full rank matrices by the following gaussian polynomial,
$$
\binom{...
- 11
7
votes
1
answer
320
views
A curious $q$-series identity on a truncated Euler function
Recall that a $q$-Pochhammer symbol is defined as
$$
(x)_n = (x;q)_n := \prod_{l=0}^{n-1}(1-q^l x).
$$
I found the following curious $q$-series identity that seems to hold for any $n\geq 0$:
$$
(-1)^{...
- 1,430
10
votes
0
answers
389
views
Has anyone met this "$q$-character" table for $S_4$?
Is anyone aware of the following $q$-character table for the
symmetric group $S_4$?
\begin{array}{|c|c|c|c|c|c|}
\hline
\mathrm{conj}\backslash\mathrm{rep}
& 2+1+1 & 3+1 & ...
- 2,137
11
votes
3
answers
557
views
In search of a $q$-analogue of a Catalan identity
Let $C_n=\frac1{n+1}\binom{2n}n$ be the all-familiar Catalan numbers. Then, the following identity has received enough attention in the literature (for example, Lagrange Inversion: When and How):
\...
- 43.2k
3
votes
0
answers
136
views
A recursion involving binomial coefficients: looking for a q-analog
Let $a_n := \frac{1}{2n+1}\binom{3n}{n}$.
Then it is known that (one can find references in the OEIS for this.)
$$
a_n = \sum_{\substack{i,j,k \geq 0 \\ i+j+k=n-1} } a_i a_j a_k.
$$
Is there a natural ...
- 15.8k
4
votes
1
answer
168
views
Discriminants of some $q$-analogs of $(1+x)^n$
Let $[n]_q=1+q+\dots +q^{n-1}$, $ {[n]_q}! =[1]_q [2]_q \dots [n]_q$ and $\binom{n}{j}_q = \frac{[n]_q!}{[j]_q![n-j]_q!}$ be the usual $q$-notation.
Consider the polynomials $p_n(q,r,x)= \sum_{j=0}^n ...
- 5,622
6
votes
0
answers
227
views
Gaussian coefficients identity
I am having difficulty showing the equivalence between (11) and (15) of Delsarte - Association schemes and $t$-designs in regular semilattices. It is somehow an application of Möbius inversion, but I ...
3
votes
1
answer
186
views
Is there a $q$-analogue to Shapiro's convolution identity?
Let $C_n=\frac1{n+1}\binom{2n}n$ denote the Catalan numbers.
This question is motivated by the (unanswered) MO post by Alexander Burstein and my own (answered by Fedor Petrov) MO post.
Specifically, ...
- 43.2k
7
votes
1
answer
325
views
Looking for a $q$-analogue of a binomial identity
The following identity is well-known and there are a few proofs to it (see Bijective proof problems, by R P Stanley, for this and similar formulae):
$$\sum_{k=0}^n\binom{2k}k\binom{2n-2k}{n-k}=4^n \...
- 43.2k
6
votes
0
answers
214
views
Looking for a combinatorial proof for an identity involving $q$-Catalan triangles
Let $C_n=\frac1{n+1}\binom{2n}n$ be the Catalan numbers. Following my earlier post on MO, one fine colleague asked me if there is a $q$-analogue of the identity formed by the so-called Shapiro's ...
- 43.2k
7
votes
1
answer
253
views
Enumerating subspaces of $\mathbb{F}_q^n$ in terms of words and inversions
When $q$ is a prime power, then on the one hand the $q$-binomial coefficient $\binom{n}{k}_q$ equals the number of $k$-dimensional subspaces of $\mathbb{F}_q^n$, and on the other hand it is the ...
- 63.1k
5
votes
1
answer
178
views
A $q$-analogue of a characterization of polynomials by binomial coefficients
Considering the binomial coefficient $\binom{x}{m}$ as a polynomial in $x$, the span of $\binom{x}{0}, \binom{x}{1}, \ldots, \binom{x}{d}$ is exactly the polynomials of degree $\le d$. A closely ...
- 11.2k
17
votes
1
answer
886
views
Proof of certain $q$-identity for $q$-Catalan numbers
Let us use the standard notation for $q$-integers, $q$-binomials,
and the $q$-analog
$$
\operatorname{Cat}_q(n) := \frac{1}{[n+1]_q} \left[\matrix{2n \\ n}\right]_q.
$$
I want to prove that for all ...
- 15.8k
9
votes
7
answers
765
views
Important combinatorial and algebraic interpretations of the coefficients in the polynomial $[n]!_q = (1+q)(1+q+q^2) \ldots (1+q+\cdots + q^{n-1})$
What are some important combinatorial and algebraic interpretations of the coefficients in the polynomial
$$[n]!_q = (1+q)(1+q+q^2) \ldots (1+q+\cdots + q^{n-1})?$$
As motivation, I will give ...
11
votes
2
answers
589
views
$q$-analogs of total positivity
A real matrix $M$ is called totally positive if all of its minors are positive; these matrices have been extensively studied, and there are generalizations to other Lie types, for example by Lusztig.
...
- 2,753
22
votes
2
answers
742
views
A q-rious identity
Let $[x]_q=\frac{1-q^x}{1-q}$, $[n]_q!=[1]_q[2]_q\cdots[n]_q$ and ${\binom{x}{n}}_{q}=\frac{[x]_q[x-1]_q\cdots[x-n+1]_q }{[n]_q!}$.
Computer experiments suggest that
$$\det \left(q^\binom{i-j}{2}\...
- 5,622
9
votes
2
answers
509
views
Lusztig's $q$-analog of weight multiplicity with product formula
For partitions $\lambda, \mu \vdash n$, the Kostka-Foulkes polynomial $K_{\lambda,\mu}(q)$, a $q$-analog of the Kostka coefficient $K_{\lambda,\mu}$, has a combinatorial description, due to Lascoux ...
- 24.2k
8
votes
1
answer
229
views
Prominent examples of $q$-analogs without known cyclic sieving
The cyclic sieving phenomenon is nicely summarized in the following AMS Notices "What is...?" article: https://www.ams.org/notices/201402/rnoti-p169.pdf.
In that article, Reiner, Stanton, and White ...
8
votes
1
answer
298
views
Product of $q$-analogues
Background
Recall that the $q$-analogue $[n]_q\in\mathbb Z[q]$ of a natural number $n\in\mathbb N$ is defined as
$$ [n]_q := \frac{q^n -1}{q-1}$$
the idea being that formulas involving $q$ will ...
- 1,838
6
votes
0
answers
132
views
Q-analogue of an inequality
Pick integers $b\geq a \geq 0$ and $k\geq j\geq 0$.
It is not super-difficult to prove the inequality
$$
\binom{kb}{ka}^j \geq \binom{jb}{ja}^k.
$$
This is actually quite a nice inequality that was ...
- 15.8k
4
votes
0
answers
113
views
Positivity of q-analogs of central binomial coefficients?
With the usual $q-$notations
$[n]_q=1+q+\cdots+q^{n-1}=\frac{\,\,1-q^n}{1-q},$
$[n]_q!=[1]_q[2]_q\cdots[n]_q$ and
$\binom{n}k_q=\frac{[n]_q!}{[k]_q!\cdot[n-k]_q!}$
let
$$b(n,k,r,q)=\det\left(q^{r\...
- 5,622
2
votes
2
answers
236
views
$q$-factorial coefficient asymptotics
Consider the $[n]!_q = \prod\limits_{k = 1}^{n} \frac{q^k - 1}{q - 1} = \sum\limits_{k = 0}^{\binom n 2} c_k q^k$ and let $\{f_n\}_{n \in \mathbb{N}}$ be the sequence of the functions on $[0; 1]$ ...
- 123
2
votes
1
answer
257
views
Major index generating polynomial for border-strip tableaux
The Question in its original form has been answered, but there is a follow-up, see the end of the post.
A border-strip is a skew Young diagram that does not contain a $2 \times 2$-box. A border-strip ...
- 95
6
votes
0
answers
191
views
A curious $q$-identity
Let $[x]_{q}=\frac{1-q^x}{1-q}$ and $\binom{x}{n}_{q}$ denote a $q$-binomial coefficient.
Let $A_n(x,q)$ be the $n\times n $ matrix with entries $$q^\binom{i-j}{2}\binom{i+j+x}{i-j+1}_{q},$$ $0 \le i,...
- 5,622
8
votes
0
answers
253
views
q-analog of $(d/dx) \binom{x}{k}$?
It is not hard to find easy formulas for the derivative of the function $\binom{x}{k}$, for instance it is not too hard to see (for $k$ an integer) that
$\frac{d}{dx} \binom{x}{k} = \sum_{i=1}^k \...
- 131
12
votes
5
answers
836
views
A divisibility of q-binomial coefficients combinatorially
Let a and b be coprime positive integers. Then the number a+b divides the binomial coefficient ${a+b \choose a}$. I know how to prove this combinatorially - for example after choosing an ordered set ...
- 8,866
9
votes
0
answers
192
views
For $q$-analogues of a known curious identity
In 2002 I published the folllowing curious combinatorial identity:
$$(x+m+1)\sum_{i=0}^m(-1)^i\binom{x+y+i}{m-i}\binom{y+2i}i-\sum_{i=0}^m\binom{x+i}{m-i}(-4)^i=(x-m)\binom xm.$$
My original proof is ...
- 15.6k
14
votes
1
answer
801
views
Is there a lift of the q-Vandermonde identity to some geometric (motivic) identity for Grassmannians over $F_q$?
The q-Vandermonde identity reads:
$$ \binom{m + n}{k}_{\!\!q} =\sum_{j} \binom{m}{k - j}_{\!\!q} \binom{n}{j}_{\!\!q} q^{j(m-k+j)} $$
The q-binomial coefficients:
$$ \binom{ a }{ b}_{\!\!q} $$
...
- 24.9k
30
votes
1
answer
1k
views
Mysterious symmetry - in search for a bijection
I have a mysterious symmetry that I have not managed to prove.
First some definitions (see picture below)
Fix a partition that fit in a staircase shape with $n$ rows.
There are $Catalan(n)$ such ...
- 15.8k
6
votes
1
answer
689
views
Q-binomials at roots of unity
As the title says, given a general $q$-binomial $\binom{n}{k}_q$,
is there some general result regarding its value at a root of unity, $q = \exp(2\pi i r/N)$?
- 15.8k
5
votes
2
answers
635
views
Some curious Hankel determinants
Let $f(n,q)=\prod_{j=1}^na(q^j)$ for a polynomial $a(q)$ and let $d(n)=\det(f(i+j,q))_{i,j=0}^n$ be its Hankel determinant.
Computer experiments suggest that
$$\lim_{q\to1}\frac{d(n)}{(q-1)^\binom{n+...
- 5,622
12
votes
1
answer
267
views
Total positivity of $q$-Pascal matrix?
A matrix of real numbers is called totally positive if all its minors are non-negative. A well-known example is the Pascal matrix $(\binom{i}{j})$.
Is it true that the minors of the $q$-Pascal matrix ...
- 5,622
12
votes
3
answers
1k
views
A "quantum" identity: in search of a proof -Part II
As usual, denote $[n]_q=1+q+\cdots+q^{n-1}=\frac{\,\,1-q^n}{1-q}$ and $[n]_q!=[1]_q[2]_q\cdots[n]_q$. Furthermore, we write
$$\binom{n}k_q=\frac{[n]_q!}{[k]_q!\cdot[n-k]_q!}.$$
As a follow up on this ...
- 43.2k
11
votes
2
answers
604
views
Does $q$-Catalan number count subspaces?
Consider the $n$-element subsets $\{a_1<a_2<\cdots <a_n\}$ of $\{1,\ldots ,2n\}$ satisfying $a_i\geq 2i$ for all $i=1,\ldots ,n$. The number of such subsets is given by $${2n\choose n}-{2n\...
- 1,305
3
votes
1
answer
253
views
What is the value of this sum involving q-binomials?
Let $n\ge 2r$ be positive integers.
Is there a closed form for following finite summation involving in q-binomial coefficients
$$\sum_{s=0}^r(-1)^sq^{\frac{s(s+1)}{2}}{n-2r+s\brack n-2r}_q{n\brack r-...
- 1,093
19
votes
1
answer
511
views
"quantum" symmetric plane partitions beget alternating sign matrices?
The "quantum" version qTSPP of the number of totally symmetric plane partitions, contained in the cube $[0,n]^3$, is enumerated by
$$f_n(q):=\prod_{j=1}^n\prod_{k=1}^j\prod_{\ell=1}^k\frac{1-...
- 43.2k
4
votes
0
answers
126
views
A $q-$binomial identity related to $q-$Narayana polynomials of type B
Denote by $ {n\brack {k}}$ a $q-$binomial coefficient.
Let ${D_{n,k}}(t,q) = \sum\limits_{j = 0}^{n - k} {{q^{{j^2} + kj}}}{n\brack {j}}{n\brack {k+j}}t^j $
and
${R_n}(x,t,q) = \sum\limits_{k = 0}...
- 5,622
11
votes
3
answers
726
views
Is this a q-count of Alternating Sign Matrices?
The number of Alternating Sign Matrices of size $n$ is well known to be
$\prod_{k=0}^{n-1}\frac{(3k+1)!}{(n+k)!}$. Is it known whether the naive q-analog expression
$$\prod_{k=0}^{n-1}\frac{[3k+1]_q!}{...
- 85.6k
8
votes
1
answer
553
views
q-analog of a combinatorial identity involving binomial coefficients
Using, e.g., properties of iterated finite differences it is easy to show that for any pair of integers $n$ and $m$ with $n>\!>m$ one has the identity
$$
\sum_{k=0}^m(-1)^{k-m} {n-k\choose m}{m\...
- 6,777
13
votes
1
answer
982
views
Generating function for certain partitions (with a restriction on the Durfee square)
First of all my apologies if this question is well known or obvious: this is not in my area of research.
Let $T(x)=\sum_{n=0}^\infty t_nx^n$, where $t_n$ is the number of partitions $\lambda$ of $n$ ...
- 934
4
votes
2
answers
292
views
How to prove that $\sum_{i=0}^n\frac{(a;q)_i}{(q;q)_i}\frac{(b;q)_{n-i}}{(q;q)_{n-i}}a^{n-i}=\frac{(ab;q)_n}{(q;q)_n}$?
By Cauchy identity, $${}_1\phi_0(a;—;q,z)=\sum_{n\geq0}\frac{(a;q)_n}{(q;q)_n}z^n=\frac{(az;q)_{\infty}}{(z;q)_\infty},\quad|z|<1,|q|<1,$$
we can obtain the $q-$analogue of $(1-z)^{-a}(1-z)^{-b}=...
- 139
8
votes
1
answer
497
views
q-Integer-valued polynomials
For $n \in \mathbb{Z}_{\geq 0}$, let $[n]_q := (1-q^n)/(1-q) = (1+q+...+q^{n-1})$ as is customary, with $[0]_q=0$.
Let $R$ be the subring of $\mathbb{Q}(q)[x]$ consisting of all $f$ such that $f([n]...
- 24.2k
13
votes
2
answers
1k
views
Is there a $q$-L'Hospital's Rule?
Let $\binom{n}{j}_q$ be a $q$-binomial coefficient and $(x;q)_n = (1-x)(1-qx)\cdots(1-q^{n-1}x).$
Consider the sum $$f(n,m,r,k)= \sum\limits_{j = 0}^{2n} {( - 1)}^{ j}q^{mj^2+rj}
\binom{2n}{j}_{q^k}$...
- 5,622
8
votes
1
answer
1k
views
Counting subspaces
We are given the finite vector space $V = V(n,p) = \mathbb{F}_p^n$ and two fixed subspaces $W_1, W_2 \subseteq V$ of dimensions $m_1$, $m_2$ respectively. Suppose
that the dimension of $W_1 \cap W_2$ ...
- 347