Page 1 Next

Displaying 1 – 20 of 284

Showing per page

A CAT algorithm for the exhaustive generation of ice piles

Paolo Massazza, Roberto Radicioni (2011)

RAIRO - Theoretical Informatics and Applications

We present a CAT (constant amortized time) algorithm for generating those partitions of n that are in the ice pile model IPM k (n), a generalization of the sand pile model SPM (n). More precisely, for any fixed integer k, we show that the negative lexicographic ordering naturally identifies a tree structure on the lattice IPM k (n): this lets us design an algorithm which generates all the ice piles of IPM k (n) in amortized time O(1) and in space O( n ).

A CAT algorithm for the exhaustive generation of ice piles

Paolo Massazza, Roberto Radicioni (2010)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We present a CAT (constant amortized time) algorithm for generating those partitions of n that are in the ice pile model IPM k (n), a generalization of the sand pile model SPM (n). More precisely, for any fixed integer k, we show that the negative lexicographic ordering naturally identifies a tree structure on the lattice IPM k (n): this lets us design an algorithm which generates all the ice piles of IPM k (n) in amortized time O(1) and in space O( n ).

A combinatorial approach to partitions with parts in the gaps

Dennis Eichhorn (1998)

Acta Arithmetica

Many links exist between ordinary partitions and partitions with parts in the “gaps”. In this paper, we explore combinatorial explanations for some of these links, along with some natural generalizations. In particular, if we let p k , m ( j , n ) be the number of partitions of n into j parts where each part is ≡ k (mod m), 1 ≤ k ≤ m, and we let p * k , m ( j , n ) be the number of partitions of n into j parts where each part is ≡ k (mod m) with parts of size k in the gaps, then p * k , m ( j , n ) = p k , m ( j , n ) .

Currently displaying 1 – 20 of 284

Page 1 Next