OFFSET
0,4
COMMENTS
From Petros Hadjicostas, Oct 10 2019: (Start)
Mallows (1979) comments that I. J. Good did not consider all kinds of independence between n random variables in deriving his formula for the e.g.f. of a(n). Unfortunately, the paper by Good (1975), where the proof of the e.g.f. was published, is not easily accessible.
We give a sketch of a proof of the formula below (using only the ideas of independence that I. J. Good considered). Given r.v.'s X_1, X_2, ..., X_n, we choose s of them on which to condition (where s = 0, 1, 2, ..., n-2). By "condition", we mean that we condition on every possible s-tuple of values of those chosen variables. This can be done in C(n, s) ways.
Note that we can only condition on up to n-2 variables, because we need at least two variables to define any kind of independence: conditional (s >= 1) or unconditional (s = 0). Thus, 2 <= n-s <= n.
From the remaining n-s variables, we choose t of them (where 2 <= t <= n-s) on which we will define (or test) independence. [According to Mallows (1979), this is the only kind of independence Good (1975) considers.] There are C(n-s, t) ways to choose the t variables on which to define (or test) independence.
Now, there are Bell(t) - 1 = A058692(t) ways to partition the set of t chosen variables into one or more subsets, say {S_1, ..., S_r} (the order of the subsets is not important). Here |S_i| >= 1 and (S_1 union S_2 union ... union S_r) equals the t chosen variables. Thus, there are Bell(t) - 1 ways to factor the joint p.d.f. of the chosen t variables into the product of the joint marginal p.d.f.'s of the variables in S_i (i = 1, ..., r). [By "joint marginal p.d.f." for group S_i we mean the joint p.d.f of all the variables in group S_i.] Each such factorization defines a different kind of independence of the chosen variables (conditional on the original chosen s variables).
Thus, in the sense of Good (1975, 1979), there are a(n) = Sum_{s = 0..n-2} Sum_{t = 2..n-s} C(n, s) * C(n-s, t) * (Bell(t) - 1) kinds of independence among the variables.
Letting k = n-s, we get a(n) = Sum_{k = 2..n} Sum_{t = 2..k} C(n, n-k) * C(k, t) * (Bell(t) - 1) = Sum_{k = 2..n} Sum_{t = 2..k} C(n, k) * C(k, t) * (Bell(t) - 1).
The second formula for a(n) follows from the fact that Sum_{m = 2..k} binomial(k,m) * (Bell(m) - 1) = A058681(k) = Bell(k+1) - 2^k.
Counting all kinds of independence, as suggested by Mallows (1979), seems to be a very difficult task. For example, for n = 3, he finds a(3) = 17 kinds of independence rather than 10.
(End)
REFERENCES
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..300
I. J. Good, The number of hypotheses of independence for a random vector or for a multidimensional contingency table, and the Bell numbers, Iranian J. Science and Technology, 4, (1975), 77-83.
I. J. Good, On the application of symmetric Dirichlet distributions and their mixtures to contingency tables, Ann. Statist. 4 (1976), no. 6, 1159-1189.
C. L. Mallows, How many independence hypotheses are there?, J. Statist. Comput. Simul. 9 (1979), 235-236.
Wikipedia, I. J. Good.
FORMULA
E.g.f.: exp(exp(x)+2*x-1) - exp(3*x).
From Petros Hadjicostas, Oct 10 2019: (Start)
a(n) = Sum_{k = 2..n} Sum_{m = 2..k} binomial(n,k) * binomial(k,m) * (Bell(m) - 1), where Bell(m) = A000110(m) and Bell(m) - 1 = A058692(m).
a(n) = Sum_{k = 2..n} (Bell(k+1) - 2^k) * binomial(n,k) = Sum_{k = 2..n} A058681(k)*binomial(n,k). (End)
From G. C. Greubel, Feb 23 2022: (Start)
a(n) = Sum_{j=0..n} ( binomial(n,j)*2^j*Bell(n-j) ) - 3^n [Good, Iranian J. Sci. Tech., pg. 80, eq (10)].
a(n) = Bell(n+2) - Bell(n+1) - 3^n. (End)
EXAMPLE
From Petros Hadjicostas, Oct 10 2019: (Start)
For two r.v.'s X and Y, there is one kind of independence: f(x,y) = f(x)*f(y) (where f denotes a p.d.f., joint or marginal). Thus, a(2) = 1.
For three r.v.'s X, Y, and Z, we have
(i) 3 pairwise independence relations (f(x,y) = f(x)*f(y), or f(x,z) = f(x)*f(z), or f(y,z) = f(y)*f(z));
(ii) a factorization of the form f(x,y,z) = f(x)*f(y)*f(z);
(iii) 3 factorizations of the form f(x,y,z) = f(x,y)*f(z), or f(x,y,z) = f(y,z)*f(x), or f(x,y,z) = f(x,z)*f(y); [e.g. f(x,y,z) = f(x,y)*f(z) means random vector (X,Y) is jointly independent of variable Z]
(iv) 3 conditional factorizations f(x,y|z) = f(x|z)*f(y|z), or f(y,z|x) = f(y|x)*f(z|x), or f(x,z|y) = f(x|y)*f(z|y).
Hence, a(3) = 3 + 1 + 3 + 3 = 10. (See Mallows (1979) for some kinds of independence not considered by Good (1975, 1976).)
For four variables X, Y, Z, W, we have several cases:
(i) If we condition on a single variable, then we have 3 + 1 + 3 = 7 conditional independence cases (cases (i), (ii), and (iii) for n = 3) --> a total of C(4,1)*7 = 28.
(ii) If we condition on 2 variables, we have 1 kind of independence; i.e., a total of C(4,2)*1 = 6.
(iii) If we do not condition on any variables, we may consider:
(A) the independence of every two r.v.'s --> C(4,2) = 6 cases.
(B) the independence of every three variables: 1 + 3 = 4 factorizations (see the unconditional cases (ii) and (iii) above for the case n=3) --> a total of C(4,3)*4 = 16 factorizations.
(C) the factorizations f(x,y,z,w) = f(x)*f(y)*f(z)*f(w), or = f(x,y,z)*f(z), or = f(x,z,w)*f(y), or = f(x,y,w)*f(z), or f(y,z,w)*f(x), or = f(x,y)*f(z,w), or = f(x,z)*f(y,w), or = f(x,w)*f(y,z), or = f(x,w)*f(y)*f(z), etc. --> a total of 15-1 = 14 factorizations.
Hence, a(4) = 28 + 6 + 6 + 16 + 14 = 70.
(End)
MATHEMATICA
With[{nn=30}, CoefficientList[Series[Exp[Exp[x]+2x-1]-Exp[3x], {x, 0, nn}], x] Range[0, nn]!] (* Harvey P. Dale, Nov 04 2015 *)
PROG
(Magma) [Bell(n+2) -Bell(n+1) -3^n: n in [0..30]]; // G. C. Greubel, Feb 23 2022
(Sage) [bell_number(n+2) -bell_number(n+1) -3^n for n in (0..30)] # G. C. Greubel, Feb 23 2022
CROSSREFS
KEYWORD
nonn,nice
AUTHOR
EXTENSIONS
More terms from N. J. A. Sloane, Jun 26 2015
STATUS
approved