# American Institute of Mathematical Sciences

May  2008, 2(2): 159-173. doi: 10.3934/amc.2008.2.159

## A combinatorial interpretation of double base number system and some consequences

 1 Center for Information Security and Cryptography, University of Calgary, 2500 University Drive NW, Calgary, AB T2N 1N4, Canada, Canada

Received  September 2007 Revised  February 2008 Published  April 2008

In Signal Processing and Cryptography a non-standard number representation, called Double Base Number System (DBNS) has found many applications. This representation has many interesting and useful properties. In traditional number systems, there is one radix used to represent numbers. For example in decimal systems, numbers are expressed as sum of powers of 10. In DBNS numbers are represented as sum of product of powers of 2 radices. In the current article we present a scheme to represent numbers in double (and multi-) base format by combinatorial objects like graphs and diagraphs. The combinatorial representation leads to proof of some interesting results about the double and multibase representation of integers. These proofs are based on simple combinatorial arguments. In this article we have provided a graph theoretic proof of the recurrence relation satisfied by the number of double base representations of a given integer. The result has been further generalized to more than 2 bases. Also, we have uncovered some interesting properties of the sequence representing the number of double (multi-) base representation of a positive integer $n$. It is expected that the combinatorial representation can serve as a tool for a better understanding of the double (and multi-) base number systems and uncover some of the mysteries still associated with it.
Citation: Pradeep Kumar Mishra, Vassil Dimitrov. A combinatorial interpretation of double base number system and some consequences. Advances in Mathematics of Communications, 2008, 2 (2) : 159-173. doi: 10.3934/amc.2008.2.159
 [1] David Auger, Irène Charon, Iiro Honkala, Olivier Hudry, Antoine Lobstein. Edge number, minimum degree, maximum independent set, radius and diameter in twin-free graphs. Advances in Mathematics of Communications, 2009, 3 (1) : 97-114. doi: 10.3934/amc.2009.3.97 [2] Roberto de A. Capistrano–Filho, Márcio Cavalcante, Fernando A. Gallego. Controllability for Schrödinger type system with mixed dispersion on compact star graphs. Evolution Equations and Control Theory, 2022  doi: 10.3934/eect.2022019 [3] Litao Guo, Bernard L. S. Lin. Vulnerability of super connected split graphs and bisplit graphs. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1179-1185. doi: 10.3934/dcdss.2019081 [4] Srimathy Srinivasan, Andrew Thangaraj. Codes on planar Tanner graphs. Advances in Mathematics of Communications, 2012, 6 (2) : 131-163. doi: 10.3934/amc.2012.6.131 [5] Cristina M. Ballantine. Ramanujan type graphs and bigraphs. Conference Publications, 2003, 2003 (Special) : 78-82. doi: 10.3934/proc.2003.2003.78 [6] Daniele D'angeli, Alfredo Donno, Michel Matter, Tatiana Nagnibeda. Schreier graphs of the Basilica group. Journal of Modern Dynamics, 2010, 4 (1) : 167-205. doi: 10.3934/jmd.2010.4.167 [7] James B. Kennedy, Jonathan Rohleder. On the hot spots of quantum graphs. Communications on Pure and Applied Analysis, 2021, 20 (9) : 3029-3063. doi: 10.3934/cpaa.2021095 [8] Yong Lin, Gábor Lippner, Dan Mangoubi, Shing-Tung Yau. Nodal geometry of graphs on surfaces. Discrete and Continuous Dynamical Systems, 2010, 28 (3) : 1291-1298. doi: 10.3934/dcds.2010.28.1291 [9] Dina Ghinelli, Jennifer D. Key. Codes from incidence matrices and line graphs of Paley graphs. Advances in Mathematics of Communications, 2011, 5 (1) : 93-108. doi: 10.3934/amc.2011.5.93 [10] Wooyeon Kim, Seonhee Lim. Notes on the values of volume entropy of graphs. Discrete and Continuous Dynamical Systems, 2020, 40 (9) : 5117-5129. doi: 10.3934/dcds.2020221 [11] Renato Iturriaga, Héctor Sánchez Morgado. The Lax-Oleinik semigroup on graphs. Networks and Heterogeneous Media, 2017, 12 (4) : 643-662. doi: 10.3934/nhm.2017026 [12] Thomas Zaslavsky. Quasigroup associativity and biased expansion graphs. Electronic Research Announcements, 2006, 12: 13-18. [13] Deng Lu, Maria De Iorio, Ajay Jasra, Gary L. Rosner. Bayesian inference for latent chain graphs. Foundations of Data Science, 2020, 2 (1) : 35-54. doi: 10.3934/fods.2020003 [14] Leandro M. Del Pezzo, Nicolás Frevenza, Julio D. Rossi. Convex and quasiconvex functions in metric graphs. Networks and Heterogeneous Media, 2021, 16 (4) : 591-607. doi: 10.3934/nhm.2021019 [15] Delio Mugnolo, Abdelaziz Rhandi. Ornstein–Uhlenbeck semigroups on star graphs. Discrete and Continuous Dynamical Systems - S, 2022  doi: 10.3934/dcdss.2022030 [16] Fabio Camilli, Adriano Festa, Silvia Tozza. A discrete Hughes model for pedestrian flow on graphs. Networks and Heterogeneous Media, 2017, 12 (1) : 93-112. doi: 10.3934/nhm.2017004 [17] Luca Schenato, Sandro Zampieri. On rendezvous control with randomly switching communication graphs. Networks and Heterogeneous Media, 2007, 2 (4) : 627-646. doi: 10.3934/nhm.2007.2.627 [18] Joachim von Below, José A. Lubary. Isospectral infinite graphs and networks and infinite eigenvalue multiplicities. Networks and Heterogeneous Media, 2009, 4 (3) : 453-468. doi: 10.3934/nhm.2009.4.453 [19] Braxton Osting, Jérôme Darbon, Stanley Osher. Statistical ranking using the $l^{1}$-norm on graphs. Inverse Problems and Imaging, 2013, 7 (3) : 907-926. doi: 10.3934/ipi.2013.7.907 [20] Jeremias Epperlein, Stefan Siegmund. Phase-locked trajectories for dynamical systems on graphs. Discrete and Continuous Dynamical Systems - B, 2013, 18 (7) : 1827-1844. doi: 10.3934/dcdsb.2013.18.1827

2021 Impact Factor: 1.015