cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-10 of 21 results. Next

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

Views

Author

N. J. A. Sloane, Oct 22 2005

Keywords

Comments

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

Crossrefs

Programs

  • Magma
    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
  • Maple
    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
  • Mathematica
    CoefficientList[ Series[ -((-3 + Sqrt[1 - 4*x] + Sqrt[2]*Sqrt[1 + Sqrt[1 - 4x] + 6x])/(4x)), {x, 0, 10}], x] (* Robert G. Wilson v *)
  • PARI
    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
    

Formula

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

A006013 a(n) = binomial(3*n+1,n)/(n+1).

Original entry on oeis.org

1, 2, 7, 30, 143, 728, 3876, 21318, 120175, 690690, 4032015, 23841480, 142498692, 859515920, 5225264024, 31983672534, 196947587823, 1219199353190, 7583142491925, 47365474641870, 296983176369495, 1868545312633440, 11793499763070480
Offset: 0

Views

Author

Keywords

Comments

Enumerates pairs of ternary trees [Knuth, 2014]. - N. J. A. Sloane, Dec 09 2014
G.f. (offset 1) is series reversion of x - 2x^2 + x^3.
Hankel transform is A005156(n+1). - Paul Barry, Jan 20 2007
a(n) = number of ways to connect 2*n - 2 points labeled 1, 2, ..., 2*n-2 in a line with 0 or more noncrossing arcs above the line such that each maximal contiguous sequence of isolated points has even length. For example, with arcs separated by dashes, a(3) = 7 counts {} (no arcs), 12, 14, 23, 34, 12-34, 14-23. It does not count 13 because 2 is an isolated point. - David Callan, Sep 18 2007
In my 2003 paper I introduced L-algebras. These are K-vector spaces equipped with two binary operations > and < satisfying (x > y) < z = x > (y < z). In my arXiv paper math-ph/0709.3453 I show that the free L-algebra on one generator is related to symmetric ternary trees with odd degrees, so the dimensions of the homogeneous components are 1, 2, 7, 30, 143, .... These L-algebras are closely related to the so-called triplicial-algebras, 3 associative operations and 3 relations whose free object is related to even trees. - Philippe Leroux (ph_ler_math(AT)yahoo.com), Oct 05 2007
a(n-1) is also the number of projective dependency trees with n nodes. - Marco Kuhlmann (marco.kuhlmann(AT)lingfil.uu.se), Apr 06 2010
Number of subpartitions of [1^2, 2^2, ..., n^2]. - Franklin T. Adams-Watters, Apr 13 2011
a(n) = sum of (n+1)-th row terms of triangle A143603. - Gary W. Adamson, Jul 07 2011
Also the number of Dyck n-paths with up steps colored in two ways (N or A) and avoiding NA. The 7 Dyck 2-paths are NDND, ADND, NDAD, ADAD, NNDD, ANDD, and AADD. - David Scambler, Jun 24 2013
a(n) is also the number of permutations avoiding 213 in the classical sense which can be realized as labels on an increasing strict binary tree with 2n-1 nodes. See A245904 for more information on increasing strict binary trees. - Manda Riehl Aug 07 2014
With offset 1, a(n) is the number of ordered trees (A000108) with n non-leaf vertices and n leaf vertices such that every non-leaf vertex has a leaf child (and hence exactly one leaf child). - David Callan, Aug 20 2014
a(n) is the number of paths in the plane with unit east and north steps, never going above the line x=2y, from (0,0) to (2n+1,n). - Ira M. Gessel, Jan 04 2018
a(n) is the number of words on the alphabet [n+1] that avoid the patterns 231 and 221 and contain exactly one 1 and exactly two occurrences of every other letter. - Colin Defant, Sep 26 2018
a(n) is the number of Motzkin paths of length 3n with n of each type of step, such that (1, 1) and (1, 0) alternate (ignoring (-1, 1) steps). All paths start with a (1, 1) step. - Helmut Prodinger, Apr 08 2019
Hankel transform omitting a(0) is A051255(n+1). - Michael Somos, May 15 2022
If f(x) is the generating function for (-1)^n*a(n), a real solution of the equation y^3 - y^2 - x = 0 is given by y = 1 + x*f(x). In particular 1 + f(1) is Narayana's cow constant, A092526, aka the "supergolden" ratio. - R. James Evans, Aug 09 2023
This is instance k = 2 of the family {c(k, n+1)}A130564.%20_Wolfdieter%20Lang">{n>=0} described in A130564. _Wolfdieter Lang, Feb 04 2024
Also the number of quadrangulations of a (2n+4)-gon which do not contain any diagonals incident to a fixed vertex. - Esther Banaian, Mar 12 2025

