Dynamics of the Picking transformation on integer partitions

Phan Ti Duong (1) , Eric Thierry (2)

1 LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications
2 LIP - Laboratoire de l'Informatique du Parallélisme

This paper studies a conservative transformation defined on families of finite sets. It consists in removing one element from each set and adding a new set composed of the removed elements. This transformation is conservative in the sense that the union of all sets of the family always remains the same. We study the dynamical process obtained when iterating this transformation on a family of sets and we focus on the evolution of the cardinalities of the sets of the family. This point of view allows to consider the transformation as an application defined on the set of all partitions of a fixed integer (which is the total number of elements in the sets). We show that iterating this particular transformation always leads to a heterogeneous distribution of the cardinalities, where almost all integers within an interval are represented. We also tackle some issues concerning the structure of the transition graph which sums up the whole dynamics of this process for all partitions of a fixed integer.

Ce papier étudie une transformation sur les familles d'ensembles finis qui consiste à enlever un élément de chaque ensemble et ajouter un nouvel ensemble composé des éléments qui viennent d'être retirés. Cette transformation set conservative au sen où l'union de tous les ensembles de la famille reste toujours la même. Nous étudions le processus dynamique obtenu en itérant cette transformations sur une famille d’ensembles et nous nous intéressons à l’évolution du cardinal de chacun des ensembles de la famille. Avec ce point de vue, la transformation devient une application définie sur ensemble des partitions d'un entier fixé (qui est le nombre total d'éléments dans la famille initiale). Nous montrons qu'itérer cette transformation converge toujours vers une distribution hétérogène des cardinaux, où presque tous les entiers d'un intervalle sont représentés. Nous abordons aussi d'autres questions concernant la structure du graphe des transitions qui représente la dynamique de ce processus pour toutes les partitions d'un entier fixé

Mots clés: Discrete Dynamical System; Integer Partitions

Mots clés: Systèmes dynamiques discrets; Partitions des entiers

Domaines: Informatique [cs]

Phan Ti Duong, Eric Thierry. Dynamics of the Picking transformation on integer partitions. [Research Report] LIP RR-2003-26, Laboratoire de l'informatique du parallélisme. 2003, 2+13p. ⟨hal-02101820⟩