The shuffle of k words
u_1
,…,
u_k
is the set of words
obtained by interleaving the letters of these words such that the order of
appearance of all letters of each word is respected. The study of the shuffle
product of words leads to the construction of an automaton whose structure is
deeply connected to a family of trees which we call araucarias. We prove many
structural properties of this family of trees and give some combinatorial
results. We introduce a family of remarkable symmetrical polynomials which play
a crucial role in the computation of the size of the araucarias. We prove that
the minimal partial automaton which recognizes the shuffle of a finite number
of special words contains an araucaria for each integer k>0.
