Some classical enumerative problems

Some classical enumerative problems#

Quelques problèmes classiques d’énumération

Subsets Sous-ensembles#

Counting Comptage#

I hold 4 different cards in my hand (which we will call « Red », « Blue », « Green », and « Yellow »). I can put a subset of my cards (between 0 and 4) into the deck. How many possibilities do I have?

Je tiens dans ma main 4 cartes différentes (qu’on appellera « Red », « Blue », « Green », et « Yellow »). Je peux déposer dans la pioche un sous-ensemble de mes cartes (entre 0 et 4). Combien ai-je de possibilités ?

.

.

.

How can we calculate this in Sage?

Comment le calculer en Sage ?

Hand = Set(["Red","Blue","Green","Yellow"])
Hand

Hand.subsets()

Hand.subsets().cardinality()

hand_subsets = Hand.subsets()
hand_subsets.cardinality??

list(hand_subsets)

hand_subsets.random_element()

A first random draw method (complexity \(O(|s|)\)):

Une première méthode de tirage aléatoire (complexité \(O(|s|)\)):

def random_subset(s):
    """
    Return a random subset of `s` uniformly
    Input:
     - s a set 
    Output: a subset of s
    """
    # Replace the next line with your code
    raise RuntimeError("Code not implemented on line 79");

random_subset(Hand)

def distribution(L):
    """
    Return the distribution by the number of occurrences of a list of elements
    Input:
     - a list L of (non-mutable) elements
    Output: a dictionary counting the occurrences of each element of the list L
    """
    d = {}
    for el in L:
        d[el] = d.get(el, 0) + 1
    return d

distribution([random_subset(Hand) for i in range(10000)])

bar_chart(list(distribution([random_subset(Hand) for i in range(10000)]).values()), ymin = 0)

Listing by bijection and unrank#

Listage par bijection et unrank

We define a bijection (a 1 to 1 match) between the numbers from \(0\) to \(2^n - 1\) and the subsets of a set of \(n\) elements.

On va définir une bijection (une correspondance 1 à 1) entre les nombres de \(0\) à \(2^n - 1\) et les sous-ensembles d’un ensemble de \(n\) éléments.

A number between 0 and \(2^n - 1\) is represented in binary by a list of \(n\) bits, each bit has a value of \(0\) or \(1\).

Un nombre entre 0 et \(2^n - 1\) est représenté en binaire par une liste de \(n\) bits, chaque bit prend comme valeur \(0\) ou \(1\).

Example : \(13 = 2^0 + 2^2 + 2^3 = (1101)_2\)

Each bit corresponds to an element of the set, if the bit is 1, the element is present. In the example below, the bits correspond to « Red », « Blue », « Green », « Yellow » (from most significant bit to less significant). In the following, the order will not matter, we will use the order given by the set Hand which is not necessarily the one given here.

Chaque bit correspond à un élément de l’ensemble, si le bit est à 1, l’élément est présent. Dans l’exemple ci-dessous, les bits correspondent respectivement à « Red », « Blue », « Green », « Yellow » (du poids fort au poids faible). Dans la suite, l’ordre n’aura pas d’importance, on utilisera l’ordre donné par l’ensemble Hand qui n’est pas forcément celui là.

\( \begin{align} 0 &= 0000 & \leftrightarrow & \emptyset \\ 1 &= 0001 & \leftrightarrow & \{Y\} \\ 2 &= 0010 & \leftrightarrow & \{G \} \\ 3 &= 0011 & \leftrightarrow & \{G,Y \} \\ 4 &= 0100 & \leftrightarrow & \{B \} \\ 5 &= 0101 & \leftrightarrow & \{B, Y \} \\ 6 &= 0110 & \leftrightarrow & \{B,G \} \\ 7 &= 0111 & \leftrightarrow & \{B,G,Y \} \\ 8 &= 1000 & \leftrightarrow & \{R \} \\ 9 &= 1001 & \leftrightarrow & \{R,Y\} \\ 10 &= 1010 & \leftrightarrow & \{R,G \} \\ 11 &= 1011 & \leftrightarrow & \{R,G,Y \} \\ 12 &= 1100 & \leftrightarrow & \{R,B \} \\ 13 &= 1101 & \leftrightarrow & \{R,B, Y \} \\ 14 &= 1110 & \leftrightarrow & \{R,B,G \} \\ 15 &= 1111 & \leftrightarrow & \{R,B,G,Y \} \\ \end{align} \)

def unrank_subset(i, s):
    """
    Return the subset of s corresponding to i 
    Input:
     - i an integer between 0 and 2^|s| - 1
     - s a set of type Set
    """
    # Replace the next line with your code
    raise RuntimeError("Code not implemented on line 160");

