Common combinatorial tools#

REFERENCES:

[NCSF] (1,2,3,4)

Gelfand, Krob, Lascoux, Leclerc, Retakh, Thibon, Noncommutative Symmetric Functions, Adv. Math. 112 (1995), no. 2, 218-348.

[QSCHUR]

Haglund, Luoto, Mason, van Willigenburg, Quasisymmetric Schur functions, J. Comb. Theory Ser. A 118 (2011), 463-490. http://www.sciencedirect.com/science/article/pii/S0097316509001745 , arXiv 0810.2489v2.

[Tev2007]

Lenny Tevlin, Noncommutative Analogs of Monomial Symmetric Functions, Cauchy Identity, and Hall Scalar Product, arXiv 0712.2201v1.

sage.combinat.ncsf_qsym.combinatorics.coeff_dab(I, J)[source]#

Return the number of standard composition tableaux of shape \(I\) with descent composition \(J\).

INPUT:

  • I, J – compositions

OUTPUT: integer

EXAMPLES:

sage: from sage.combinat.ncsf_qsym.combinatorics import coeff_dab
sage: coeff_dab(Composition([2,1]),Composition([2,1]))
1
sage: coeff_dab(Composition([1,1,2]),Composition([1,2,1]))
0

>>> from sage.all import *
>>> from sage.combinat.ncsf_qsym.combinatorics import coeff_dab
>>> coeff_dab(Composition([Integer(2),Integer(1)]),Composition([Integer(2),Integer(1)]))
1
>>> coeff_dab(Composition([Integer(1),Integer(1),Integer(2)]),Composition([Integer(1),Integer(2),Integer(1)]))
0
sage.combinat.ncsf_qsym.combinatorics.coeff_ell(J, I)[source]#

Returns the coefficient \(\ell_{J,I}\) as defined in [NCSF].

INPUT:

  • J – a composition

  • I – a composition refining J

OUTPUT: integer

EXAMPLES:

sage: from sage.combinat.ncsf_qsym.combinatorics import coeff_ell
sage: coeff_ell(Composition([1,1,1]), Composition([2,1]))
2
sage: coeff_ell(Composition([2,1]), Composition([3]))
2

>>> from sage.all import *
>>> from sage.combinat.ncsf_qsym.combinatorics import coeff_ell
>>> coeff_ell(Composition([Integer(1),Integer(1),Integer(1)]), Composition([Integer(2),Integer(1)]))
2
>>> coeff_ell(Composition([Integer(2),Integer(1)]), Composition([Integer(3)]))
2
sage.combinat.ncsf_qsym.combinatorics.coeff_lp(J, I)[source]#

Returns the coefficient \(lp_{J,I}\) as defined in [NCSF].

INPUT:

  • J – a composition

  • I – a composition refining J

OUTPUT: integer

EXAMPLES:

sage: from sage.combinat.ncsf_qsym.combinatorics import coeff_lp
sage: coeff_lp(Composition([1,1,1]), Composition([2,1]))
1
sage: coeff_lp(Composition([2,1]), Composition([3]))
1

>>> from sage.all import *
>>> from sage.combinat.ncsf_qsym.combinatorics import coeff_lp
>>> coeff_lp(Composition([Integer(1),Integer(1),Integer(1)]), Composition([Integer(2),Integer(1)]))
1
>>> coeff_lp(Composition([Integer(2),Integer(1)]), Composition([Integer(3)]))
1
sage.combinat.ncsf_qsym.combinatorics.coeff_pi(J, I)[source]#

Returns the coefficient \(\pi_{J,I}\) as defined in [NCSF].

INPUT:

  • J – a composition

  • I – a composition refining J

OUTPUT: integer

EXAMPLES:

sage: from sage.combinat.ncsf_qsym.combinatorics import coeff_pi
sage: coeff_pi(Composition([1,1,1]), Composition([2,1]))
2
sage: coeff_pi(Composition([2,1]), Composition([3]))
6

