A226909 Number of placements of brackets in a monomial of degree n in an algebra with two commutative multiplications.

1, 2, 4, 14, 44, 164, 616, 2450, 9908, 41116, 173144, 739884, 3196344, 13944200, 61327312, 271653254, 1210772124, 5426133764, 24435934568, 110524288836, 501864708968, 2286937749496, 10454921456688, 47936304101860, 220383617137704, 1015714229399256

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

Cf. Wedderburn-Etherington numbers (A001190), A241555.

Sequence in context: A128750 A047152 A007866 * A121751 A327644 A151355

Adjacent sequences: A226906 A226907 A226908 * A226910 A226911 A226912

Keyword

nice,nonn

Author

Murray R. Bremner, Jun 21 2013

Status

approved