In Per's lecture, you learned about many combinatorial structures:
In Hans's lecture yesterday, you learned about some lattice paths.
SageMath already knows about all these!
In Sage, to generate instances of a combinatorial stucture (that Sage knows of), one simply uses the word with a capital letter.
p = Permutation([2,1,4,5,3]); p
[2, 1, 4, 5, 3]
p.to_cycles()
[(1, 2), (3, 4, 5)]
And to generate all instances of the combinatorial structure, one simply marks the plural.
P = Permutations(5); P
Standard permutations of 5
For example, one can ask how many permutations of 5 there are.
One can either generate all permutations and then count them (using len(P)
), or one could ask SageMath to count them. For every structure, this is achieved through asking for the cardinality of a set.
print(len(P))
print(P.cardinality())
120 120
Of course, if we know that the number of permutations of $n$ is $n!$, one can simply ask how large is $n!$.
factorial(5)
120
In general, we could learn how the cardinality is computed.
Takeaway: SageMath is also a repository for knowledge, since it lists the desired theorems.
P.cardinality??
shows
Source:
def cardinality(self):
"""
Return the number of permutations of size `n`, which is `n!`.
EXAMPLES::
sage: Permutations(0).cardinality()
1
sage: Permutations(3).cardinality()
6
sage: Permutations(4).cardinality()
24
"""
return factorial(self.n)
meaning that to compute the number of permutations of $n$, Sage only computes $n!$, and does not generate all permutations.
cardinality
:
One must be mindful of memory and time, and that it induces limitations. Even though cardinality
is fast, listing all permutations is not always possible.
Permutations(30).cardinality()
265252859812191058636308480000000
len(Permutations(30))
--------------------------------------------------------------------------- OverflowError Traceback (most recent call last) Cell In [29], line 1 ----> 1 len(Permutations(Integer(30))) OverflowError: cannot fit 'int' into an index-sized integer
30 is too large to list all 30! permutations 🤷♀️
SetPartitions
(takes either a set as a parameter, or n
for the set partitions of $\{1,2,\ldots, n\}$.)Subsets
(takes either a set as a parameter, or n
for the set partitions of $\{1,2,\ldots, n\}$.)Compositions
(takes a positive integer as a parameter)Partitions
(takes a positive integer as a parameter)DyckWords
.Very often, we don't need to generate or count all instances of a structure, but only a subset with a specific constraint. Often, we can specifiy these
Example (from last lecture)
How many (integer) partitions of 13 have their largest part at most 3?
All instances -> All partitions of 13
What we are interested in -> Partitions of 13 with all parts at most 3
There are two options:
# Do the example in class:
# Ask SageMath to generate only the partitions that have only parts at most 3
# through an *argument* in the generator, passed as a parameter.
# Do the example in class:
# Ask SageMath to generate all partitions of 13, then sort through those whose maximal part is at most 3.
Of course, we should get the same answer regardless of how we generated the partitions.
Set(list_partitions_with_max_part(13, 3)) == Set(Partitions(13, max_part=3))
True
Phew! Sage and us got the same thing using two different methods.
Question: What are all constraints that one can easily give to SageMath for partitions?
# Figuring it out with the notebook
SageMath knows many combinatorial sequences
factorial
bell_number
catalan_number
narayana_number
eulerian_number
(and Eulerian polynomial, eulerian_polynomial
)fibonacci
stirling_number1
, and of the second kind
stirling_number2
.polygonal_number
To find that list, you can look up the documentation, or I looked up the internet for combinatorial sequences sagemath
.
If you don't know some of these numbers, ask the documentation:
bell_number?
shows
Signature: bell_number(n, algorithm='flint', **options) -> 'Integer'
Docstring:
Return the n-th Bell number.
This is the number of ways to partition a set of n elements into
pairwise disjoint nonempty subsets.
INPUT:
* "n" -- a positive integer
* "algorithm" -- (Default: "'flint'") any one of the following:
* "'dobinski'" -- Use Dobinski's formula implemented in Sage
* "'flint'" -- Wrap FLINT's "arith_bell_number"
* "'gap'" -- Wrap GAP's "Bell"
* "'mpmath'" -- Wrap mpmath's "bell"
[...] The documentation is very long.
The list of sequences above all comes from the combinat
part of SageMath. Some of them are not referenced in the main part of SageMath, so you'll have to import the combinat part.
narayana_number?
Object `narayana_number` not found.
from sage.combinat.combinat import *
narayana_number(5,2)
20
narayana_number?
The Narayana numbers, according to Wikipedia, count the number of Dyck Paths with $2n$ steps and $k+1$ peaks. Can we draw these paths?
# Only a few appear on the slides, they are all in the notebook
for path in DyckWords(5):
if len(path.peaks()) == 3:
print(ascii_art(path), '\n')
/\ / \ /\/\/ \ /\ /\ /\/ \/ \ /\ /\/ \ /\/ \ /\ / \ /\/ \/\ /\ / \/\ /\/ \ /\/\ / \ /\/ \ /\ /\ / \/\/ \ /\ /\ / \/ \/\ /\ /\/\ / \/ \ /\/\ /\ / \/ \ /\ /\/\/ \ / \ /\ /\/ \ / \/\ /\ /\/ \/\ / \ /\/\ /\/ \ / \ /\ / \ / \/\/\ /\ / \/\ / \/\ /\ / \/\/\ / \ /\/\ / \ / \/\ /\/\ / \/\ / \ /\/\/\ / \ / \
For example, one might be interested in drawing the paths in different ways, or to copy it in a LaTeX document.
For most objects, there are multiple ways to draw them. Typically:
plot()
: displays it in a standard waypp()
: pretty print in ascii artascii_art()
: a simple way to represent it visuallylatex
or show
: returns the LaTeX code for adding it to your documentpath = DyckWords(5).random_element();
path
show(path) # latex source
# A more compact, yet visual representation (works for many structures)
ascii_art(path)
/\ / \/\/\ / \
path.plot() # draw it as a graphic
latex(path) # also latex source
\vcenter{\hbox{$\begin{tikzpicture}[scale=1] \draw[dotted] (0, 0) grid (10, 3); \draw[rounded corners=1, color=black, line width=2] (0, 0) -- (1, 1) -- (2, 2) -- (3, 3) -- (4, 2) -- (5, 1) -- (6, 2) -- (7, 1) -- (8, 2) -- (9, 1) -- (10, 0); \end{tikzpicture}$}}
path.pp() # pp stands for "pretty print". Look how different it is!
# This is because a Dyck Path is also a lattice path that does not go below the diagonal.
___ _| x ___| x . | x x . . | x . . . | . . . .