cp's OEIS Frontend

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

%I A216041 #16 Mar 24 2017 06:46:37
%S A216041 0,0,0,1,5,22,84,314,1144,4143,14954,54020,195526,709927,2586629,
%T A216041 9459464,34722823,127923631,472950024,1754436962,6528898588,
%U A216041 24369211839,91214280785,342315888666,1287836972679,4856186764942,18351269337823,69488543849735
%N A216041 Number of redundant function representations of x^x^...^x with n x's and parentheses inserted in all possible ways.
%C A216041 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).
%C A216041 For n>=6 we have a(n) > A000081(n), so the number of redundant function representations is larger than the number of essential representations.
%H A216041 Alois P. Heinz, <a href="/A216041/b216041.txt">Table of n, a(n) for n = 1..1000</a>
%F A216041 a(n) = A000108(n-1) - A000081(n).
%e A216041 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.
%p A216041 with(numtheory):
%p A216041 b:= proc(n) option remember; `if`(n<=1, n,
%p A216041       (add(add(d*b(d), d=divisors(j))*b(n-j), j=1..n-1))/(n-1))
%p A216041     end:
%p A216041 C:= n-> binomial(2*n, n)/(n+1):
%p A216041 a:= n-> C(n-1) -b(n):
%p A216041 seq(a(n), n=1..40);
%t A216041 b[n_] := b[n] = If[n <= 1, n, Sum[DivisorSum[j, #*b[#]&]*b[n-j], {j, 1, n-1}]/(n-1)];
%t A216041 c[n_] := Binomial[2*n, n]/(n+1);
%t A216041 a[n_] := c[n-1] - b[n];
%t A216041 Table[a[n], {n, 1, 40}] (* _Jean-François Alcover_, Mar 24 2017, translated from Maple *)
%Y A216041 Cf. A000081, A000108, A215703.
%K A216041 nonn
%O A216041 1,5
%A A216041 _Alois P. Heinz_, Aug 30 2012