q-Analogues¶
-
sage.combinat.q_analogues.
gaussian_binomial
(n, k, q=None, algorithm='auto')¶ 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
-
sage.combinat.q_analogues.
gaussian_multinomial
(seq, q=None, binomial_algorithm='auto')¶ Return the
-multinomial coefficient.
This is also known as the Gaussian multinomial coefficient, and is defined by
where
.
If
is unspecified, then the variable is the generator
for a univariate polynomial ring over the integers.
INPUT:
seq
– an iterable of the valuesto
defined above
q
– (default:None
) the variable; if
None
, then use a default variable inbinomial_algorithm
– (default:'auto'
) the algorithm to use inq_binomial()
; see possible values there
ALGORITHM:
We use the equivalent formula
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
-
sage.combinat.q_analogues.
q_binomial
(n, k, q=None, algorithm='auto')¶ Return the
-binomial coefficient.
This is also known as the Gaussian binomial coefficient, and is defined by
See Wikipedia article Gaussian_binomial_coefficient.
If
is unspecified, then the variable is the generator
for a univariate polynomial ring over the integers.
INPUT:
n, k
– the valuesand
defined above
q
– (default:None
) the variable; if
None
, then use a default variable inalgorithm
– (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 ork
is small with respect ton
, one uses the naive algorithm. When bothn
andk
are big, one uses the cyclotomic algorithm.If
q
is in the symbolic ring, 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
:
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
The
-binomial coefficient vanishes unless
:
sage: q_binomial(4,5) 0 sage: q_binomial(5,-1) 0
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
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(25, 't') sage: t = R.gen(0) sage: q_binomial(6, 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]
TESTS:
One checks that the first two arguments are integers:
sage: q_binomial(1/2,1) Traceback (most recent call last): ... TypeError: no conversion of this rational to integer
One checks that
is nonnegative:
sage: q_binomial(-4,1) Traceback (most recent call last): ... ValueError: n must be nonnegative
This also works for variables in the symbolic ring:
sage: z = var('z') sage: factor(q_binomial(4,2,z)) (z^2 + z + 1)*(z^2 + 1)
This also works for complex roots of unity:
sage: q_binomial(6, 1, QQbar(I)) I + 1
Note that the symbolic computation works (see trac ticket #14982):
sage: q_binomial(6, 1, I) I + 1
Check that the algorithm does not matter:
sage: q_binomial(6,3, algorithm='naive') == q_binomial(6,3, algorithm='cyclotomic') True
One more test:
sage: q_binomial(4, 2, Zmod(6)(2), algorithm='naive') 5
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:
- Frederic Chapoton, David Joyner and William Stein
-
sage.combinat.q_analogues.
q_catalan_number
(n, q=None)¶ Returns the
-Catalan number of index
.
If
is unspecified, then it defaults to using the generator
for a univariate polynomial ring over the integers.
There are several
-Catalan numbers. This procedure returns the one which can be written using the
-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
The
-Catalan number of index
is only defined for
a nonnegative integer (trac ticket #11411):
sage: q_catalan_number(-2) Traceback (most recent call last): ... ValueError: Argument (-2) must be a nonnegative integer.
-
sage.combinat.q_analogues.
q_factorial
(n, q=None)¶ Returns the
-analogue of the factorial
.
If
is unspecified, then it defaults to using the generator
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
The
-analogue of
is only defined for
a non-negative integer (trac ticket #11411):
sage: q_factorial(-2) Traceback (most recent call last): ... ValueError: Argument (-2) must be a nonnegative integer.
-
sage.combinat.q_analogues.
q_int
(n, q=None)¶ Return the
-analogue of the integer
.
The
-analogue of the integer
is given by
Consequently, if
then
and if
then
.
If the argument
is not specified then it defaults to the generator
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^2 - q - 1)/q^3 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
TESTS:
We check that trac ticket #15805 is fixed:
sage: from sage.combinat.q_analogues import q_int sage: q_int(0).parent() Univariate Polynomial Ring in q over Integer Ring
-
sage.combinat.q_analogues.
q_jordan
(t, q)¶ INPUT:
– a partition of an integer
– an integer or an indeterminate
OUTPUT:
If
is the power of a prime number, the output is the number of complete flags in
(where
is the size of
) stable under a linear nilpotent endomorphism
whose Jordan type is given by
, i.e. such that for all
:
If
is an indeterminate, the output is a polynomial whose values at powers of prime numbers are the previous numbers.
The result is cached.
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=PolynomialRing(ZZ,'q').gen() sage: q_jordan(Partition([3,2,1]),q) 16*q^4 + 24*q^3 + 14*q^2 + 5*q + 1
If the partition is trivial (i.e. has only one part), we get the
-factorial (in this case, the nilpotent endomorphism is necessarily
):
sage: from sage.combinat.q_analogues import q_factorial sage: q_jordan(Partition([5]),3) == q_factorial(5,3) True sage: q_jordan(Partition([11]),5) == q_factorial(11,5) True
TESTS:
sage: q_jordan(Partition([4,3,1]),1) Traceback (most recent call last): ... ValueError: q must not be equal to 1
AUTHOR:
- Xavier Caruso (2012-06-29)
-
sage.combinat.q_analogues.
q_multinomial
(seq, q=None, binomial_algorithm='auto')¶ Return the
-multinomial coefficient.
This is also known as the Gaussian multinomial coefficient, and is defined by
where
.
If
is unspecified, then the variable is the generator
for a univariate polynomial ring over the integers.
INPUT:
seq
– an iterable of the valuesto
defined above
q
– (default:None
) the variable; if
None
, then use a default variable inbinomial_algorithm
– (default:'auto'
) the algorithm to use inq_binomial()
; see possible values there
ALGORITHM:
We use the equivalent formula
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
-
sage.combinat.q_analogues.
q_subgroups_of_abelian_group
(la, mu, q=None, algorithm='birkhoff')¶ Return the
-number of subgroups of type
mu
in a finite abelian group of typela
.INPUT:
la
– type of the ambient group as aPartition
mu
– type of the subgroup as aPartition
q
– (default:None
) an indeterminat or a prime number; ifNone
, this defaults toalgorithm
– (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 typela
as a polynomial inq
.ALGORITHM:
Let
be a prime number and
be a partition. A finite abelian
-group is of type
if it is isomorphic to
The formula from [Bu87] works as follows: Let
and
be partitions. Let
and
denote the conjugate partitions to
and
, respectively. The number of subgroups of type
in a group of type
is given by
The formula from [Delsarte48] works as follows: Let
and
be partitions. Let
and
denote the parts of the partitions conjugate to
and
respectively. Let
Then the number of subgroups of type
in a group of type
is given by
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
TESTS:
Check the same examples with
algorithm='delsarte'
:sage: q_subgroups_of_abelian_group([1,1], [1], algorithm='delsarte') q + 1 sage: q_subgroups_of_abelian_group([3,3,2,1], [2,1], algorithm='delsarte') q^6 + 2*q^5 + 3*q^4 + 2*q^3 + q^2 sage: q_subgroups_of_abelian_group([5,3,1], [3,1], t, algorithm='delsarte') t^4 + 2*t^3 + t^2 sage: q_subgroups_of_abelian_group([5,3,1], [3,1], 3, algorithm='delsarte') 144 sage: q_subgroups_of_abelian_group([1,1,1], [1], algorithm='delsarte') == q_subgroups_of_abelian_group([1,1,1], [1,1]) True sage: q_subgroups_of_abelian_group([5], [3], algorithm='delsarte') 1 sage: q_subgroups_of_abelian_group([1], [2], algorithm='delsarte') 0 sage: q_subgroups_of_abelian_group([2], [1,1], algorithm='delsarte') 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 Mobius Sur Les Groupes Abeliens 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-09-26): Implemented the Birkhoff algorithm
-
sage.combinat.q_analogues.
qt_catalan_number
(n)¶ Returns the
-Catalan number of index
.
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
The
-Catalan number of index
is only defined for
a nonnegative integer (trac ticket #11411):
sage: qt_catalan_number(-2) Traceback (most recent call last): ... ValueError: Argument (-2) must be a nonnegative integer.