A306668 -id:A306668 - 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.

0, 1, 0, 1, 1, 5, 11, 41, 120, 421, 1381, 4840, 16721, 59357, 210861, 759071, 2744393, 10000437, 36609977, 134750450, 498016753, 1848174708, 6882643032, 25715836734, 96365606679, 362102430069, 1364028272451, 5150156201026, 19486989838057, 73880877535315

Offset: 0

Jeppe Stig Nielsen, Jun 15 2000

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).
Also bracketings of f => f => ... => f where f is "false" and "=>" is implication.
Self-convolution yields A187430. - Paul D. Hanna, May 31 2015
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
Series reversion is related to A001006. - F. Chapoton, Jul 14 2021

			Number of bracketings of 0^0^0^0^0^0 giving 0 is 11, so a(6) = 11.
From _Jon E. Schoenfield_, Dec 24 2017: (Start)
The 11 ways of parenthesizing 0^0^0^0^0^0 to obtain 0 are
0^(0^(0^((0^0)^0))) = 0^(0^(0^(1^0))) = 0^(0^(0^1)) = 0^(0^0) = 0^1 = 0;
0^((0^0)^(0^(0^0))) = 0^(1^(0^1)) = 0^(1^0) = 0^1 = 0;
0^((0^0)^((0^0)^0)) = 0^(1^(1^0)) = 0^(1^1) = 0^1 = 0;
0^(((0^0)^0)^(0^0)) = 0^((1^0)^1) = 0^(1^1) = 0^1 = 0;
0^((0^(0^(0^0)))^0) = 0^((0^(0^1))^0) = 0^((0^0)^0) = 0^(1^0) = 0^1 = 0;
0^((0^((0^0)^0))^0) = 0^((0^(1^0))^0) = 0^((0^1)^0) = 0^(0^0) = 0^1 = 0;
0^(((0^0)^(0^0))^0) = 0^((1^1)^0) = 0^(1^0) = 0^1 = 0;
0^(((0^(0^0))^0)^0) = 0^(((0^1)^0)^0) = 0^((0^0)^0) = 0^(1^0) = 0^1 = 0;
0^((((0^0)^0)^0)^0) = 0^(((1^0)^0)^0) = 0^((1^0)^0) = 0^(1^0) = 0^1 = 0;
(0^(0^0))^((0^0)^0) = (0^1)^(1^0) = 0^1 = 0;
(0^((0^0)^0))^(0^0) = (0^(1^0))^1. (End)

Thanks to Soren Galatius Smith, Jesper Torp Kristensen et al.

Alois P. Heinz, Table of n, a(n) for n = 0..1671 (terms n = 1..200 from T. D. Noe)
E. A. Bender and S. G. Williamson, Foundations of Combinatorics with Applications (see Chap. 11, Example 11.3, pp. 312-313 and Example 11.31, pp. 351-352).
V. Čačić and V. Kovač, On the fraction of IL formulas that have normal forms, arXiv preprint arXiv:1309.3408 [math.LO], 2013-2015.
D. G. Rogers, Comments on A111160, A055113 and A006013
Wikipedia, Zero to the power of zero

Column k=2 of A185286.

Cf. A000108, A001006, A055392, A055395, A006632, A111160, A187430, A296619, A306668.

