اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدIsoperimetric Sequences for Infinite Complete Binary Trees, Meta-Fibonacci Sequences and Signed Almost Binary Partitions
193
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In this paper we demonstrate connections between three seemingly unrelated concepts. (1) The discrete isoperimetric problem in the infinite binary tree with all the leaves at the same level, $ {mathcal T}_{infty}$: The $n$-th edge isoperimetric number $delta(n)$ is defined to be $min_{|S|=n, S subset V({mathcal T}_{infty})} |(S,bar{S})|$, where $(S,bar{S})$ is the set of edges in the cut defined by $S$. (2) Signed almost binary partitions: This is the special case of the coin-changing problem where the coins are drawn from the set ${pm (2^d - 1): $d$ is a positive integer}$. The quantity of interest is $tau(n)$, the minimum number of coins necessary to make change for $n$ cents. (3) Certain Meta-Fibonacci sequences: The Tanny sequence is defined by $T(n)=T(n{-}1{-}T(n{-}1))+T(n{-}2{-}T(n{-}2))$ and the Conolly sequence is defined by $C(n)=C(n{-}C(n{-}1))+C(n{-}1{-}C(n{-}2))$, where the initial conditions are $T(1) = C(1) = T(2) = C(2) = 1$. These are well-known meta-Fibonacci sequences. The main result that ties these three together is the following: $$ delta(n) = tau(n) = n+ 2 + 2 min_{1 le k le n} (C(k) - T(n-k) - k).$$ Apart from this, we prove several other results which bring out the interconnections between the above three concepts.
قيم البحث
اقرأ أيضاً
Building on a bijection of Vandervelde, we enumerate certain unimodal sequences whose alternating sum equals zero. This enables us to refine the enumeration of strict partitions with respect to the number of parts and the BG-rank.
We study the generalized random Fibonacci sequences defined by their first nonnegative terms and for $nge 1$, $F_{n+2} = lambda F_{n+1} pm F_{n}$ (linear case) and $widetilde F_{n+2} = |lambda widetilde F_{n+1} pm widetilde F_{n}|$ (non-linear case),
where each $pm$ sign is independent and either $+$ with probability $p$ or $-$ with probability $1-p$ ($0<ple 1$). Our main result is that, when $lambda$ is of the form $lambda_k = 2cos (pi/k)$ for some integer $kge 3$, the exponential growth of $F_n$ for $0<ple 1$, and of $widetilde F_{n}$ for $1/k < ple 1$, is almost surely positive and given by $$ int_0^infty log x d u_{k, rho} (x), $$ where $rho$ is an explicit function of $p$ depending on the case we consider, taking values in $[0, 1]$, and $ u_{k, rho}$ is an explicit probability distribution on $RR_+$ defined inductively on generalized Stern-Brocot intervals. We also provide an integral formula for $0<ple 1$ in the easier case $lambdage 2$. Finally, we study the variations of the exponent as a function of $p$.
An edge-ordered graph is a graph with a total ordering of its edges. A path $P=v_1v_2ldots v_k$ in an edge-ordered graph is called increasing if $(v_iv_{i+1}) > (v_{i+1}v_{i+2})$ for all $i = 1,ldots,k-2$; it is called decreasing if $(v_iv_{i+1}) < (
v_{i+1}v_{i+2})$ for all $i = 1,ldots,k-2$. We say that $P$ is monotone if it is increasing or decreasing. A rooted tree $T$ in an edge-ordered graph is called monotone if either every path from the root of to a leaf is increasing or every path from the root to a leaf is decreasing. Let $G$ be a graph. In a straight-line drawing $D$ of $G$, its vertices are drawn as different points in the plane and its edges are straight line segments. Let $overline{alpha}(G)$ be the maximum integer such that every edge-ordered straight-line drawing of $G$ %under any edge labeling contains a monotone non-crossing path of length $overline{alpha}(G)$. Let $overline{tau}(G)$ be the maximum integer such that every edge-ordered straight-line drawing of $G$ %under any edge labeling contains a monotone non-crossing complete binary tree of size $overline{tau}(G)$. In this paper we show that $overline alpha(K_n) = Omega(loglog n)$, $overline alpha(K_n) = O(log n)$, $overline tau(K_n) = Omega(loglog log n)$ and $overline tau(K_n) = O(sqrt{n log n})$.
The generalized Fibonacci sequences are sequences ${f_n}$ which satisfy the recurrence $f_n(s, t) = sf_{n - 1}(s, t) + tf_{n - 2}(s, t)$ ($s, t in mathbb{Z}$) with initial conditions $f_0(s, t) = 0$ and $f_1(s, t) = 1$. In a recent paper, Amdeberhan,
Chen, Moll, and Sagan considered some arithmetic properites of the generalized Fibonacci sequence. Specifically, they considered the behavior of analogues of the $p$-adic valuation and the Riemann zeta function. In this paper, we resolve some conjectures which they raised relating to these topics. We also consider the rank modulo $n$ in more depth and find an interpretation of the rank in terms of the order of an element in the multiplicative group of a finite field when $n$ is an odd prime. Finally, we study the distribution of the rank over different values of $s$ when $t = -1$ and suggest directions for further study involving the rank modulo prime powers of generalized Fibonacci sequences.
We study two kinds of random Fibonacci sequences defined by $F_1=F_2=1$ and for $nge 1$, $F_{n+2} = F_{n+1} pm F_{n}$ (linear case) or $F_{n+2} = |F_{n+1} pm F_{n}|$ (non-linear case), where each sign is independent and either + with probability $p$
or - with probability $1-p$ ($0<ple 1$). Our main result is that the exponential growth of $F_n$ for $0<ple 1$ (linear case) or for $1/3le ple 1$ (non-linear case) is almost surely given by $$int_0^infty log x d u_alpha (x), $$ where $alpha$ is an explicit function of $p$ depending on the case we consider, and $ u_alpha$ is an explicit probability distribution on $RR_+$ defined inductively on Stern-Brocot intervals. In the non-linear case, the largest Lyapunov exponent is not an analytic function of $p$, since we prove that it is equal to zero for $0<ple1/3$. We also give some results about the variations of the largest Lyapunov exponent, and provide a formula for its derivative.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
