\(q\)-Analogues#

sage.combinat.q_analogues.gaussian_binomial(n, k, q=None, algorithm='auto')[source]#

This is an alias of q_binomial().

See q_binomial() for the full documentation.

EXAMPLES:

sage: gaussian_binomial(4,2)
q^4 + q^3 + 2*q^2 + q + 1

>>> from sage.all import *
>>> gaussian_binomial(Integer(4),Integer(2))
q^4 + q^3 + 2*q^2 + q + 1
sage.combinat.q_analogues.gaussian_multinomial(seq, q=None, binomial_algorithm='auto')[source]#

Return the \(q\)-multinomial coefficient.

This is also known as the Gaussian multinomial coefficient, and is defined by

\[\binom{n}{k_1, k_2, \ldots, k_m}_q = \frac{[n]_q!} {[k_1]_q! [k_2]_q! \cdots [k_m]_q!}\]

where \(n = k_1 + k_2 + \cdots + k_m\).

If \(q\) is unspecified, then the variable is the generator \(q\) for a univariate polynomial ring over the integers.

INPUT:

  • seq – an iterable of the values \(k_1\) to \(k_m\) defined above

  • q – (default: None) the variable \(q\); if None, then use a default variable in \(\ZZ[q]\)

  • binomial_algorithm – (default: 'auto') the algorithm to use in q_binomial(); see possible values there

ALGORITHM:

We use the equivalent formula

\[\binom{k_1 + \cdots + k_m}{k_1, \ldots, k_m}_q = \prod_{i=1}^m \binom{\sum_{j=1}^i k_j}{k_i}_q.\]

EXAMPLES:

sage: from sage.combinat.q_analogues import q_multinomial
sage: q_multinomial([1,2,1])
q^5 + 2*q^4 + 3*q^3 + 3*q^2 + 2*q + 1
sage: q_multinomial([1,2,1], q=1) == multinomial([1,2,1])
True
sage: q_multinomial((3,2)) == q_binomial(5,3)
True
sage: q_multinomial([])
1

>>> from sage.all import *
>>> from sage.combinat.q_analogues import q_multinomial
>>> q_multinomial([Integer(1),Integer(2),Integer(1)])
q^5 + 2*q^4 + 3*q^3 + 3*q^2 + 2*q + 1
>>> q_multinomial([Integer(1),Integer(2),Integer(1)], q=Integer(1)) == multinomial([Integer(1),Integer(2),Integer(1)])
True
>>> q_multinomial((Integer(3),Integer(2))) == q_binomial(Integer(5),Integer(3))
True
>>> q_multinomial([])
1
sage.combinat.q_analogues.number_of_irreducible_polynomials(n, q=None, m=1)[source]#

Return the number of monic irreducible polynomials of degree n in m variables over the finite field with q elements.

If q is not given, the result is returned as an integer-valued polynomial in \(\QQ[q]\).

INPUT:

  • n – positive integer

  • q – None (default) or a prime power

  • m – positive integer (default \(1\))

OUTPUT: integer or integer-valued polynomial over \(\QQ\)

EXAMPLES:

sage: number_of_irreducible_polynomials(8, q=2)
30
sage: number_of_irreducible_polynomials(9, q=9)
43046640
sage: number_of_irreducible_polynomials(5, q=11, m=3)
2079650567184059145647246367401741345157369643207055703168

>>> from sage.all import *
>>> number_of_irreducible_polynomials(Integer(8), q=Integer(2))
30
>>> number_of_irreducible_polynomials(Integer(9), q=Integer(9))
43046640
>>> number_of_irreducible_polynomials(Integer(5), q=Integer(11), m=Integer(3))
2079650567184059145647246367401741345157369643207055703168

sage: poly = number_of_irreducible_polynomials(12); poly
1/12*q^12 - 1/12*q^6 - 1/12*q^4 + 1/12*q^2
sage: poly(5) == number_of_irreducible_polynomials(12, q=5)
True
sage: poly = number_of_irreducible_polynomials(5, m=3); poly
q^55 + q^54 + q^53 + q^52 + q^51 + q^50 + ... + 1/5*q^5 - 1/5*q^3 - 1/5*q^2 - 1/5*q
sage: poly(11) == number_of_irreducible_polynomials(5, q=11, m=3)
True

