login
Common residues of binomial(3n,n)/(2n+1) modulo 2: relates ternary trees (A001764) to the infinite Fibonacci word (A003849).
16

%I #55 Sep 08 2022 08:45:11

%S 1,1,1,0,1,1,0,0,1,1,1,0,0,0,0,0,1,1,1,0,1,1,0,0,0,0,0,0,0,0,0,0,1,1,

%T 1,0,1,1,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,

%U 1,1,0,0,1,1,1,0,0,0,0,0,1,1,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

%N Common residues of binomial(3n,n)/(2n+1) modulo 2: relates ternary trees (A001764) to the infinite Fibonacci word (A003849).

%C The n-th runs of ones is given by: 3 - A003849(n) (infinite Fibonacci word) = A076662(n+1). Runs of zeros are given by: A085358 and are also directly related to the Fibonacci sequence. Coefficients of A(x)^3 are found in A085359.

%C a(n) = 0 iff some binary digit of n is 1 while the corresponding binary digit of 3*n is 0. - _Robert Israel_, Jul 12 2016

%C The Run Length Transform of [0,1,0,0,0,...], A063524, the characteristic function of 1. (See A227349 for the definition). - _Antti Karttunen_, Oct 15 2016

%H Robert Israel, <a href="/A085357/b085357.txt">Table of n, a(n) for n = 0..10000</a>

%H J.-P. Allouche, F. v. Haeseler, H.-O. Peitgen, A. Petersen and G. Skordev, <a href="http://dx.doi.org/10.1016/S0304-3975(96)00298-8">Automaticity of double sequences generated by one-dimensional linear cellular automata</a>, Theoret. Comput. Sci. 186 (1997), 195-209.

%H J.-P. Allouche, F. v. Haeseler, H.-O. Peitgen and G. Skordev, <a href="http://dx.doi.org/10.1016/0166-218X(94)00132-W">Linear cellular automata, finite automata and Pascal's triangle</a>, Discrete Appl. Math. 66 (1996), 1-22.

%H R. Bacher, C. Reutenauer, <a href="http://bookstore.ams.org/conm-592/12">The number of right ideals of given codimension over a finite field</a>, in Noncommutative Birational Geometry, Representations and Combinatorics, edited by Arkady. Berenstein and Vladimir. Retakha, Contemporary Mathematics, Vol. 592, 2013.

%H Paul Tarau, <a href="http://dx.doi.org/10.1007/978-3-642-23283-1_15">Emulating Primality with Multiset Representations of Natural Numbers</a>, in Theoretical Aspects of Computing, ICTAC 2011, Lecture Notes in Computer Science, 2011, Volume 6916/2011, 218-238, DOI: 10.1007/978-3-642-23283-1_15.

%H <a href="/index/Ch#char_fns">Index entries for characteristic functions</a>

%H <a href="/index/Ru#rlt">Index entries for sequences computed with run length transform</a>

%F G.f.: 1 + x*A(x)^3 = A(x) (Mod 2); a(n) = A001764(n) (Mod 2).

%F a(n) = binomial(3n, n) (mod 2). Characteristic function of Fibbinary numbers (i.e. a(n)=1 iff n is in A003714). - _Benoit Cloitre_, Nov 15 2003

%F Recurrence: a(0) = 1, a(2n) = a(4n+1) = a(n), a(4n+3) = 0.

%F a(n-2) = A000256(n)(mod 2), for n>2. - _John M. Campbell_, Jul 08 2016

%F a(n) = A000621(n+1)(mod 2). - _John M. Campbell_, Jul 15 2016

%F a(n) = A000625(n)(mod 2). - _John M. Campbell_, Jul 15 2016

%F a(n) = A008966(A005940(1+n)). [Follows from the Run Length Transform interpretation, see also A277010.] - _Antti Karttunen_, Oct 15 2016

%F a(n) = abs(A132971(n)) = abs(A008683(A005940(1+n))). - _Antti Karttunen_, May 30 2017

%p f:= proc(n) local L,Lp;

%p L:= convert(n,base,2);

%p Lp:= convert(3*n,base,2);

%p if has(L-Lp[1..nops(L)],1) then 0 else 1 fi

%p end proc:

%p map(f, [$0..100]); # _Robert Israel_, Jul 12 2016

%t Table[Mod[Binomial[3 n, n], 2], {n, 0, 120}] (* _Michael De Vlieger_, Jul 08 2016 *)

%o (Magma) [Binomial(3*n,n) mod 2: n in [0..100]]; // _Vincenzo Librandi_, Jul 09 2016

%o (PARI) A085357(n) = !bitand(n,n<<1); \\ _Antti Karttunen_, Aug 22 2019

%Y Cf. A001764 (ternary trees), A085358 (runs of zeros), A076662 (runs of ones), A003849 (infinite Fibonacci word), A085359 (A(x)^3).

%Y Cf. also A003714, A005940, A008966, A063524, A227349, A277010, A324964.

%Y Absolute values of A132971.

%K nonn

%O 0,1

%A _Paul D. Hanna_, Jun 25 2003