Coverage for local/lib/python2.7/site-packages/sage/combinat/partition.py: 76%

sage: loads(b'x\x9ck`J.NLO\xd5K\xce\xcfM\xca\xccK,\xd1+H,*\xc9,\xc9\xcc\xcf\xe3\n\x80\xb1\xe2\x93s\x12\x8b\x8b\xb9\n\x195\x1b\x0b\x99j\x0b\x995BY\xe33\x12\x8b3\nY\xfc\x80\xac\x9c\xcc\xe2\x92B\xd6\xd8B6\r\x88IE\x99y\xe9\xc5z\x99y%\xa9\xe9\xa9E\\\xb9\x89\xd9\xa9\xf10N!{(\xa3qkP!G\x06\x90a\x04dp\x82\x18\x86@\x06Wji\x92\x1e\x00x0.\xb5')

[3, 2, 1]

sage: loads(dumps( Partition([3,2,1]) )) # indirect doctest

[3, 2, 1]

"""

if isinstance(state, dict): # for old pickles from Partition_class

self._set_parent(_Partitions)

self.__dict__ = state

else:

self._set_parent(state[0])

self.__dict__ = state[1]

def __init__(self, parent, mu):

"""

Initialize ``self``.

EXAMPLES::

sage: p = Partition([3,1])

sage: TestSuite(p).run()

TESTS:

Fix that tuples raise the correct error::

sage: Partition((3,1,7))

Traceback (most recent call last):

...

ValueError: [3, 1, 7] is not an element of Partitions

"""

if isinstance(mu, Partition):

# Since we are (suppose to be) immutable, we can share the underlying data

CombinatorialElement.__init__(self, parent, mu._list)

return

elif not mu:

CombinatorialElement.__init__(self, parent, mu)

elif (all(mu[i] in NN and mu[i] >= mu[i+1] for i in range(len(mu)-1))

and mu[-1] in NN):

if mu[-1] == 0: # From the above checks, the last value must be == 0 or > 0

# strip all trailing zeros

temp = len(mu) - 1

while temp > 0 and mu[temp-1] == 0:

temp -= 1

CombinatorialElement.__init__(self, parent, mu[:temp])

else:

CombinatorialElement.__init__(self, parent, mu)

else:

raise ValueError("%s is not a valid partition"%repr(mu))

@cached_method

def __hash__(self):

r"""

Return the hash of ``self``.

TESTS::

sage: P = Partition([4,2,2,1])

sage: hash(P) == hash(P)

True

"""

return hash(tuple(self._list))

def _repr_(self):

r"""

Return a string representation of ``self`` depending on

:meth:`Partitions.options`.

EXAMPLES::

sage: mu=Partition([7,7,7,3,3,2,1,1,1,1,1,1,1]); mu # indirect doctest

[7, 7, 7, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1]

sage: Partitions.options.display="diagram"; mu

*******

***

sage: Partitions.options.display="list"; mu

[7, 7, 7, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1]

sage: Partitions.options.display="compact_low"; mu

1^7,2,3^2,7^3

sage: Partitions.options.display="compact_high"; mu

7^3,3^2,2,1^7

sage: Partitions.options.display="exp_low"; mu

1^7, 2, 3^2, 7^3

sage: Partitions.options.display="exp_high"; mu

7^3, 3^2, 2, 1^7

sage: Partitions.options.convention="French";

sage: mu=Partition([7,7,7,3,3,2,1,1,1,1,1,1,1]); mu # indirect doctest

7^3, 3^2, 2, 1^7

sage: Partitions.options.display="diagram"; mu

***

*******

sage: Partitions.options.display="list"; mu

[7, 7, 7, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1]

sage: Partitions.options.display="compact_low"; mu

1^7,2,3^2,7^3

sage: Partitions.options.display="compact_high"; mu

7^3,3^2,2,1^7

sage: Partitions.options.display="exp_low"; mu

1^7, 2, 3^2, 7^3

sage: Partitions.options.display="exp_high"; mu

7^3, 3^2, 2, 1^7

sage: Partitions.options._reset()

"""

return self.parent().options._dispatch(self, '_repr_', 'display')

def _ascii_art_(self):

"""

TESTS::

sage: ascii_art(Partitions(5).list())

[ * ]

[ ** * ]

[ *** ** * * ]

[ **** *** * ** * * ]

[ *****, * , ** , * , * , * , * ]

"""

from sage.typeset.ascii_art import AsciiArt

return AsciiArt(self._repr_diagram().splitlines(), baseline=0)

def _unicode_art_(self):

"""

TESTS::

sage: unicode_art(Partitions(5).list())

⎡ ┌┐ ⎤

⎢ ┌┬┐ ├┤ ⎥

⎢ ┌┬┬┐ ┌┬┐ ├┼┘ ├┤ ⎥

⎢ ┌┬┬┬┐ ┌┬┬┐ ├┼┴┘ ├┼┤ ├┤ ├┤ ⎥

⎢ ┌┬┬┬┬┐ ├┼┴┴┘ ├┼┼┘ ├┤ ├┼┘ ├┤ ├┤ ⎥

⎣ └┴┴┴┴┘, └┘ , └┴┘ , └┘ , └┘ , └┘ , └┘ ⎦

sage: Partitions.options.convention = "French"

sage: unicode_art(Partitions(5).list())

⎡ ┌┐ ⎤

⎢ ┌┐ ├┤ ⎥

⎢ ┌┐ ┌┐ ├┤ ├┤ ⎥

⎢ ┌┐ ┌┬┐ ├┤ ├┼┐ ├┤ ├┤ ⎥

⎢ ┌┬┬┬┬┐ ├┼┬┬┐ ├┼┼┐ ├┼┬┐ ├┼┤ ├┼┐ ├┤ ⎥

⎣ └┴┴┴┴┘, └┴┴┴┘, └┴┴┘, └┴┴┘, └┴┘, └┴┘, └┘ ⎦

sage: Partitions.options._reset()

"""

if not self._list:

return u'∅'

if self.parent().options.convention == "English":

data = list(self)

else:

data = list(reversed(self))

txt = [u'┌' + u'┬' * (data[0] - 1) + u'┐']

for i in range(len(data) - 1):

p = data[i]

q = data[i + 1]

if p < q:

txt += [u'├' + u'┼' * p + u'┬' * (q - p - 1) + u'┐']

elif p == q:

txt += [u'├' + u'┼' * (p - 1) + u'┤']

else:

txt += [u'├' + u'┼' * q + u'┴' * (p - q - 1) + u'┘']

txt += [u'└' + u'┴' * (data[-1] - 1) + u'┘']

from sage.typeset.unicode_art import UnicodeArt

return UnicodeArt(txt, baseline=0)

def _repr_list(self):

"""

Return a string representation of ``self`` as a list.

EXAMPLES::

sage: print(Partition([7,7,7,3,3,2,1,1,1,1,1,1,1])._repr_list())

[7, 7, 7, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1]

"""

return '[%s]' % ', '.join('%s'%m for m in self)

def _repr_exp_low(self):

"""

Return a string representation of ``self`` in exponential form (lowest

first).

EXAMPLES::

sage: print(Partition([7,7,7,3,3,2,1,1,1,1,1,1,1])._repr_exp_low())

1^7, 2, 3^2, 7^3

sage: print(Partition([])._repr_exp_low())

"""

if not self._list:

return '-'

exp = self.to_exp()

return '%s' % ', '.join('%s%s' % (m+1, '' if e==1 else '^%s'%e)

for (m,e) in enumerate(exp) if e > 0)

def _repr_exp_high(self):

"""

Return a string representation of ``self`` in exponential form (highest

first).

EXAMPLES::

sage: print(Partition([7,7,7,3,3,2,1,1,1,1,1,1,1])._repr_exp_high())

7^3, 3^2, 2, 1^7

sage: print(Partition([])._repr_exp_high())

"""

if not self._list:

return '-'

exp = self.to_exp()[::-1] # reversed list of exponents

M=max(self)

return '%s' % ', '.join('%s%s' % (M-m, '' if e==1 else '^%s'%e)

for (m,e) in enumerate(exp) if e>0)

def _repr_compact_low(self):

"""

Return a string representation of ``self`` in compact form (exponential

form with lowest first).

EXAMPLES::

sage: print(Partition([7,7,7,3,3,2,1,1,1,1,1,1,1])._repr_compact_low())

1^7,2,3^2,7^3

sage: print(Partition([])._repr_compact_low())

"""

if not self._list:

return '-'

exp = self.to_exp()

return '%s' % ','.join('%s%s' % (m+1, '' if e==1 else '^%s'%e)

for (m,e) in enumerate(exp) if e > 0)

def _repr_compact_high(self):

"""

Return a string representation of ``self`` in compact form (exponential

form with highest first).

EXAMPLES::

sage: print(Partition([7,7,7,3,3,2,1,1,1,1,1,1,1])._repr_compact_high())

7^3,3^2,2,1^7

sage: print(Partition([])._repr_compact_low())

"""

if not self._list:

return '-'

exp = self.to_exp()[::-1] # reversed list of exponents

M=max(self)

return '%s' % ','.join('%s%s' % (M-m, '' if e==1 else '^%s'%e)

for (m,e) in enumerate(exp) if e>0)

def _repr_diagram(self):

r"""

Return a representation of ``self`` as a Ferrers diagram.

EXAMPLES::

sage: print(Partition([7,7,7,3,3,2,1,1,1,1,1,1,1])._repr_diagram())

*******

***

"""

return self.ferrers_diagram()

def level(self):

"""

Return the level of ``self``, which is always 1.

This method exists only for compatibility with

:class:`PartitionTuples`.

EXAMPLES::

sage: Partition([4,3,2]).level()

"""

return 1

def components(self):

"""

Return a list containing the shape of ``self``.

This method exists only for compatibility with

:class:`PartitionTuples`.

EXAMPLES::

sage: Partition([3,2]).components()

[[3, 2]]

"""

return [ self ]

def _latex_(self):

r"""

Return a LaTeX version of ``self``.

For more on the latex options, see :meth:`Partitions.options`.

EXAMPLES::

sage: mu = Partition([2, 1])

sage: Partitions.options.latex='diagram'; latex(mu) # indirect doctest

{\def\lr#1{\multicolumn{1}{@{\hspace{.6ex}}c@{\hspace{.6ex}}}{\raisebox{-.3ex}{$#1$}}}

\raisebox{-.6ex}{$\begin{array}[b]{*{2}c}\\

\lr{\ast}&\lr{\ast}\\

\lr{\ast}\\

\end{array}$}

}

sage: Partitions.options.latex='exp_high'; latex(mu) # indirect doctest

2,1

sage: Partitions.options.latex='exp_low'; latex(mu) # indirect doctest

1,2

sage: Partitions.options.latex='list'; latex(mu) # indirect doctest

[2, 1]

sage: Partitions.options.latex='young_diagram'; latex(mu) # indirect doctest

{\def\lr#1{\multicolumn{1}{|@{\hspace{.6ex}}c@{\hspace{.6ex}}|}{\raisebox{-.3ex}{$#1$}}}

\raisebox{-.6ex}{$\begin{array}[b]{*{2}c}\cline{1-2}

\lr{\phantom{x}}&\lr{\phantom{x}}\\\cline{1-2}

\lr{\phantom{x}}\\\cline{1-1}

\end{array}$}

}

sage: Partitions.options(latex="young_diagram", convention="french")

sage: Partitions.options.latex='exp_high'; latex(mu) # indirect doctest

2,1

sage: Partitions.options.latex='exp_low'; latex(mu) # indirect doctest

1,2

sage: Partitions.options.latex='list'; latex(mu) # indirect doctest

[2, 1]

sage: Partitions.options.latex='young_diagram'; latex(mu) # indirect doctest

{\def\lr#1{\multicolumn{1}{|@{\hspace{.6ex}}c@{\hspace{.6ex}}|}{\raisebox{-.3ex}{$#1$}}}

\raisebox{-.6ex}{$\begin{array}[t]{*{2}c}\cline{1-1}

\lr{\phantom{x}}\\\cline{1-2}

\lr{\phantom{x}}&\lr{\phantom{x}}\\\cline{1-2}

\end{array}$}

}

sage: Partitions.options._reset()

"""

return self.parent().options._dispatch(self, '_latex_', 'latex')

def _latex_young_diagram(self):

r"""

LaTeX output as a Young diagram.

EXAMPLES::

sage: print(Partition([2, 1])._latex_young_diagram())

{\def\lr#1{\multicolumn{1}{|@{\hspace{.6ex}}c@{\hspace{.6ex}}|}{\raisebox{-.3ex}{$#1$}}}

\raisebox{-.6ex}{$\begin{array}[b]{*{2}c}\cline{1-2}

\lr{\phantom{x}}&\lr{\phantom{x}}\\\cline{1-2}

\lr{\phantom{x}}\\\cline{1-1}

\end{array}$}

}

