# Ticket #14136: ppart.py

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

Line | |
---|---|

1 | def 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 |