>>> from sage.all import *
>>> poly = number_of_irreducible_polynomials(Integer(12)); poly
1/12*q^12 - 1/12*q^6 - 1/12*q^4 + 1/12*q^2
>>> poly(Integer(5)) == number_of_irreducible_polynomials(Integer(12), q=Integer(5))
True
>>> poly = number_of_irreducible_polynomials(Integer(5), m=Integer(3)); poly
q^55 + q^54 + q^53 + q^52 + q^51 + q^50 + ... + 1/5*q^5 - 1/5*q^3 - 1/5*q^2 - 1/5*q
>>> poly(Integer(11)) == number_of_irreducible_polynomials(Integer(5), q=Integer(11), m=Integer(3))
True

This function is much faster than enumerating the polynomials:

sage: num = number_of_irreducible_polynomials(99, q=101)
sage: num.bit_length()
653

>>> from sage.all import *
>>> num = number_of_irreducible_polynomials(Integer(99), q=Integer(101))
>>> num.bit_length()
653

ALGORITHM:

In the univariate case, classical formula \(\frac1n \sum_{d\mid n} \mu(n/d) q^d\) using the Möbius function \(\mu\); see moebius().

In the multivariate case, formula from [Bodin2007], independently [Alekseyev2006].

sage.combinat.q_analogues.q_binomial(n, k, q=None, algorithm='auto')[source]#

Return the \(q\)-binomial coefficient.

This is also known as the Gaussian binomial coefficient, and is defined by

\[\binom{n}{k}_q = \frac{(1-q^n)(1-q^{n-1}) \cdots (1-q^{n-k+1})} {(1-q)(1-q^2)\cdots (1-q^k)}.\]

See Wikipedia article Gaussian_binomial_coefficient.

If \(q\) is unspecified, then the variable is the generator \(q\) for a univariate polynomial ring over the integers.

INPUT:

  • n, k – the values \(n\) and \(k\) defined above

  • q – (default: None) the variable \(q\); if None, then use a default variable in \(\ZZ[q]\)

  • algorithm – (default: 'auto') the algorithm to use and can be one of the following:

    • 'auto' – automatically choose the algorithm; see the algorithm section below

    • 'naive' – use the naive algorithm

    • 'cyclotomic' – use cyclotomic algorithm

ALGORITHM:

The naive algorithm uses the product formula. The cyclotomic algorithm uses a product of cyclotomic polynomials (cf. [CH2006]).

When the algorithm is set to 'auto', we choose according to the following rules:

  • If q is a polynomial:

    When n is small or k is small with respect to n, one uses the naive algorithm. When both n and k are big, one uses the cyclotomic algorithm.

  • If q is in the symbolic ring (or a symbolic subring), one uses the cyclotomic algorithm.

  • Otherwise one uses the naive algorithm, unless q is a root of unity, then one uses the cyclotomic algorithm.

EXAMPLES:

By default, the variable is the generator of \(\ZZ[q]\):

sage: from sage.combinat.q_analogues import q_binomial
sage: g = q_binomial(5,1) ; g
q^4 + q^3 + q^2 + q + 1
sage: g.parent()
Univariate Polynomial Ring in q over Integer Ring

>>> from sage.all import *
>>> from sage.combinat.q_analogues import q_binomial
>>> g = q_binomial(Integer(5),Integer(1)) ; g
q^4 + q^3 + q^2 + q + 1
>>> g.parent()
Univariate Polynomial Ring in q over Integer Ring

For \(n \geq 0\), the \(q\)-binomial coefficient vanishes unless \(0 \leq k \leq n\):

sage: q_binomial(4,5)
0
sage: q_binomial(5,-1)
0

>>> from sage.all import *
>>> q_binomial(Integer(4),Integer(5))
0
>>> q_binomial(Integer(5),-Integer(1))
0

For \(k \geq 0\), the \(q\)-binomial coefficient is extended as a polynomial in \(n\):

sage: q_binomial(-4,1)
-q^-4 - q^-3 - q^-2 - q^-1
sage: q_binomial(-2,3)
-q^-9 - q^-8 - q^-7 - q^-6

>>> from sage.all import *
>>> q_binomial(-Integer(4),Integer(1))
-q^-4 - q^-3 - q^-2 - q^-1
>>> q_binomial(-Integer(2),Integer(3))
-q^-9 - q^-8 - q^-7 - q^-6

Other variables can be used, given as third parameter:

sage: p = ZZ['p'].gen()
sage: q_binomial(4,2,p)
p^4 + p^3 + 2*p^2 + p + 1

