On the number of hypercubic bipartitions of an integer

Autor:	Geir Agnarsson
Rok vydání:	2013
Předmět:	Discrete mathematics Induced subgraph Generating function Characterization (mathematics) Theoretical Computer Science Combinatorics Integer FOS: Mathematics 05A15 05C35 Mathematics - Combinatorics Discrete Mathematics and Combinatorics Combinatorics (math.CO) Hypercube Mathematics
Zdroj:	Discrete Mathematics. 313:2857-2864
ISSN:	0012-365X
DOI:	10.1016/j.disc.2013.08.033
Popis:	We revisit a well-known divide-and-conquer maximin recurrence $f(n) = \max(\min(n_1,n_2) + f(n_1) + f(n_2))$ where the maximum is taken over all proper bipartitions $n = n_1+n_2$, and we present a new characterization of the pairs $(n_1,n_2)$ summing to $n$ that yield the maximum $f(n) = \min(n_1,n_2) + f(n_1) + f(n_2)$. This new characterization allows us, for a given $n\in\nats$, to determine the number $h(n)$ of these bipartitions that yield the said maximum $f(n)$. We present recursive formulae for $h(n)$, a generating function $h(x)$, and an explicit formula for $h(n)$ in terms of a special representation of $n$. Comment: 13 pages
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::cbaf9bddda9cc80d5d25a3a66162100c https://doi.org/10.1016/j.disc.2013.08.033 Zobrazit plný text záznamu Full Text from ScienceDirect