A226909 - OEIS

%I #35 Dec 12 2018 14:24:02

%S 1,2,4,14,44,164,616,2450,9908,41116,173144,739884,3196344,13944200,

%T 61327312,271653254,1210772124,5426133764,24435934568,110524288836,

%U 501864708968,2286937749496,10454921456688,47936304101860,220383617137704,1015714229399256

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

%C This sequence generalizes the Wedderburn-Etherington numbers (A001190) to the case of two different types of brackets, such as square brackets [-.-] and curly brackets {-,-}.

%C Also number of N-free graphs [Cameron]. - _Michael Somos_, Apr 18 2014

%D 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).

%H Alois P. Heinz, <a href="/A226909/b226909.txt">Table of n, a(n) for n = 1..500</a>

%H M. Bremner, S. Madariaga, <a href="http://arxiv.org/abs/1408.3069">Lie and Jordan products in interchange algebras</a>, arXiv preprint arXiv:1408.3069, 2014.

%H Murray Bremner, Martin Markl, <a href="https://arxiv.org/abs/1809.08191">Distributive laws between the Three Graces</a>, arXiv:1809.08191 [math.AT], 2018.

%H P. J. Cameron, <a href="http://dx.doi.org/10.1093/qmath/38.2.155">Some treelike objects</a>, Quart. J. Math. Oxford, 38 (1987), 155-183. See p. 166, but note that 14 is missing. - _Michael Somos_, Apr 18 2014

%F G.f. A(x) satisfies A(x) = x + A(x^2) + A(x)^2. - _Michael Somos_, Jun 13 2014

%F a(n) ~ c * d^n / n^(3/2), where d = 4.8925511471743497508362229157295..., c = 0.155553379207933493345508839... . - _Vaclav Kotesovec_, Sep 07 2014

%e For n = 4 the 14 different bracketings are as follows:

%e [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}}.

%e G.f. = x + 2*x^2 + 4*x^3 + 14*x^4 + 44*x^5 + 164*x^6 + 616*x^7 + ...

%p BBcount := table():

%p BBcount[ 1 ] := 1:

%p for n from 2 to 10 do

%p   BBcount[ n ] := 0:

%p for i to floor((n-1)/2) do

%p     BBcount[n] := BBcount[n] + 2*BBcount[i]*BBcount[n-i]

%p   od:

%p if n mod 2 = 0 then

%p     BBcount[n] := BBcount[n] + 2*binomial(BBcount[n/2]+1,2)

%p   fi:

%p print( n, BBcount[ n ] )

%p od:

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

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

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

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

%K nice,nonn

%O 1,2

%A _Murray R. Bremner_, Jun 21 2013