Examples

			a(3) = 30 since the top row of Q^3 = (12, 12, 5, 1).
G.f. = 1 + 2*x + 7*x^2 + 30*x^3 + 143*x^4 + 728*x^5 + 3876*x^6 + 21318*x^7 + ... - _Michael Somos_, May 15 2022
		

References

  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Crossrefs

These are the odd indices of A047749.
Cf. A305574 (the same with offset 1 and the initial 1 replaced with 5).
Cf. A130564 (comment on c(k, n+1)).

Programs

  • Haskell
    a006013 n = a007318 (3 * n + 1) n `div` (n + 1)
    a006013' n = a258708 (2 * n + 1) n
    -- Reinhard Zumkeller, Jun 22 2015
    
  • Magma
    [Binomial(3*n+1,n)/(n+1): n in [0..30]]; // Vincenzo Librandi, Mar 29 2015
    
  • Mathematica
    Binomial[3#+1,#]/(#+1)&/@Range[0,30]  (* Harvey P. Dale, Mar 16 2011 *)
  • PARI
    A006013(n) = binomial(3*n+1,n)/(n+1) \\ M. F. Hasler, Jan 08 2024
    
  • Python
    from math import comb
    def A006013(n): return comb(3*n+1,n)//(n+1) # Chai Wah Wu, Jul 30 2022
  • Sage
    def A006013_list(n) :
        D = [0]*(n+1); D[1] = 1
        R = []; b = false; h = 1
        for i in range(2*n) :
            for k in (1..h) : D[k] += D[k-1]
            if b : R.append(D[h]); h += 1
            b = not b
        return R
    A006013_list(23) # Peter Luschny, May 03 2012
    

Formula

G.f. is square of g.f. for ternary trees, A001764 [Knuth, 2014]. - N. J. A. Sloane, Dec 09 2014
Convolution of A001764 with itself: 2*C(3*n + 2, n)/(3*n + 2), or C(3*n + 2, n+1)/(3*n + 2).
G.f.: (4/(3*x)) * sin((1/3)*arcsin(sqrt(27*x/4)))^2.
G.f.: A(x)/x with A(x)=x/(1-A(x))^2. - Vladimir Kruchinin, Dec 26 2010
From Gary W. Adamson, Jul 14 2011: (Start)
a(n) is the top left term in M^n, where M is the infinite square production matrix:
2, 1, 0, 0, 0, ...
3, 2, 1, 0, 0, ...
4, 3, 2, 1, 0, ...
5, 4, 3, 2, 1, ...
... (End)
From Gary W. Adamson, Aug 11 2011: (Start)
a(n) is the sum of top row terms in Q^n, where Q is the infinite square production matrix as follows:
1, 1, 0, 0, 0, ...
2, 2, 1, 0, 0, ...
3, 3, 2, 1, 0, ...
4, 4, 3, 2, 1, ...
... (End)
D-finite with recurrence: 2*(n+1)*(2n+1)*a(n) = 3*(3n-1)*(3n+1)*a(n-1). - R. J. Mathar, Dec 17 2011
a(n) = 2*A236194(n)/n for n > 0. - Bruno Berselli, Jan 20 2014
a(n) = A258708(2*n+1, n). - Reinhard Zumkeller, Jun 22 2015
From Ilya Gutkovskiy, Dec 29 2016: (Start)
E.g.f.: 2F2([2/3, 4/3]; [3/2,2]; 27*x/4).
a(n) ~ 3^(3*n+3/2)/(sqrt(Pi)*4^(n+1)*n^(3/2)). (End)
a(n) = A110616(n+1, 1). - Ira M. Gessel, Jan 04 2018
0 = v0*(+98415*v2 -122472*v3 +32340*v4) +v1*(+444*v3 -2968*v4) +v2*(-60*v2 +56*v3 +64*v4) where v0=a(n)^2, v1=a(n)*a(n+1), v2=a(n+1)^2, v3=a(n+1)*a(n+2), v4=a(n+2)^2 for all n in Z if a(-1)=-2/3 and a(n)=0 for n<-1. - Michael Somos, May 15 2022
a(n) = (1/4^n) * Product_{1 <= i <= j <= 2*n} (2*i + j + 2)/(2*i + j - 1). Cf. A000260. - Peter Bala, Feb 21 2023
From Karol A. Penson, Jun 02 2023: (Start)
a(n) = Integral_{x=0..27/4} x^n*W(x) dx, where
W(x) = (((9 + sqrt(81 - 12*x))^(2/3) - (9 - sqrt(81 - 12*x))^(2/3)) * 2^(1/3) * 3^(1/6)) / (12 * Pi * x^(1/3)), for x in (0, 27/4).
This integral representation is unique as W(x) is the solution of the Hausdorff power moment problem. Using only the definition of a(n), W(x) can be proven to be positive. W(x) is singular at x = 0, with the singularity x^(-1/3), and for x > 0 is monotonically decreasing to zero at x = 27/4. At x = 27/4 the first derivative of W(x) is infinite. (End)
G.f.: hypergeometric([2/3,1,4/3], [3/2,2], (3^3/2^2)*x). See the e.g.f. above. - Wolfdieter Lang, Feb 04 2024
a(n) = A024485(n+1)/3. - Michael Somos, Oct 14 2024
G.f.: (Sum_{n >= 0} binomial(3*n+2, n)*x^n) / (Sum_{n >= 0} binomial(3*n, n)*x^n) = (B(x) - 1)/(x*B(x)), where B(x) = Sum_{n >= 0} binomial(3*n, n)/(2*n+1) * x^n is the g.f. of A001764. - Peter Bala, Dec 13 2024
The g.f. A(x) is uniquely determined by the conditions A(0) = 1 and [x^n] A(x)^(-n) = -2 for all n >= 1. Cf. A006632. - Peter Bala, Jul 24 2025

Extensions

Edited by N. J. A. Sloane, Feb 21 2008

A187430 Number of nonnegative walks of n steps with step sizes 1 and 2, starting and ending at 0.

Original entry on oeis.org

1, 0, 2, 2, 11, 24, 93, 272, 971, 3194, 11293, 39148, 139687, 497756, 1798002, 6517194, 23807731, 87336870, 322082967, 1192381270, 4431889344, 16527495396, 61831374003, 231973133544, 872598922407, 3290312724374, 12434632908623, 47089829065940, 178672856753641
Offset: 0

Views

Author

Keywords

Comments

Equivalently, the number of paths from (0,0) to (n,0) using steps of the form (1,2),(1,1),(1,-1) or (1,-2) and staying on or above the x-axis.
Self-convolution of A055113. - Paul D. Hanna, May 31 2015
Logarithmic derivative yields A092765 (with offset 1). - Paul D. Hanna, May 31 2015

Examples

			The 11 length-4 walks are 0,2,4,2,0; 0,2,3,2,0; 0,2,3,1,0; 0,2,1,2,0; 0,2,0,2,0; 0,2,0,1,0; 0,1,3,2,0; 0,1,3,1,0; 0,1,2,1,0; 0,1,0,2,0; and 0,1,0,1,0.
		

Crossrefs

Programs

  • Maple
    a:= proc(n) option remember; `if`(n<3, (n-1)*(3*n-2)/2,
         ((n+1)*(115*n^3-137*n^2-10*n+8) *a(n-1)
          +4*(2*n-1)*(5*n^3+36*n^2-26*n-12) *a(n-2)
          -36*(n-2)*(2*n-1)*(2*n-3)*(5*n+1) *a(n-3))
          / (2*(5*n-4)*(2*n+1)*(n+2)*(n+1)))
        end:
    seq(a(n), n=0..30); # Alois P. Heinz, May 16 2013
  • Mathematica
    a[n_] := (Sum[Binomial[n+1, l]*Sum[Binomial[n-2*i-1, 2*l-1]*Binomial[n-l+1, i], {i, 0, (n-1)/2}], {l, 0, n+1}] + (((-1)^n+1)*Binomial[n+1, n/2])/2)/(n+1); Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Oct 24 2016, after Vladimir Kruchinin *)
  • Maxima
    a(n):=((sum(binomial(n+1,l)*sum(binomial(n-2*i-1,2*l-1)*binomial(n-l+1,i),i,0,(n-1)/2),l,0,n+1))+(((-1)^n+1)*binomial(n+1,n/2))/2)/(n+1); /* Vladimir Kruchinin, Jun 26 2015 */
  • PARI
    al(n)={local(r,p);
    r=vector(n);r[1]=p=1;
    for(k=2,n,p*=1+x+x^3+x^4;p=(p-polcoeff(p,0)-polcoeff(p,1)*x)/x^2;r[k]=polcoeff(p,0));
    r}
    