unrank_subset(0,Hand)

unrank_subset(15,Hand)

unrank_subset(1,Hand)

unrank_subset(2,Hand)

unrank_subset(4,Hand)

unrank_subset(8,Hand)

def subsets_by_unrank(s):
    """
    Return an iterator over the set of subsets of s using unrank
    Input:
     - a set of s
    Output: an iterator on the subsets of s
    """
    # Replace the next line with your code
    raise RuntimeError("Code not implemented on line 196");

list(subsets_by_unrank(Hand))

def random_subset_by_unrank(s):
    """
    Returns a uniform random subset using unrank
    Input:
     - s a set 
    Output: a subset of s
    """
    # Replace the next line with your code
    raise RuntimeError("Code not implemented on line 212");

random_subset_by_unrank(Hand)

distribution([random_subset_by_unrank(Hand) for i in range(10000)])

bar_chart(list(distribution([random_subset(Hand) for i in range(10000)]).values()), ymin = 0)

Recursive listing#

Listage récursif

The algorithm can also be designed as follows:

  • if the set \(S\) is empty, then the only existing subset is the empty set

  • otherwise, we choose an element \(t \in S\). The subsets of \(S\) are

    • the subsets of \(S \setminus t\)

    • the subsets of \(S \setminus t\) to which we add \(t\)

On peut aussi concevoir l’algorithme de la façon suivante :

  • si l’ensemble \(S\) est vide alors le seul sous-ensemble existant est l’ensemble vide

  • sinon, on choisit un élément \(t \in S\). Les sous-ensembles de \(S\) sont

    • les sous-ensembles de \(S \setminus t\)

    • les sous-ensembles de \(S \setminus t\) auxquels on ajoute \(t\)

Note: some useful methods on Set of Sage

Note : quelques méthodes utiles sur les Set de Sage

len(Hand)

Hand.an_element()

Hand + Set(["Black"])

Hand - Set(["Blue"])

def subsets_recurs(s):
    """
    Return an iterator on all subsets of s using recursive iteration
    Input :
     - a set s of type Set
    Output : an iterator on S subets
    """
    # Replace the next line with your code
    raise RuntimeError("Code not implemented on line 273");

list(subsets_recurs(Hand))

Arrangements, permutations, combinations#

An arrangement of \(k\) elements from a set \(S\) is an ordered choice of \(k\) elements from \(S\). For example: \(Red,Green\) is an arrangement of 2 of the 4 cards in my hand, and \(Green, Red\) is another.

Un arrangement de \(k\) éléments parmi un ensemble \(S\) est un choix ordonné de \(k\) éléments parmi \(S\). Par exemple : \(Red,Green\) est un arrangement de 2 éléments parmi les 4 cartes que j’ai en main, et \(Green, Red\) en est un autre.

Arrangements(Hand, 2)

How many arrangements of 2 out of 4 do I have?

Combien ai-je d’arrangements de 2 parmi 4 ?

Arrangements(Hand, 2).cardinality()

Why? I have 4 possible choices for the first card times 3 choices for the second card.

pourquoi ? J’ai 4 choix pour la première carte fois 3 choix pour la seconde carte.

list(Arrangements(Hand,2))

In general, there are

\[n \times (n-1) \times \dots \times (n- k +1) = \frac{n!}{(n-k)!}\]

arrangements of \(k\) out of \(n\).

Arrangements(Hand,1).cardinality() # 4! / 3!

Arrangements(Hand,2).cardinality() # 4! / 2!

Arrangements(Hand,3).cardinality() # 4! / 1!

The arrangements of \(n\) elements among a set \(S\) of size \(n\) are the permutations of \(S\), counted by \(n!\)

Les arrangements de \(n\) éléments parmi un ensemble \(S\) de taille \(n\) sont les permutations de \(S\), comptées par \(n!\)

Arrangements(Hand,4).cardinality()

list(Arrangements(Hand,4))

A combination of \(k\) elements from a set \(S\) of size \(n\) is a choice of \(k\) elements of \(S\) but this time, the order of the elements does not matter. For example \(\{ Red, Green \} = \{ Green, Red \}\) is a combination of 2 out of the 4 cards I have in my hand.

Une combinaison de \(k\) élements parmi un ensemble \(S\) de taille \(n\) est un choix de \(k\) élements de \(S\) mais cette fois, l’ordre des éléments ne compte pas. Par exemple \(\{ Rouge, Verte \} = \{ Verte, Rouge \}\) est une combinaison de 2 cartes parmi les 4 que j’ai en main.

Combinations(Hand,2)

Look at the list of arrangements of 2 cards among the 4, which ones correspond to the same combination? How many different combinations are there in total?