>>> from sage.all import *
>>> p = ZZ['p'].gen()
>>> q_binomial(Integer(4),Integer(2),p)
p^4 + p^3 + 2*p^2 + p + 1

The third parameter can also be arbitrary values:

sage: q_binomial(5,1,2) == g.subs(q=2)
True
sage: q_binomial(5,1,1)
5
sage: q_binomial(4,2,-1)
2
sage: q_binomial(4,2,3.14)
152.030056160000
sage: R = GF((5, 2), 't')
sage: t = R.gen(0)
sage: q_binomial(6, 3, t)
2*t + 3

>>> from sage.all import *
>>> q_binomial(Integer(5),Integer(1),Integer(2)) == g.subs(q=Integer(2))
True
>>> q_binomial(Integer(5),Integer(1),Integer(1))
5
>>> q_binomial(Integer(4),Integer(2),-Integer(1))
2
>>> q_binomial(Integer(4),Integer(2),RealNumber('3.14'))
152.030056160000
>>> R = GF((Integer(5), Integer(2)), 't')
>>> t = R.gen(Integer(0))
>>> q_binomial(Integer(6), Integer(3), t)
2*t + 3

We can also do this for more complicated objects such as matrices or symmetric functions:

sage: q_binomial(4,2,matrix([[2,1],[-1,3]]))
[ -6  84]
[-84  78]
sage: Sym = SymmetricFunctions(QQ)
sage: s = Sym.schur()
sage: q_binomial(4,1, s[2]+s[1])
s[] + s[1] + s[1, 1] + s[1, 1, 1] + 2*s[2] + 4*s[2, 1] + 3*s[2, 1, 1]
 + 4*s[2, 2] + 3*s[2, 2, 1] + s[2, 2, 2] + 3*s[3] + 7*s[3, 1] + 3*s[3, 1, 1]
 + 6*s[3, 2] + 2*s[3, 2, 1] + s[3, 3] + 4*s[4] + 6*s[4, 1] + s[4, 1, 1]
 + 3*s[4, 2] + 3*s[5] + 2*s[5, 1] + s[6]

>>> from sage.all import *
>>> q_binomial(Integer(4),Integer(2),matrix([[Integer(2),Integer(1)],[-Integer(1),Integer(3)]]))
[ -6  84]
[-84  78]
>>> Sym = SymmetricFunctions(QQ)
>>> s = Sym.schur()
>>> q_binomial(Integer(4),Integer(1), s[Integer(2)]+s[Integer(1)])
s[] + s[1] + s[1, 1] + s[1, 1, 1] + 2*s[2] + 4*s[2, 1] + 3*s[2, 1, 1]
 + 4*s[2, 2] + 3*s[2, 2, 1] + s[2, 2, 2] + 3*s[3] + 7*s[3, 1] + 3*s[3, 1, 1]
 + 6*s[3, 2] + 2*s[3, 2, 1] + s[3, 3] + 4*s[4] + 6*s[4, 1] + s[4, 1, 1]
 + 3*s[4, 2] + 3*s[5] + 2*s[5, 1] + s[6]

REFERENCES:

[CH2006]

William Y.C. Chen and Qing-Hu Hou, Factors of the Gaussian coefficients, Discrete Mathematics 306 (2006), 1446-1449. doi:10.1016/j.disc.2006.03.031

AUTHORS:

  • Frédéric Chapoton, David Joyner and William Stein

sage.combinat.q_analogues.q_catalan_number(n, q=None, m=1)[source]#

Return the \(q\)-Catalan number of index \(n\).

INPUT:

  • q – optional variable

  • m – (optional integer) to get instead the m-Fuss-Catalan numbers

If \(q\) is unspecified, then it defaults to using the generator \(q\) for a univariate polynomial ring over the integers.

There are several \(q\)-Catalan numbers. This procedure returns the one which can be written using the \(q\)-binomial coefficients.

EXAMPLES:

sage: from sage.combinat.q_analogues import q_catalan_number
sage: q_catalan_number(4)
q^12 + q^10 + q^9 + 2*q^8 + q^7 + 2*q^6 + q^5 + 2*q^4 + q^3 + q^2 + 1

sage: p = ZZ['p'].0
sage: q_catalan_number(4, p)
p^12 + p^10 + p^9 + 2*p^8 + p^7 + 2*p^6 + p^5 + 2*p^4 + p^3 + p^2 + 1

sage: q_catalan_number(3, m=2)
q^12 + q^10 + q^9 + q^8 + q^7 + 2*q^6 + q^5 + q^4 + q^3 + q^2 + 1

