A006447 -id:A006447 - cp's OEIS frontend

A000992 "Half-Catalan numbers": a(n) = Sum_{k=1..floor(n/2)} a(k)*a(n-k) with a(1) = 1.

1, 1, 1, 2, 3, 6, 11, 24, 47, 103, 214, 481, 1030, 2337, 5131, 11813, 26329, 60958, 137821, 321690, 734428, 1721998, 3966556, 9352353, 21683445, 51296030, 119663812, 284198136, 666132304, 1586230523, 3734594241, 8919845275, 21075282588, 50441436842

Offset: 1

N. J. A. Sloane

From David Callan, Nov 02 2006: (Start)
a(n) = number of (unlabeled, rooted) ordered trees on n-1 vertices in which all outdegrees are <= 2 and, for each vertex of outdegree 2, the sizes of its two subtrees are weakly increasing left to right (n >= 2). The number b(n) of such trees on n vertices satisfies the recurrence b[1]=1; b[n_]/;n>=2 := b[n] = b[n-1] + Sum_{i=1..floor((n-1)/2)} b[i]b[n-1-i], the first term counting trees whose root has outdegree 1 and the sum counting trees whose root has outdegree 2 by size of the left subtree. This recurrence generates b(n) = a(n+1), n >= 1. For example, the a(5)=3 such trees are:
.|....|...../\..
.|.../.\.....|..
.|.............. (End)
From R. J. Mathar, Mar 27 2009: (Start)
The connection with the Rayleigh polynomials Phi(2n,x) of A158616 is that Phi(2n,x) = Sum_{i=1..a(n)} 2^(n_i) Product_{j=2..n-1} (x+j)^(n_ij), as described by Kishore.
So a(n) counts the terms in the representation of the polynomial Phi(2n,x) as a sum over these "base" polynomials.
For example, Phi(12,x) = 2^4*(x+2)^2*(x+3) + 2^2*(x+2)*(x+3)^2 + 2^3*(x+2)*(x+3)*(x+4) + 2^3*(x+2)*(x+3)*(x+5) + 2^2*(x+2)*(x+4)*(x+5) + 2*(x+3)^2*(x+5) has a(6)=6 terms. (End)
From Wolfdieter Lang, Jan 06 2012: (Start)
The o.g.f. G(x) := Sum_{n>=0} a(n)*x^n, with a(0)=0, satisfies the relation (G(x))^2 - 2*G(x) + G2(x^2) + 2*x = 0, with the o.g.f. G2(x) := Sum_{n>=0} a(n)^2*x^n of the squares. This can be proved from the connection to the half-convolution of the sequence with itself (for this notion see a comment on A201204, where also the rule for the o.g.f. is given). (End)
Limit_{n->infinity} a(n)^(1/n) = 2.49086422... . - Vaclav Kotesovec, Oct 15 2014
This sequence diverges from A001190 for n >= 8. A001190(n) gives the number of unlabeled binary trees with n leaves and n-1 internal nodes. - Andrew Howroyd, Apr 01 2023

			G.f. = x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 11*x^7 + 24*x^8 + 47*x^9 + ...

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

Vaclav Kotesovec, Table of n, a(n) for n = 1..2500 (first 200 terms from T. D. Noe)
E. Bohl, P. Lancaster, Implementation of a Markov model for phylogenetic trees, J. Theor. Biol. 239 (3) (2006) 324-333.
J. T. Butler, Letter to N. J. A. Sloane, Jun. 1975.
David S. Evans, Stars of Higher Multiplicity, Quarterly Journal of the Royal Astronomical Society, Vol. 9 (1968), pp. 388-400.
T. Feil, K.Hutson, R. J. Kretchmar, Tree traversals and permutations, Congr. Numer. 175 (2005) 201-221 (mentions the sequence only in the references, not in the text).
N. Kishore, A structure of the Rayleigh polynomial, Duke Math. J., 31 (1964), 513-518.

Compare recurrence for A000108 (the Catalan numbers).
A093637 counts above trees without the restriction that all outdegrees are <= 2.
Cf. A001190, A124973, A248748.