Observez la liste des arrangements de 2 cartes parmi les 4, lesquels correspondent à la même combinaison ? Combien a-t-on de combinaisons différentes au total ?

Combinations(Hand,2).cardinality()

list(Combinations(Hand,2))

Let \(\{ a,b,c \} \) be a combination of 3 elements. There are \(6 = 3!\) corresponding arrangements: these are the 6 ways of ordering the elements \(a\), \(b\), and \(c\). In general, a combination of \(k\) elements corresponds to \(k!\) arrangements. This gives the following formula:

Soit \(\{ a,b,c \} \) une combinaison de 3 éléments. Il existe \(6 = 3!\) arrangements correspondant : ce sont les 6 façons d’ordonner les éléments \(a\), \(b\), et \(c\). De façon générale, une combinaison de \(k\) éléments correspond à \(k!\) arrangements. On obtient alors la formule suivante :

\[ C_n^k = \frac{A_n^k}{k!} = \frac{n!}{(n-k)!\,k!} \]

where \(C_n^k\) (also written as \(n \choose k\)) is the number of combinations of \(k\) out of \(n\) (or \(n\) chooses \(k\)) and \(A_n^k\), the number of arrangements.

où \(C_n^k\) (qu’on écrit aussi \(n \choose k\)) est le nombre de combinaisons de \(k\) parmi \(n\) et \(A_n^k\), le nombre d’arrangements.

Combinations(Hand,0).cardinality()

Combinations(Hand,1).cardinality()

Combinations(Hand,2).cardinality()

Combinations(Hand,3).cardinality()

Combinations(Hand,4).cardinality()

Note that the sum of all possible combinations gives: \(1+4+6+4+1 = 16 = 2^4\). Indeed, the combinations of \(k\) among \(n\) for \(k\) ranging from 0 to \(n\), are the subsets!

Exercise TP (see report) Implement (with the algorithm of your choice) functions used to list the arrangements/combinations and to draw them randomly and uniformly.

Remarquez que la somme de toutes les combinaisons possibles donne : \(1+4+6+4+1 = 16 = 2^4\). En effet, les combinaisons de \(k\) parmi \(n\) pour \(k\) allant de 0 à \(n\), sont les sous-ensembles !

Exercice TP (cf rapport) Implantez (avec l’algorithme de votre choix) des fonctions permettant de lister les arrangements / combinaisons et d’en tirer au hasard de façon uniforme.

Cartesian products#

Produits cartésiens

The Cartesian product \(A \times B\) of two sets \(A\) and \(B\) is the set of pairs \((a,b)\) where \(a\in A\) and \(b\in B\).

Le produit cartésien \(A \times B\) de deux ensembles \(A\) et \(B\) est l’ensemble des couples \((a,b)\) où \(a\in A\) et \(b\in B\).

Suits = Set(["Spades", "Hearts", "Diamonds", "Clubs"])
Numbers = Set(["Ace","2","3","4","5","6","7","8","9","10","J","Q","K"])
Cards = cartesian_product([Suits, Numbers])
Cards

Cards.cardinality()

Suits.cardinality() * Numbers.cardinality()

Cards.an_element()

list(Cards)

Recursive listing#

Listage récursif

def products_listing(s1, s2):
    """
    Return an iterator over the elements of the Cartesian product between s1 and s2
    Input:
       - s1, a set of type Set
       - s2, a set of type Set
    Output: an iterator over all tuples (e1,e2) with e1 in s1 and e2 in s2
    """
    # Replace the next line with your code
    raise RuntimeError("Code not implemented on line 448");

list(products_listing(Suits, Numbers))

len(list(products_listing(Suits, Numbers)))

def random_product(s1,s2):
    """
    Return an element drawn uniformly from the product of s1 x s2
    Input:
       - s1, a set of type Set
       - s2, a set of type Set
    Output: an element (e1,e2) with e1 in s1 and e2 in s2 drawn uniformly
    """
    # Replace the next line with your code
    raise RuntimeError("Code not implemented on line 469");

random_product(Suits, Numbers)

Unrank#

Let’s also look at how to write an « unrank » method. The idea is to define an « order » on the elements and to number them. We will assume that there is an order of elements in s1 and s2 (by transforming them into a list and taking the obtained order)

Voyons aussi comment écrire une méthode « unrank ». L’idée est de définir un « ordre » sur les élements et de les numéroter. On va supposer qu’il existe un ordre des éléments dans s1 et s2 (en les transformant en liste et en prenant l’ordre obtenu)

list(Suits)

list(Numbers)

The elements of the product are ordered first by the first element (from s1) and then by the second element (from s2). Their rank is their number in the list of elements. The unrank method lets us obtain the element corresponding to a given number without browsing the list!