Formula

G.f.: 1/(2*x)-(1+(1-4*x)^(1/2))*((2+2*(1-4*x)^(1/2)+12*x)^(1/2)-2)/(8*x^2). - Mark van Hoeij, May 16 2013
a(n) ~ (3/sqrt(5)-1) * 2^(2*n+1) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Sep 09 2014
G.f.: exp( Sum_{n>=1} A092765(n)*x^n/n ), where A092765(n) = Sum_{k=0..n} binomial(n,k)*binomial(n,2*n-3*k). - Paul D. Hanna, May 31 2015
a(n) = ((Sum_{l=0..n+1} (C(n+1,l)*Sum_{i=0..(n-1)/2}(C(n-2*i-1,2*l-1)*C(n-l+1,i))))+(((-1)^n+1)/2*C(n+1,n/2)))/(n+1). - Vladimir Kruchinin, Jun 26 2015
Sum_{n>=0} a(n)*x^(n+1) is the compositional inverse of x*(1-x^2)^2/(1+x^3)^2. - Ira M. Gessel, Sep 19 2017
Conjecture: 1 + Sum_{n>=0} a(n)*(-1)^n x^(n+1)/(1-x)^(2*n+2) = C(x), the g.f. for the Catalan numbers A000108. - Benedict W. J. Irwin, Jan 13 2017
D-finite with recurrence 2*(2*n+1)*(n+2)*(n+1)*a(n) +(n+1)*(n^2-27*n+2)*a(n-1) +2*(-73*n^3+204*n^2-167*n+6)*a(n-2) +12*(n-3)*(2*n-3)*(4*n-7)*a(n-3) +216*(2*n-5)*(n-3)*(2*n-3)*a(n-4)=0. - R. J. Mathar, Sep 29 2020
From Seiichi Manyama, Jan 17 2024: (Start)
G.f.: (1/x) * Series_Reversion( x * (1-x)^2 / (1-x+x^2)^2 ).
a(n) = (1/(n+1)) * Sum_{k=0..floor(n/2)} binomial(2*n+2,k) * binomial(n-k-1,n-2*k). (End)

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

Views

Author

Alois P. Heinz, Feb 18 2013

Keywords

Comments

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.

Examples

			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.
		

Crossrefs

Programs

  • Maple
    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);
  • Mathematica
    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 *)

Formula

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)

A222379 Number of distinct functions f representable as x -> x^x^...^x with n x's and parentheses inserted in all possible ways giving result f(0)=0, with conventions that 0^0=1^0=1^1=1, 0^1=0.

Original entry on oeis.org

0, 1, 0, 1, 1, 4, 6, 19, 38, 107, 247, 668, 1666, 4468, 11603, 31210, 83044, 224893, 607658, 1657966, 4528193, 12441364, 34254321, 94696165, 262389581, 729258392, 2031264865, 5671570468, 15867219821, 44480785907, 124913622052, 351393746745, 990048748684
Offset: 0

Views

Author

Alois P. Heinz, Feb 17 2013

Keywords

Comments

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.

Examples

			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. Thus a(4) = 1.
		

Crossrefs

Programs

  • Maple
    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-> g(n-1$2)[2]:
    seq(a(n), n=0..40);
  • Mathematica
    f[l_, h_] := {Binomial[l[[2]] + l[[1]] + j - 1, j]*(h[[1]] + h[[2]]), Binomial[l[[1]] + j - 1, j]*h[[2]]};
    g[n_, i_] := g[n, i] = If[n == 0, {0, 1}, If[i < 1, {0, 0}, Function[v, {v[[1]] - v[[2]], v[[2]]}][Sum[f[g[i - 1, i - 1], g[n - i*j, i - 1]], {j, 0, Quotient[n, i]}]]]];
    a[n_] := g[n - 1, n - 1][[2]];
    Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 27 2019, after Alois P. Heinz *)

Formula

A222380(n) + a(n) = A000081(n).
A222380(n) - a(n) = A211192(n).
a(n) = Sum_{i=A087803(n-1)+1..A087803(n)} (1-A306710(i)).

