|
|
A226909
|
|
Number of placements of brackets in a monomial of degree n in an algebra with two commutative multiplications.
|
|
5
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|