a000992 n = a000992_list !! (n-1)
a000992_list = 1 : f 1 0 [1] where
   f x y zs = z : f (x + y) (1 - y) (z:zs) where
     z = sum $ take x $ zipWith (*) zs $ reverse zs
-- Reinhard Zumkeller, Dec 21 2011

al := 1/2; M1 := 30; a[ 0 ] := 1; for n from 0 to M1 do n0 := floor(al*n);
a[ n+1 ] := sum( a[ i ]*a[ n-i ], i=0..n0); i := 'i'; od: [ seq(a[ j ],j=0..M1) ];
# second Maple program:
a:= proc(n) option remember; `if`(n=1, 1,
      add(a(j)*a(n-j), j=1..n/2))
    end:
seq(a(n), n=1..42);  # Alois P. Heinz, Sep 22 2019

a[1]=1; a[n_]:=a[n]=Sum[a[k] a[n-k],{k,1,Floor[n/2]}]; Table[a[n],{n,1,32}] (* Jean-François Alcover, Mar 21 2011 *)

A000992_list(n)={for(i=4,#n=vector(n,i,1),n[i]=sum(j=1,i\2,n[j]*n[i-j]));n}  \\ M. F. Hasler, Dec 20 2011

from functools import lru_cache
@lru_cache(maxsize=None)
def A000992(n): return sum(A000992(k)*A000992(n-k) for k in range(1,(n>>1)+1)) if n>1 else 1 # Chai Wah Wu, Nov 04 2024

A005613 Cascade-realizable Boolean functions of n variables.

Original entry on oeis.org

2, 2, 10, 114, 1842, 37226, 902570, 25530658, 825345250, 30016622298, 1212957186330, 53916514446482, 2614488320210258, 137345270749953610, 7770078330925987210, 470977659902530345986, 30451167044311817097666, 2091878780326890801618362

Offset: 0

N. J. A. Sloane

nonn

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

E. A. Bender and J. T. Butler, Asymptotic approximations for the number of fanout-free functions, IEEE Trans. Computers, 27 (1978), 1180-1183. (Annotated scanned copy)
J. T. Butler, Letter to N. J. A. Sloane, Jun. 1975 and Dec. 1978.
J. T. Butler, On the number of functions realized by cascades and disjunctive networks, IEEE Trans. Computers, C-24 (1975), 681-690. (Annotated scanned copy)
K. L. Kodandapani and S. C. Seth, On combinational networks with restricted fan-out, IEEE Trans. Computers, 27 (1978), 309-318. (Annotated scanned copy)
Index entries for sequences related to Boolean functions

a(0) = 2, a(1) = 2, a(n) = Sum_{k=1..n-1} ((-1)^(k+1) * binomial(n,k) * (2^(k+1)+1) * a(n-k)) - (-1)^n(2^n+1)a(1). [From Butler] - Sean A. Irvine, Jul 14 2016

More terms from Sean A. Irvine, Jul 14 2016

a(0) added by Sean A. Irvine, Aug 22 2016

A005616 Number of non-degenerate disjunctively-realizable functions of n variables.

Original entry on oeis.org

2, 2, 10, 114, 2154, 56946, 1935210, 80371122, 3944568042, 223374129138, 14335569726570, 1028242536825906, 81514988432370666, 7077578056972377714, 667946328512863533930, 68080118128074301929138, 7453010693997492901047018

Offset: 0

N. J. A. Sloane

nonn

Number of non-degenerate fanout-free Boolean functions of n variables using And, Or, Xor, and Not gates.

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

Andrew Howroyd, Table of n, a(n) for n = 0..200
E. A. Bender and J. T. Butler, Asymptotic approximations for the number of fanout-free functions, IEEE Trans. Computers, 27 (1978), 1180-1183. (Annotated scanned copy)
J. T. Butler, Letter to N. J. A. Sloane, Jun. 1975 and Dec. 1978.
J. T. Butler, On the number of functions realized by cascades and disjunctive networks, IEEE Trans. Computers, C-24 (1975), 681-690. (Annotated scanned copy)
K. L. Kodandapani and S. C. Seth, On combinational networks with restricted fan-out, IEEE Trans. Computers, 27 (1978), 309-318. (Annotated scanned copy)

Cf. A005738, A005739.

seq(n)=my(p=2*exp(x + O(x*x^n)), g=serreverse(x + log(p-1) - p + 2)); Vec(serlaplace(2*exp(g))) \\ Andrew Howroyd, Apr 03 2025

seq(n)=Vec(2*serlaplace(1 + serreverse(log(1 + 3*x + 2*x^2 + O(x*x^n)) - 2*x))) \\ Andrew Howroyd, Apr 03 2025

From Andrew Howroyd, Apr 03 2025: (Start)
E.g.f.: 2*(p + q + 1) where p,q satisfy q = exp(p) - p - 1, p = exp(2*q + p + x) - (2*q + p + 1).
E.g.f.: 2*exp( Series_Reversion(x + log(2*exp(x)-1) - 2*(exp(x) - 1)) ).
E.g.f.: 2 + 2*Series_Reversion(log(1 + 3*x + 2*x^2) - 2*x). (End)

a(0), a(14)-a(16) from Sean A. Irvine, Jul 21 2016

A005739 Number of disjunctively-realizable functions of n variables.

Original entry on oeis.org

2, 4, 16, 152, 2680, 68968, 2311640, 95193064, 4645069336, 261938616104, 16756882325464, 1198897678224232, 94851206834082200, 8221740727881348520, 774839374768829174104, 78880995816162599086568, 8626562553228821851608856

Offset: 0

N. J. A. Sloane

nonn

Number of fanout-free Boolean functions of n variables using And, Or, Xor, and Not gates. - Andrew Howroyd, Apr 03 2025

K. L. Kodandapani and S. C. Seth, On combinational networks with restricted fan-out, IEEE Trans. Computers, C-27 (1978), 309-318.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 0..200
J. T. Butler, Letter to N. J. A. Sloane, Jun. 1975.
J. T. Butler, On the number of functions realized by cascades and disjunctive networks, IEEE Trans. Computers, C-24 (1975), 681-690. (Annotated scanned copy)
K. L. Kodandapani and S. C. Seth, On combinational networks with restricted fan-out, IEEE Trans. Computers, 27 (1978), 309-318. (Annotated scanned copy)

Cf. A005616, A005738.

a(n) = A005616(n) + A005738(n) [From Kodandapani and Seth]. - Sean A. Irvine, Jul 21 2016

Binomial transform of A005616. - Andrew Howroyd, Apr 03 2025

More terms from Sean A. Irvine, Jul 21 2016

a(0)=2 prepended by Andrew Howroyd, Apr 03 2025

A005749 Cascade-realizable Boolean functions of n variables.

Original entry on oeis.org

4, 16, 152, 2368, 47688, 1156000, 32699080, 1057082752, 38444581640, 1553526946144, 69054999618888, 3348574955346496, 175908582307762312, 9951733002164182048, 603217074746723736776, 39001136297834245139200, 2679228986900726147063304

Offset: 1

N. J. A. Sloane

nonn

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

J. T. Butler, Letter to N. J. A. Sloane, Jun. 1975.
J. T. Butler, On the number of functions realized by cascades and disjunctive networks, IEEE Trans. Computers, C-24 (1975), 681-690. (Annotated scanned copy)
Index entries for sequences related to Boolean functions

Cf. A005613.

a(n) = Sum_{k=0..n} binomial(n, k) * A005613(k). - Sean A. Irvine, Aug 22 2016

More terms from Sean A. Irvine, Aug 22 2016

cp's OEIS Frontend

A000992 "Half-Catalan numbers": a(n) = Sum_{k=1..floor(n/2)} a(k)*a(n-k) with a(1) = 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

A005613 Cascade-realizable Boolean functions of n variables.

Views

Author

Keywords

References

Links

Formula

Extensions

A005616 Number of non-degenerate disjunctively-realizable functions of n variables.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

PARI

Formula

Extensions

A005739 Number of disjunctively-realizable functions of n variables.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A005749 Cascade-realizable Boolean functions of n variables.

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions