OFFSET
1,2
COMMENTS
This sequence generalizes the Wedderburn-Etherington numbers (A001190) to the case of two different types of brackets, such as square brackets [-.-] and curly brackets {-,-}.
Also number of N-free graphs [Cameron]. - Michael Somos, Apr 18 2014
REFERENCES
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence as M1302, except that, copying Cameron's error, 14 is missing).
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..500
M. Bremner, S. Madariaga, Lie and Jordan products in interchange algebras, arXiv preprint arXiv:1408.3069, 2014.
Murray Bremner, Martin Markl, Distributive laws between the Three Graces, arXiv:1809.08191 [math.AT], 2018.
P. J. Cameron, Some treelike objects, Quart. J. Math. Oxford, 38 (1987), 155-183. See p. 166, but note that 14 is missing. - Michael Somos, Apr 18 2014
FORMULA
G.f. A(x) satisfies A(x) = x + A(x^2) + A(x)^2. - Michael Somos, Jun 13 2014
a(n) ~ c * d^n / n^(3/2), where d = 4.8925511471743497508362229157295..., c = 0.155553379207933493345508839... . - Vaclav Kotesovec, Sep 07 2014
EXAMPLE
For n = 4 the 14 different bracketings are as follows:
[1[2[34]]], {1[2[34]]}, [1{2[34]}], {1{2[34]}}, [1[2{34}]], {1[2{34}]}, [1{2{34}}], {1{2{34}}}, [[12][34]], {[12][34]}, [[12]{34}], {[12]{34}}, [{12}{34}], {{12}{34}}.
G.f. = x + 2*x^2 + 4*x^3 + 14*x^4 + 44*x^5 + 164*x^6 + 616*x^7 + ...
MAPLE
BBcount := table():
BBcount[ 1 ] := 1:
for n from 2 to 10 do
BBcount[ n ] := 0:
for i to floor((n-1)/2) do
BBcount[n] := BBcount[n] + 2*BBcount[i]*BBcount[n-i]
od:
if n mod 2 = 0 then
BBcount[n] := BBcount[n] + 2*binomial(BBcount[n/2]+1, 2)
fi:
print( n, BBcount[ n ] )
od:
MATHEMATICA
max = 26; Clear[BBcount]; BBcount[1] = 1; For[n = 2, n <= max, n++, BBcount[n] = 0; For[i = 1, i <= Floor[(n-1)/2], i++, BBcount[n] = BBcount[n] + 2*BBcount[i]*BBcount[n-i]]; If[EvenQ[n], BBcount[n] = BBcount[n] + 2*Binomial[BBcount[n/2]+1, 2]]]; Array[BBcount, max] (* Jean-François Alcover, Mar 24 2014, translated from Maple *)
PROG
(PARI) {a(n) = local(A); if( n<2, n>0, A = x + O(x^2); for(k=2, n, A = x + A^2 + subst(A, x, x^2)); polcoeff(A, n))}; /* Michael Somos, Jun 13 2014 */
(PARI) {a(n) = if( n<2, n>0, 2 * sum(k=1, (n-1)\2, a(k) * a(n-k)) + if( n%2==0, 2 * binomial( a(n/2) + 1, 2)))}; /* Michael Somos, Jun 13 2014 */
CROSSREFS
KEYWORD
nice,nonn
AUTHOR
Murray R. Bremner, Jun 21 2013
STATUS
approved