A222380 Number of distinct functions f representable as x -> x^x^...^x with n x's and parentheses inserted in all possible ways giving result f(0)=1, with conventions that 0^0=1^0=1^1=1, 0^1=0.

Original entry on oeis.org

0, 0, 1, 1, 3, 5, 14, 29, 77, 179, 472, 1174, 3100, 8018, 21370, 56601, 152337, 409954, 1113501, 3030710, 8298035, 22780468, 62800860, 173586690, 481335403, 1337916253, 3728371645, 10412163861, 29139846448, 81705768401, 229513225545, 645777766253
Offset: 0

Views

Author

Alois P. Heinz, Feb 17 2013

Keywords

Comments

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.

Examples

			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.
		

Crossrefs

Programs

  • Maple
    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-> g(n-1$2)[1]:
    seq(a(n), n=0..40);
  • Mathematica
    f[l_, h_] := {Binomial[l[[2]] + l[[1]] + j - 1, j]*(h[[1]] + h[[2]]), Binomial[l[[1]] + j - 1, j]*h[[2]]};
    g[n_, i_] := g[n, i] = If[n == 0, {0, 1}, If[i < 1, {0, 0}, Function[v, {v[[1]] - v[[2]], v[[2]]}][Sum[f[g[i - 1, i - 1], g[n - i*j, i - 1]], {j, 0, Quotient[n, i]}]]]];
    a[n_] := g[n - 1, n - 1][[1]];
    Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 27 2019, after Alois P. Heinz *)

Formula

a(n) + A222379(n) = A000081(n).
a(n) - A222379(n) = A211192(n).
a(n) = Sum_{i=A087803(n-1)+1..A087803(n)} A306710(i).

A055392 Number of bracketings of 0#0#0#...#0 giving result 0, where 0#0 = 1, 0#1 = 1#0 = 1#1 = 0.

Original entry on oeis.org

1, 0, 2, 1, 12, 14, 100, 180, 990, 2310, 10920, 30030, 129612, 396576, 1620168, 5318841, 21029580, 72364578, 280735884, 997356360, 3828988020, 13905563100, 53108050320, 195875639310, 746569720572, 2784329809344, 10610782107800
Offset: 1

Views

Author

Jeppe Stig Nielsen, Jun 24 2000

Keywords

Comments

Operation # can be interpreted as NOT OR. The ratio a(n)/A000108(n-1) converges to sqrt(3)/3. Thanks to Soren Galatius Smith.
Essentially second column of A112519. - Paul Barry, Sep 09 2005

Crossrefs

Programs

  • Magma
    [(1/n)*(&+[(-1)^j*Binomial(2*j,j)*Binomial(2*n-j-2,n-j-1): j in [0..n-1]]): n in [1..30]]; // G. C. Greubel, Jan 12 2022
  • Mathematica
    CoefficientList[ Series[1/2 + 1/2(3 - 2(1 - 4x)^(1/2))^(1/2), {x, 0, 27}], x] (* Robert G. Wilson v, May 04 2004 *)
  • PARI
    {a(n)=if(n<1,0,polcoeff(serreverse(x - 2*x^3 - x^4 +x*O(x^n)),n))} /* Paul D. Hanna, Apr 05 2012 */
    
  • Sage
    [(1/n)*sum( (-1)^j*binomial(2*j,j)*binomial(2*n-j-2,n-j-1) for j in (0..n-1) ) for n in (1..30)] # G. C. Greubel, Jan 12 2022
    

Formula

G.f.: (1/2)*(1 + sqrt(3 - 2*sqrt(1 - 4*x))).
The g.f. Z is also given by Z(x) = C(x)U(xC(x)), where U(x) = C(-x) and C is the g.f. of the Catalan numbers. - D. G. Rogers, Oct 20 2005
a(n) = Sum_{j=0..n} (1/n)*(-1)^(j-1)*C(2*n-j-1, n-j)*C(2*(j-1), j-1). - Paul Barry, Sep 09 2005, corrected by Peter Bala, Aug 19 2014
G.f. A(x) satisfies: A(x) = x + 2*A(x)^3 + A(x)^4; thus, A(x - 2*x^3 - x^4) = x. - Paul D. Hanna, Apr 05 2012
G.f. A(x) satisfies: x = Sum_{n>=1} 1/(1+A(x))^(2*n-1) * Product_{k=1..n} (1 - 1/(1+A(x))^k). - Paul D. Hanna, Apr 05 2012
Conjecture: 500*n*(n-1)*a(n) +100*(n-1)*(5*n -12)*a(n-1) +20*(25*n^2 -463*n +846)*a(n-2) +(-140161*n^2 +966559*n -1637508)*a(n-3) +2*(250*n^2 -26509*n +105084)*a(n-4) +98036*(4*n -19)*(4*n -21)*a(n-5) = 0. - R. J. Mathar, Nov 26 2012
a(n) ~ 4^(n-1) / (sqrt(3*Pi) * n^(3/2)). - Vaclav Kotesovec, Sep 03 2019

