A216041 Number of redundant function representations of x^x^...^x with n x's and parentheses inserted in all possible ways.

0, 0, 0, 1, 5, 22, 84, 314, 1144, 4143, 14954, 54020, 195526, 709927, 2586629, 9459464, 34722823, 127923631, 472950024, 1754436962, 6528898588, 24369211839, 91214280785, 342315888666, 1287836972679, 4856186764942, 18351269337823, 69488543849735

Offset: 1

Author

Alois P. Heinz, Aug 30 2012

Keywords

• nonn

Comments

A000081(n) distinct functions are representable as x -> x^x^...^x with n x's and parentheses inserted in all possible ways. The number of valid parenthesizations is A000108(n-1). So the number of redundant representations is A000108(n-1) - A000081(n).

For n>=6 we have a(n) > A000081(n), so the number of redundant function representations is larger than the number of essential representations.

Examples

			a(4) = 1: there are A000108(3) = 5 valid parenthesizations of x^x^x^x, namely x^(x^(x^x)), x^((x^x)^x), (x^(x^x))^x, (x^x)^(x^x), ((x^x)^x)^x, but only A000081(4) = 4 distinct functions. (x^(x^x))^x and (x^x)^(x^x) represent the same function x -> x^(x^x*x), so 1 representation is redundant.
		

Links

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

Crossrefs

Cf. A000081, A000108, A215703.

Programs

Maple

with(numtheory):
b:= proc(n) option remember; `if`(n<=1, n,
      (add(add(d*b(d), d=divisors(j))*b(n-j), j=1..n-1))/(n-1))
    end:
C:= n-> binomial(2*n, n)/(n+1):
a:= n-> C(n-1) -b(n):
seq(a(n), n=1..40);

Mathematica

b[n_] := b[n] = If[n <= 1, n, Sum[DivisorSum[j, #*b[#]&]*b[n-j], {j, 1, n-1}]/(n-1)];
c[n_] := Binomial[2*n, n]/(n+1);
a[n_] := c[n-1] - b[n];
Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Mar 24 2017, translated from Maple *)

Formula

a(n) = A000108(n-1) - A000081(n).