>>> from sage.all import *
>>> from sage.combinat.ncsf_qsym.combinatorics import coeff_pi
>>> coeff_pi(Composition([Integer(1),Integer(1),Integer(1)]), Composition([Integer(2),Integer(1)]))
2
>>> coeff_pi(Composition([Integer(2),Integer(1)]), Composition([Integer(3)]))
6
sage.combinat.ncsf_qsym.combinatorics.coeff_sp(J, I)[source]#

Returns the coefficient \(sp_{J,I}\) as defined in [NCSF].

INPUT:

  • J – a composition

  • I – a composition refining J

OUTPUT: integer

EXAMPLES:

sage: from sage.combinat.ncsf_qsym.combinatorics import coeff_sp
sage: coeff_sp(Composition([1,1,1]), Composition([2,1]))
2
sage: coeff_sp(Composition([2,1]), Composition([3]))
4

>>> from sage.all import *
>>> from sage.combinat.ncsf_qsym.combinatorics import coeff_sp
>>> coeff_sp(Composition([Integer(1),Integer(1),Integer(1)]), Composition([Integer(2),Integer(1)]))
2
>>> coeff_sp(Composition([Integer(2),Integer(1)]), Composition([Integer(3)]))
4
sage.combinat.ncsf_qsym.combinatorics.compositions_order(n)[source]#

Return the compositions of \(n\) ordered as defined in [QSCHUR].

Let \(S(\gamma)\) return the composition \(\gamma\) after sorting. For compositions \(\alpha\) and \(\beta\), we order \(\alpha \rhd \beta\) if

  1. \(S(\alpha) > S(\beta)\) lexicographically, or

  2. \(S(\alpha) = S(\beta)\) and \(\alpha > \beta\) lexicographically.

INPUT:

  • n – a positive integer

OUTPUT:

  • A list of the compositions of n sorted into decreasing order by \(\rhd\)

EXAMPLES:

sage: from sage.combinat.ncsf_qsym.combinatorics import compositions_order
sage: compositions_order(3)
[[3], [2, 1], [1, 2], [1, 1, 1]]
sage: compositions_order(4)
[[4], [3, 1], [1, 3], [2, 2], [2, 1, 1], [1, 2, 1], [1, 1, 2], [1, 1, 1, 1]]

>>> from sage.all import *
>>> from sage.combinat.ncsf_qsym.combinatorics import compositions_order
>>> compositions_order(Integer(3))
[[3], [2, 1], [1, 2], [1, 1, 1]]
>>> compositions_order(Integer(4))
[[4], [3, 1], [1, 3], [2, 2], [2, 1, 1], [1, 2, 1], [1, 1, 2], [1, 1, 1, 1]]
sage.combinat.ncsf_qsym.combinatorics.m_to_s_stat(R, I, K)[source]#

Return the coefficient of the complete non-commutative symmetric function \(S^K\) in the expansion of the monomial non-commutative symmetric function \(M^I\) with respect to the complete basis over the ring \(R\). This is the coefficient in formula (36) of Tevlin’s paper [Tev2007].

INPUT:

  • R – A ring, supposed to be a \(\QQ\)-algebra

  • I, K – compositions

OUTPUT:

  • The coefficient of \(S^K\) in the expansion of \(M^I\) in the complete basis of the non-commutative symmetric functions over R.

EXAMPLES:

sage: from sage.combinat.ncsf_qsym.combinatorics import m_to_s_stat
sage: m_to_s_stat(QQ, Composition([2,1]), Composition([1,1,1]))
-1
sage: m_to_s_stat(QQ, Composition([3]), Composition([1,2]))
-2
sage: m_to_s_stat(QQ, Composition([2,1,2]), Composition([2,1,2]))
8/3