sage: print(Partition([])._latex_young_diagram())

{\emptyset}

"""

if not self._list:

return "{\\emptyset}"

from sage.combinat.output import tex_from_array

return tex_from_array([ ["\\phantom{x}"]*row_size for row_size in self._list ])

def _latex_diagram(self):

r"""

LaTeX output as a Ferrers' diagram.

EXAMPLES::

sage: print(Partition([2, 1])._latex_diagram())

{\def\lr#1{\multicolumn{1}{@{\hspace{.6ex}}c@{\hspace{.6ex}}}{\raisebox{-.3ex}{$#1$}}}

\raisebox{-.6ex}{$\begin{array}[b]{*{2}c}\\

\lr{\ast}&\lr{\ast}\\

\lr{\ast}\\

\end{array}$}

}

sage: print(Partition([])._latex_diagram())

{\emptyset}

"""

if not self._list:

return "{\\emptyset}"

entry = self.parent().options("latex_diagram_str")

from sage.combinat.output import tex_from_array

return tex_from_array([ [entry]*row_size for row_size in self._list ], False)

def _latex_list(self):

r"""

LaTeX output as a list.

EXAMPLES::

sage: print(Partition([2, 1])._latex_list())

[2, 1]

sage: print(Partition([])._latex_list())

[]

"""

return repr(self._list)

def _latex_exp_low(self):

r"""

LaTeX output in exponential notation (lowest first).

EXAMPLES::

sage: print(Partition([2,2,1])._latex_exp_low())

1,2^{2}

sage: print(Partition([])._latex_exp_low())

{\emptyset}

"""

if not self._list:

return "{\\emptyset}"

exp = self.to_exp()

return '%s' % ','.join('%s%s' % (m+1, '' if e==1 else '^{%s}'%e)

for (m,e) in enumerate(exp) if e > 0)

def _latex_exp_high(self):

r"""

LaTeX output in exponential notation (highest first).

EXAMPLES::

sage: print(Partition([2,2,1])._latex_exp_high())

2^{2},1

sage: print(Partition([])._latex_exp_high())

{\emptyset}

"""

if not self._list:

return "{\\emptyset}"

exp = self.to_exp()[::-1] # reversed list of exponents

M = max(self)

return '%s' % ','.join('%s%s' % (M-m, '' if e==1 else '^{%s}'%e)

for (m,e) in enumerate(exp) if e>0)

def ferrers_diagram(self):

r"""

Return the Ferrers diagram of ``self``.

EXAMPLES::

sage: mu=Partition([5,5,2,1])

sage: Partitions.options(diagram_str='*', convention="english")

sage: print(mu.ferrers_diagram())

*****

sage: Partitions.options(diagram_str='#')

sage: print(mu.ferrers_diagram())

#####

sage: Partitions.options.convention="french"

sage: print(mu.ferrers_diagram())

#####

sage: print(Partition([]).ferrers_diagram())

sage: Partitions.options(diagram_str='-')

sage: print(Partition([]).ferrers_diagram())

(/)

sage: Partitions.options._reset()

"""

diag_str = self.parent().options.diagram_str

if not self._list:

return '-' if diag_str != '-' else "(/)"

if self.parent().options.convention == "English":

return '\n'.join([diag_str * p for p in self])

else:

return '\n'.join([diag_str * p for p in reversed(self)])

def pp(self):

r"""

Prints the Ferrers diagram.

See :meth:`ferrers_diagram` for more on the Ferrers diagram.

EXAMPLES::

sage: Partition([5,5,2,1]).pp()

*****

sage: Partitions.options.convention='French'

sage: Partition([5,5,2,1]).pp()

*****

sage: Partitions.options._reset()

"""

print(self.ferrers_diagram())

def __truediv__(self, p):

"""

Returns the skew partition ``self / p``.

EXAMPLES::

sage: p = Partition([3,2,1])

sage: p/[1,1]

[3, 2, 1] / [1, 1]

sage: p/[3,2,1]

[3, 2, 1] / [3, 2, 1]

sage: p/Partition([1,1])

[3, 2, 1] / [1, 1]

sage: p/[2,2,2]

Traceback (most recent call last):

...

ValueError: To form a skew partition p/q, q must be contained in p.

"""

if not self.contains(p):

raise ValueError("To form a skew partition p/q, q must be contained in p.")

return SkewPartition([self[:], p])

__div__ = __truediv__

def power(self, k):

r"""

Return the cycle type of the `k`-th power of any permutation

with cycle type ``self`` (thus describes the powermap of

symmetric groups).

Equivalent to GAP's ``PowerPartition``.

EXAMPLES::

sage: p = Partition([5,3])

sage: p.power(1)

[5, 3]

sage: p.power(2)

[5, 3]

sage: p.power(3)

[5, 1, 1, 1]

sage: p.power(4)

[5, 3]

Now let us compare this to the power map on `S_8`::

sage: G = SymmetricGroup(8)

sage: g = G([(1,2,3,4,5),(6,7,8)])

sage: g

(1,2,3,4,5)(6,7,8)

sage: g^2

(1,3,5,2,4)(6,8,7)

sage: g^3

(1,4,2,5,3)

sage: g^4

(1,5,4,3,2)(6,7,8)

sage: Partition([3,2,1]).power(3)

[2, 1, 1, 1, 1]

"""

res = []

for i in self:

g = gcd(i, k)

res.extend( [ZZ(i//g)]*int(g) )

res.sort(reverse=True)

return Partition(res)

def __next__(self):

"""

Return the partition that lexicographically follows ``self``. If

``self`` is the last partition, then return ``False``.

EXAMPLES::

sage: next(Partition([4]))

[3, 1]

sage: next(Partition([1,1,1,1]))

False

"""

p = self

n = 0

m = 0

for i in p:

n += i

m += 1

next_p = p[:] + [1]*(n - len(p))

#Check to see if we are at the last (all ones) partition

if p == [1]*n:

return False

#If we are not, then run the ZS1 algorithm.

#Let h be the number of non-one entries in the

#partition

h = 0

for i in next_p:

if i != 1:

h += 1

if next_p[h-1] == 2:

m += 1

next_p[h-1] = 1

h -= 1

else:

r = next_p[h-1] - 1

t = m - h + 1

next_p[h-1] = r

while t >= r :

h += 1

next_p[h-1] = r

t -= r

if t == 0:

m = h

else:

m = h + 1

if t > 1:

h += 1

next_p[h-1] = t

return self.parent()(next_p[:m])

next = __next__

def size(self):

"""

Return the size of ``self``.

EXAMPLES::

sage: Partition([2,2]).size()

sage: Partition([3,2,1]).size()

"""

return sum(self)

def sign(self):

r"""

Return the sign of any permutation with cycle type ``self``.

This function corresponds to a homomorphism from the symmetric

group `S_n` into the cyclic group of order 2, whose kernel

is exactly the alternating group `A_n`. Partitions of sign

`1` are called even partitions while partitions of sign

`-1` are called odd.

EXAMPLES::

sage: Partition([5,3]).sign()

sage: Partition([5,2]).sign()

-1

Zolotarev's lemma states that the Legendre symbol

`\left(\frac{a}{p}\right)` for an integer

`a \pmod p` (`p` a prime number), can be computed

as sign(p_a), where sign denotes the sign of a permutation and

p_a the permutation of the residue classes `\pmod p`

induced by modular multiplication by `a`, provided

`p` does not divide `a`.

We verify this in some examples.

sage: F = GF(11)

sage: a = F.multiplicative_generator();a

sage: plist = [int(a*F(x)) for x in range(1,11)]; plist

[2, 4, 6, 8, 10, 1, 3, 5, 7, 9]

This corresponds to the permutation (1, 2, 4, 8, 5, 10, 9, 7, 3, 6)

(acting the set `\{1,2,...,10\}`) and to the partition

[10].

sage: p = PermutationGroupElement('(1, 2, 4, 8, 5, 10, 9, 7, 3, 6)')

sage: p.sign()

-1

sage: Partition([10]).sign()

-1

sage: kronecker_symbol(11,2)

-1

Now replace `2` by `3`::

sage: plist = [int(F(3*x)) for x in range(1,11)]; plist

[3, 6, 9, 1, 4, 7, 10, 2, 5, 8]

sage: list(range(1, 11))

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

sage: p = PermutationGroupElement('(3,4,8,7,9)')

sage: p.sign()

sage: kronecker_symbol(3,11)

sage: Partition([5,1,1,1,1,1]).sign()

In both cases, Zolotarev holds.

REFERENCES:

:wikipedia:`Zolotarev's_lemma`

"""

return (-1)**(self.size()-self.length())

def standard_tableaux(self):

"""

Return the :class:`standard tableaux<StandardTableaux>` of this shape.

EXAMPLES::

sage: Partition([3,2,2,1]).standard_tableaux()

Standard tableaux of shape [3, 2, 2, 1]

"""

return tableau.StandardTableaux(self)

def up(self):

r"""

Returns a generator for partitions that can be obtained from ``self``

by adding a cell.

EXAMPLES::

sage: [p for p in Partition([2,1,1]).up()]

[[3, 1, 1], [2, 2, 1], [2, 1, 1, 1]]

sage: [p for p in Partition([3,2]).up()]

[[4, 2], [3, 3], [3, 2, 1]]

sage: [p for p in Partition([]).up()]

[[1]]

"""

p = self

previous = p.get_part(0) + 1

for i, current in enumerate(p):

if current < previous:

yield Partition(p[:i] + [ p[i] + 1 ] + p[i+1:])

previous = current

else:

yield Partition(p + [1])

def up_list(self):

"""

Return a list of the partitions that can be formed from ``self`` by

adding a cell.

EXAMPLES::

sage: Partition([2,1,1]).up_list()

[[3, 1, 1], [2, 2, 1], [2, 1, 1, 1]]

sage: Partition([3,2]).up_list()

[[4, 2], [3, 3], [3, 2, 1]]

sage: Partition([]).up_list()

[[1]]

"""

return [p for p in self.up()]

def down(self):

r"""

Return a generator for partitions that can be obtained from ``self``

by removing a cell.

EXAMPLES::

sage: [p for p in Partition([2,1,1]).down()]

[[1, 1, 1], [2, 1]]

sage: [p for p in Partition([3,2]).down()]

[[2, 2], [3, 1]]

sage: [p for p in Partition([3,2,1]).down()]

[[2, 2, 1], [3, 1, 1], [3, 2]]

TESTS:

We check that :trac:`11435` is fixed::

sage: Partition([]).down_list() #indirect doctest

[]

"""

p = self

l = len(p)

for i in range(l-1):

if p[i] > p[i+1]:

yield Partition(p[:i] + [ p[i]-1 ] + p[i+1:])

if l >= 1:

last = p[-1]

if last == 1:

yield Partition(p[:-1])

else:

yield Partition(p[:-1] + [ p[-1] - 1 ])

def down_list(self):

"""

Return a list of the partitions that can be obtained from ``self``

by removing a cell.

EXAMPLES::

sage: Partition([2,1,1]).down_list()

[[1, 1, 1], [2, 1]]

sage: Partition([3,2]).down_list()

[[2, 2], [3, 1]]

sage: Partition([3,2,1]).down_list()

[[2, 2, 1], [3, 1, 1], [3, 2]]

sage: Partition([]).down_list() #checks :trac:`11435`

[]

"""

return [p for p in self.down()]

@combinatorial_map(name="cell poset")

def cell_poset(self, orientation="SE"):

"""

Return the Young diagram of ``self`` as a poset. The optional

keyword variable ``orientation`` determines the order relation

of the poset.

The poset always uses the set of cells of the Young diagram

of ``self`` as its ground set. The order relation of the poset

depends on the ``orientation`` variable (which defaults to

``"SE"``). Concretely, ``orientation`` has to be specified to

one of the strings ``"NW"``, ``"NE"``, ``"SW"``, and ``"SE"``,

standing for "northwest", "northeast", "southwest" and

"southeast", respectively. If ``orientation`` is ``"SE"``, then

the order relation of the poset is such that a cell `u` is

greater or equal to a cell `v` in the poset if and only if `u`

lies weakly southeast of `v` (this means that `u` can be

reached from `v` by a sequence of south and east steps; the

sequence is allowed to consist of south steps only, or of east

steps only, or even be empty). Similarly the order relation is

defined for the other three orientations. The Young diagram is

supposed to be drawn in English notation.

The elements of the poset are the cells of the Young diagram

of ``self``, written as tuples of zero-based coordinates (so

that `(3, 7)` stands for the `8`-th cell of the `4`-th row,

etc.).

EXAMPLES::

sage: p = Partition([3,3,1])