A055395 Number of bracketings of 0#0#0#...#0 giving result 0, where 0#0 = 0#1 = 1#0 = 1, 1#1 = 0.

Original entry on oeis.org

1, 0, 0, 1, 4, 12, 36, 116, 392, 1350, 4696, 16500, 58572, 209824, 757440, 2752185, 10057636, 36943044, 136319052, 505086728, 1878395920, 7009239644, 26235435248, 98475145476, 370584275964, 1397918543552, 5284861554816
Offset: 1

Views

Author

Jeppe Stig Nielsen, Jun 24 2000

Keywords

Comments

Operation # can be interpreted as NOT AND. The ratio a(n)/A000108(n-1) converges to (2-sqrt(2))/2. Thanks to Soren Galatius Smith

Crossrefs

Programs

  • Mathematica
    f[x_] := (1 - Sqrt[1 - 4*x])/2; CoefficientList[Series[(1 + 2*f[x] - Sqrt[1 + 4*(f[x])^2])/(2*x), {x, 0, 50}], x] (* G. C. Greubel, Jun 10 2016 *)

Formula

G.f.: 1 - (1/2)*(1 - 4*x)^(1/2) - (1/2)*(3 - 2*(1 - 4*x)^(1/2) - 4*x)^(1/2).
G.f.: (1 + 2*C(x) - sqrt(1 + 4*C(x)^2))/2, where C(x) = (1 - sqrt(1 - 4*x))/2 is the g.f. of the Catalan numbers (A000108). - Paul D. Hanna, Jun 10 2016
G.f. A(x) satisfies: A(x) = x + (A(x) - C(x))^2, where C(x) = x + C(x)^2 is a g.f. of the Catalan numbers (A000108). - Paul D. Hanna, Jun 11 2016

A306668 Difference between numbers of binary bracketings of 0^0^...^0 with n 0's giving the result 1 and those giving the result 0, with conventions that 0^0=1^0=1^1=1, 0^1=0.

Original entry on oeis.org

0, -1, 1, 0, 3, 4, 20, 50, 189, 588, 2100, 7116, 25344, 89298, 321178, 1156298, 4206059, 15356796, 56424836, 208137800, 771229684, 2867771004, 10700980956, 40050890172, 150328400292, 565699287186, 2133889856550, 8067040670100, 30559571239890, 115986196679730
Offset: 0

Views

Author

Alois P. Heinz, Mar 04 2019

Keywords

Comments

The total number of binary bracketings of 0^0^...^0 with n 0's is A000108(n-1) for n > 0.

Examples

			There are A000108(3) = 5 binary bracketings of 0^0^0^0: ((0^0)^0)^0, (0^0)^(0^0), (0^(0^0))^0, 0^((0^0)^0), 0^(0^(0^0)). Only 0^((0^0)^0) evaluates to 0: 0^((0^0)^0) = 0^(1^0) = 0^1 = 0. The four other bracketings evaluate to 1. Thus a(4) = 4-1 = 3.
		

Crossrefs

Programs

  • Maple
    b:= proc(n) option remember; `if`(n<2, [n, 0], add(((f, g)-> [f[1]*g[2],
          f[1]*g[1] +f[2]*g[1] +f[2]*g[2]])(b(i), b(n-i)), i=1..n-1))
        end:
    a:= n-> (v-> v[2]-v[1])(b(n)):
    seq(a(n), n=0..29);
    # second Maple program:
    a:= proc(n) option remember; `if`(n<2, -n, ((35*n^3-147*n^2+220*n-120)*
          a(n-1)+18*(n-2)*(5*n-6)*(2*n-5)*a(n-2))/((2*(5*n-11))*(2*n-1)*n))
        end:
    seq(a(n), n=0..29);
  • Mathematica
    a[n_] := a[n] = If[n<2, -n, ((35n^3 - 147n^2 + 220n - 120) a[n-1] + 18(n-2) (5n - 6)(2n - 5) a[n-2])/((2(5n - 11))(2n - 1)n)];
    a /@ Range[0, 29] (* Jean-François Alcover, Apr 02 2021, after 2nd Maple program *)

