cp's OEIS Frontend

A055113 Number of bracketings of 0^0^0^...^0, with n 0's, giving the result 0, with conventions that 0^0 = 1^0 = 1^1 = 1, 0^1 = 0.

%I A055113 #81 Aug 13 2024 21:00:47
%S A055113 0,1,0,1,1,5,11,41,120,421,1381,4840,16721,59357,210861,759071,
%T A055113 2744393,10000437,36609977,134750450,498016753,1848174708,6882643032,
%U A055113 25715836734,96365606679,362102430069,1364028272451,5150156201026,19486989838057,73880877535315
%N A055113 Number of bracketings of 0^0^0^...^0, with n 0's, giving the result 0, with conventions that 0^0 = 1^0 = 1^1 = 1, 0^1 = 0.
%C A055113 Total number of bracketings of 0^0^...^0 is A000108(n-1) (this is Catalan's problem). So the number of bracketings giving 1 is A000108(n-1) - a(n).
%C A055113 Also bracketings of f => f => ... => f where f is "false" and "=>" is implication.
%C A055113 Self-convolution yields A187430. - _Paul D. Hanna_, May 31 2015
%C A055113 Also, number of nonnegative walks of n steps with step sizes 1 and 2, starting at 0 and ending at 1. - _Andrew Howroyd_, Dec 23 2017
%C A055113 Series reversion is related to A001006. - _F. Chapoton_, Jul 14 2021
%D A055113 Thanks to Soren Galatius Smith, Jesper Torp Kristensen et al.
%H A055113 Alois P. Heinz, <a href="/A055113/b055113.txt">Table of n, a(n) for n = 0..1671</a> (terms n = 1..200 from T. D. Noe)
%H A055113 E. A. Bender and S. G. Williamson, <a href="http://www.math.ucsd.edu/~ebender/CombText/index.html">Foundations of Combinatorics with Applications</a> (see Chap. 11, Example 11.3, pp. 312-313 and Example 11.31, pp. 351-352).
%H A055113 V. Čačić and V. Kovač, <a href="http://arxiv.org/abs/1309.3408">On the fraction of IL formulas that have normal forms</a>, arXiv preprint arXiv:1309.3408 [math.LO], 2013-2015.
%H A055113 D. G. Rogers, <a href="/A111160/a111160.txt">Comments on A111160, A055113 and A006013</a>
%H A055113 Wikipedia, <a href="https://en.wikipedia.org/wiki/Zero_to_the_power_of_zero">Zero to the power of zero</a>
%F A055113 G.f.: - 1/4 - (1/4)*(1 - 4*x)^(1/2) + (1/4)*(2 + 2*(1 - 4*x)^(1/2) + 12*x)^(1/2).
%F A055113 The ratio a(n)/A000108(n-1) converges to (5-sqrt(5))/10 as n->oo.
%F A055113 a(n) = (Sum_{j=0..n-1} binomial(2*j+n-1, j+n-1)*(-1)^(n-j-1)*binomial(2*n-1, j+n))/(2*n-1). - _Vladimir Kruchinin_, May 10 2011
%F A055113 a(n) ~ (1-1/sqrt(5))*2^(2*n-3)/(sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Aug 09 2013
%F A055113 D-finite with recurrence: 2*n*(2*n-1)*(n-1)*a(n) -(n-1)*(19*n^2-60*n+48)*a(n-1) +(-31*n^3+173*n^2-346*n+264)*a(n-2) +4*(2*n-7)*(17*n^2-83*n+102)*a(n-3) +36*(2*n-7)*(2*n-9)*(n-4)*a(n-4)=0. - _R. J. Mathar_, Feb 20 2020
%F A055113 a(n) + A111160(n) = A000108(n). - _F. Chapoton_, Jul 14 2021
%e A055113 Number of bracketings of 0^0^0^0^0^0 giving 0 is 11, so a(6) = 11.
%e A055113 From _Jon E. Schoenfield_, Dec 24 2017: (Start)
%e A055113 The 11 ways of parenthesizing 0^0^0^0^0^0 to obtain 0 are
%e A055113 0^(0^(0^((0^0)^0))) = 0^(0^(0^(1^0))) = 0^(0^(0^1)) = 0^(0^0) = 0^1 = 0;
%e A055113 0^((0^0)^(0^(0^0))) = 0^(1^(0^1)) = 0^(1^0) = 0^1 = 0;
%e A055113 0^((0^0)^((0^0)^0)) = 0^(1^(1^0)) = 0^(1^1) = 0^1 = 0;
%e A055113 0^(((0^0)^0)^(0^0)) = 0^((1^0)^1) = 0^(1^1) = 0^1 = 0;
%e A055113 0^((0^(0^(0^0)))^0) = 0^((0^(0^1))^0) = 0^((0^0)^0) = 0^(1^0) = 0^1 = 0;
%e A055113 0^((0^((0^0)^0))^0) = 0^((0^(1^0))^0) = 0^((0^1)^0) = 0^(0^0) = 0^1 = 0;
%e A055113 0^(((0^0)^(0^0))^0) = 0^((1^1)^0) = 0^(1^0) = 0^1 = 0;
%e A055113 0^(((0^(0^0))^0)^0) = 0^(((0^1)^0)^0) = 0^((0^0)^0) = 0^(1^0) = 0^1 = 0;
%e A055113 0^((((0^0)^0)^0)^0) = 0^(((1^0)^0)^0) = 0^((1^0)^0) = 0^(1^0) = 0^1 = 0;
%e A055113 (0^(0^0))^((0^0)^0) = (0^1)^(1^0) = 0^1 = 0;
%e A055113 (0^((0^0)^0))^(0^0) = (0^(1^0))^1. (End)
%p A055113 a:= proc(n) option remember; `if`(n<3, n*(2-n),
%p A055113       ((n-1)*(115*n^3-689*n^2+1332*n-840) *a(n-1)
%p A055113        +(8*n-20)*(5*n^3+12*n^2-113*n+126) *a(n-2)
%p A055113        -36*(n-3)*(5*n-8)*(2*n-5)*(2*n-7)  *a(n-3))
%p A055113       /((2*(2*n-1))*(5*n-13)*n*(n-1)))
%p A055113     end:
%p A055113 seq(a(n), n=0..30);  # _Alois P. Heinz_, Mar 04 2019
%t A055113 Rest[ CoefficientList[ Series[(-1 - Sqrt[1 - 4x] + Sqrt[2]Sqrt[1 + Sqrt[1 - 4x] + 6x])/4, {x, 0, 28}], x]] (* _Robert G. Wilson v_, Oct 28 2005 *)
%t A055113 a[n_] := (-1)^(n+1)*Binomial[2n-1, n]*HypergeometricPFQ[{1-n, (n+1)/2, n/2}, {n, n+1}, 4]/(2n-1);
%t A055113 Array[a, 27] (* _Jean-François Alcover_, Dec 26 2017, after _Vladimir Kruchinin_ *)
%o A055113 (Maxima) a(n):= sum(binomial(2*j+n-1,j+n-1)*(-1)^(n-j-1)*binomial(2*n-1,j+n), j,0,n-1)/(2*n-1); /* _Vladimir Kruchinin_, May 10 2011 */
%o A055113 (PARI) a(n)={sum(j=0, n-1, binomial(2*j+n-1, j+n-1)*(-1)^(n-j-1)*binomial(2*n-1, j+n))/(2*n-1)} \\ _Andrew Howroyd_, Dec 23 2017
%o A055113 (PARI) first(n) = x='x+O('x^(n+1)); Vec(-((1 - 4*x)^(1/2) + 1)/4 + (2 + 2*(1 - 4*x)^(1/2) + 12*x)^(1/2)/4) \\ _Iain Fox_, Dec 23 2017
%Y A055113 Column k=2 of A185286.
%Y A055113 Cf. A000108, A001006, A055392, A055395, A006632, A111160, A187430, A296619, A306668.
%K A055113 nonn,nice,easy
%O A055113 0,6
%A A055113 _Jeppe Stig Nielsen_, Jun 15 2000
%E A055113 a(0)=0 prepended by _Alois P. Heinz_, Mar 04 2019