Les éléments du produit sont ordonnés d’abord par le premier élément (issu de s1) puis par le second élément (issu de s2). Leur rang est leur numéro dans la liste des éléments. La méthode unrank permet d’obtenir l’élément correspondant à un numéro donné sans parcourir la liste !

def unrank_product(i,s1,s2):
    """
    Returns the element corresponding to number i in the list of Cartesian product elements
    Input:
       - i, an integer between 0 and len(s1) * len(s2) - 1
       - s1, a set of type Set
       - s2, a set of type Set
    Output: the element (e1,e2) corresponding to i
    """
    # Replace the next line with your code
    raise RuntimeError("Code not implemented on line 506");

unrank_product(0,Suits,Numbers)

unrank_product(51,Suits,Numbers)

[unrank_product(i,Suits,Numbers) for i in range(Suits.cardinality() * Numbers.cardinality())] == \
list(products_listing(Suits, Numbers))

Application: binary trees#

Application : les arbres binaires

A binary tree is defined in the following recursive way, that is:

  • either an empty tree (a leaf)

  • or a node with a sub-tree on the left and a sub-tree on the right, which are both binary trees

The size of a binary tree is its number of nodes (not counting the leaves).

Binary trees are implemented in Sage:

Un arbre binaire est défini de la façon récursive suivante, c’est :

  • soit un arbre vide (une feuille)

  • soit un noeud avec un sous-arbre à gauche et un sous-arbre à droite qui sont tous les deux des arbres binaires

La taille d’un arbre binaire est son nombre de noeuds (on ne compte pas les feuilles).

Les arbres binaires sont implanté en Sage :

BinaryTree() # a leaf

BinaryTree([BinaryTree(), BinaryTree()]) # a tree with a leaf to the left and to the right

ascii_art(BinaryTree([BinaryTree(), BinaryTree()])) # broken in sage 9.6 (but works in 9.4 and 9.7)

view(BinaryTree([BinaryTree(), BinaryTree()]))

leaf = BinaryTree()
bt1 = BinaryTree([BinaryTree([leaf, leaf]), leaf]) # un arbre binaire de taille 2
bt1

leaf = BinaryTree()
bt2 = BinaryTree([leaf, BinaryTree([leaf, leaf])]) # un arbre binaire de taille 2
bt2

Exercise:

  • List the binary trees of size 3 by hand

  • How many binary trees of size 4 are there? 5? 6?

  • Find a recursive expression for the sequence \(C_n\) of the number of binary trees of size n

The numbers \(C_n\) are actually well known, they are called Catalan numbers. Next week, we will see how we prove that binary trees are counted by Catalan numbers.

  • Faites à la main la liste des arbres binaires de taille 3

  • Combien a-t-on d’arbres binaires de taille 4 ? 5 ? 6 ?

  • Trouvez une expression récursive pour la suite \(C_n\) du nombre d’arbre binaire de taille n

Les nombres \(C_n\) sont en réalité bien connus, on les appelle les nombres de Catalan. On verra la semaine prochaine comment on prouve que les arbres binaires sont comptés par les nombres de Catalan.

BT3 = BinaryTrees(3)
list(BT3)

BT3.cardinality()

BT3.cardinality??

For today, we will be satisfied with the recursive formula and implement the following methods:

Pour aujourd’hui, on va se contenter de la formule récursive et implanter les méthodes suivantes :

@cached_function
def cardinality_binaryTrees(n):
    """
    Return the number of binary trees of size n
    """
    # Replace the next line with your code
    raise RuntimeError("Code not implemented on line 609");

cardinality_binaryTrees(3)

cardinality_binaryTrees(4)

cardinality_binaryTrees(5)

assert all(cardinality_binaryTrees(n) == catalan_number(n) for n in range(20))

cardinality_binaryTrees(100)

catalan_number(100)

def binarytrees(n):
    """
    Return an iterator over binary trees of size n
    """
    # Replace the next line with your code
    raise RuntimeError("Code not implemented on line 642");

list(binarytrees(3))

ascii_art(list(binarytrees(3)))

def unrank_binarytree(i,n):
    """
    Returns the binary tree corresponding to number i in the list of binary trees
    (according to the order given by the `binarytrees` function)
    """
    # Replace the next line with your code
    raise RuntimeError("Code not implemented on line 660");

unrank_binarytree(0,3)

unrank_binarytree(1,3)

unrank_binarytree(2,3)

unrank_binarytree(3,3)

unrank_binarytree(4,3)

def random_binarytree(n):
    """
    Return random binary tree of size n drawn uniformly
    """
    card = cardinality_binaryTrees(n)
    i = randint(0,card-1)
    return unrank_binarytree(i,n)

random_binarytree(5)

random_binarytree(50)

bt = random_binarytree(100)
bt

bt.node_number()