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,5

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.

Links

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

Formula

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

Example

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.

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 *)

Crossrefs

Cf. A000081, A000108, A215703.

Sequence in context: A266358 A183925 A296583 * A122058 A191008 A006148

Adjacent sequences: A216038 A216039 A216040 * A216042 A216043 A216044

Keyword

nonn

Author

Alois P. Heinz, Aug 30 2012

Status

approved