Combinatorics of balanced carries

DOI10.1016/J.AAM.2014.05.005zbMATH Open1308.60018arXiv1309.5116OpenAlexW2038000335MaRDI QIDQ404287FDOQ404287

Authors: Jason Fulman, Persi Diaconis 

Publication date: 4 September 2014

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

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.

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

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

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)

Cites Work

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

Cited In (10)

• A generalization of carries processes and Eulerian numbers
• Foulkes characters, Eulerian idempotents, and an amazing matrix
• On Foulkes characters
• Topology of arrangements and representation stability. Abstracts from the workshop held January 14--20, 2018
• Carries, group theory, and additive combinatorics
• 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
• Analysis of carries in signed digit expansions
• The characters of symmetric groups that depend only on length

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)