sage: Q = p.cell_poset(); Q

Finite poset containing 7 elements

sage: sorted(Q)

[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0)]

sage: sorted(Q.maximal_elements())

[(1, 2), (2, 0)]

sage: Q.minimal_elements()

[(0, 0)]

sage: sorted(Q.upper_covers((1, 0)))

[(1, 1), (2, 0)]

sage: Q.upper_covers((1, 1))

[(1, 2)]

sage: P = p.cell_poset(orientation="NW"); P

Finite poset containing 7 elements

sage: sorted(P)

[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0)]

sage: sorted(P.minimal_elements())

[(1, 2), (2, 0)]

sage: P.maximal_elements()

[(0, 0)]

sage: P.upper_covers((2, 0))

[(1, 0)]

sage: sorted(P.upper_covers((1, 2)))

[(0, 2), (1, 1)]

sage: sorted(P.upper_covers((1, 1)))

[(0, 1), (1, 0)]

sage: sorted([len(P.upper_covers(v)) for v in P])

[0, 1, 1, 1, 1, 2, 2]

sage: R = p.cell_poset(orientation="NE"); R

Finite poset containing 7 elements

sage: sorted(R)

[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0)]

sage: R.maximal_elements()

[(0, 2)]

sage: R.minimal_elements()

[(2, 0)]

sage: sorted([len(R.upper_covers(v)) for v in R])

[0, 1, 1, 1, 1, 2, 2]

sage: R.is_isomorphic(P)

False

sage: R.is_isomorphic(P.dual())

False

Linear extensions of ``p.cell_poset()`` are in 1-to-1 correspondence

with standard Young tableaux of shape `p`::

sage: all( len(p.cell_poset().linear_extensions())

....: == len(p.standard_tableaux())

....: for n in range(8) for p in Partitions(n) )

True

This is not the case for northeast orientation::

sage: q = Partition([3, 1])

sage: q.cell_poset(orientation="NE").is_chain()

True

TESTS:

We check that the posets are really what they should be for size

up to `7`::

sage: def check_NW(n):

....: for p in Partitions(n):

....: P = p.cell_poset(orientation="NW")

....: for c in p.cells():

....: for d in p.cells():

....: if P.le(c, d) != (c[0] >= d[0]

....: and c[1] >= d[1]):

....: return False

....: return True

sage: all( check_NW(n) for n in range(8) )

True

sage: def check_NE(n):

....: for p in Partitions(n):

....: P = p.cell_poset(orientation="NE")

....: for c in p.cells():

....: for d in p.cells():

....: if P.le(c, d) != (c[0] >= d[0]

....: and c[1] <= d[1]):

....: return False

....: return True

sage: all( check_NE(n) for n in range(8) )

True

sage: def test_duality(n, ori1, ori2):

....: for p in Partitions(n):

....: P = p.cell_poset(orientation=ori1)

....: Q = p.cell_poset(orientation=ori2)

....: for c in p.cells():

....: for d in p.cells():

....: if P.lt(c, d) != Q.lt(d, c):

....: return False

....: return True

sage: all( test_duality(n, "NW", "SE") for n in range(8) )

True

sage: all( test_duality(n, "NE", "SW") for n in range(8) )

True

sage: all( test_duality(n, "NE", "SE") for n in range(4) )

False

"""

from sage.combinat.posets.posets import Poset

covers = {}

if orientation == "NW":

for i, row in enumerate(self):

if i == 0:

covers[(0, 0)] = []

for j in range(1, row):

covers[(0, j)] = [(0, j - 1)]

else:

covers[(i, 0)] = [(i - 1, 0)]

for j in range(1, row):

covers[(i, j)] = [(i - 1, j), (i, j - 1)]

elif orientation == "NE":

for i, row in enumerate(self):

if i == 0:

covers[(0, row - 1)] = []

for j in range(row - 1):

covers[(0, j)] = [(0, j + 1)]

else:

covers[(i, row - 1)] = [(i - 1, row - 1)]

for j in range(row - 1):

covers[(i, j)] = [(i - 1, j), (i, j + 1)]

elif orientation == "SE":

l = len(self) - 1

for i, row in enumerate(self):

if i == l:

covers[(i, row - 1)] = []

for j in range(row - 1):

covers[(i, j)] = [(i, j + 1)]

else:

next_row = self[i + 1]

if row == next_row:

covers[(i, row - 1)] = [(i + 1, row - 1)]

for j in range(row - 1):

covers[(i, j)] = [(i + 1, j), (i, j + 1)]

else:

covers[(i, row - 1)] = []

for j in range(next_row):

covers[(i, j)] = [(i + 1, j), (i, j + 1)]

for j in range(next_row, row - 1):

covers[(i, j)] = [(i, j + 1)]

elif orientation == "SW":

l = len(self) - 1

for i, row in enumerate(self):

if i == l:

covers[(i, 0)] = []

for j in range(1, row):

covers[(i, j)] = [(i, j - 1)]

else:

covers[(i, 0)] = [(i + 1, 0)]

next_row = self[i + 1]

for j in range(1, next_row):

covers[(i, j)] = [(i + 1, j), (i, j - 1)]

for j in range(next_row, row):

covers[(i, j)] = [(i, j - 1)]

return Poset(covers)

def frobenius_coordinates(self):

"""

Return a pair of sequences of Frobenius coordinates aka beta numbers

of the partition.

These are two strictly decreasing sequences of nonnegative integers

of the same length.

EXAMPLES::

sage: Partition([]).frobenius_coordinates()

([], [])

sage: Partition([1]).frobenius_coordinates()

([0], [0])

sage: Partition([3,3,3]).frobenius_coordinates()

([2, 1, 0], [2, 1, 0])

sage: Partition([9,1,1,1,1,1,1]).frobenius_coordinates()

([8], [6])

"""

mu = self

muconj = mu.conjugate() # Naive implementation

if len(mu) <= len(muconj):

a = [x for x in (val-i-1 for i, val in enumerate(mu)) if x>=0]

b = [x for x in (muconj[i]-i-1 for i in range(len(a))) if x>=0]

else:

b = [x for x in (val-i-1 for i, val in enumerate(muconj)) if x>=0]

a = [x for x in (mu[i]-i-1 for i in range(len(b))) if x>=0]

return (a,b)

def frobenius_rank(self):

r"""

Return the Frobenius rank of the partition ``self``.

The Frobenius rank of a partition

`\lambda = (\lambda_1, \lambda_2, \lambda_3, \cdots)` is

defined to be the largest `i` such that `\lambda_i \geq i`.

In other words, it is the number of cells on the main diagonal

of `\lambda`. In yet other words, it is the size of the largest

square fitting into the Young diagram of `\lambda`.

EXAMPLES::

sage: Partition([]).frobenius_rank()

sage: Partition([1]).frobenius_rank()

sage: Partition([3,3,3]).frobenius_rank()

sage: Partition([9,1,1,1,1,1]).frobenius_rank()

sage: Partition([2,1,1,1,1,1]).frobenius_rank()

sage: Partition([2,2,1,1,1,1]).frobenius_rank()

sage: Partition([3,2]).frobenius_rank()

sage: Partition([3,2,2]).frobenius_rank()

sage: Partition([8,4,4,4,4]).frobenius_rank()

sage: Partition([8,4,1]).frobenius_rank()

sage: Partition([3,3,1]).frobenius_rank()

"""

for i, x in enumerate(self):

if x <= i:

return i

return len(self)

def beta_numbers(self, length=None):

"""

Return the set of beta numbers corresponding to ``self``.

The optional argument ``length`` specifies the length of the beta set

(which must be at least the length of ``self``).

For more on beta numbers, see :meth:`frobenius_coordinates`.

EXAMPLES::

sage: Partition([4,3,2]).beta_numbers()

[6, 4, 2]

sage: Partition([4,3,2]).beta_numbers(5)

[8, 6, 4, 1, 0]

sage: Partition([]).beta_numbers()

[]

sage: Partition([]).beta_numbers(3)

[2, 1, 0]

sage: Partition([6,4,1,1]).beta_numbers()

[9, 6, 2, 1]

sage: Partition([6,4,1,1]).beta_numbers(6)

[11, 8, 4, 3, 1, 0]

sage: Partition([1,1,1]).beta_numbers()

[3, 2, 1]

sage: Partition([1,1,1]).beta_numbers(4)

[4, 3, 2, 0]

"""

true_length = len(self)

if length is None:

length = true_length

elif length < true_length:

raise ValueError("length must be at least the length of the partition")

beta = [l + length - i - 1 for (i, l) in enumerate(self)]

if length > true_length:

beta.extend(list(range(length-true_length-1,-1,-1)))

return beta

def crank(self):

r"""

Return the Dyson crank of ``self``.

The Dyson crank of a partition `\lambda` is defined as follows:

If `\lambda` contains at least one `1`, then the crank is

`\mu(\lambda) - \omega(\lambda)`, where `\omega(\lambda)` is the

number of `1`s in `\lambda`, and `\mu(\lambda)` is the number of

parts of `\lambda` larger than `\omega(\lambda)`. If `\lambda`

contains no `1`, then the crank is simply the largest part of

`\lambda`.

REFERENCES:

.. [AG1988] George E. Andrews, F. G. Garvan,

*Dyson's crank of a partition*.

Bull. Amer. Math. Soc. (N.S.) Volume 18, Number 2 (1988),

167-171.

http://projecteuclid.org/euclid.bams/1183554533

EXAMPLES::

sage: Partition([]).crank()

sage: Partition([3,2,2]).crank()

sage: Partition([5,4,2,1,1]).crank()

sage: Partition([1,1,1]).crank()

-3

sage: Partition([6,4,4,3]).crank()

sage: Partition([6,3,3,1,1]).crank()

sage: Partition([6]).crank()

sage: Partition([5,1]).crank()

sage: Partition([4,2]).crank()

sage: Partition([4,1,1]).crank()

-1

sage: Partition([3,3]).crank()

sage: Partition([3,2,1]).crank()

sage: Partition([3,1,1,1]).crank()

-3

sage: Partition([2,2,2]).crank()

sage: Partition([2,2,1,1]).crank()

-2

sage: Partition([2,1,1,1,1]).crank()

-4

sage: Partition([1,1,1,1,1,1]).crank()

-6

"""

l = len(self)

if l == 0:

return 0

if self[-1] > 1:

return self[0]

ind_1 = self.index(1)

w = l - ind_1 # w is omega(self).

m = len([x for x in self if x > w])

return m - w

def t_completion(self, t):

r"""

Return the ``t``-completion of the partition ``self``.

If `\lambda = (\lambda_1, \lambda_2, \lambda_3, \ldots)` is a

partition and `t` is an integer greater or equal to

`\left\lvert \lambda \right\rvert + \lambda_1`, then the

`t`-*completion of* `\lambda` is defined as the partition

`(t - \left\lvert \lambda \right\rvert, \lambda_1, \lambda_2,

\lambda_3, \ldots)` of `t`. This partition is denoted by `\lambda[t]`

in [BOR09]_, by `\lambda_{[t]}` in [BdVO12]_, and by `\lambda(t)`

in [CO10]_.

REFERENCES:

.. [BOR09] Emmanuel Briand, Rosa Orellana, Mercedes Rosas.

*The stability of the Kronecker products of Schur

functions*.

:arxiv:`0907.4652v2`.

.. [CO10] Jonathan Comes, Viktor Ostrik.

*On blocks of Deligne's category*

`\underline{\mathrm{Rep}}(S_t)`.

:arxiv:`0910.5695v2`,

http://pages.uoregon.edu/jcomes/blocks.pdf

.. [BdVO12] Christopher Bowman, Maud De Visscher, Rosa Orellana.

*The partition algebra and the Kronecker coefficients*.

:arXiv:`1210.5579v6`.

EXAMPLES::

sage: Partition([]).t_completion(0)

[]

sage: Partition([]).t_completion(1)

[1]

sage: Partition([]).t_completion(2)

[2]

sage: Partition([]).t_completion(3)

[3]

sage: Partition([2, 1]).t_completion(5)

[2, 2, 1]

sage: Partition([2, 1]).t_completion(6)

[3, 2, 1]

sage: Partition([4, 2, 2, 1]).t_completion(13)

[4, 4, 2, 2, 1]

sage: Partition([4, 2, 2, 1]).t_completion(19)

[10, 4, 2, 2, 1]

sage: Partition([4, 2, 2, 1]).t_completion(10)

Traceback (most recent call last):

...

ValueError: 10-completion is not defined

sage: Partition([4, 2, 2, 1]).t_completion(5)

Traceback (most recent call last):

...

ValueError: 5-completion is not defined

"""

if self._list and t < self.size() + self._list[0]:

raise ValueError("{}-completion is not defined".format(t))

return Partition([t - self.size()] + self._list)

def larger_lex(self, rhs):

"""