>>> from sage.all import *
>>> from sage.combinat.q_analogues import q_catalan_number
>>> q_catalan_number(Integer(4))
q^12 + q^10 + q^9 + 2*q^8 + q^7 + 2*q^6 + q^5 + 2*q^4 + q^3 + q^2 + 1

>>> p = ZZ['p'].gen(0)
>>> q_catalan_number(Integer(4), p)
p^12 + p^10 + p^9 + 2*p^8 + p^7 + 2*p^6 + p^5 + 2*p^4 + p^3 + p^2 + 1

>>> q_catalan_number(Integer(3), m=Integer(2))
q^12 + q^10 + q^9 + q^8 + q^7 + 2*q^6 + q^5 + q^4 + q^3 + q^2 + 1
sage.combinat.q_analogues.q_factorial(n, q=None)[source]#

Return the \(q\)-analogue of the factorial \(n!\).

This is the product

\[[1]_q [2]_q \cdots [n]_q = 1 \cdot (1+q) \cdot (1+q+q^2) \cdots (1+q+q^2+\cdots+q^{n-1}) .\]

If \(q\) is unspecified, then this function defaults to using the generator \(q\) for a univariate polynomial ring over the integers.

EXAMPLES:

sage: from sage.combinat.q_analogues import q_factorial
sage: q_factorial(3)
q^3 + 2*q^2 + 2*q + 1
sage: p = ZZ['p'].0
sage: q_factorial(3, p)
p^3 + 2*p^2 + 2*p + 1

>>> from sage.all import *
>>> from sage.combinat.q_analogues import q_factorial
>>> q_factorial(Integer(3))
q^3 + 2*q^2 + 2*q + 1
>>> p = ZZ['p'].gen(0)
>>> q_factorial(Integer(3), p)
p^3 + 2*p^2 + 2*p + 1

