Combinatorics of balanced carries

DOI10.1016/J.AAM.2014.05.005MaRDI QIDQ404287zbMATH OpenOpenAlexFDO

Authors Jason Fulman, Persi Diaconis

Publication date 4 September 2014

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.5116

zbMATH Keywords

Markov chaindeterminantal processcarriesEulerian idempotentFoulkes character

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Combinatorial probability (60C05)

Abstract: We study the combinatorics of addition using balanced digits, deriving an analog of Holte's "amazing matrix" for carries in usual addition. The eigenvalues of this matrix for base b balanced addition of n numbers are found to be 1,1/b,...,1/b^n, and formulas are given for its left and right eigenvectors. It is shown that the left eigenvectors can be identified with hyperoctahedral Foulkes characters, and that the right eigenvectors can be identified with hyperoctahedral Eulerian idempotents. We also examine the carries that occur when a column of balanced digits is added, showing this process to be determinantal. The transfer matrix method and a serendipitous diagonalization are used to study this determinantal process.

Recommendations

• scientific article; zbMATH DE number 3849241
• Carries, Combinatorics, and an Amazing Matrix
• scientific article; zbMATH DE number 4179388
• scientific article; zbMATH DE number 22635
• Carries, shuffling, and symmetric functions
• Carries, group theory, and additive combinatorics
• Balancing permuted copies of multigraphs and integer matrices
• Combinatorial configurations in balance layout optimization problems
• The log-balancedness of combinatorial sequences
• On the balanced decomposition number

Cites work

• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 6604219 (Why is no real title available?)
• A Cohomological Viewpoint on Elementary School Arithmetic
• A generalization of carries processes and Eulerian numbers
• Applied finite group actions.
• Carries, Combinatorics, and an Amazing Matrix
• Carries, shuffling, and an amazing matrix
• Carries, shuffling, and symmetric functions
• Foulkes characters, Eulerian idempotents, and an amazing matrix
• Hopf algebras and Markov chains: two examples and a theory
• Minimizing the number of carries in addition
• Noncommutative symmetric functions and an amazing matrix
• On adding a list of numbers (and other one-dependent determinantal processes)
• Orthogonal idempotents in the descent algebra of \(B_ n\) and applications
• The Veronese construction for formal power series and graded algebras

Cited in

(10)

• Carries, group theory, and additive combinatorics
• A generalization of carries processes and Eulerian numbers
• On Foulkes characters
• Proof of a conjecture on the total positivity of amazing matrices
• A generalization of carries process and riffle shuffles
• Determinantal formula for generalized riffle shuffle
• Foulkes characters, Eulerian idempotents, and an amazing matrix
• The characters of symmetric groups that depend only on length
• Analysis of carries in signed digit expansions
• Topology of arrangements and representation stability. Abstracts from the workshop held January 14--20, 2018

This page was built for publication: Combinatorics of balanced carries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q404287)