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