login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A079438 a(0) = a(1) = 1, a(n) = 2*(floor((n+1)/3) + (if n >= 14) (floor((n-10)/4) + floor((n-14)/8))). 10

%I #32 Jan 19 2019 07:05:44

%S 1,1,2,2,2,4,4,4,6,6,6,8,8,8,12,12,12,14,16,16,18,18,22,24,24,24,28,

%T 28,28,30,34,34,36,36,38,40,40,40,46,46,46,48,50,50,52,52,56,58,58,58,

%U 62,62,62,64,68,68,70,70,72,74,74,74,80,80,80,82,84,84,86,86,90,92,92,92

%N a(0) = a(1) = 1, a(n) = 2*(floor((n+1)/3) + (if n >= 14) (floor((n-10)/4) + floor((n-14)/8))).

%C The original definition was: Number of rooted general plane trees which are symmetric and will stay symmetric after the underlying plane binary tree has been reflected, i.e., number of integers i in range [A014137(n-1)..A014138(n-1)] such that A057164(i) = i and A057164(A057163(i)) = A057163(i).

%C (Thus also) the number of fixed points in range [A014137(n-1)..A014138(n)] of permutation A071661 (= Donaghey's automorphism M "squared"), which is equal to condition A057164(i) = A069787(i) = i, i.e., the size of the intersection of fixed points of permutations A057164 and A069787 in the same range.

%C Additional comment from _Antti Karttunen_, Dec 13 2017: (Start)

%C However, _David Callan_'s A123050 claims to give more correct version of that count from n=26 onward, so I probably made a little mistake when converting my insights into the formula given here. At that time I reckoned that if the conjecture given in A080070 were true, then it would imply that the formula given here were exact, otherwise it would give only a lower bound.

%C It would be nice to know what an empirical program would give as the count of fixed points of A071661 for n in range [A014137(25)..A014138(26)] = [6619846420553 .. 24987199492704], with total A000108(26) = 18367353072151 points to check.

%C (End)

%D D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 4: Generating All Trees--History of Combinatorial Generation, vi+120pp. ISBN 0-321-33570-8 Addison-Wesley Professional; 1ST edition (Feb 06, 2006).

%H G. C. Greubel, <a href="/A079438/b079438.txt">Table of n, a(n) for n = 0..10000</a>

%H R. Donaghey, <a href="https://doi.org/10.1016/0095-8956(80)90045-3">Automorphisms on Catalan trees and bracketing</a>, J. Combin. Theory, Series B, 29 (1980), 75-90.

%H A. Karttunen, <a href="/A089408/a089408.c.txt">C-program for counting the initial terms of this sequence (empirically)</a>

%H A. Karttunen, <a href="/A079438/a079438.pdf">Illustration of initial terms for trees of sizes n=2..18</a>

%H A. Karttunen, <a href="https://oeis.org/wiki/User:Antti_Karttunen/Speculations/On_the_fixed_points_of_A071661">On the fixed points of A071661</a> (Notes in OEIS Wiki)

%H D. E. Knuth, <a href="http://www-cs-staff.Stanford.EDU/~knuth/fasc4a.ps.gz">Pre-Fascicle 4a: Generating All Trees</a>, Exercise 17, 7.2.1.6.

%F a(0) = a(1) = 1, a(n) = 2*(floor((n+1)/3) + (if n >= 14) (floor((n-10)/4) + floor((n-14)/8))).

%p A079438 := n -> `if`((n<2),1,2*(floor((n+1)/3) + `if`((n>=14),floor((n-10)/4)+floor((n-14)/8),0)));

%t a[0]:= 1; a[1]:= 1; a[n_]:= a[n] = 2*Floor[(n+1)/3] +2*If[ n >= 14, (Floor[(n-10)/4] +Floor[(n-14)/8]), 0]; Table[a[n], {n, 0, 100}] (* _G. C. Greubel_, Jan 18 2019 *)

%o (PARI) {a(n) = if(n==0, 1, if(n==1, 1, 2*floor((n+1)/3) + 2*if(n >= 14, floor( (n-10)/4) + floor((n-14)/8), 0)))}; \\ _G. C. Greubel_, Jan 18 2019

%Y Cf. A000108, A057163, A057164, A057505, A069787, A071661, A079437, A079439, A079442, A080070, A243490, A243491, A243492.

%Y From n>= 2 onward A079440(n) = a(n)/2.

%Y Occurs in A073202 as row 13373289.

%Y Differs from A123050 for the first time at n=26.

%K nonn

%O 0,3

%A _Antti Karttunen_, Jan 27 2003

%E Entry edited (the definition replaced by a formula, the old definition moved to the comments) - _Antti Karttunen_, Dec 13 2017

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 04:05 EDT 2024. Contains 371235 sequences. (Running on oeis4.)