Return ``True`` if ``self`` is larger than ``rhs`` in lexicographic

order. Otherwise return ``False``.

EXAMPLES::

sage: p = Partition([3,2])

sage: p.larger_lex([3,1])

True

sage: p.larger_lex([1,4])

True

sage: p.larger_lex([3,2,1])

False

sage: p.larger_lex([3])

True

sage: p.larger_lex([5])

False

sage: p.larger_lex([3,1,1,1,1,1,1,1])

True

"""

return CombinatorialElement.__gt__(self, rhs)

def dominates(self, p2):

r"""

Return ``True`` if ``self`` dominates the partition ``p2``. Otherwise

it returns ``False``.

EXAMPLES::

sage: p = Partition([3,2])

sage: p.dominates([3,1])

True

sage: p.dominates([2,2])

True

sage: p.dominates([2,1,1])

True

sage: p.dominates([3,3])

False

sage: p.dominates([4])

False

sage: Partition([4]).dominates(p)

False

sage: Partition([]).dominates([1])

False

sage: Partition([]).dominates([])

True

sage: Partition([1]).dominates([])

True

"""

p1 = self

sum1 = 0

sum2 = 0

min_length = min(len(p1), len(p2))

if min_length == 0:

return not p2 # equivalent to len(p1) >= len(p2) = 0

for i in range(min_length):

sum1 += p1[i]

sum2 += p2[i]

if sum2 > sum1:

return False

return sum(p1) >= sum(p2)

def cells(self):

"""

Return the coordinates of the cells of ``self``.

EXAMPLES::

sage: Partition([2,2]).cells()

[(0, 0), (0, 1), (1, 0), (1, 1)]

sage: Partition([3,2]).cells()

[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1)]

"""

res = []

for i in range(len(self)):

for j in range(self[i]):

res.append( (i,j) )

return res

def generalized_pochhammer_symbol(self, a, alpha):

r"""

Return the generalized Pochhammer symbol

`(a)_{self}^{(\alpha)}`. This is the product over all

cells `(i,j)` in ``self`` of `a - (i-1) / \alpha + j - 1`.

EXAMPLES::

sage: Partition([2,2]).generalized_pochhammer_symbol(2,1)

"""

res = 1

for (i,j) in self.cells():

res *= (a - (i-1)/alpha + j-1)

return res

def get_part(self, i, default=Integer(0)):

r"""

Return the `i^{th}` part of ``self``, or ``default`` if it does

not exist.

EXAMPLES::

sage: p = Partition([2,1])

sage: p.get_part(0), p.get_part(1), p.get_part(2)

(2, 1, 0)

sage: p.get_part(10,-1)

-1

sage: Partition([]).get_part(0)

"""

if i < len(self._list):

return self._list[i]

else:

return default

@combinatorial_map(name="partition to minimal Dyck word")

def to_dyck_word(self, n=None):

r"""

Return the ``n``-Dyck word whose corresponding partition is

``self`` (or, if ``n`` is not specified, the `n`-Dyck word with

smallest `n` to satisfy this property).

If `w` is an `n`-Dyck word (that is, a Dyck word with `n` open

symbols and `n` close symbols), then the Dyck path corresponding

to `w` can be regarded as a lattice path in the northeastern

half of an `n \times n`-square. The region to the northeast of

this Dyck path can be regarded as a partition. It is called the

partition corresponding to the Dyck word `w`. (See

:meth:`~sage.combinat.dyck_word.DyckWord.to_partition`.)

For every partition `\lambda` and every nonnegative integer `n`,

there exists at most one `n`-Dyck word `w` such that the

partition corresponding to `w` is `\lambda` (in fact, such `w`

exists if and only if `\lambda_i + i \leq n` for every `i`,

where `\lambda` is written in the form

`(\lambda_1, \lambda_2, \ldots, \lambda_k)` with `\lambda_k > 0`).

This method computes this `w` for a given `\lambda` and `n`.

If `n` is not specified, this method computes the `w` for the

smallest possible `n` for which such an `w` exists.

(The minimality of `n` means that the partition demarcated by the

Dyck path touches the diagonal.)

EXAMPLES::

sage: Partition([2,2]).to_dyck_word()

[1, 1, 0, 0, 1, 1, 0, 0]

sage: Partition([2,2]).to_dyck_word(4)

[1, 1, 0, 0, 1, 1, 0, 0]

sage: Partition([2,2]).to_dyck_word(5)

[1, 1, 1, 0, 0, 1, 1, 0, 0, 0]

sage: Partition([6,3,1]).to_dyck_word()

[1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0]

sage: Partition([]).to_dyck_word()

[]

sage: Partition([]).to_dyck_word(3)

[1, 1, 1, 0, 0, 0]

The partition corresponding to ``self.dyck_word()`` is ``self``

indeed::

sage: all( p.to_dyck_word().to_partition() == p

....: for p in Partitions(5) )

True

"""

from sage.combinat.dyck_word import DyckWord

if not self._list:

if n is None:

return DyckWord([])

return DyckWord([1]*n + [0]*n)

list_of_word = []

if n is None:

n = max(i + l + 1 for (i, l) in enumerate(self))

# This n is also max(i+j for (i,j) in self.cells()) + 2.

list_of_word.extend([1]*(n-self.length()))

copy_part = list(self)

while copy_part:

c = copy_part.pop()

list_of_word.extend([0]*c)

for i in range(len(copy_part)):

copy_part[i] -= c

list_of_word.append(1)

list_of_word.extend([0]*(n-self[0]))

return DyckWord(list_of_word)

@combinatorial_map(order=2, name="conjugate partition")

def conjugate(self):

"""

Return the conjugate partition of the partition ``self``. This

is also called the associated partition or the transpose in the

literature.

EXAMPLES::

sage: Partition([2,2]).conjugate()

[2, 2]

sage: Partition([6,3,1]).conjugate()

[3, 2, 2, 1, 1, 1]

The conjugate partition is obtained by transposing the Ferrers

diagram of the partition (see :meth:`.ferrers_diagram`)::

sage: print(Partition([6,3,1]).ferrers_diagram())

******

***

sage: print(Partition([6,3,1]).conjugate().ferrers_diagram())

***

"""

p = list(self)

if p == []:

return self

l = len(p)

conj = [l] * p[-1]

for i in range(l - 1, 0, -1):

conj.extend([i] * (p[i - 1] - p[i]))

return Partition(conj)

def suter_diagonal_slide(self, n, exp=1):

r"""

Return the image of ``self`` in `Y_n` under Suter's diagonal slide

`\sigma_n`, where the notations used are those defined in [Sut2002]_.

The set `Y_n` is defined as the set of all partitions

`\lambda` such that the hook length of the `(0, 0)`-cell (i.e. the

northwestern most cell in English notation) of `\lambda` is less

than `n`, including the empty partition.

The map `\sigma_n` sends a partition (with non-zero entries)

`(\lambda_1, \lambda_2, \ldots, \lambda_m) \in Y_n` to the partition

`(\lambda_2 + 1, \lambda_3 + 1, \ldots, \lambda_m + 1,

\underbrace{1, 1, \ldots, 1}_{n - m - \lambda_1\text{ ones}})`.

In other words, it pads the partition with trailing zeroes

until it has length `n - \lambda_1`, then removes its first

part, and finally adds `1` to each part.

By Theorem 2.1 of [Sut2002]_, the dihedral group `D_n` with

`2n` elements acts on `Y_n` by letting the primitive rotation

act as `\sigma_n` and the reflection act as conjugation of

partitions (:meth:`conjugate()`). This action is faithful if

`n \geq 3`.

INPUT:

- ``n`` -- nonnegative integer

- ``exp`` -- (default: 1) how many times `\sigma_n` should be applied

OUTPUT:

The result of applying Suter's diagonal slide `\sigma_n` to

``self``, assuming that ``self`` lies in `Y_n`. If the

optional argument ``exp`` is set, then the slide

`\sigma_n` is applied not just once, but ``exp`` times

(note that ``exp`` is allowed to be negative, since

the slide has finite order).

EXAMPLES::

sage: Partition([5,4,1]).suter_diagonal_slide(8)

[5, 2]

sage: Partition([5,4,1]).suter_diagonal_slide(9)

[5, 2, 1]

sage: Partition([]).suter_diagonal_slide(7)

[1, 1, 1, 1, 1, 1]

sage: Partition([]).suter_diagonal_slide(1)

[]

sage: Partition([]).suter_diagonal_slide(7, exp=-1)

[6]

sage: Partition([]).suter_diagonal_slide(1, exp=-1)

[]

sage: P7 = Partitions(7)

sage: all( p == p.suter_diagonal_slide(9, exp=-1).suter_diagonal_slide(9)

....: for p in P7 )

True

sage: all( p == p.suter_diagonal_slide(9, exp=3)

....: .suter_diagonal_slide(9, exp=3)

....: for p in P7 )

True

sage: all( p == p.suter_diagonal_slide(9, exp=6)

....: .suter_diagonal_slide(9, exp=6)

....: for p in P7 )

True

sage: all( p == p.suter_diagonal_slide(9, exp=-1)

....: .suter_diagonal_slide(9, exp=1)

....: for p in P7 )

True

Check of the assertion in [Sut2002]_ that `\sigma_n\bigl( \sigma_n(

\lambda^{\prime})^{\prime} \bigr) = \lambda`::

sage: all( p.suter_diagonal_slide(8).conjugate()

....: == p.conjugate().suter_diagonal_slide(8, exp=-1)

....: for p in P7 )

True

Check of Claim 1 in [Sut2002]_::

sage: P5 = Partitions(5)

sage: all( all( (p.suter_diagonal_slide(6) in q.suter_diagonal_slide(6).down())

....: or (q.suter_diagonal_slide(6) in p.suter_diagonal_slide(6).down())

....: for p in q.down() )

....: for q in P5 )

True

TESTS:

Check for ``exp = 0``::

sage: P = Partitions(4)

sage: all(p == p.suter_diagonal_slide(7, 0) for p in P)

True

Check for invalid input::

sage: p = Partition([2,1])

sage: p.hook_length(0, 0)

sage: p.suter_diagonal_slide(2)

Traceback (most recent call last):

...

ValueError: the hook length must be less than n

REFERENCES:

.. [Sut2002] Ruedi Suter.

*Young's Lattice and Dihedral Symmetries*.

Europ. J. Combinatorics (2002) 23, 233--238.

http://www.sciencedirect.com/science/article/pii/S0195669801905414

"""

# Check for valid input

if len(self) > 0 and len(self) + self._list[0] > n: # >, not >=, since we double count the (0,0) cell

raise ValueError("the hook length must be less than n")

ret = self

# Arbitrary exp

exp = exp % n # It is at most order n

if exp > n / 2:

exp -= n

while exp != 0:

leng = len(ret)

if exp > 0:

# Suter's map \sigma_n

if leng == 0: # Taking extra care about the empty partition.

ret = Partition([1] * (n - 1))

exp -= 1

continue

res = [i + 1 for i in ret._list[1:]]

res += [1] * (n - leng - ret._list[0])

ret = Partition(res)

exp -= 1

else: # exp < 0 since if exp == 0, we would exit the while loop

# inverse map \sigma_n^{-1}

if leng == 0: # Taking extra care about the empty partition.

ret = Partition([n - 1])

exp += 1

continue

res = [n - leng - 1]

res.extend([i - 1 for i in ret._list if i > 1])

ret = Partition(res)

exp += 1

return ret

@combinatorial_map(name="reading tableau")

def reading_tableau(self):

r"""

Return the RSK recording tableau of the reading word of the

(standard) tableau `T` labeled down (in English convention)

each column to the shape of ``self``.

For an example of the tableau `T`, consider the partition

`\lambda = (3,2,1)`, then we have::

1 4 6

2 5

For more, see :func:`~sage.combinat.rsk.RSK()`.

EXAMPLES::

sage: Partition([3,2,1]).reading_tableau()

[[1, 3, 6], [2, 5], [4]]

"""

st = tableau.StandardTableaux(self).first()

return st.reading_word_permutation().right_tableau()

@combinatorial_map(name="initial tableau")

def initial_tableau(self):

r"""

Return the :class:`standard tableau<StandardTableau>` which has the

numbers `1, 2, \ldots, n` where `n` is the :meth:`size` of ``self``

entered in order from left to right along the rows of each component,

where the components are ordered from left to right.

EXAMPLES::

sage: Partition([3,2,2]).initial_tableau()

[[1, 2, 3], [4, 5], [6, 7]]

"""

mu = self._list

# In Python 3, improve this using itertools.accumulate

tab = [list(range(1+sum(mu[:i]), 1+sum(mu[:(i+1)])))

for i in range(len(mu))]

return tableau.StandardTableau(tab)

def initial_column_tableau(self):

r"""

