login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A222380 Number of distinct functions f representable as x -> x^x^...^x with n x's and parentheses inserted in all possible ways giving result f(0)=1, with conventions that 0^0=1^0=1^1=1, 0^1=0. 7
0, 0, 1, 1, 3, 5, 14, 29, 77, 179, 472, 1174, 3100, 8018, 21370, 56601, 152337, 409954, 1113501, 3030710, 8298035, 22780468, 62800860, 173586690, 481335403, 1337916253, 3728371645, 10412163861, 29139846448, 81705768401, 229513225545, 645777766253 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

A000081(n) distinct functions are representable as x -> x^x^...^x with n x's and parentheses inserted in all possible ways.  Some functions are representable in more than one way, the number of valid parenthesizations is A000108(n-1) for n>0.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Alois P. Heinz, Plot of A000081(8) = 115 = 77 + 38 functions with 8 x's

Wikipedia, Zero to the power of zero

FORMULA

a(n) + A222379(n) = A000081(n).

a(n) - A222379(n) = A211192(n).

a(n) = Sum_{i=A087803(n-1)+1..A087803(n)} A306710(i).

EXAMPLE

There are A000081(4) = 4 functions f representable as x -> x^x^...^x with 4 x's and parentheses inserted in all possible ways: ((x^x)^x)^x, (x^x)^(x^x) == (x^(x^x))^x, x^((x^x)^x), x^(x^(x^x)).  Only x^((x^x)^x) evaluates to 0 at x=0: 0^((0^0)^0) = 0^(1^0) = 0^1 = 0.  Three functions evaluate to 1 at x=0: ((0^0)^0)^0 = (1^0)^0 = 1^0 = 1, (0^0)^(0^0) = 1^1 = 1, 0^(0^(0^0)) = 0^(0^1) = 0^0 = 1. Thus a(4) = 3.

MAPLE

g:= proc(n, i) option remember; `if`(n=0, [0, 1], `if`(i<1, 0, (v->[v[1]-

      v[2], v[2]])(add(((l, h)-> [binomial(l[2]+l[1]+j-1, j)*(h[1]+h[2]),

      binomial(l[1]+j-1, j)*h[2]])(g(i-1$2), g(n-i*j, i-1)), j=0..n/i))))

    end:

a:= n-> g(n-1$2)[1]:

seq(a(n), n=0..40);

MATHEMATICA

f[l_, h_] := {Binomial[l[[2]] + l[[1]] + j - 1, j]*(h[[1]] + h[[2]]), Binomial[l[[1]] + j - 1, j]*h[[2]]};

g[n_, i_] := g[n, i] = If[n == 0, {0, 1}, If[i < 1, {0, 0}, Function[v, {v[[1]] - v[[2]], v[[2]]}][Sum[f[g[i - 1, i - 1], g[n - i*j, i - 1]], {j, 0, Quotient[n, i]}]]]];

a[n_] := g[n - 1, n - 1][[1]];

Table[a[n], {n, 0, 40}] (* Jean-Fran├žois Alcover, Feb 27 2019, after Alois P. Heinz *)

CROSSREFS

Cf. A000081, A000108, A055113, A087803, A211192, A215703, A222379, A306710.

Sequence in context: A147544 A192478 A198785 * A271867 A295064 A052974

Adjacent sequences:  A222377 A222378 A222379 * A222381 A222382 A222383

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Feb 17 2013

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 23 22:32 EDT 2020. Contains 337315 sequences. (Running on oeis4.)