a:= proc(n) option remember; `if`(n<3, n*(2-n),
      ((n-1)*(115*n^3-689*n^2+1332*n-840) *a(n-1)
       +(8*n-20)*(5*n^3+12*n^2-113*n+126) *a(n-2)
       -36*(n-3)*(5*n-8)*(2*n-5)*(2*n-7)  *a(n-3))
      /((2*(2*n-1))*(5*n-13)*n*(n-1)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Mar 04 2019

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 *)
a[n_] := (-1)^(n+1)*Binomial[2n-1, n]*HypergeometricPFQ[{1-n, (n+1)/2, n/2}, {n, n+1}, 4]/(2n-1);
Array[a, 27] (* Jean-François Alcover, Dec 26 2017, after Vladimir Kruchinin *)

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

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

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

G.f.: - 1/4 - (1/4)*(1 - 4*x)^(1/2) + (1/4)*(2 + 2*(1 - 4*x)^(1/2) + 12*x)^(1/2).
The ratio a(n)/A000108(n-1) converges to (5-sqrt(5))/10 as n->oo.
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
a(n) ~ (1-1/sqrt(5))*2^(2*n-3)/(sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Aug 09 2013
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
a(n) + A111160(n) = A000108(n). - F. Chapoton, Jul 14 2021

a(0)=0 prepended by Alois P. Heinz, Mar 04 2019

A211192 Consider all distinct functions f representable as x -> x^x^...^x with n x's and parentheses inserted in all possible ways; sequence gives difference between numbers of f with f(0)=1 and numbers of f with f(0)=0, with conventions that 0^0=1^0=1^1=1, 0^1=0.

Original entry on oeis.org

0, -1, 1, 0, 2, 1, 8, 10, 39, 72, 225, 506, 1434, 3550, 9767, 25391, 69293, 185061, 505843, 1372744, 3769842, 10339104, 28546539, 78890525, 218945822, 608657861, 1697106780, 4740593393, 13272626627, 37224982494, 104599603493, 294384019508, 829836855332

Offset: 0

Alois P. Heinz, Feb 18 2013

sign

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.

			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-1 = 2.
a(8) = A222380(8) - A222379(8) = 77 - 38 = 39.

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

Cf. A000081, A000108, A055113, A215703, A222379, A222380, A258592, A263831, A306668.

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-> (f-> f[1]-f[2])(g(n-1$2)):
seq(a(n), n=0..40);

g[n_, i_] := g[n, i] = If[n==0, {0, 1}, If[i<1, {0, 0}, ({#[[1]]-#[[2]], #[[2]]}&)[Sum[Function[{l, h}, {(h[[1]]+h[[2]])*Binomial[j+l[[1]]+l[[2]] -1, j], h[[2]]*Binomial[j+l[[1]]-1, j]}][g[i-1, i-1]], g[n-i*j, i-1]]], {j, 0, Quotient[n, i]}]];
a[n_] := (#[[1]]-#[[2]]&)[g[n-1, n-1]]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 22 2017, translated from Maple *)

a(n) = A222380(n) - A222379(n).
From Alois P. Heinz, Mar 01 2019: (Start)
a(n) is even <=> n in { A258592 }.
a(n) is odd  <=> n in { A263831 }. (End)

A111160 G.f.: C - Z; where C is the g.f. for the Catalan numbers (A000108) and Z is the g.f. for A055113 with offset 0.

Original entry on oeis.org

0, 1, 1, 4, 9, 31, 91, 309, 1009, 3481, 11956, 42065, 148655, 532039, 1915369, 6950452, 25357233, 93034813, 342888250, 1269246437, 4715945712, 17583623988, 65766726906, 246694006971, 927801717255, 3497918129001, 13217196871126, 50046561077947

Offset: 0

N. J. A. Sloane, Oct 22 2005

nonn

Expressible in terms of ballot numbers.

Number of positive walks with n steps {-2,-1,1,2} starting at the origin, ending at altitude 2, and staying strictly above the x-axis. - David Nguyen, Dec 16 2016

T. D. Noe, Table of n, a(n) for n=0..200
C. Banderier, C. Krattenthaler, A. Krinik, D. Kruchinin, V. Kruchinin, D. Nguyen, and M. Wallner, Explicit formulas for enumeration of lattice paths: basketball and the kernel method, arXiv preprint arXiv:1609.06473 [math.CO], 2016.
Jean-Luc Baril and José L. Ramírez, Knight's paths towards Catalan numbers, Univ. Bourgogne Franche-Comté (2022).
D. G. Rogers, Comments on A111160, A055113 and A006013

Cf. A000108, A055113, A006013, A187430, A276901, A306668.

I:=[1,1,4]; [0] cat [n le 3 select I[n] else (n*(115*n^3 - 344*n^2 + 299*n - 82)*Self(n-1) + 4*(2*n-3)*(5*n^3 + 27*n^2 - 74*n + 30)*Self(n-2) - 36*(n-2)*(2*n-5)*(2*n-3)*(5*n-3)*Self(n-3))/(2*n*(n+1)*(2*n+1)*(5*n-8)): n in [1..30]]; // Vincenzo Librandi, Oct 06 2015

a := n -> (-1)^(n+1)*binomial(2*n+1,n)*hypergeom([-n-1,n/2+1/2,n/2],[n,n+1],4)/ (2*n+1);
[0, op([seq(round(evalf(a(n),32)), n=1..27)])]; # Peter Luschny, Oct 06 2015

CoefficientList[ Series[ -((-3 + Sqrt[1 - 4*x] + Sqrt[2]*Sqrt[1 + Sqrt[1 - 4x] + 6x])/(4x)), {x, 0, 10}], x] (* Robert G. Wilson v *)

a(n) = if(n==0, 0, sum(k=0, (n+1)/2, binomial(n-k,n-2*k+1)*binomial(2*n+1,k))/(2*n+1)); \\ Altug Alkan, Oct 05 2015

Let C := (1 - sqrt(1 - 4*x)) / (2*x), Z := (- 1/4 - (1/4)*(1 - 4*x)^(1/2) + (1/4)*(2 + 2*(1 - 4*x)^(1/2) + 12*x)^(1/2))/x; g.f. is W := C - Z.
G.f.: -((-3 + sqrt(1 - 4x) + sqrt(2)*sqrt(1 + sqrt(1 - 4x) + 6x))/(4x)).
a(n) = sum(j=0..n+1, binomial(n+2*j-1,j)*(-1)^(n+j+1)*binomial(2*n+1,j+n))/(2*n+1). [Vladimir Kruchinin, Feb 15 2013]
a(n) ~ (1+1/sqrt(5))*2^(2*n-1)/(sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Aug 13 2013
Recurrence: 2*n*(n+1)*(2*n+1)*(5*n-8)*a(n) = n*(115*n^3 - 344*n^2 + 299*n - 82)*a(n-1) + 4*(2*n-3)*(5*n^3 + 27*n^2 - 74*n + 30)*a(n-2) - 36*(n-2)*(2*n-5)*(2*n-3)*(5*n-3)*a(n-3). - Vaclav Kotesovec, Aug 13 2013
a(n) = Sum_{j=0..(n+1)/2}(binomial(n-j,n-2*j+1)*binomial(2*n+1,j))/(2*n+1). - Vladimir Kruchinin, Oct 05 2015
a(n) = (-1)^(n+1)*C(2*n+1,n)*hypergeom([-n-1,n/2+1/2,n/2],[n,n+1],4)/(2*n+1) for n>0. - Peter Luschny, Oct 06 2015

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

PARI

Formula

Extensions

A211192 Consider all distinct functions f representable as x -> x^x^...^x with n x's and parentheses inserted in all possible ways; sequence gives difference between numbers of f with f(0)=1 and numbers of f with f(0)=0, with conventions that 0^0=1^0=1^1=1, 0^1=0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A111160 G.f.: C - Z; where C is the g.f. for the Catalan numbers (A000108) and Z is the g.f. for A055113 with offset 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula