Report, session 6#
For the following combinatorial sets, give a recursive combinatorial definition and the corresponding generating function in Sage. Then compute the first coefficients.
Pour les ensembles combinatoires suivant, donnez une définition récursive combinatoire puis définissez dans Sage la série génératrice correspondante et calculez les premiers coefficients.
Example : binary trees#
Combinatorial definition
A binary tree is either
an empty tree
a node with 2 binary trees
# Sage 9.7
L.<z> = LazyPowerSeriesRing(QQ)
f = L()
f.define(1 + z*f*f)
f.compute_coefficients(10)
f
# Sage 10
L.<z> = LazyPowerSeriesRing(QQ)
f = L.undefined()
f.define(1 + z*f*f)
f
oeis([f.coefficient(i) for i in range(11)])
Binary words#
Les mots binaires
Words in the alphabet \(\{0,1 \}\)
Les mots sur l’alphabet \(\{0,1 \}\)
\(0, 1, 00, 01, 10, 11, 000, 001, \dots\)
EDIT THIS CELL
Combinatorial definition
…
L.<z> = LazyPowerSeriesRing(QQ)
# Sage 9.7
f = L()
# Sage 10
f = L.undefined()
# Write your code here
# Write your code here
oeis([f.coefficient(i) for i in range(11)])
Les Palindromes#
Palindromes in the alphabet \(\{a, b \}\), i.e. words that read the same backward as forward.
Les palindromes sur l’alphabet \(\{a, b \}\), c’est à dire les mots qui se lisent de la même façon de gauche à droite ou de droite à gauche.
\(a, b, aa, bb, aaa, aba, bab, bbb, \dots\)
EDIT THIS CELL
Combinatorial definition
…
L.<z> = LazyPowerSeriesRing(QQ)
# Sage 9.7
f = L()
# Sage 10
f = L.undefined()
# Write your code here
# Write your code here
Ternary trees#
Arbres ternaires
Trees where all nodes have 3 children.
Les arbres dont tous les noeuds ont 3 fils.
EDIT THIS CELL
Combinatorial definition
…
L.<z> = LazyPowerSeriesRing(QQ)
# Sage 9.7
f = L()
# Sage 10
f = L.undefined()
# Write your code here
# Write your code here
oeis([f.coefficient(i) for i in range(11)])
trees with binary / ternary levels#
Les arbres à niveau binaires / ternaires
Trees where the root has two children, level 1 nodes (children of the root) have 3 children, level 2 nodes have 2 children, etc.
Arbres dont la racine a deux fils, les noeuds de niveau 1 (fils de la racine) ont 3 fils, les noeuds de niveau 2 ont 2 fils, etc.
EDIT THIS CELL
Combinatorial definition
…
L.<z> = LazyPowerSeriesRing(QQ)
# Write your code here
# Write your code here
A binary tree of binary trees#
Un arbre binaire d’arbres binaires
A binary tree such that there is another binary tree in each node.
Un arbre binaire tel que les noeuds contiennent d’autres arbres binaires.
EDIT THIS CELL
Combinatorial definition
…
L.<z> = LazyPowerSeriesRing(QQ)
# Write your code here