The \(q\)-analogue of \(n!\) is only defined for \(n\) a non-negative integer (Issue #11411):

sage: q_factorial(-2)
Traceback (most recent call last):
...
ValueError: argument (-2) must be a nonnegative integer

>>> from sage.all import *
>>> q_factorial(-Integer(2))
Traceback (most recent call last):
...
ValueError: argument (-2) must be a nonnegative integer
sage.combinat.q_analogues.q_int(n, q=None)[source]#

Return the \(q\)-analogue of the integer \(n\).

The \(q\)-analogue of the integer \(n\) is given by

\[\begin{split}[n]_q = \begin{cases} 1 + q + \cdots + q^{n-1}, & \text{if } n \geq 0, \\ -q^{-n} [-n]_q, & \text{if } n \leq 0. \end{cases}\end{split}\]

Consequently, if \(q = 1\) then \([n]_1 = n\) and if \(q \neq 1\) then \([n]_q = (q^n-1)/(q-1)\).

If the argument \(q\) is not specified then it defaults to the generator \(q\) of the univariate polynomial ring over the integers.

EXAMPLES:

sage: from sage.combinat.q_analogues import q_int
sage: q_int(3)
q^2 + q + 1
sage: q_int(-3)
-q^-3 - q^-2 - q^-1
sage: p = ZZ['p'].0
sage: q_int(3,p)
p^2 + p + 1
sage: q_int(3/2)
Traceback (most recent call last):
...
ValueError: 3/2 must be an integer

>>> from sage.all import *
>>> from sage.combinat.q_analogues import q_int
>>> q_int(Integer(3))
q^2 + q + 1
>>> q_int(-Integer(3))
-q^-3 - q^-2 - q^-1
>>> p = ZZ['p'].gen(0)
>>> q_int(Integer(3),p)
p^2 + p + 1
>>> q_int(Integer(3)/Integer(2))
Traceback (most recent call last):
...
ValueError: 3/2 must be an integer
sage.combinat.q_analogues.q_jordan(q=None)[source]#

Return the \(q\)-Jordan number of \(t\).

If \(q\) is the power of a prime number, the output is the number of complete flags in \(\GF{q}^N\) (where \(N\) is the size of \(t\)) stable under a linear nilpotent endomorphism \(f_t\) whose Jordan type is given by \(t\), i.e. such that for all \(i\):

\[\dim (\ker f_t^i) = t[0] + \cdots + t[i-1]\]

If \(q\) is unspecified, then it defaults to using the generator \(q\) for a univariate polynomial ring over the integers.

The result is cached.

INPUT:

  • t – an integer partition, or an argument accepted by Partition

  • q – (default: None) the variable \(q\); if None, then use a default variable in \(\ZZ[q]\)

EXAMPLES:

sage: from sage.combinat.q_analogues import q_jordan
sage: [q_jordan(mu, 2) for mu in Partitions(5)]
[9765, 1029, 213, 93, 29, 9, 1]
sage: [q_jordan(mu, 2) for mu in Partitions(6)]
[615195, 40635, 5643, 2331, 1491, 515, 147, 87, 47, 11, 1]
sage: q_jordan([3,2,1])
16*q^4 + 24*q^3 + 14*q^2 + 5*q + 1
sage: q_jordan([2,1], x)                                                        # needs sage.symbolic
2*x + 1

>>> from sage.all import *
>>> from sage.combinat.q_analogues import q_jordan
>>> [q_jordan(mu, Integer(2)) for mu in Partitions(Integer(5))]
[9765, 1029, 213, 93, 29, 9, 1]
>>> [q_jordan(mu, Integer(2)) for mu in Partitions(Integer(6))]
[615195, 40635, 5643, 2331, 1491, 515, 147, 87, 47, 11, 1]
>>> q_jordan([Integer(3),Integer(2),Integer(1)])
16*q^4 + 24*q^3 + 14*q^2 + 5*q + 1
>>> q_jordan([Integer(2),Integer(1)], x)                                                        # needs sage.symbolic
2*x + 1

If the partition is trivial (i.e. has only one part), we get the \(q\)-factorial (in this case, the nilpotent endomorphism is necessarily \(0\)):

sage: from sage.combinat.q_analogues import q_factorial
sage: q_jordan([5]) == q_factorial(5)
True
sage: q_jordan([11], 5) == q_factorial(11, 5)
True

>>> from sage.all import *
>>> from sage.combinat.q_analogues import q_factorial
>>> q_jordan([Integer(5)]) == q_factorial(Integer(5))
True
>>> q_jordan([Integer(11)], Integer(5)) == q_factorial(Integer(11), Integer(5))
True

AUTHOR:

  • Xavier Caruso (2012-06-29)

sage.combinat.q_analogues.q_multinomial(seq, q=None, binomial_algorithm='auto')[source]#

Return the \(q\)-multinomial coefficient.

This is also known as the Gaussian multinomial coefficient, and is defined by

\[\binom{n}{k_1, k_2, \ldots, k_m}_q = \frac{[n]_q!} {[k_1]_q! [k_2]_q! \cdots [k_m]_q!}\]

where \(n = k_1 + k_2 + \cdots + k_m\).

If \(q\) is unspecified, then the variable is the generator \(q\) for a univariate polynomial ring over the integers.

INPUT:

  • seq – an iterable of the values \(k_1\) to \(k_m\) defined above

  • q – (default: None) the variable \(q\); if None, then use a default variable in \(\ZZ[q]\)

  • binomial_algorithm – (default: 'auto') the algorithm to use in q_binomial(); see possible values there

ALGORITHM:

We use the equivalent formula

\[\binom{k_1 + \cdots + k_m}{k_1, \ldots, k_m}_q = \prod_{i=1}^m \binom{\sum_{j=1}^i k_j}{k_i}_q.\]

EXAMPLES:

sage: from sage.combinat.q_analogues import q_multinomial
sage: q_multinomial([1,2,1])
q^5 + 2*q^4 + 3*q^3 + 3*q^2 + 2*q + 1
sage: q_multinomial([1,2,1], q=1) == multinomial([1,2,1])
True
sage: q_multinomial((3,2)) == q_binomial(5,3)
True
sage: q_multinomial([])
1

>>> from sage.all import *
>>> from sage.combinat.q_analogues import q_multinomial
>>> q_multinomial([Integer(1),Integer(2),Integer(1)])
q^5 + 2*q^4 + 3*q^3 + 3*q^2 + 2*q + 1
>>> q_multinomial([Integer(1),Integer(2),Integer(1)], q=Integer(1)) == multinomial([Integer(1),Integer(2),Integer(1)])
True
>>> q_multinomial((Integer(3),Integer(2))) == q_binomial(Integer(5),Integer(3))
True
>>> q_multinomial([])
1
sage.combinat.q_analogues.q_pochhammer(n, a, q=None)[source]#

Return the \(q\)-Pochhammer \((a; q)_n\).

The \(q\)-Pochhammer symbol is defined by

\[(a; q)_n = \prod_{k=0}^{n-1} (1 - aq^k)\]

with \((a; q)_0 = 1\) for all \(a, q\) and \(n \in \NN\). By using the identity

\[(a; q)_n = \frac{(a; q)_{\infty}}{(aq^n; q)_{\infty}},\]

we can extend the definition to \(n < 0\) by

\[(a; q)_n = \frac{1}{(aq^n; q)_{-n}} = \prod_{k=1}^{-n} \frac{1}{1 - a/q^k}.\]

EXAMPLES:

sage: from sage.combinat.q_analogues import q_pochhammer
sage: q_pochhammer(3, 1/7)
6/343*q^3 - 6/49*q^2 - 6/49*q + 6/7
sage: q_pochhammer(3, 3)
-18*q^3 + 6*q^2 + 6*q - 2
sage: q_pochhammer(3, 1)
0

sage: R.<q> = ZZ[]
sage: q_pochhammer(4, q)
q^10 - q^9 - q^8 + 2*q^5 - q^2 - q + 1
sage: q_pochhammer(4, q^2)
q^14 - q^12 - q^11 - q^10 + q^8 + 2*q^7 + q^6 - q^4 - q^3 - q^2 + 1
sage: q_pochhammer(-3, q)
1/(-q^9 + q^7 + q^6 + q^5 - q^4 - q^3 - q^2 + 1)

>>> from sage.all import *
>>> from sage.combinat.q_analogues import q_pochhammer
>>> q_pochhammer(Integer(3), Integer(1)/Integer(7))
6/343*q^3 - 6/49*q^2 - 6/49*q + 6/7
>>> q_pochhammer(Integer(3), Integer(3))
-18*q^3 + 6*q^2 + 6*q - 2
>>> q_pochhammer(Integer(3), Integer(1))
0

>>> R = ZZ['q']; (q,) = R._first_ngens(1)
>>> q_pochhammer(Integer(4), q)
q^10 - q^9 - q^8 + 2*q^5 - q^2 - q + 1
>>> q_pochhammer(Integer(4), q**Integer(2))
q^14 - q^12 - q^11 - q^10 + q^8 + 2*q^7 + q^6 - q^4 - q^3 - q^2 + 1
>>> q_pochhammer(-Integer(3), q)
1/(-q^9 + q^7 + q^6 + q^5 - q^4 - q^3 - q^2 + 1)

REFERENCES:

sage.combinat.q_analogues.q_stirling_number1(k, q=None)[source]#

Return the (unsigned) \(q\)-Stirling number of the first kind.

This is a \(q\)-analogue of sage.combinat.combinat.stirling_number1() .

INPUT:

  • n, k – integers with 1 <= k <= n

  • q – optional variable (default \(q\))

OUTPUT: a polynomial in the variable \(q\)

These polynomials satisfy the recurrence

\[s_{n,k} = s_{n-1,k-1} + [n-1]_q s_{n-1, k}.\]

EXAMPLES:

sage: from sage.combinat.q_analogues import q_stirling_number1
sage: q_stirling_number1(4,2)
q^3 + 3*q^2 + 4*q + 3

sage: all(stirling_number1(6,k) == q_stirling_number1(6,k)(1)                   # needs sage.libs.gap
....:     for k in range(1,6))
True

sage: x = polygen(QQ['q'],'x')
sage: S = sum(q_stirling_number1(5,k)*x**k for k in range(1, 6))
sage: factor(S)                                                                 # needs sage.libs.singular
x * (x + 1) * (x + q + 1) * (x + q^2 + q + 1) * (x + q^3 + q^2 + q + 1)

>>> from sage.all import *
>>> from sage.combinat.q_analogues import q_stirling_number1
>>> q_stirling_number1(Integer(4),Integer(2))
q^3 + 3*q^2 + 4*q + 3

>>> all(stirling_number1(Integer(6),k) == q_stirling_number1(Integer(6),k)(Integer(1))                   # needs sage.libs.gap
...     for k in range(Integer(1),Integer(6)))
True

>>> x = polygen(QQ['q'],'x')
>>> S = sum(q_stirling_number1(Integer(5),k)*x**k for k in range(Integer(1), Integer(6)))
>>> factor(S)                                                                 # needs sage.libs.singular
x * (x + 1) * (x + q + 1) * (x + q^2 + q + 1) * (x + q^3 + q^2 + q + 1)

REFERENCES:

sage.combinat.q_analogues.q_stirling_number2(k, q=None)[source]#

Return the (unsigned) \(q\)-Stirling number of the second kind.

This is a \(q\)-analogue of sage.combinat.combinat.stirling_number2().

INPUT:

  • n, k – integers with 1 <= k <= n

  • q – optional variable (default \(q\))

OUTPUT: a polynomial in the variable \(q\)

These polynomials satisfy the recurrence

\[S_{n,k} = q^{k-1} S_{n-1,k-1} + [k]_q s_{n-1, k}.\]

EXAMPLES:

sage: from sage.combinat.q_analogues import q_stirling_number2
sage: q_stirling_number2(4,2)
q^3 + 3*q^2 + 3*q

sage: all(stirling_number2(6,k) == q_stirling_number2(6,k)(1)
....:     for k in range(7))
True

>>> from sage.all import *
>>> from sage.combinat.q_analogues import q_stirling_number2
>>> q_stirling_number2(Integer(4),Integer(2))
q^3 + 3*q^2 + 3*q

>>> all(stirling_number2(Integer(6),k) == q_stirling_number2(Integer(6),k)(Integer(1))
...     for k in range(Integer(7)))
True

REFERENCES:

sage.combinat.q_analogues.q_subgroups_of_abelian_group(la, mu, q=None, algorithm='birkhoff')[source]#

Return the \(q\)-number of subgroups of type mu in a finite abelian group of type la.

INPUT:

  • la – type of the ambient group as a Partition

  • mu – type of the subgroup as a Partition

  • q – (default: None) an indeterminate or a prime number; if None, this defaults to \(q \in \ZZ[q]\)

  • algorithm – (default: 'birkhoff') the algorithm to use can be one of the following:

    • 'birkhoff – use the Birkhoff formula from [Bu87]

    • 'delsarte' – use the formula from [Delsarte48]

OUTPUT:

The number of subgroups of type mu in a group of type la as a polynomial in q.

ALGORITHM:

Let \(q\) be a prime number and \(\lambda = (\lambda_1, \ldots, \lambda_l)\) be a partition. A finite abelian \(q\)-group is of type \(\lambda\) if it is isomorphic to

\[\ZZ / q^{\lambda_1} \ZZ \times \cdots \times \ZZ / q^{\lambda_l} \ZZ.\]

The formula from [Bu87] works as follows: Let \(\lambda\) and \(\mu\) be partitions. Let \(\lambda^{\prime}\) and \(\mu^{\prime}\) denote the conjugate partitions to \(\lambda\) and \(\mu\), respectively. The number of subgroups of type \(\mu\) in a group of type \(\lambda\) is given by

\[\prod_{i=1}^{\mu_1} q^{\mu^{\prime}_{i+1} (\lambda^{\prime}_i - \mu^{\prime}_i)} \binom{\lambda^{\prime}_i - \mu^{\prime}_{i+1}} {\mu^{\prime}_i - \mu^{\prime}_{i+1}}_q\]

The formula from [Delsarte48] works as follows: Let \(\lambda\) and \(\mu\) be partitions. Let \((s_1, s_2, \ldots, s_l)\) and \((r_1, r_2, \ldots, r_k)\) denote the parts of the partitions conjugate to \(\lambda\) and \(\mu\) respectively. Let

\[\mathfrak{F}(\xi_1, \ldots, \xi_k) = \xi_1^{r_2} \xi_2^{r_3} \cdots \xi_{k-1}^{r_k} \prod_{i_1=r_2}^{r_1-1} (\xi_1-q^{i_1}) \prod_{i_2=r_3}^{r_2-1} (\xi_2-q^{i_2}) \cdots \prod_{i_k=0}^{r_k-1} (\xi_k-q^{-i_k}).\]

Then the number of subgroups of type \(\mu\) in a group of type \(\lambda\) is given by

\[\frac{\mathfrak{F}(q^{s_1}, q^{s_2}, \ldots, q^{s_k})}{\mathfrak{F} (q^{r_1}, q^{r_2}, \ldots, q^{r_k})}.\]

EXAMPLES:

sage: from sage.combinat.q_analogues import q_subgroups_of_abelian_group
sage: q_subgroups_of_abelian_group([1,1], [1])
q + 1
sage: q_subgroups_of_abelian_group([3,3,2,1], [2,1])
q^6 + 2*q^5 + 3*q^4 + 2*q^3 + q^2
sage: R.<t> = QQ[]
sage: q_subgroups_of_abelian_group([5,3,1], [3,1], t)
t^4 + 2*t^3 + t^2
sage: q_subgroups_of_abelian_group([5,3,1], [3,1], 3)
144
sage: q_subgroups_of_abelian_group([1,1,1], [1]) == q_subgroups_of_abelian_group([1,1,1], [1,1])
True
sage: q_subgroups_of_abelian_group([5], [3])
1
sage: q_subgroups_of_abelian_group([1], [2])
0
sage: q_subgroups_of_abelian_group([2], [1,1])
0

>>> from sage.all import *
>>> from sage.combinat.q_analogues import q_subgroups_of_abelian_group
>>> q_subgroups_of_abelian_group([Integer(1),Integer(1)], [Integer(1)])
q + 1
>>> q_subgroups_of_abelian_group([Integer(3),Integer(3),Integer(2),Integer(1)], [Integer(2),Integer(1)])
q^6 + 2*q^5 + 3*q^4 + 2*q^3 + q^2
>>> R = QQ['t']; (t,) = R._first_ngens(1)
>>> q_subgroups_of_abelian_group([Integer(5),Integer(3),Integer(1)], [Integer(3),Integer(1)], t)
t^4 + 2*t^3 + t^2
>>> q_subgroups_of_abelian_group([Integer(5),Integer(3),Integer(1)], [Integer(3),Integer(1)], Integer(3))
144
>>> q_subgroups_of_abelian_group([Integer(1),Integer(1),Integer(1)], [Integer(1)]) == q_subgroups_of_abelian_group([Integer(1),Integer(1),Integer(1)], [Integer(1),Integer(1)])
True
>>> q_subgroups_of_abelian_group([Integer(5)], [Integer(3)])
1
>>> q_subgroups_of_abelian_group([Integer(1)], [Integer(2)])
0
>>> q_subgroups_of_abelian_group([Integer(2)], [Integer(1),Integer(1)])
0

REFERENCES:

[Bu87] (1,2)

Butler, Lynne M. A unimodality result in the enumeration of subgroups of a finite abelian group. Proceedings of the American Mathematical Society 101, no. 4 (1987): 771-775. doi:10.1090/S0002-9939-1987-0911049-8

[Delsarte48] (1,2)

S. Delsarte, Fonctions de Möbius Sur Les Groupes Abéliens Finis, Annals of Mathematics, second series, Vol. 45, No. 3, (Jul 1948), pp. 600-609. http://www.jstor.org/stable/1969047

AUTHORS:

  • Amritanshu Prasad (2013-06-07): Implemented the Delsarte algorithm

  • Tomer Bauer (2013, 2018): Implemented the Birkhoff algorithm and refactoring

sage.combinat.q_analogues.qt_catalan_number(n)[source]#

Return the \(q,t\)-Catalan number of index \(n\).

EXAMPLES:

sage: from sage.combinat.q_analogues import qt_catalan_number
sage: qt_catalan_number(1)
1
sage: qt_catalan_number(2)
q + t
sage: qt_catalan_number(3)
q^3 + q^2*t + q*t^2 + t^3 + q*t
sage: qt_catalan_number(4)
q^6 + q^5*t + q^4*t^2 + q^3*t^3 + q^2*t^4 + q*t^5 + t^6 + q^4*t + q^3*t^2 + q^2*t^3 + q*t^4 + q^3*t + q^2*t^2 + q*t^3

>>> from sage.all import *
>>> from sage.combinat.q_analogues import qt_catalan_number
>>> qt_catalan_number(Integer(1))
1
>>> qt_catalan_number(Integer(2))
q + t
>>> qt_catalan_number(Integer(3))
q^3 + q^2*t + q*t^2 + t^3 + q*t
>>> qt_catalan_number(Integer(4))
q^6 + q^5*t + q^4*t^2 + q^3*t^3 + q^2*t^4 + q*t^5 + t^6 + q^4*t + q^3*t^2 + q^2*t^3 + q*t^4 + q^3*t + q^2*t^2 + q*t^3

The \(q,t\)-Catalan number of index \(n\) is only defined for \(n\) a nonnegative integer (Issue #11411):

sage: qt_catalan_number(-2)
Traceback (most recent call last):
...
ValueError: argument (-2) must be a nonnegative integer

>>> from sage.all import *
>>> qt_catalan_number(-Integer(2))
Traceback (most recent call last):
...
ValueError: argument (-2) must be a nonnegative integer