1,3

This sequence may have relevance to machine-learning where an n-ary probability distribution is sometimes assembled out of multiple binary distributions. These decompositions may be depicted as binary trees (with every node having zero or 2 children) and with n leaves. Every bifurcation in the tree corresponds to a binary probability distribution. The sequence defined here grows faster than the sequence of Catalan numbers A000108.

a(1) = 1 a(2) = 1 a(3) = Binomial(3, 1) * a(1) * a(2) a(4) = Binomial(4, 1) * a(1) * a(3) + Binomial(4, 2) * a(2) * a(2) a(5) = Binomial(5, 1) * a(1) * a(4) + Binomial(5, 2) * a(2) * a(3) a(6) = Binomial(6, 1) * a(1) * a(5) + Binomial(6, 2) * a(2) * a(4) + Binomial(6, 3) * a(3) * a(3) ... a(n) = Sum_{i=1 ... Floor(n/2)} Binomial(n, i) * a(i) * a(n-i)

Example for n = 3:

Let a,b,c be three mutually exclusive events so that the probabilities of these three events sum to one: P(a)+P(b)+P(c) = 1. This is a 3-ary probability distribution. There are three ways to decompose this distribution in terms of binary distributions:

1. P(a) = P(~(b||c)), P(b) = P(b||c) * P(b | (b||c) ), P(c) = P(b||c) * P(c | (b||c) )

2. P(b) = P(~(a||c)), P(a) = P(a||c) * P(a | (a||c) ), P(c) = P(a||c) * P(c | (a||c) )

3. P(c) = P(~(a||b)), P(a) = P(a||b) * P(a | (a||b) ), P(b) = P(a||b) * P(b | (a||b) )

Here ~ denotes NOT, || denotes OR, | denotes 'given'. The probability distribution P(a||b), P(~(a||b)) is a binary distribution and so is P(a| (a||b)), P(b | (a||b)) and so on.

(MATLAB) function m = a(n); if n==1 m = 1; elseif n==2 m = 1; else m = 0; for i=1:floor(n/2); f1 = binomial(n, i); f2 = a(i); f3 = a(n-i); m = m + f1*f2*f3; end; end;

Cf. A000108.

Sequence in context: A113328 A153394 A009065 this_sequence A118348 A011792 A127188

Adjacent sequences: A109711 A109712 A109713 this_sequence A109715 A109716 A109717

easy,nonn

Niko Brummer (niko.brummer(AT)gmail.com), Aug 08 2005