login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 20
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,6

COMMENTS

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

REFERENCES

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

LINKS

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

FORMULA

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

EXAMPLE

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)

MAPLE

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

MATHEMATICA

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

PROG

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

(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

(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

CROSSREFS

Column k=2 of A185286.

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

Sequence in context: A047976 A006382 A295504 * A260268 A129015 A209976

Adjacent sequences:  A055110 A055111 A055112 * A055114 A055115 A055116

KEYWORD

nonn,nice,easy

AUTHOR

Jeppe Stig Nielsen, Jun 15 2000

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 17 18:14 EST 2020. Contains 330987 sequences. (Running on oeis4.)