Return the initial column tableau of shape ``self``.

The initial column taleau of shape self is the standard tableau

that has the numbers `1` to `n`, where `n` is the :meth:`size` of ``self``,

entered in order from top to bottom and then left to right down the

columns of ``self``.

EXAMPLES::

sage: Partition([3,2]).initial_column_tableau()

[[1, 3, 5], [2, 4]]

"""

return self.conjugate().initial_tableau().conjugate()

def garnir_tableau(self,*cell):

r"""

Return the Garnir tableau of shape ``self`` corresponding to the cell

``cell``. If ``cell`` `= (a,c)` then `(a+1,c)` must belong to the

diagram of ``self``.

The Garnir tableaux play an important role in integral and

non-semisimple representation theory because they determine the

"straightening" rules for the Specht modules over an arbitrary ring.

The Garnir tableaux are the "first" non-standard tableaux which arise

when you act by simple transpositions. If `(a,c)` is a cell in the

Young diagram of a partition, which is not at the bottom of its

column, then the corresponding Garnir tableau has the integers

`1, 2, \ldots, n` entered in order from left to right along the rows

of the diagram up to the cell `(a,c-1)`, then along the cells

`(a+1,1)` to `(a+1,c)`, then `(a,c)` until the end of row `a` and

then continuing from left to right in the remaining positions. The

examples below probably make this clearer!

.. NOTE::

The function also sets ``g._garnir_cell``, where ``g`` is the

resulting Garnir tableau, equal to ``cell`` which is used by

some other functions.

EXAMPLES::

sage: g=Partition([5,3,3,2]).garnir_tableau((0,2)); g.pp()

1 2 6 7 8

3 4 5

9 10 11

12 13

sage: g.is_row_strict(); g.is_column_strict()

True

False

sage: Partition([5,3,3,2]).garnir_tableau(0,2).pp()

1 2 6 7 8

3 4 5

9 10 11

12 13

sage: Partition([5,3,3,2]).garnir_tableau(2,1).pp()

1 2 3 4 5

6 7 8

9 12 13

10 11

sage: Partition([5,3,3,2]).garnir_tableau(2,2).pp()

Traceback (most recent call last):

...

ValueError: (row+1, col) must be inside the diagram

.. SEEALSO::

- :meth:`top_garnir_tableau`

"""

try:

(row,col)=cell

except ValueError:

(row,col)=cell[0]

if row+1>=len(self) or col>=self[row+1]:

raise ValueError('(row+1, col) must be inside the diagram')

g=self.initial_tableau().to_list()

a=g[row][col]

g[row][col:] = list(range(a+col+1,g[row+1][col]+1))

g[row+1][:col+1] = list(range(a,a+col+1))

g=tableau.Tableau(g)

g._garnir_cell=(row,col)

return g

def top_garnir_tableau(self,e,cell):

r"""

Return the most dominant *standard* tableau which dominates the

corresponding Garnir tableau and has the same ``e``-residue.

The Garnir tableau play an important role in integral and non-semisimple

representation theory because they determine the "straightening" rules

for the Specht modules. The *top Garnir tableaux* arise in the graded

representation theory of the symmetric groups and higher level Hecke

algebras. They were introduced in [KMR]_.

If the Garnir node is ``cell=(r,c)`` and `m` and `M` are the entries

in the cells ``(r,c)`` and ``(r+1,c)``, respectively, in the initial

tableau then the top ``e``-Garnir tableau is obtained by inserting the

numbers `m, m+1, \ldots, M` in order from left to right first in the

cells in row ``r+1`` which are not in the ``e``-Garnir belt, then in

the cell in rows ``r`` and ``r+1`` which are in the Garnir belt and

then, finally, in the remaining cells in row ``r`` which are not in

the Garnir belt. All other entries in the tableau remain unchanged.

If ``e = 0``, or if there are no ``e``-bricks in either row ``r``

or ``r+1``, then the top Garnir tableau is the corresponding Garnir

tableau.

EXAMPLES::

sage: Partition([5,4,3,2]).top_garnir_tableau(2,(0,2)).pp()

1 2 4 5 8

3 6 7 9

10 11 12

13 14

sage: Partition([5,4,3,2]).top_garnir_tableau(3,(0,2)).pp()

1 2 3 4 5

6 7 8 9

10 11 12

13 14

sage: Partition([5,4,3,2]).top_garnir_tableau(4,(0,2)).pp()

1 2 6 7 8

3 4 5 9

10 11 12

13 14

sage: Partition([5,4,3,2]).top_garnir_tableau(0,(0,2)).pp()

1 2 6 7 8

3 4 5 9

10 11 12

13 14

TESTS::

sage: Partition([5,4,3,2]).top_garnir_tableau(0,(3,2)).pp()

Traceback (most recent call last):

...

ValueError: (4,2)=(row+1,col) must be inside the diagram

REFERENCE:

- [KMR]_

"""

(row,col)=cell

if row+1>=len(self) or col>=self[row+1]:

raise ValueError('(%s,%s)=(row+1,col) must be inside the diagram' %(row+1,col))

g=self.garnir_tableau(cell) # start with the Garnir tableau and modify

if e==0: return g # no more dominant tableau of the same residue

a=e*int((self[row]-col)/e) # number of cells in the e-bricks in row `row`

b=e*int((col+1)/e) # number of cells in the e-bricks in row `row+1`

if a==0 or b==0: return g

t=g.to_list()

m=g[row+1][0] # smallest number in 0-Garnir belt

# now we will put the number m,m+1,...,t[row+1][col] in order into t

t[row][col:a+col]=[m+col-b+1+i for i in range(a)]

t[row+1][col-b+1:col+1]=[m+a+col-b+1+i for i in range(b)]

return tableau.StandardTableau(t)

@cached_method

def young_subgroup(self):

r"""

Return the corresponding Young, or parabolic, subgroup of the symmetric

group.

The Young subgroup of a partition

`\lambda = (\lambda_1, \lambda_2, \ldots, \lambda_{\ell})` of `n` is

the group:

.. MATH::

S_{\lambda_1} \times S_{\lambda_2} \times \cdots \times

S_{\lambda_{\ell}}

embedded into `S_n` in the standard way (i.e.,

the `S_{\lambda_i}` factor acts on the numbers from

`\lambda_1 + \lambda_2 + \cdots + \lambda_{i-1} + 1` to

`\lambda_1 + \lambda_2 + \cdots + \lambda_i`).

EXAMPLES::

sage: Partition([4,2]).young_subgroup()

Permutation Group with generators [(), (5,6), (3,4), (2,3), (1,2)]

"""

gens=[]

m=0

for row in self:

gens.extend([ (c,c+1) for c in range(m+1,m+row)])

m+=row

gens.append(list(range(1,self.size() + 1))) # to ensure we get a subgroup of Sym_n

return PermutationGroup( gens )

def young_subgroup_generators(self):

"""

Return an indexing set for the generators of the corresponding Young

subgroup. Here the generators correspond to the simple adjacent

transpositions `s_i = (i \; i+1)`.

EXAMPLES::

sage: Partition([4,2]).young_subgroup_generators()

[1, 2, 3, 5]

sage: Partition([1,1,1]).young_subgroup_generators()

[]

sage: Partition([2,2]).young_subgroup_generators()

[1, 3]

.. SEEALSO::

:meth:`young_subgroup`

"""

gens = []

m = 0

for row in self:

gens.extend(list(range(m + 1, m + row)))

m += row

return gens

@cached_method

def _initial_degree(self, e, multicharge=(0,)):

r"""

Return the Brundan-Kleshchev-Wang degree of the initial row tableau

of shape ``self``.

This degree depends only the shape of the tableau and it is

used as the base case for computing the degrees of all tableau

of shape ``self``, which is why this method is cached. See

:meth:`sage.combinat.tableau.Tableau.degree` for more information.

EXAMPLES::

sage: Partition([5,3,2])._initial_degree(0)

sage: Partition([5,3,2])._initial_degree(2)

sage: Partition([5,3,2])._initial_degree(3)

sage: Partition([5,3,2])._initial_degree(4)

"""

if e == 0:

return ZZ.zero()

else:

return sum(m // e for m in self)

def degree(self, e):

r"""

Return the ``e``-th degree of ``self``.

The `e`-th degree of a partition `\lambda` is the sum of the `e`-th

degrees of the standard tableaux of shape `\lambda`. The `e`-th degree

is the exponent of `\Phi_e(q)` in the Gram determinant of the Specht

module for a semisimple Iwahori-Hecke algebra of type `A` with

parameter `q`.

INPUT:

- ``e`` -- an integer `e > 1`

OUTPUT:

A non-negative integer.

EXAMPLES::

sage: Partition([4,3]).degree(2)

sage: Partition([4,3]).degree(3)

sage: Partition([4,3]).degree(4)

sage: Partition([4,3]).degree(5)

sage: Partition([4,3]).degree(6)

sage: Partition([4,3]).degree(7)

Therefore, the Gram determinant of `S(5,3)` when the Hecke parameter

`q` is "generic" is

.. MATH::

q^N \Phi_2(q)^{28} \Phi_3(q)^{15} \Phi_4(q)^8 \Phi_5(q)^{13}

for some integer `N`. Compare with :meth:`prime_degree`.

"""

return sum(t.degree(e) for t in self.standard_tableaux())

def prime_degree(self, p):

r"""

Return the prime degree for the prime integer``p`` for ``self``.

INPUT:

- ``p`` -- a prime integer

OUTPUT:

A non-negative integer

The degree of a partition `\lambda` is the sum of the

`e`-:meth:`degree` of the standard tableaux of shape `\lambda`, for

`e` a poer of the prime `p`. The prime degree gives the exponent of

`p` in the Gram determinant of the integral Specht module of the

symmetric group.

EXAMPLES::

sage: Partition([4,3]).prime_degree(2)

sage: Partition([4,3]).prime_degree(3)

sage: Partition([4,3]).prime_degree(5)

sage: Partition([4,3]).prime_degree(7)

THerefore, the Gram determinant of `S(5,3)` when `q = 1` is

`2^{36} 3^{15} 5^{13}`. Compare with :meth:`degree`.

"""

ps = [p]

while ps[-1] * p < self.size():

ps.append(ps[-1] * p)

return sum(t.degree(pk) for pk in ps for t in self.standard_tableaux())

def arm_length(self, i, j):

r"""

Return the length of the arm of cell `(i,j)` in ``self``.

The arm of cell `(i,j)` is the cells that appear to the right of

cell `(i,j)`.

The cell coordinates are zero-based, i. e., the northwesternmost

cell is `(0,0)`.

INPUT:

- ``i, j`` -- two integers

OUTPUT:

An integer or a ``ValueError``

EXAMPLES::

sage: p = Partition([2,2,1])

sage: p.arm_length(0, 0)

sage: p.arm_length(0, 1)

sage: p.arm_length(2, 0)

sage: Partition([3,3]).arm_length(0, 0)

sage: Partition([3,3]).arm_length(*[0,0])

"""

p = self

if i < len(p) and j < p[i]:

return p[i]-(j+1)

else:

raise ValueError("The cell is not in the diagram")

def arm_lengths(self, flat=False):

"""

Return a tableau of shape ``self`` where each cell is filled with

its arm length. The optional boolean parameter ``flat`` provides

the option of returning a flat list.

EXAMPLES::

sage: Partition([2,2,1]).arm_lengths()

[[1, 0], [1, 0], [0]]

sage: Partition([2,2,1]).arm_lengths(flat=True)

[1, 0, 1, 0, 0]

sage: Partition([3,3]).arm_lengths()

[[2, 1, 0], [2, 1, 0]]

sage: Partition([3,3]).arm_lengths(flat=True)

[2, 1, 0, 2, 1, 0]

"""

p = self

res = [[p[i]-(j+1) for j in range(p[i])] for i in range(len(p))]

if flat:

return sum(res, [])

else:

return res

def arm_cells(self, i, j):

r"""

Return the list of the cells of the arm of cell `(i,j)` in ``self``.

The arm of cell `c = (i,j)` is the boxes that appear to the right of

`c`.

The cell coordinates are zero-based, i. e., the northwesternmost

cell is `(0,0)`.

INPUT:

- ``i, j`` -- two integers

OUTPUT:

A list of pairs of integers

EXAMPLES::

sage: Partition([4,4,3,1]).arm_cells(1,1)

[(1, 2), (1, 3)]

sage: Partition([]).arm_cells(0,0)

Traceback (most recent call last):

...

ValueError: The cell is not in the diagram

"""

p = self

if i < len(p) and j < p[i]:

return [ (i, x) for x in range(j+1, p[i]) ]

else:

raise ValueError("The cell is not in the diagram")

def leg_length(self, i, j):

"""

Return the length of the leg of cell `(i,j)` in ``self``.

The leg of cell `c = (i,j)` is defined to be the cells below `c`

(in English convention).

The cell coordinates are zero-based, i. e., the northwesternmost

cell is `(0,0)`.

INPUT:

- ``i, j`` -- two integers

OUTPUT:

An integer or a ``ValueError``

EXAMPLES::

sage: p = Partition([2,2,1])

sage: p.leg_length(0, 0)

sage: p.leg_length(0,1)

sage: p.leg_length(2,0)

sage: Partition([3,3]).leg_length(0, 0)

sage: cell = [0,0]; Partition([3,3]).leg_length(*cell)

"""

conj = self.conjugate()

if j < len(conj) and i < conj[j]:

return conj[j]-(i+1)

else:

raise ValueError("The cell is not in the diagram")

def leg_lengths(self, flat=False):

"""

Return a tableau of shape ``self`` with each cell filled in with

its leg length. The optional boolean parameter ``flat`` provides

the option of returning a flat list.

EXAMPLES::

sage: Partition([2,2,1]).leg_lengths()

[[2, 1], [1, 0], [0]]

sage: Partition([2,2,1]).leg_lengths(flat=True)

[2, 1, 1, 0, 0]

sage: Partition([3,3]).leg_lengths()

[[1, 1, 1], [0, 0, 0]]

sage: Partition([3,3]).leg_lengths(flat=True)

[1, 1, 1, 0, 0, 0]

"""

p = self

conj = p.conjugate()

res = [[conj[j]-(i+1) for j in range(p[i])] for i in range(len(p))]

if flat:

return sum(res, [])

else:

return res

def leg_cells(self, i, j):

r"""

Return the list of the cells of the leg of cell `(i,j)` in ``self``.

The leg of cell `c = (i,j)` is defined to be the cells below `c` (in

English convention).

The cell coordinates are zero-based, i. e., the northwesternmost

cell is `(0,0)`.

INPUT:

- ``i, j`` -- two integers

OUTPUT:

A list of pairs of integers

EXAMPLES::

sage: Partition([4,4,3,1]).leg_cells(1,1)

[(2, 1)]

sage: Partition([4,4,3,1]).leg_cells(0,1)

[(1, 1), (2, 1)]

sage: Partition([]).leg_cells(0,0)

Traceback (most recent call last):

...

ValueError: The cell is not in the diagram

"""

l = self.leg_length(i, j)

return [(x, j) for x in range(i+1, i+l+1)]

def attacking_pairs(self):

"""

Return a list of the attacking pairs of the Young diagram of

``self``.

A pair of cells `(c, d)` of a Young diagram (in English notation) is

said to be attacking if one of the following conditions holds:

1. `c` and `d` lie in the same row with `c` strictly to the west

of `d`.

2. `c` is in the row immediately to the south of `d`, and `c`

lies strictly east of `d`.

This particular method returns each pair `(c, d)` as a tuple,

where each of `c` and `d` is given as a tuple `(i, j)` with

`i` and `j` zero-based (so `i = 0` means that the cell lies

in the topmost row).

EXAMPLES::

sage: p = Partition([3, 2])

sage: p.attacking_pairs()

[((0, 0), (0, 1)),

((0, 0), (0, 2)),

((0, 1), (0, 2)),

((1, 0), (1, 1)),

((1, 1), (0, 0))]

sage: Partition([]).attacking_pairs()

[]

"""

attacking_pairs = []

for i, r in enumerate(self):

for j in range(r):

#c is in position (i,j)

#Find the d that satisfy condition 1

for k in range(j+1, r):

attacking_pairs.append( ((i,j),(i,k)) )

#Find the d that satisfy condition 2

if i == 0:

continue

for k in range(j):

attacking_pairs.append( ((i,j),(i-1,k)) )

return attacking_pairs

def dominated_partitions(self, rows=None):

"""

Return a list of the partitions dominated by `n`. If ``rows`` is

specified, then it only returns the ones whose number of rows

is at most ``rows``.

EXAMPLES::

sage: Partition([3,2,1]).dominated_partitions()

[[3, 2, 1], [3, 1, 1, 1], [2, 2, 2], [2, 2, 1, 1], [2, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1]]

sage: Partition([3,2,1]).dominated_partitions(rows=3)

[[3, 2, 1], [2, 2, 2]]

"""

#Naive implementation because iteration is so fast

n = sum(self)

P = Partitions_n(n)

if rows:

return [P(x) for x in ZS1_iterator_nk(n, rows) if self.dominates(x)]

else:

return [P(x) for x in ZS1_iterator(n) if self.dominates(x)]

def contains(self, x):

"""

Return ``True`` if ``x`` is a partition whose Ferrers diagram is

contained in the Ferrers diagram of ``self``.

EXAMPLES::

sage: p = Partition([3,2,1])

sage: p.contains([2,1])

True

sage: all(p.contains(mu) for mu in Partitions(3))

True

sage: all(p.contains(mu) for mu in Partitions(4))

False

"""

return len(self) >= len(x) and all(self[i] >= x[i] for i in range(len(x)))

def hook_product(self, a):

"""

Return the Jack hook-product.

EXAMPLES::

sage: Partition([3,2,1]).hook_product(x)

(2*x + 3)*(x + 2)^2

sage: Partition([2,2]).hook_product(x)

2*(x + 2)*(x + 1)

"""

nu = self.conjugate()

res = 1

for i in range(len(self)):

for j in range(self[i]):

res *= a*(self[i]-j-1)+nu[j]-i

return res

def hook_polynomial(self, q, t):

"""

Return the two-variable hook polynomial.

EXAMPLES::

sage: R.<q,t> = PolynomialRing(QQ)

sage: a = Partition([2,2]).hook_polynomial(q,t)

sage: a == (1 - t)*(1 - q*t)*(1 - t^2)*(1 - q*t^2)

True

sage: a = Partition([3,2,1]).hook_polynomial(q,t)

sage: a == (1 - t)^3*(1 - q*t^2)^2*(1 - q^2*t^3)

True

"""

nu = self.conjugate()

res = 1

for i in range(len(self)):

for j in range(self[i]):

res *= 1-q**(self[i]-j-1)*t**(nu[j]-i)

return res

def hook_length(self, i, j):

r"""

Return the length of the hook of cell `(i,j)` in ``self``.

The (length of the) hook of cell `(i,j)` of a partition `\lambda`

.. MATH::

\lambda_i + \lambda^{\prime}_j - i - j + 1

where `\lambda^{\prime}` is the conjugate partition. In English

convention, the hook length is the number of cells horizontally

to the right and vertically below the cell `(i,j)` (including

that cell).

EXAMPLES::

sage: p = Partition([2,2,1])

sage: p.hook_length(0, 0)

sage: p.hook_length(0, 1)

sage: p.hook_length(2, 0)

sage: Partition([3,3]).hook_length(0, 0)

sage: cell = [0,0]; Partition([3,3]).hook_length(*cell)

"""

return self.leg_length(i,j)+self.arm_length(i,j)+1

def hooks(self):

"""

Return a sorted list of the hook lengths in ``self``.

EXAMPLES::

sage: Partition([3,2,1]).hooks()

[5, 3, 3, 1, 1, 1]

"""

res = []

for row in self.hook_lengths():

res += row

res.sort(reverse=True)

return res

def hook_lengths(self):

r"""

Return a tableau of shape ``self`` with the cells filled in with the

hook lengths.

In each cell, put the sum of one plus the number of cells

horizontally to the right and vertically below the cell (the

hook length).

For example, consider the partition ``[3,2,1]`` of 6 with Ferrers

diagram::

# # #

# #

When we fill in the cells with the hook lengths, we obtain::

5 3 1

3 1

EXAMPLES::

sage: Partition([2,2,1]).hook_lengths()

[[4, 2], [3, 1], [1]]

sage: Partition([3,3]).hook_lengths()

[[4, 3, 2], [3, 2, 1]]

sage: Partition([3,2,1]).hook_lengths()

[[5, 3, 1], [3, 1], [1]]

sage: Partition([2,2]).hook_lengths()

[[3, 2], [2, 1]]

sage: Partition([5]).hook_lengths()

[[5, 4, 3, 2, 1]]

REFERENCES:

- http://mathworld.wolfram.com/HookLengthFormula.html

"""

p = self

conj = p.conjugate()

return [[p[i]-(i+1)+conj[j]-(j+1)+1 for j in range(p[i])] for i in range(len(p))]

def upper_hook(self, i, j, alpha):

r"""

Return the upper hook length of the cell `(i,j)` in ``self``.

When ``alpha = 1``, this is just the normal hook length.

The upper hook length of a cell `(i,j)` in a partition

`\kappa` is defined by

.. MATH::

h^*_\kappa(i,j) = \kappa^\prime_j - i + \alpha(\kappa_i - j + 1).

EXAMPLES::

sage: p = Partition([2,1])

sage: p.upper_hook(0,0,1)

sage: p.hook_length(0,0)

sage: [ p.upper_hook(i,j,x) for i,j in p.cells() ]

[2*x + 1, x, x]

"""

p = self

conj = self.conjugate()

return conj[j] - (i+1) + alpha*(p[i]-j)

def upper_hook_lengths(self, alpha):

r"""

Return a tableau of shape ``self`` with the cells filled in with the

upper hook lengths. When ``alpha = 1``, these are just the normal hook

lengths.

The upper hook length of a cell `(i,j)` in a partition

`\kappa` is defined by

.. MATH::

h^*_\kappa(i,j) = \kappa^\prime_j - i + \alpha(\kappa_i - j + 1).

EXAMPLES::

sage: Partition([3,2,1]).upper_hook_lengths(x)

[[3*x + 2, 2*x + 1, x], [2*x + 1, x], [x]]

sage: Partition([3,2,1]).upper_hook_lengths(1)

[[5, 3, 1], [3, 1], [1]]

sage: Partition([3,2,1]).hook_lengths()

[[5, 3, 1], [3, 1], [1]]

"""

p = self

conj = p.conjugate()

return [[conj[j] - (i+1) + alpha*(p[i]-j) for j in range(p[i])] for i in range(len(p))]

def lower_hook(self, i, j, alpha):

r"""

Return the lower hook length of the cell `(i,j)` in ``self``.

When ``alpha = 1``, this is just the normal hook length.

The lower hook length of a cell `(i,j)` in a partition

`\kappa` is defined by

.. MATH::

h_*^\kappa(i,j) = \kappa^\prime_j - i + 1 + \alpha(\kappa_i - j).

EXAMPLES::

sage: p = Partition([2,1])

sage: p.lower_hook(0,0,1)

sage: p.hook_length(0,0)

sage: [ p.lower_hook(i,j,x) for i,j in p.cells() ]

[x + 2, 1, 1]

"""

p = self

conj = self.conjugate()

return conj[j] - i + alpha*(p[i] - (j+1))

def lower_hook_lengths(self, alpha):

r"""

Return a tableau of shape ``self`` with the cells filled in with the

lower hook lengths. When ``alpha = 1``, these are just the normal hook

lengths.

The lower hook length of a cell `(i,j)` in a partition

`\kappa` is defined by

.. MATH::

h_*^\kappa(i,j) = \kappa^\prime_j - i + 1 + \alpha(\kappa_i - j).

EXAMPLES::

sage: Partition([3,2,1]).lower_hook_lengths(x)

[[2*x + 3, x + 2, 1], [x + 2, 1], [1]]

sage: Partition([3,2,1]).lower_hook_lengths(1)

[[5, 3, 1], [3, 1], [1]]

sage: Partition([3,2,1]).hook_lengths()

[[5, 3, 1], [3, 1], [1]]

"""

p = self

conj = p.conjugate()

return [[conj[j] - i + alpha*(p[i]-(j+1)) for j in range(p[i])] for i in range(len(p))]

def weighted_size(self):

r"""

Return the weighted size of ``self``.

The weighted size of a partition `\lambda` is

.. MATH::

\sum_i i \cdot \lambda_i,

where `\lambda = (\lambda_0, \lambda_1, \lambda_2, \cdots )`.

This also the sum of the leg length of every cell in `\lambda`, or

.. MATH::

\sum_i \binom{\lambda^{\prime}_i}{2}

where `\lambda^{\prime}` is the conjugate partition of `\lambda`.

EXAMPLES::

sage: Partition([2,2]).weighted_size()

sage: Partition([3,3,3]).weighted_size()

sage: Partition([5,2]).weighted_size()

sage: Partition([]).weighted_size()

"""

p = self

return sum([i*p[i] for i in range(len(p))])

def is_empty(self):

"""

Return ``True`` if ``self`` is the empty partition.

EXAMPLES::

sage: Partition([]).is_empty()

True

sage: Partition([2,1,1]).is_empty()

False

"""

return len(self) == 0

def length(self):

"""

Return the number of parts in ``self``.

EXAMPLES::

sage: Partition([3,2]).length()

sage: Partition([2,2,1]).length()

sage: Partition([]).length()

"""

return len(self)

def to_exp(self, k=0):

"""

Return a list of the multiplicities of the parts of a partition.

Use the optional parameter ``k`` to get a return list of length at

least ``k``.

EXAMPLES::

sage: Partition([3,2,2,1]).to_exp()

[1, 2, 1]

sage: Partition([3,2,2,1]).to_exp(5)

[1, 2, 1, 0, 0]

TESTS::

sage: [parent(x) for x in Partition([3,2,2,1]).to_exp(5)]

[Integer Ring, Integer Ring, Integer Ring, Integer Ring, Integer Ring]

"""

p = self

if len(p) > 0:

k = max(k, p[0])

a = [ZZ.zero()] * k

for i in p:

a[i-1] += 1

return a

def evaluation(self):

r"""

Return the evaluation of ``self``.

The **commutative evaluation**, often shortened to **evaluation**, of

a word (we think of a partition as a word in `\{1, 2, 3, \ldots\}`)

is its image in the free commutative monoid. In other words,

this counts how many occurrences there are of each letter.

This is also is known as **Parikh vector** and **abelianization** and

has the same output as :meth:`to_exp()`.

EXAMPLES::

sage: Partition([4,3,1,1]).evaluation()

[2, 0, 1, 1]

"""

return self.to_exp()

def to_exp_dict(self):

"""

Return a dictionary containing the multiplicities of the parts of

``self``.

EXAMPLES::

sage: p = Partition([4,2,2,1])

sage: d = p.to_exp_dict()

sage: d[4]

sage: d[2]

sage: d[1]

sage: 5 in d

False

"""

d = {}

for part in self:

d[part] = d.get(part, 0) + 1

return d

def centralizer_size(self, t=0, q=0):

r"""

Return the size of the centralizer of any permutation of cycle type

``self``.

If `m_i` is the multiplicity of `i` as a part of `p`, this is given by

.. MATH::

\prod_i m_i! i^{m_i}.

Including the optional parameters `t` and `q` gives the `q,t` analog,

which is the former product times

.. MATH::

\prod_{i=1}^{\mathrm{length}(p)} \frac{1 - q^{p_i}}{1 - t^{p_i}}.

See [Ker]_.

EXAMPLES::

sage: Partition([2,2,1]).centralizer_size()

sage: Partition([2,2,2]).centralizer_size()

sage: Partition([2,2,1]).centralizer_size(q=2, t=3)

9/16

sage: Partition([]).centralizer_size()

sage: Partition([]).centralizer_size(q=2, t=4)

"""

size = prod(i ** mi * factorial(mi)

for i, mi in six.iteritems(self.to_exp_dict()))

if t or q:

size *= prod((ZZ.one() - q ** j) / (ZZ.one() - t ** j)

for j in self)

return size

def aut(self):

r"""

Return a factor for the number of permutations with cycle type

``self``.

This method returns `1^{j_1}j_1! \cdots n^{j_n}j_n!` where

`j_k` is the number of parts in ``self`` equal to `k`.

The number of permutations having ``self`` as a cycle type is

given by

.. MATH::

\frac{n!}{1^{j_1}j_1! \cdots n^{j_n}j_n!}

(where `n` is the size of ``self``).

EXAMPLES::

sage: Partition([2,1]).aut()

"""

m = self.to_exp()

return prod([(i+1)**m[i]*factorial(m[i]) for i in range(len(m)) if m[i] > 0])

def content(self, r, c, multicharge=(0,)):

r"""

Return the content of the cell at row `r` and column `c`.

The content of a cell is `c - r`.

For consistency with partition tuples there is also an optional

``multicharge`` argument which is an offset to the usual content. By

setting the ``multicharge`` equal to the 0-element of the ring

`\ZZ/e\ZZ`, the corresponding `e`-residue will be returned. This is

the content modulo `e`.

The content (and residue) do not strictly depend on the partition,

however, this method is included because it is often useful in the

context of partitions.

EXAMPLES::

sage: Partition([2,1]).content(1,0)

-1

sage: p = Partition([3,2])

sage: sum([p.content(*c) for c in p.cells()])

and now we return the 3-residue of a cell::

sage: Partition([2,1]).content(1,0, multicharge=[IntegerModRing(3)(0)])

"""

return c - r + multicharge[0]

def residue(self, r, c, l):

"""

Return the ``l``-residue of the cell at row ``r`` and column ``c``.

The `\ell`-residue of a cell is `c - r` modulo `\ell`.

This does not strictly depend upon the partition, however, this method

is included because it is often useful in the context of partitions.

EXAMPLES::

sage: Partition([2,1]).residue(1, 0, 3)

"""

return (c - r) % l

def defect(self, e, multicharge=(0,)):

r"""

Return the ``e``-defect or the ``e``-weight of ``self``.

The `e`-defect is the number of (connected) `e`-rim hooks that

can be removed from the partition.

The defect of a partition is given by

.. MATH::

\text{defect}(\beta) = (\Lambda, \beta) - \tfrac12(\beta, \beta)

where `\Lambda = \sum_r \Lambda_{\kappa_r}` for the multicharge

`(\kappa_1, \ldots, \kappa_{\ell})` and

`\beta = \sum_{(r,c)} \alpha_{(c-r) \pmod e}`, with the sum

being over the cells in the partition.

EXAMPLES::

sage: Partition([4,3,2]).defect(3)

sage: Partition([0]).defect(3)

sage: Partition([3]).defect(3)

sage: Partition([6]).defect(3)

sage: Partition([9]).defect(3)

sage: Partition([12]).defect(3)

TESTS::

sage: all(mu.core(e).size() + e * mu.defect(e) == 9

....: for mu in Partitions(9) for e in [2,3,4])

True

"""

beta = [0]*e # element of positive root lattice corresponding to the block

Ie = IntegerModRing(e)

for (r,c) in self.cells():

beta[Ie(r-c)] += 1

return beta[multicharge[0]] - sum(beta[i]**2 - beta[i] * beta[Ie(i+1)]

for i in range(e))

def conjugacy_class_size(self):

"""

Return the size of the conjugacy class of the symmetric group

indexed by ``self``.

EXAMPLES::

sage: Partition([2,2,2]).conjugacy_class_size()

sage: Partition([2,2,1]).conjugacy_class_size()

sage: Partition([2,1,1]).conjugacy_class_size()

REFERENCES:

.. [Ker] Kerber, A. 'Algebraic Combinatorics via Finite Group Actions'

1.3 p24

"""

return factorial(sum(self))/self.centralizer_size()

def corners(self):

r"""

Return a list of the corners of the partition ``self``.

A corner of a partition `\lambda` is a cell of the Young diagram

of `\lambda` which can be removed from the Young diagram while

still leaving a straight shape behind.

The entries of the list returned are pairs of the form `(i,j)`,

where `i` and `j` are the coordinates of the respective corner.

The coordinates are counted from `0`.

EXAMPLES::

sage: Partition([3,2,1]).corners()

[(0, 2), (1, 1), (2, 0)]

sage: Partition([3,3,1]).corners()

[(1, 2), (2, 0)]

sage: Partition([]).corners()

[]

"""

p = self

if p.is_empty():

return []

lcors = [[0,p[0]-1]]

nn = len(p)

if nn == 1:

return [tuple(_) for _ in lcors]

lcors_index = 0

for i in range(1, nn):

if p[i] == p[i-1]:

lcors[lcors_index][0] += 1

else:

lcors.append([i,p[i]-1])

lcors_index += 1

return [tuple(_) for _ in lcors]

inside_corners = corners

removable_cells = corners # for compatibility with partition tuples

def corners_residue(self, i, l):

r"""

Return a list of the corners of the partition ``self`` having

``l``-residue ``i``.

A corner of a partition `\lambda` is a cell of the Young diagram

of `\lambda` which can be removed from the Young diagram while

still leaving a straight shape behind. See :meth:`residue` for

the definition of the ``l``-residue.

The entries of the list returned are pairs of the form `(i,j)`,

where `i` and `j` are the coordinates of the respective corner.

The coordinates are counted from `0`.

EXAMPLES::

sage: Partition([3,2,1]).corners_residue(0, 3)

[(1, 1)]

sage: Partition([3,2,1]).corners_residue(1, 3)

[(2, 0)]

sage: Partition([3,2,1]).corners_residue(2, 3)

[(0, 2)]

"""

return [x for x in self.corners() if self.residue(*x, l=l) == i]

inside_corners_residue = corners_residue

removable_cells_residue = corners_residue

def outside_corners(self):

r"""

Return a list of the outside corners of the partition ``self``.

An outside corner (also called a cocorner) of a partition

`\lambda` is a cell on `\ZZ^2` which does not belong to

the Young diagram of `\lambda` but can be added to this Young

diagram to still form a straight-shape Young diagram.

The entries of the list returned are pairs of the form `(i,j)`,

where `i` and `j` are the coordinates of the respective corner.

The coordinates are counted from `0`.

EXAMPLES::

sage: Partition([2,2,1]).outside_corners()

[(0, 2), (2, 1), (3, 0)]

sage: Partition([2,2]).outside_corners()

[(0, 2), (2, 0)]

sage: Partition([6,3,3,1,1,1]).outside_corners()

[(0, 6), (1, 3), (3, 1), (6, 0)]

sage: Partition([]).outside_corners()

[(0, 0)]

"""

p = self

if p.is_empty():

return [(0,0)]

res = [ (0, p[0]) ]

for i in range(1, len(p)):

if p[i-1] != p[i]:

res.append((i,p[i]))

res.append((len(p), 0))

return res

addable_cells = outside_corners # for compatibility with partition tuples

def outside_corners_residue(self, i, l):

r"""

Return a list of the outside corners of the partition ``self``

having ``l``-residue ``i``.

An outside corner (also called a cocorner) of a partition

`\lambda` is a cell on `\ZZ^2` which does not belong to

the Young diagram of `\lambda` but can be added to this Young

diagram to still form a straight-shape Young diagram. See

:meth:`residue` for the definition of the ``l``-residue.

The entries of the list returned are pairs of the form `(i,j)`,

where `i` and `j` are the coordinates of the respective corner.

The coordinates are counted from `0`.

EXAMPLES::

sage: Partition([3,2,1]).outside_corners_residue(0, 3)

[(0, 3), (3, 0)]

sage: Partition([3,2,1]).outside_corners_residue(1, 3)

[(1, 2)]

sage: Partition([3,2,1]).outside_corners_residue(2, 3)

[(2, 1)]

"""

return [x for x in self.outside_corners() if self.residue(*x, l=l) == i]

addable_cells_residue = outside_corners_residue

def rim(self):

r"""

Return the rim of ``self``.

The rim of a partition `\lambda` is defined as the cells which belong

to `\lambda` and which are adjacent to cells not in `\lambda`.

EXAMPLES:

The rim of the partition `[5,5,2,1]` consists of the cells marked with

``#`` below::

****#

*####

sage: Partition([5,5,2,1]).rim()

[(3, 0), (2, 0), (2, 1), (1, 1), (1, 2), (1, 3), (1, 4), (0, 4)]

sage: Partition([2,2,1]).rim()

[(2, 0), (1, 0), (1, 1), (0, 1)]

sage: Partition([2,2]).rim()

[(1, 0), (1, 1), (0, 1)]

sage: Partition([6,3,3,1,1]).rim()

[(4, 0), (3, 0), (2, 0), (2, 1), (2, 2), (1, 2), (0, 2), (0, 3), (0, 4), (0, 5)]

sage: Partition([]).rim()

[]

"""

p = self

res = []

prevLen = 1

for i in range(len(p)-1, -1, -1):

for c in range(prevLen-1, p[i]):

res.append((i,c))

prevLen = p[i]

return res

def outer_rim(self):

r"""

Return the outer rim of ``self``.

The outer rim of a partition `\lambda` is defined as the cells which do

not belong to `\lambda` and which are adjacent to cells in `\lambda`.

EXAMPLES:

The outer rim of the partition `[4,1]` consists of the cells marked

with ``#`` below::

****#

*####

sage: Partition([4,1]).outer_rim()

[(2, 0), (2, 1), (1, 1), (1, 2), (1, 3), (1, 4), (0, 4)]

sage: Partition([2,2,1]).outer_rim()

[(3, 0), (3, 1), (2, 1), (2, 2), (1, 2), (0, 2)]

sage: Partition([2,2]).outer_rim()

[(2, 0), (2, 1), (2, 2), (1, 2), (0, 2)]

sage: Partition([6,3,3,1,1]).outer_rim()