Formula

a(n) = A111160(n-1) - A055113(n) for n > 0.
a(n) is odd <=> n in { A000079 }.

A166135 Number of possible paths to each node that lies along the edge of a cut 4-nomial tree, that is rooted one unit from the cut.

Original entry on oeis.org

1, 1, 3, 7, 22, 65, 213, 693, 2352, 8034, 28014, 98505, 350548, 1256827, 4542395, 16517631, 60417708, 222087320, 820099720, 3040555978, 11314532376, 42243332130, 158196980682, 594075563613, 2236627194858, 8440468925400, 31921622746680, 120970706601255
Offset: 1

Views

Author

Rick Jarosh (rick(AT)jarosh.net), Oct 08 2009

Keywords

Comments

This is the third member of an infinite series of infinite series, the first two being the Catalan and Motzkin integers. The Catalan numbers lie on the edge of cut 2-nomial trees, Motzkin integers on the edge of cut 3-nomial trees.
a(n) is the number of increasing unary-binary trees with associated permutation that avoids 213. For more information about increasing unary-binary trees with an associated permutation, see A245888. - Manda Riehl, Aug 07 2014
Number of positive walks with n steps {-2,-1,1,2} starting at the origin, ending at altitude 1, and staying strictly above the x-axis. - David Nguyen, Dec 16 2016

Crossrefs

A055113 is the third sequence from the top of the graph illustrated above.

Programs

  • Magma
    [(&+[Binomial(n,k)*Binomial(n,2*n-3*k-1): k in [0..n]])/n : n in [1..30]]; // G. C. Greubel, Dec 12 2019
    
  • Maple
    seq( add(binomial(n,k)*binomial(n,2*n-3*k-1), k=0..n)/n, n=1..30); # G. C. Greubel, Dec 12 2019
  • Mathematica
    Rest[CoefficientList[Series[(Sqrt[(2-2Sqrt[1-4x]-3x)/x]-1)/2, {x, 0, 30}],x]] (* Benedict W. J. Irwin, Sep 24 2016 *)
  • PARI
    vector(30, n, sum(k=0,n, binomial(n,k)*binomial(n,2*n-3*k-1))/n ) \\ G. C. Greubel, Dec 12 2019
    
  • Sage
    [sum(binomial(n,k)*binomial(n,2*n-3*k-1) for k in (0..n))/n for n in (1..30)] # G. C. Greubel, Dec 12 2019

Formula

a(n) = ((36*n+18)*A092765(n) + (11*n+9)*A092765(n+1))/(2*(5*n+3)*(2*n+3)) (based on guessed recurrence). - Mark van Hoeij, Jul 14 2010
A(x) satisfies A(x)+A(x)^2 = A000108(x)-1, a(n) = (1/n)*Sum_{k=1..n} (-1)^(k+1) * C(2*n,n-k)*C(2*k-2,k-1). - Vladimir Kruchinin, May 12 2012
G.f.: (sqrt((2 - 2*sqrt(1-4*x) - 3*x)/x) - 1)/2. - Benedict W. J. Irwin, Sep 24 2016
a(n) ~ 4^n/(sqrt(5*Pi)*n^(3/2)). - Vaclav Kotesovec, Sep 25 2016
Conjecture: 2*n*(2*n+1)*a(n) + (17*n^2-53*n+24)*a(n-1) + 6*(-13*n^2+43*n-36)*a(n-2) - 108*(2*n-5)*(n-3)*a(n-3) = 0. - R. J. Mathar, Oct 08 2016
a(n) = (1/n)*Sum_{k=0..n} binomial(n,k)*binomial(n,2*n-3*k-1). - David Nguyen, Dec 31 2016
From Alexander Burstein, Dec 12 2019: (Start)
1 + x*A(x) = 1/C(-x*C(x)^2), where C(x) is the g.f. of A000108.
F(x) = x*(1+x*A(x)) = x/C(-x*C(x)^2) is a pseudo-involution, i.e., the series reversion of x*(1 + x*A(x)) is x*(1 - x*A(-x)).
The B-sequence of F(x) is A069271, i.e., F(x) = x + x*F(x)*A069271(x*F(x)). (End)
Showing 1-10 of 21 results. Next