# 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)

Return the number of standard composition tableaux of shape $$I$$ with descent composition $$J$$.

INPUT:

• I, J – compositions

OUTPUT:

• An 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

sage.combinat.ncsf_qsym.combinatorics.coeff_ell(J, I)

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())
2

sage.combinat.ncsf_qsym.combinatorics.coeff_lp(J, I)

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())
1

sage.combinat.ncsf_qsym.combinatorics.coeff_pi(J, I)

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())
6

sage.combinat.ncsf_qsym.combinatorics.coeff_sp(J, I)

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())
4

sage.combinat.ncsf_qsym.combinatorics.compositions_order(n)

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)
[, [2, 1], [1, 2], [1, 1, 1]]
sage: compositions_order(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)

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(), Composition([1,2]))
-2
sage: m_to_s_stat(QQ, Composition([2,1,2]), Composition([2,1,2]))
8/3

sage.combinat.ncsf_qsym.combinatorics.number_of_SSRCT(content_comp, shape_comp)

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

sage.combinat.ncsf_qsym.combinatorics.number_of_fCT(content_comp, shape_comp)

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