|
|
A137591
|
|
Number of parenthesizings of products formed by n factors assuming nonassociativity and partial commutativity: individual factors commute, but bracketed expressions don't commute with anything.
|
|
3
|
|
|
1, 1, 6, 54, 660, 10260, 194040, 4326840, 111177360, 3234848400, 105135861600, 3775206204000, 148426878600000, 6341634955656000, 292576856395824000, 14496220038251952000, 767691210706291872000, 43274547687106768032000, 2587028200730649643968000, 163484729048197101504960000
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
See the double factorials A001147 for the case when the product is commutative and nonassociative.
Another interpretation is possible in terms of dendrograms. A001147 gives the number labeled, non-ranked, binary dendrograms, so-called L-NR dendrograms. This sequence gives the number of L-NR dendrograms if the order of objects counts within a dendrogram class.
See the Murtagh paper cited in A001147 for more on dendrograms. See also Vandev.
Vandev's formula (1) is our recurrence for this sequence, but it seems that Vandev meant a(n) = Sum_{k=1..n-1} binomial(n-1, k)*a(k)*a(n-k) with a(1)=1, a(2)=1. This recurrence gives the double factorials.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{k=1..n-1} binomial(n,k)*a(k)*a(n-k), with a(1)=1, a(2)=1.
E.g.f.: (1/2)*(1 - sqrt(1 - 4*x + 2*x^2)). - Thomas Wieder, May 02 2009, edited by May Cai, Feb 13 2024
a(n) ~ sqrt(2+2*sqrt(2))/2 * n^n * (2+sqrt(2))^n / exp(n). - Vaclav Kotesovec, Oct 07 2013
|
|
EXAMPLE
|
a(4)=54 because we have
w(x(yz)), w((yz)x), (x(yz))w, ((yz)x)w,
w(y(xz)), w((xz)y), (y(xz))w, ((xz)y)w,
w(z(xy)), w((xy)z), (z(xy))w, ((xy)z)w,
x(w(yz)), x((yz)w), (w(yz))x, ((yz)w)x,
x(y(wz)), x((wz)y), (y(wz))x, ((wz)y)x,
x(z(wy)), x((wy)z), (z(wy))x, ((wy)z)x,
y(w(xz)), y((xz)w), (w(xz))y, ((xz)w)y,
y(x(wz)), y((wz)x), (x(wz))y, ((wz)x)y,
y(z(wx)), y((wx)z), (z(wx))y, ((wx)z)y,
z(w(xy)), z((xy)w), (w(xy))z, ((xy)w)z,
z(x(wy)), z((wy)x), (x(wy))z, ((wy)x)z,
z(y(wx)), z((wx)y), (y(wx))z, ((wx)y)z,
(wx)(yz), (yz)(wx)
(wy)(xz), (xz)(wy)
(wz)(xy), (xy)(wz)
and 12*4 + 3*2 = 48 + 6 = 54.
Note that:
w(x(yz)) is equivalent to w(x(zy)) but not to (x(yz))w or w((yz)x);
(wx)(yz) is equivalent to (xw)(yz) or (wx)(zy) but not to (yz)(wx).
|
|
MAPLE
|
H(1):=1; H(2):=1; for n from 3 to 12 do H(n):=0: for k from 1 to n-1 do H(n):= H(n)+binomial(n, k)*H(k)*H(n-k) od: print(H(n)); od:
|
|
MATHEMATICA
|
CoefficientList[Series[(1-x)/Sqrt[1-4*x+2*x^2], {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Oct 07 2013 *)
|
|
PROG
|
(PARI) x='x+O('x^66); Vec( serlaplace((1-x)/sqrt(1-4*x+2*x^2)) ) \\ Joerg Arndt, Oct 08 2013
(GAP) a := [1, 1];; for n in [3..10^2] do a[n] := Sum([1..n-1], k->Binomial(n, k)*a[k]*a[n-k]); od; a; # Muniru A Asiru, Jan 30 2018
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,changed
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|