[seqfan] Re: Intersections of x^x^...^x

Alois Heinz heinz at hs-heilbronn.de
Thu Nov 3 11:53:43 CET 2011

See this comment from A000081:

Take a string of n x's and insert n-1 ^'s and n-1 pairs of parentheses
in all possible legal ways (cf. A003018). Sequence gives number of
distinct functions. The single node tree is "x". Making a node f2 a
child of f1 represents f1^f2. Since (f1^f2)^f3 is just f1^(f2*f3) we
can think of it as f1 raised to both f2 and f3, that is, f1 with f2
and f3 as children. E.g. for n=4 the distinct functions are
((x^x)^x)^x; (x^(x^x))^x; x^((x^x)^x); x^(x^(x^x )). - Edwin Clark
(eclark(AT)math.usf.edu) and Russ Cox (rsc(AT)swtch.com) Apr 29, 2003;
corrected by Keith Briggs (keith.briggs(AT)bt.com), Nov 14 2005

See also comment in https://oeis.org/draft/A199085

Vladimir Reshetnikov: A000081 gives a number of distinct function that
can be obtained by parenthesizing x^x^...^x. So, it is an upper bound
for this sequence.


Am 03.11.2011 09:39, schrieb franktaw at netscape.net:
> It's perhaps a subtle point, but he asked for intersections of the 
> functions, not of the expressions. Expressions that produce the same 
> function are not considered different.
> On a related note, I can't find the number of distinct function with n 
> x's in the database. I can find a number of cases where a particular 
> value of x is counted, but not the general case. Is it there and I'm 
> just not looking for it right? If it isn't there, it should be added.
> Franklin T. Adams-Watters

More information about the SeqFan mailing list