|
| |
|
|
A109714
|
|
Number of different ways an n-ary probability distribution can be decomposed in terms of products of binary probability distributions.
|
|
0
| |
|
|
1, 1, 3, 18, 120, 1170, 12600, 176400, 2608200, 46607400, 883159200
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,3
|
|
|
COMMENTS
| 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.
|
|
|
FORMULA
| 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
| 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.
|
|
|
PROG
| (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;
|
|
|
CROSSREFS
| Cf. A000108.
Sequence in context: A196865 A153394 A009065 * A118348 A011792 A183145
Adjacent sequences: A109711 A109712 A109713 * A109715 A109716 A109717
|
|
|
KEYWORD
| easy,nonn
|
|
|
AUTHOR
| Niko Brummer (niko.brummer(AT)gmail.com), Aug 08 2005
|
| |
|
|