[(5, 0), (5, 1), (4, 1), (3, 1), (3, 2), (3, 3), (2, 3), (1, 3), (1, 4), (1, 5), (1, 6), (0, 6)]

sage: Partition([]).outer_rim()

[(0, 0)]

"""

p = self

res = []

prevLen = 0

for i in range(len(p)-1, -1, -1):

for c in range(prevLen, p[i]+1):

res.append((i+1,c))

prevLen = p[i]

res.append((0, prevLen))

return res

def zero_one_sequence(self):

r"""

Compute the finite `0-1` sequence of the partition.

The full `0-1` sequence is the sequence (infinite in both

directions) indicating the steps taken when following the

outer rim of the diagram of the partition. We use the convention

that in English convention, a 1 corresponds to an East step, and

a 0 corresponds to a North step.

Note that every full `0-1` sequence starts with infinitely many 0's and

ends with infinitely many 1's.

One place where these arise is in the affine symmetric group where

one takes an affine permutation `w` and every `i` such that

`w(i) \leq 0` corresponds to a 1 and `w(i) > 0` corresponds to a 0.

See pages 24-25 of [LLMMSZ13]_ for connections to affine Grassmannian

elements (note there they use the French convention for their

partitions).

These are also known as **path sequences**, **Maya diagrams**,

**plus-minus diagrams**, **Comet code** [Sta-EC2]_, among others.

OUTPUT:

The finite `0-1` sequence is obtained from the full `0-1`

sequence by omitting all heading 0's and trailing 1's. The

output sequence is finite, starts with a 1 and ends with a

0 (unless it is empty, for the empty partition). Its length

is the sum of the first part of the partition with the

length of the partition.

REFERENCES:

.. [LLMMSZ13] Thomas Lam, Luc Laponte, Jennifer Morse, Anne Schilling,

Mark Shimozono, and Mike Zabrocki. `k`-Schur Functions and Affine

Schubert Calculus. 2013. :arxiv:`1301.3569`.

EXAMPLES::

sage: Partition([5,4]).zero_one_sequence()

[1, 1, 1, 1, 0, 1, 0]

sage: Partition([]).zero_one_sequence()

[]

sage: Partition([2]).zero_one_sequence()

[1, 1, 0]

TESTS::

sage: all(Partitions().from_zero_one(mu.zero_one_sequence()) == mu for n in range(10) for mu in Partitions(n))

True

"""

tmp = [self[i]-i for i in range(len(self))]

return ([Integer(not (i in tmp)) for i in range(-len(self)+1,self.get_part(0)+1)])

def core(self, length):

r"""

Return the ``length``-core of the partition -- in the literature

the core is commonly referred to as the `k`-core, `p`-core,

`r`-core, ... .

The `r`-core of a partition `\lambda` can be obtained by

repeatedly removing rim hooks of size `r` from (the Young diagram

of) `\lambda` until this is no longer possible. The remaining

partition is the core.

EXAMPLES::

sage: Partition([6,3,2,2]).core(3)

[2, 1, 1]

sage: Partition([]).core(3)

[]

sage: Partition([8,7,7,4,1,1,1,1,1]).core(3)

[2, 1, 1]

TESTS::

sage: Partition([3,3,3,2,1]).core(3)

[]

sage: Partition([10,8,7,7]).core(4)

[]

sage: Partition([21,15,15,9,6,6,6,3,3]).core(3)

[]

"""

p = self

#Normalize the length

remainder = len(p) % length

part = p[:] + [0]*remainder

#Add the canonical vector to the partition

part = [part[i-1] + len(part)-i for i in range(1, len(part)+1)]

for e in range(length):

k = e

for i in reversed(range(1,len(part)+1)):

if part[i-1] % length == e:

part[i-1] = k

k += length

part.sort()

part.reverse()

#Remove the canonical vector

part = [part[i-1]-len(part)+i for i in range(1, len(part)+1)]

#Select the r-core

return Partition([x for x in part if x != 0])

def quotient(self, length):

r"""

Return the quotient of the partition -- in the literature the

quotient is commonly referred to as the `k`-quotient, `p`-quotient,

`r`-quotient, ... .

The `r`-quotient of a partition `\lambda` is a list of `r`

partitions (labelled from `0` to `r-1`), constructed in the following

way. Label each cell in the Young diagram of `\lambda` with its

content modulo `r`. Let `R_i` be the set of rows ending in a cell

labelled `i`, and `C_i` be the set of columns ending in a cell

labelled `i`. Then the `j`-th component of the quotient of

`\lambda` is the partition defined by intersecting `R_j` with

`C_{j+1}`. (See Theorem 2.7.37 in [JamesKerber]_.)

REFERENCES:

.. [JamesKerber] Gordon James, Adalbert Kerber,

*The Representation Theory of the Symmetric Group*,

Encyclopedia of Mathematics and its Applications, vol. 16,

Addison-Wesley 1981.

EXAMPLES::

sage: Partition([7,7,5,3,3,3,1]).quotient(3)

([2], [1], [2, 2, 2])

TESTS::

sage: Partition([8,7,7,4,1,1,1,1,1]).quotient(3)

([2, 1], [2, 2], [2])

sage: Partition([10,8,7,7]).quotient(4)

([2], [3], [2], [1])

sage: Partition([6,3,3]).quotient(3)

([1], [1], [2])

sage: Partition([3,3,3,2,1]).quotient(3)

([1], [1, 1], [1])

sage: Partition([6,6,6,3,3,3]).quotient(3)

([2, 1], [2, 1], [2, 1])

sage: Partition([21,15,15,9,6,6,6,3,3]).quotient(3)

([5, 2, 1], [5, 2, 1], [7, 3, 2])

sage: Partition([21,15,15,9,6,6,3,3]).quotient(3)

([5, 2], [5, 2, 1], [7, 3, 1])

sage: Partition([14,12,11,10,10,10,10,9,6,4,3,3,2,1]).quotient(5)

([3, 3], [2, 2, 1], [], [3, 3, 3], [1])

sage: all(p == Partition(core=p.core(k), quotient=p.quotient(k))

....: for i in range(10) for p in Partitions(i)

....: for k in range(1,6))

True

"""

p = self

#Normalize the length

remainder = len(p) % length

part = p[:] + [0]*(length-remainder)

#Add the canonical vector to the partition

part = [part[i-1] + len(part)-i for i in range(1, len(part)+1)]

result = [None]*length

#Reducing vector

for e in range(length):

k = e

tmp = []

for i in reversed(range(len(part))):

if part[i] % length == e:

tmp.append(ZZ((part[i]-k)//length))

k += length

a = [i for i in tmp if i != 0]

a.reverse()

result[e] = a

from .partition_tuple import PartitionTuple

return PartitionTuple(result) #tuple(map(Partition, result))

def is_core(self, k):

r"""

Tests whether the partition is a `k`-core or not. Visuallly, this can

be checked by trying to remove border strips of size `k` from ``self``.

If this is not possible, then ``self`` is a `k`-core.

A partition is said to be a *`k`-core* if it has no hooks of length

`k`. Equivalently, a partition is said to be a `k`-core if it is its

own `k`-core (where the latter is defined as in :meth:`core`).

EXAMPLES::

sage: p = Partition([12,8,5,5,2,2,1])

sage: p.is_core(4)

False

sage: p.is_core(5)

True

sage: p.is_core(0)

True

"""

return not k in self.hooks()

def k_interior(self, k):

r"""

Return the partition consisting of the cells of ``self`` whose hook

lengths are greater than ``k``.

EXAMPLES::

sage: p = Partition([3,2,1])

sage: p.hook_lengths()

[[5, 3, 1], [3, 1], [1]]

sage: p.k_interior(2)

[2, 1]

sage: p.k_interior(3)

[1]

sage: p = Partition([])

sage: p.k_interior(3)

[]

"""

return Partition([len([i for i in row if i > k])

for row in self.hook_lengths()])

def k_boundary(self, k):

r"""

Return the skew partition formed by removing the cells of the

``k``-interior, see :meth:`k_interior`.

EXAMPLES::

sage: p = Partition([3,2,1])

sage: p.k_boundary(2)

[3, 2, 1] / [2, 1]

sage: p.k_boundary(3)

[3, 2, 1] / [1]

sage: p = Partition([12,8,5,5,2,2,1])

sage: p.k_boundary(4)

[12, 8, 5, 5, 2, 2, 1] / [8, 5, 2, 2]

"""

return SkewPartition([self, self.k_interior(k)])

def add_cell(self, i, j = None):

r"""

Return a partition corresponding to ``self`` with a cell added in

row ``i``. (This does not change ``self``.)

EXAMPLES::

sage: Partition([3, 2, 1, 1]).add_cell(0)

[4, 2, 1, 1]

sage: cell = [4, 0]; Partition([3, 2, 1, 1]).add_cell(*cell)

[3, 2, 1, 1, 1]

"""

if j is None:

if i >= len(self):

j = 0

else:

j = self[i]

if (i,j) in self.outside_corners():

pl = self.to_list()

if i == len(pl):

pl.append(1)

else:

pl[i] += 1

return Partition(pl)

raise ValueError("[%s, %s] is not an addable cell"%(i,j))

def remove_cell(self, i, j = None):

"""

Return the partition obtained by removing a cell at the end of row

``i`` of ``self``.

EXAMPLES::

sage: Partition([2,2]).remove_cell(1)

[2, 1]

sage: Partition([2,2,1]).remove_cell(2)

[2, 2]

sage: #Partition([2,2]).remove_cell(0)

sage: Partition([2,2]).remove_cell(1,1)

[2, 1]

sage: #Partition([2,2]).remove_cell(1,0)

"""

if i >= len(self):

raise ValueError("i must be less than the length of the partition")

if j is None:

j = self[i] - 1

if (i,j) not in self.corners():

raise ValueError("[%d,%d] is not a corner of the partition" % (i,j))

if self[i] == 1:

return Partition(self[:-1])

else:

return Partition(self[:i] + [ self[i:i+1][0] - 1 ] + self[i+1:])

def k_irreducible(self, k):

r"""

Return the partition with all `r \times (k+1-r)` rectangles removed.

If ``self`` is a `k`-bounded partition, then this method will return the partition

where all rectangles of dimension `r \times (k+1-r)` for `1 \leq r \leq k`

have been deleted.

If ``self`` is not a `k`-bounded partition then the method will raise an error.

INPUT:

- ``k`` -- a non-negative integer

OUTPUT:

- a partition

EXAMPLES::

sage: Partition([3,2,2,1,1,1]).k_irreducible(4)

[3, 2, 2, 1, 1, 1]

sage: Partition([3,2,2,1,1,1]).k_irreducible(3)

[]

sage: Partition([3,3,3,2,2,2,2,2,1,1,1,1]).k_irreducible(3)

[2, 1]

"""

pexp = self.to_exp()

return Partition(sum(([r+1] for r in range(len(pexp)-1,-1,-1) for m in range(pexp[r] % (k-r))),[]))

def k_skew(self, k):

r"""

Return the `k`-skew partition.

The `k`-skew diagram of a `k`-bounded partition is the skew diagram

denoted `\lambda/^k` satisfying the conditions:

1. row `i` of `\lambda/^k` has length `\lambda_i`,

2. no cell in `\lambda/^k` has hook-length exceeding `k`,

3. every square above the diagram of `\lambda/^k` has hook

length exceeding `k`.

REFERENCES:

.. [LM2004] Lapointe, L. and Morse, J. 'Order Ideals in Weak Subposets

of Young's Lattice and Associated Unimodality Conjectures'. Ann.

Combin. (2004)

EXAMPLES::

sage: p = Partition([4,3,2,2,1,1])

sage: p.k_skew(4)

[9, 5, 3, 2, 1, 1] / [5, 2, 1]

"""

if len(self) == 0:

return SkewPartition([[],[]])

if self[0] > k:

raise ValueError("the partition must be %d-bounded" % k)

#Find the k-skew diagram of the partition formed

#by removing the first row

s = Partition(self[1:]).k_skew(k)

s_inner = list(s.inner())

s_outer = list(s.outer())

s_conj_rl = s.conjugate().row_lengths()

#Find the leftmost column with less than

# or equal to kdiff cells

kdiff = k - self[0]

if s_outer == []:

spot = 0

else:

spot = s_outer[0]

for i in range(len(s_conj_rl)):

if s_conj_rl[i] <= kdiff:

spot = i

break

outer = [ self[0] + spot ] + s_outer[:]

if spot > 0:

inner = [ spot ] + s_inner[:]

else:

inner = s_inner[:]

return SkewPartition([outer, inner])

def to_core(self, k):

r"""

Maps the `k`-bounded partition ``self`` to its corresponding `k+1`-core.

Coverage for local/lib/python2.7/site-packages/sage/combinat/partition.py : 76%

1600 statements 1214 run 386 missing 0 excluded