# Ticket #14136: ppart.py

File ppart.py, 3.2 KB (added by darij, 9 years ago)

P-partition enumerators for QSym

Line
1def ppenum(P, ps, R, check=False):
2    """
3    P-partition enumerator in QSym for a labelled poset P.
4
5    INPUT:
6
7    P: finite poset.
8
9    ps: tuple of elements of P, each appearing exactly once, determining a linear
10    order on P which does not have to be a linear extension.
11    [It would be so much better to implement this as a dictionary, but
12    dictionaries cannot be hashed so far, and caching is a must with
13    these functions.]
14
15    R: commutative ring.
16
17    OUTPUT:
18
19    P-partition enumerator for (P, ps) in QSym over ring R. This is defined
20    to be the quasisymmetric function \sum\limits_{f\text{ is a }P\text{-partition}}
21    \prod\limits_{p \in P} x_{f(p)} over the ring R, where a P-partition means
22    a function P \to \{1,2,3,...\} satisfying the following properties:
23
24    - Any two elements i and j of P with i < j satisfy f(i) \leq f(j).
25
26    - Any two elements i and j of P with i < j such that i appears after
27    left of j in the list ps satisfy f(i) < f(j).
28
29    EXAMPLES::
30        sage: P = Poset([[1,2,3,4],[[1,4],[2,4],[4,3]]])
31        sage: ps = (3,1,2,4)
32        sage: FP = ppenum(P, ps, QQ, check=True)
33        sage: FP.expand(5)
34        x0^3*x1 + x0^3*x2 + x0^2*x1*x2 + 2*x0*x1^2*x2 + x1^3*x2 + x0^3*x3 + x0^2*x1*x3 + 2*x0*x1^2*x3 + x1^3*x3 + x0^2*x2*x3 + 2*x0*x1*x2*x3 + x1^2*x2*x3 + 2*x0*x2^2*x3 + 2*x1*x2^2*x3 + x2^3*x3 + x0^3*x4 + x0^2*x1*x4 + 2*x0*x1^2*x4 + x1^3*x4 + x0^2*x2*x4 + 2*x0*x1*x2*x4 + x1^2*x2*x4 + 2*x0*x2^2*x4 + 2*x1*x2^2*x4 + x2^3*x4 + x0^2*x3*x4 + 2*x0*x1*x3*x4 + x1^2*x3*x4 + 2*x0*x2*x3*x4 + 2*x1*x2*x3*x4 + x2^2*x3*x4 + 2*x0*x3^2*x4 + 2*x1*x3^2*x4 + 2*x2*x3^2*x4 + x3^3*x4
35        sage: xs = FP.expand(5).parent().gens()
36        sage: u = sum([xs[a] * xs[b] * xs[c] * xs[d] for a in range(5) for b in range(5) for c in range(5) for d in range(5) if a <= b and c <= b and b < d])
37        sage: u == FP.expand(5)
38        True
39        sage: P = Poset([[],[]])
40        sage: ps = ()
41        sage: FP = ppenum(P, ps, QQ, check=True)
42        sage: FP
43        M[]
44
45    """
46
47    from sage.categories.finite_posets import FinitePosets
48    from sage.categories.commutative_rings import CommutativeRings
49    from sage.combinat.ncsf_qsym.qsym import QuasiSymmetricFunctions
50    from sage.combinat.composition import Composition
51    if check:
52        if not (P in FinitePosets()):
53            raise ValueError("P is not a finite poset!")
54        if len(ps) != len(set(ps)):
55            raise ValueError("ps has equal elements!")
56        if set(P.list()) != set(ps):
57            raise ValueError("The elements of ps are not those of P !")
58        if not (R in CommutativeRings()):
59            raise ValueError("R is not a commutative ring!")
60    QR = QuasiSymmetricFunctions(R)
61    n = len(ps)
62    res = QR.zero()
63    psdict = dict(zip(ps, range(n)))
64    for lin in P.linear_extensions():
65        descents = [i + 1 for i in xrange(n - 1) if psdict[lin[i]] > psdict[lin[i+1]]]
66        c = Composition(from_subset=(descents, n))
67        res += QR.Fundamental()(c)
68    return res
69