>>> from sage.all import *
>>> from sage.combinat.ncsf_qsym.combinatorics import m_to_s_stat
>>> m_to_s_stat(QQ, Composition([Integer(2),Integer(1)]), Composition([Integer(1),Integer(1),Integer(1)]))
-1
>>> m_to_s_stat(QQ, Composition([Integer(3)]), Composition([Integer(1),Integer(2)]))
-2
>>> m_to_s_stat(QQ, Composition([Integer(2),Integer(1),Integer(2)]), Composition([Integer(2),Integer(1),Integer(2)]))
8/3
sage.combinat.ncsf_qsym.combinatorics.number_of_SSRCT(shape_comp)[source]#

The number of semi-standard reverse composition tableaux.

The dual quasisymmetric-Schur functions satisfy a left Pieri rule where \(S_n dQS_\gamma\) is a sum over dual quasisymmetric-Schur functions indexed by compositions which contain the composition \(\gamma\). The definition of an SSRCT comes from this rule. The number of SSRCT of content \(\beta\) and shape \(\alpha\) is equal to the number of SSRCT of content \((\beta_2, \ldots, \beta_\ell)\) and shape \(\gamma\) where \(dQS_\alpha\) appears in the expansion of \(S_{\beta_1} dQS_\gamma\).

In sage the recording tableau for these objects are called CompositionTableaux.

INPUT:

  • content_comp, shape_comp – compositions

OUTPUT:

  • An integer

EXAMPLES:

sage: from sage.combinat.ncsf_qsym.combinatorics import number_of_SSRCT
sage: number_of_SSRCT(Composition([3,1]), Composition([1,3]))
0
sage: number_of_SSRCT(Composition([1,2,1]), Composition([1,3]))
1
sage: number_of_SSRCT(Composition([1,1,2,2]), Composition([3,3]))
2
sage: all(CompositionTableaux(be).cardinality()
....:     == sum(number_of_SSRCT(al,be)*binomial(4,len(al))
....:            for al in Compositions(4))
....:     for be in Compositions(4))
True

>>> from sage.all import *
>>> from sage.combinat.ncsf_qsym.combinatorics import number_of_SSRCT
>>> number_of_SSRCT(Composition([Integer(3),Integer(1)]), Composition([Integer(1),Integer(3)]))
0
>>> number_of_SSRCT(Composition([Integer(1),Integer(2),Integer(1)]), Composition([Integer(1),Integer(3)]))
1
>>> number_of_SSRCT(Composition([Integer(1),Integer(1),Integer(2),Integer(2)]), Composition([Integer(3),Integer(3)]))
2
>>> all(CompositionTableaux(be).cardinality()
...     == sum(number_of_SSRCT(al,be)*binomial(Integer(4),len(al))
...            for al in Compositions(Integer(4)))
...     for be in Compositions(Integer(4)))
True
sage.combinat.ncsf_qsym.combinatorics.number_of_fCT(shape_comp)[source]#

Return the number of Immaculate tableaux of shape shape_comp and content content_comp.

See [BBSSZ2012], Definition 3.9, for the notion of an immaculate tableau.

INPUT:

  • content_comp, shape_comp – compositions

OUTPUT:

  • An integer

EXAMPLES:

sage: from sage.combinat.ncsf_qsym.combinatorics import number_of_fCT
sage: number_of_fCT(Composition([3,1]), Composition([1,3]))
0
sage: number_of_fCT(Composition([1,2,1]), Composition([1,3]))
1
sage: number_of_fCT(Composition([1,1,3,1]), Composition([2,1,3]))
2

>>> from sage.all import *
>>> from sage.combinat.ncsf_qsym.combinatorics import number_of_fCT
>>> number_of_fCT(Composition([Integer(3),Integer(1)]), Composition([Integer(1),Integer(3)]))
0
>>> number_of_fCT(Composition([Integer(1),Integer(2),Integer(1)]), Composition([Integer(1),Integer(3)]))
1
>>> number_of_fCT(Composition([Integer(1),Integer(1),Integer(3),Integer(1)]), Composition([Integer(2),Integer(1),Integer(3)]))
2