source: sage/combinat/skew_partition.py @ 8006:90d75762f161

Revision 8006:90d75762f161, 21.7 KB checked in by Mike Hansen <mhansen@…>, 5 years ago (diff)

Restructuring symmetric functions and misc. combinatorics updates ( #1685 )
Line 
1r"""
2Skew Partitions
3"""
4#*****************************************************************************
5#       Copyright (C) 2007 Mike Hansen <mhansen@gmail.com>,
6#
7#  Distributed under the terms of the GNU General Public License (GPL)
8#
9#    This code is distributed in the hope that it will be useful,
10#    but WITHOUT ANY WARRANTY; without even the implied warranty of
11#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12#    General Public License for more details.
13#
14#  The full text of the GPL is available at:
15#
16#                  http://www.gnu.org/licenses/
17#*****************************************************************************
18
19import sage.combinat.composition
20import sage.combinat.partition
21import sage.combinat.misc as misc
22import sage.combinat.generator as generator
23from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
24from sage.rings.all import QQ, ZZ
25from sage.sets.set import Set
26from sage.graphs.graph import DiGraph
27from UserList import UserList
28from combinat import CombinatorialClass, CombinatorialObject
29import sage.combinat.sf.sfa as sfa
30from sage.matrix.matrix_space import MatrixSpace
31from sage.rings.infinity import PlusInfinity
32infinity = PlusInfinity()
33
34def SkewPartition(skp):
35    """
36    Returns the skew partition object corresponding to skp.
37
38    EXAMPLES:
39        sage: skp = SkewPartition([[3,2,1],[2,1]]); skp
40        [[3, 2, 1], [2, 1]]
41        sage: skp.inner()
42        [2, 1]
43        sage: skp.outer()
44        [3, 2, 1]
45    """
46    if skp not in SkewPartitions():
47        raise ValueError, "invalid skew partition"
48    else:
49        return SkewPartition_class(skp)
50
51class SkewPartition_class(CombinatorialObject):
52    def __init__(self, skp):
53        """
54        TESTS:
55            sage: skp = SkewPartition([[3,2,1],[2,1]])
56            sage: skp == loads(dumps(skp))
57            True
58        """
59        outer = sage.combinat.partition.Partition(skp[0])
60        inner = sage.combinat.partition.Partition(skp[1])
61        CombinatorialObject.__init__(self, [outer, inner])
62
63    def inner(self):
64        """
65        Returns the inner partition of the skew partition.
66
67        EXAMPLES:
68            sage: SkewPartition([[3,2,1],[1,1]]).inner()
69            [1, 1]
70        """
71        return self[1]
72
73    def outer(self):
74        """
75        Returns the outer partition of the skew partition.
76
77        EXAMPLES:
78            sage: SkewPartition([[3,2,1],[1,1]]).outer()
79            [3, 2, 1]
80        """       
81        return self[0]
82     
83   
84
85    def row_lengths(self):
86        """
87        Returns the sum of the row lengths of the skew partition.
88
89        EXAMPLES:
90            sage: SkewPartition([[3,2,1],[1,1]]).row_lengths()
91            [2, 1, 1]
92
93        """
94        skp = self
95        o = skp[0]
96        i = skp[1]+[0]*(len(skp[0])-len(skp[1]))
97        return [x[0]-x[1] for x in zip(o,i)]
98
99
100    def size(self):
101        """
102        Returns the size of the skew partition.
103
104        EXAMPLES:
105            sage: SkewPartition([[3,2,1],[1,1]]).size()
106            4
107        """
108        return sum(self.row_lengths())
109
110
111
112    def conjugate(self):
113        """
114        Returns the conjugate of the skew partition skp.
115
116        EXAMPLES:
117            sage: SkewPartition([[3,2,1],[2]]).conjugate()
118            [[3, 2, 1], [1, 1]]
119        """
120        return SkewPartition(map(lambda x: x.conjugate(), self))
121
122
123    def outer_corners(self):
124        """
125        Returns a list of the outer corners of the skew partition skp.
126
127        EXAMPLES:
128            sage: SkewPartition([[4, 3, 1], [2]]).outer_corners()
129            [[0, 3], [1, 2], [2, 0]]
130        """
131        return self.outer().corners()
132
133
134    def inner_corners(self):
135        """
136        Returns a list of the inner corners of the skew partition skp.
137
138        EXAMPLES:
139            sage: SkewPartition([[4, 3, 1], [2]]).inner_corners()
140            [[0, 2], [1, 0]]
141        """
142       
143        inner = self.inner()
144        outer = self.outer()
145        if inner == []:
146            if outer == []:
147                return []
148            else:
149                return [[0,0]]
150        icorners = [[0, inner[0]]]
151        nn = len(inner)
152        for i in range(1,nn):
153            if inner[i] != inner[i-1]:
154                icorners += [ [i, inner[i]] ]
155
156        icorners += [[nn, 0]]
157        return icorners
158
159    def to_list(self):
160        """
161        EXAMPLES:
162        """
163        return map(list, list(self))
164
165
166    def to_dag(self):
167        """
168        Returns a directed acyclic graph corresponding to the
169        skew partition.
170
171        EXAMPLES:
172            sage: dag = SkewPartition([[3, 2, 1], [1, 1]]).to_dag()
173            sage: dag.edges()
174            [('0,1', '0,2', None), ('0,1', '1,1', None)]
175            sage: dag.vertices()
176            ['0,1', '0,2', '1,1', '2,0']
177        """
178        i = 0
179
180        #Make the skew tableau from the shape
181        skew = [[1]*row_length for row_length in self.outer()]
182        inner = self.inner()
183        for i in range(len(inner)):
184            for j in range(inner[i]):
185                skew[i][j] = None
186
187        G = DiGraph()
188        for row in range(len(skew)):
189            for column in range(len(skew[row])):
190                if skew[row][column] is not None:
191                    string = "%d,%d" % (row, column)
192                    G.add_vertex(string)
193                    #Check to see if there is a node to the right
194                    if column != len(skew[row]) - 1:
195                        newstring = "%d,%d" % (row, column+1)
196                        G.add_edge(string, newstring)
197
198                    #Check to see if there is anything below
199                    if row != len(skew) - 1:
200                        if len(skew[row+1]) > column:
201                            if skew[row+1][column] is not None:
202                                newstring = "%d,%d" % (row+1, column)
203                                G.add_edge(string, newstring)
204        return G
205
206
207##     def r_quotient(self, k):
208##         """
209##         The quotient map extended to skew partitions.
210
211##         """
212##         ## k-th element is the skew partition built using the k-th partition of the
213##         ## k-quotient of the outer and the inner partition.
214##         ## This bijection is only defined if the inner and the outer partition
215##         ## have the same core
216##         if self.inner().r_core(k) == self.outer().r_core(k):
217##             rQinner = self.inner().r_quotient(k)
218##             rQouter = self.outer().r_quotient(k)
219##             return
220
221    def rows_intersection_set(self):
222        """
223        Returns the set of boxes in the lines of lambda which intersect the
224        skew partition.
225
226        EXAMPLES:
227            sage: skp = SkewPartition([[3,2,1],[2,1]])
228            sage: boxes = Set([ (0,0), (0, 1), (0,2), (1, 0), (1, 1), (2, 0)])
229            sage: skp.rows_intersection_set() == boxes
230            True
231        """
232        res = []
233        outer = self.outer()
234        inner = self.inner()
235        inner += [0] * int(len(outer)-len(inner))
236
237        for i in range(len(outer)):
238            for j in range(outer[i]):
239                if outer[i] != inner[i]:
240                    res.append((i,j))
241        return Set(res)
242
243    def columns_intersection_set(self):
244        """
245        Returns the set of boxes in the lines of lambda which intersect the
246        skew partition.
247
248        EXAMPLES:
249            sage: skp = SkewPartition([[3,2,1],[2,1]])
250            sage: boxes = Set([ (0,0), (0, 1), (0,2), (1, 0), (1, 1), (2, 0)])
251            sage: skp.columns_intersection_set() == boxes
252            True
253        """
254        res = [ (x[1], x[0]) for x in self.conjugate().rows_intersection_set()]
255        return Set(res)
256
257
258    def pieri_macdonald_coeffs(self):
259        """
260        Computation of the coefficients which appear in the Pieri formula
261        for Macdonald polynomails given in his book ( Chapter 6.6
262        formula 6.24(ii) )
263
264        EXAMPLES:
265            sage: SkewPartition([[3,2,1],[2,1]]).pieri_macdonald_coeffs()
266            1
267            sage: SkewPartition([[3,2,1],[2,2]]).pieri_macdonald_coeffs()
268            (q^2*t^3 - q^2*t - t^2 + 1)/(q^2*t^3 - q*t^2 - q*t + 1)
269            sage: SkewPartition([[3,2,1],[2,2,1]]).pieri_macdonald_coeffs()
270            (q^6*t^8 - q^6*t^6 - q^4*t^7 - q^5*t^5 + q^4*t^5 - q^3*t^6 + q^5*t^3 + 2*q^3*t^4 + q*t^5 - q^3*t^2 + q^2*t^3 - q*t^3 - q^2*t - t^2 + 1)/(q^6*t^8 - q^5*t^7 - q^5*t^6 - q^4*t^6 + q^3*t^5 + 2*q^3*t^4 + q^3*t^3 - q^2*t^2 - q*t^2 - q*t + 1)
271            sage: SkewPartition([[3,3,2,2],[3,2,2,1]]).pieri_macdonald_coeffs()
272            (q^5*t^6 - q^5*t^5 + q^4*t^6 - q^4*t^5 - q^4*t^3 + q^4*t^2 - q^3*t^3 - q^2*t^4 + q^3*t^2 + q^2*t^3 - q*t^4 + q*t^3 + q*t - q + t - 1)/(q^5*t^6 - q^4*t^5 - q^3*t^4 - q^3*t^3 + q^2*t^3 + q^2*t^2 + q*t - 1)
273        """
274       
275        set_prod = self.rows_intersection_set() - self.columns_intersection_set()
276        res = 1
277        for s in set_prod:
278            res *= self.inner().arms_legs_coeff(s[0],s[1])
279            res /= self.outer().arms_legs_coeff(s[0],s[1])
280        return res
281
282    def k_conjugate(self, k):
283        """
284        Returns the k-conjugate of the skew partition.
285
286        EXAMPLES:
287            sage: SkewPartition([[3,2,1],[2,1]]).k_conjugate(3)
288            [[2, 1, 1, 1, 1], [2, 1]]
289            sage: SkewPartition([[3,2,1],[2,1]]).k_conjugate(4)
290            [[2, 2, 1, 1], [2, 1]]
291            sage: SkewPartition([[3,2,1],[2,1]]).k_conjugate(5)
292            [[3, 2, 1], [2, 1]]
293        """
294        return SkewPartition([ self.outer().k_conjugate(k), self.inner().k_conjugate(k) ])
295
296    def jacobi_trudi(self):
297        """
298        EXAMPLES:
299            sage: SkewPartition([[3,2,1],[2,1]]).jacobi_trudi()
300            [h[1]    0    0]
301            [h[3] h[1]    0]
302            [h[5] h[3] h[1]]
303            sage: SkewPartition([[4,3,2],[2,1]]).jacobi_trudi()
304            [h[2]  h[]    0]
305            [h[4] h[2]  h[]]
306            [h[6] h[4] h[2]]
307        """
308        p = self.outer()
309        q = self.inner()
310        if len(p) == 0 and len(q) == 0:
311            return MatrixSpace(sfa.SFAHomogeneous(QQ), 0)(0)
312        nn = len(p)
313        h = sfa.SFAHomogeneous(QQ)
314        H = MatrixSpace(h, nn)
315
316        q  = q + [0]*int(nn-len(q))
317        m = []
318        for i in range(1,nn+1):
319            row = []
320            for j in range(1,nn+1):
321                v = p[j-1]-q[i-1]-j+i
322                if v < 0:
323                    row.append(h(0))
324                elif v == 0:
325                    row.append(h([]))
326                else:
327                    row.append(h([v]))
328            m.append(row)
329        return H(m)
330
331    def overlap(self):
332        """
333        """
334        return overlap_aux(self)
335
336def overlap_aux(skp):
337    """
338    Returns the overlap of the skew partition skp.
339
340    EXAMPLES:
341        sage: overlap = sage.combinat.skew_partition.overlap_aux
342        sage: overlap([[],[]])
343        +Infinity
344        sage: overlap([[1],[]])
345        +Infinity
346        sage: overlap([[10],[2]])
347        +Infinity
348        sage: overlap([[10,1],[2]])
349        -1
350    """
351    p,q = skp
352    if len(p) <= 1:
353        return infinity
354    if q == []:
355        return min(p)
356    r = [ q[0] ] + q
357    return min(rowlengths_aux([p,r]))
358
359def rowlengths_aux(skp):
360    """
361
362    """
363    if skp[0] == []:
364        return []
365    else:
366        return map(lambda x: x[0] - x[1], zip(skp[0], skp[1]))
367
368def SkewPartitions(n=None, row_lengths=None, overlap=0):
369    """
370    Returns the combinatorial class of skew partitions.
371
372    EXAMPLES:
373    """
374    number_of_arguments = 0
375    for arg in ['n', 'row_lengths']:
376        if eval(arg) is not None:
377            number_of_arguments += 1
378
379    if number_of_arguments > 1:
380        raise ValueError, "you can only specify one of n or row_lengths"
381
382    if number_of_arguments == 0:
383        return SkewPartitions_all()
384   
385    if n is not None:
386        return SkewPartitions_n(n, overlap)
387    else:
388        return SkewPartitions_rowlengths(row_lengths, overlap)
389
390class SkewPartitions_all(CombinatorialClass):
391    def __init__(self):
392        """
393        TESTS:
394            sage: S = SkewPartitions()
395            sage: S == loads(dumps(S))
396            True
397        """
398        pass
399   
400    object_class = SkewPartition_class
401   
402    def __contains__(self, x):
403        """
404        TESTS:
405            sage: [[], []] in SkewPartitions()
406            True
407            sage: [[], [1]] in SkewPartitions()
408            False
409            sage: [[], [-1]] in SkewPartitions()
410            False
411            sage: [[], [0]] in SkewPartitions()
412            False
413            sage: [[3,2,1],[]] in SkewPartitions()
414            True
415            sage: [[3,2,1],[1]] in SkewPartitions()
416            True
417            sage: [[3,2,1],[2]] in SkewPartitions()
418            True
419            sage: [[3,2,1],[3]] in SkewPartitions()
420            True
421            sage: [[3,2,1],[4]] in SkewPartitions()
422            False           
423            sage: [[3,2,1],[1,1]] in SkewPartitions()
424            True
425            sage: [[3,2,1],[1,2]] in SkewPartitions()
426            False
427            sage: [[3,2,1],[2,1]] in SkewPartitions()
428            True
429            sage: [[3,2,1],[2,2]] in SkewPartitions()
430            True
431            sage: [[3,2,1],[3,2]] in SkewPartitions()
432            True
433            sage: [[3,2,1],[1,1,1]] in SkewPartitions()
434            True
435            sage: [[7, 4, 3, 2], [8, 2, 1]] in SkewPartitions()
436            False
437            sage: [[7, 4, 3, 2], [5, 2, 1]] in SkewPartitions()
438            True
439        """
440        if isinstance(x, SkewPartition_class):
441            return True
442       
443        try:
444            if len(x) != 2:
445                return False
446        except:
447            return False
448
449        p = sage.combinat.partition.Partitions()
450        if x[0] not in p:
451            return False
452        if x[1] not in p:
453            return False
454
455        if not sage.combinat.partition.Partition(x[0]).dominates(x[1]):
456            return False
457
458        return True
459       
460    def __repr__(self):
461        """
462        TESTS:
463            sage: repr(SkewPartitions())
464            'Skew partitions'
465        """
466        return "Skew partitions"
467   
468    def list(self):
469        """
470        TESTS:
471            sage: SkewPartitions().list()
472            Traceback (most recent call last):
473            ...
474            NotImplementedError
475        """
476        raise NotImplementedError
477
478class SkewPartitions_n(CombinatorialClass):
479    def __init__(self, n, overlap=0):
480        """
481        TESTS:
482            sage: S = SkewPartitions(3)
483            sage: S == loads(dumps(S))
484            True
485            sage: S = SkewPartitions(3, overlap=1)
486            sage: S == loads(dumps(S))
487            True
488        """
489        self.n = n
490        if overlap == 'connected':
491            self.overlap = 1
492        else:
493            self.overlap = overlap
494           
495    object_class = SkewPartition_class
496
497    def __contains__(self, x):
498        """
499        TESTS:
500            sage: [[],[]] in SkewPartitions(0)
501            True
502            sage: [[3,2,1], []] in SkewPartitions(6)
503            True
504            sage: [[3,2,1], []] in SkewPartitions(7)
505            False
506            sage: [[3,2,1], []] in SkewPartitions(5)
507            False
508            sage: [[7, 4, 3, 2], [8, 2, 1]] in SkewPartitions(8)
509            False
510            sage: [[7, 4, 3, 2], [5, 2, 1]] in SkewPartitions(8)
511            False
512            sage: [[7, 4, 3, 2], [5, 2, 1]] in SkewPartitions(5)
513            False
514            sage: [[7, 4, 3, 2], [5, 2, 1]] in SkewPartitions(5, overlap=-1)
515            False
516            sage: [[7, 4, 3, 2], [5, 2, 1]] in SkewPartitions(8, overlap=-1)
517            True
518            sage: [[7, 4, 3, 2], [5, 2, 1]] in SkewPartitions(8, overlap=0)
519            False
520            sage: [[7, 4, 3, 2], [5, 2, 1]] in SkewPartitions(8, overlap='connected')
521            False
522            sage: [[7, 4, 3, 2], [5, 2, 1]] in SkewPartitions(8, overlap=-2)
523            True
524           
525        """
526        return x in SkewPartitions() and sum(x[0])-sum(x[1]) == self.n and self.overlap <= overlap_aux(x)
527
528   
529    def __repr__(self):
530        """
531        TESTS:
532            sage: repr(SkewPartitions(3))
533            'Skew partitions of 3'
534            sage: repr(SkewPartitions(3, overlap=1))
535            'Skew partitions of 3 with overlap of 1'
536        """
537        string = "Skew partitions of %s"%self.n
538        if self.overlap:
539            string += " with overlap of %s"%self.overlap
540        return string
541   
542   
543    def _count_slide(self, co, overlap=0):
544        """
545        // auxiliary function for count
546        // count_slide(compo, overlap) counts all the skew partitions related to
547        // the composition co by 'sliding'. (co has is the list of rowLengths).
548        // See fromRowLengths_aux function and note that if connected, skew partitions
549        // are nn = min(ck_1, ck)-1 but the for loop begins in step 0.
550        // The skew partitions are unconnected if overlap = 0 (default case).
551        """
552        nn = len(co)
553        result = 1
554        for i in range(nn-1):
555            comb    = min(co[i], co[i+1])
556            comb   += 1 - overlap
557            result *= comb
558
559        return result
560
561    def count(self):
562        """
563        Returns the number of skew partitions of the integer n.
564
565        EXAMPLES:
566        """
567        n = self.n
568        overlap = self.overlap
569       
570        if n == 0:
571            return 1
572
573        if overlap > 0:
574            gg = sage.combinat.composition.Compositions(n, min_part = overlap).iterator()
575        else:
576            gg = sage.combinat.composition.Compositions(n).iterator()
577
578        sum_a = 0
579        for co in gg:
580            sum_a += self._count_slide(co, overlap=overlap)
581
582        return sum_a
583
584    def list(self):
585        """
586        Returns a list of the skew partitions of n.
587
588        EXAMPLES:
589            sage: SkewPartitions(3).list()
590            [[[1, 1, 1], []],
591             [[2, 2, 1], [1, 1]],
592             [[2, 1, 1], [1]],
593             [[3, 2, 1], [2, 1]],
594             [[2, 2], [1]],
595             [[3, 2], [2]],
596             [[2, 1], []],
597             [[3, 1], [1]],
598             [[3], []]]
599            sage: SkewPartitions(3, overlap=0).list()
600            [[[1, 1, 1], []],
601             [[2, 2, 1], [1, 1]],
602             [[2, 1, 1], [1]],
603             [[3, 2, 1], [2, 1]],
604             [[2, 2], [1]],
605             [[3, 2], [2]],
606             [[2, 1], []],
607             [[3, 1], [1]],
608             [[3], []]]
609            sage: SkewPartitions(3, overlap=1).list()
610            [[[1, 1, 1], []], [[2, 2], [1]], [[2, 1], []], [[3], []]]
611            sage: SkewPartitions(3, overlap=2).list()
612            [[[3], []]]
613            sage: SkewPartitions(3, overlap=3).list()
614            [[[3], []]]
615            sage: SkewPartitions(3, overlap=4).list()
616            []
617
618        """
619        n = self.n
620        overlap = self.overlap
621
622        result = []
623        for co in sage.combinat.composition.Compositions(n, min_part=overlap).list():
624            result += SkewPartitions(row_lengths=co, overlap=overlap).list()
625
626        return result
627   
628######################################
629# Skew Partitions (from row lengths) #
630######################################
631class SkewPartitions_rowlengths(CombinatorialClass):
632    """
633    The combinatorial class of all skew partitions with
634    given row lengths.
635   
636    """
637    def __init__(self, co, overlap=0):
638        """
639        TESTS:
640            sage: S = SkewPartitions(row_lengths=[2,1])
641            sage: S == loads(dumps(S))
642            True
643        """
644        self.co = co
645        if overlap == 'connected':
646            self.overlap = 1
647        else:
648            self.overlap = overlap
649
650    object_class = SkewPartition_class
651   
652    def __contains__(self, x):
653        valid = x in SkewPartitions()
654        if valid:
655            o = x[0]
656            i = x[1]+[0]*(len(x[0])-len(x[1]))
657            return [x[0]-x[1] for x in zip(o,i)] == self.co
658   
659
660    def __repr__(self):
661        """
662        TESTS:
663            sage: repr(SkewPartitions(row_lengths=[2,1]))
664            'Skew partitions with row lengths [2, 1]'
665        """
666        return "Skew partitions with row lengths %s"%self.co
667
668    def _from_row_lengths_aux(self, sskp, ck_1, ck, overlap=0):
669        """
670        // auxiliary function for fromRowLengths
671        // fromRowLengths_aux(skp, ck_1, ck, overlap) is a step in the computation of
672        // the skew partitions related to the composition [c1,c2,..ck-1,ck].
673        // skp corresponds to a skew partition related to [c1,c2,..ck-1],
674        // and fromRowLengths_aux computes all the possibilities when sliding part
675        // 'ck' added to the top of skp. (old 'slide function')
676        // The skew partitions are unconnected if overlap = 0 (default case).
677
678        """
679        lskp = []
680        nn = min(ck_1, ck)
681        mm = max(0, ck-ck_1)
682        # nn should be >= 0.  In the case of the positive overlap,
683        # the min_part condition insures ck>=overlap for all k
684
685        nn -= overlap
686        for i in range(nn+1):
687            (skp1, skp2) = sskp
688            skp2 += [0]*(len(skp1)-len(skp2))
689            skp1 = map(lambda x: x + i + mm, skp1)
690            skp1 += [ck]
691            skp2 = map(lambda x: x + i + mm, skp2)
692            skp2 = filter(lambda x: x != 0, skp2)
693            lskp += [ SkewPartition([skp1, skp2]) ]
694        return lskp
695
696
697    def list(self):
698        """
699        Returns a list of all the skew partitions that have row lengths
700        given by the composition self.co.
701
702        EXAMPLES:
703            sage: SkewPartitions(row_lengths=[2,2]).list()
704            [[[2, 2], []], [[3, 2], [1]], [[4, 2], [2]]]
705            sage: SkewPartitions(row_lengths=[2,2], overlap=1).list()
706            [[[2, 2], []], [[3, 2], [1]]]
707        """
708        co = self.co
709        overlap = self.overlap
710
711        if co == []:
712            return [ SkewPartition([[],[]]) ]
713
714        nn = len(co) 
715        if nn == 1:
716            return [ SkewPartition([[co[0]],[]]) ]
717
718        result = []
719        for sskp in SkewPartitions(row_lengths=co[:-1], overlap=overlap):
720            result += self._from_row_lengths_aux(sskp, co[-2], co[-1], overlap)
721        return result
722
723
724
725
726
Note: See TracBrowser for help on using the repository browser.