|
Search: id:A128832
|
|
|
| A128832 |
|
Number of n-tuples where each entry is chosen from the subsets of {1,2,3,4} such that the intersection of all n entries is empty. |
|
+0
2
|
|
| 1, 81, 2401, 50625, 923521, 15752961, 260144641, 4228250625, 68184176641, 1095222947841, 17557851463681, 281200199450625, 4501401006735361, 72040003462430721, 1152780773560811521, 18445618199572250625
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
The general formula where each entry is chosen from the subsets of {1,..,k} is (2^n-1)^k. This may be shown by exhibiting a bijection to a set whose cardinality is obviously (2^n-1)^k, namely the set of all k-tuples with each entry chosen from the 2^n-1 proper subsets of {1,..,n}, i.e. for of the k entries {1,..,n} is forbidden. The bijection is given by (X_1,..,X_n) |-> (Y_1,..,Y_k) where for each j in {1,..,k} and each i in {1,..,n}, i is in Y_j if and only if j is in X_i. Sequence A060867 is the case where the entries are chosen from subsets of {1,2}.
|
|
REFERENCES
|
Stanley, R.P.: Enumerative Combinatorics: Volume 1: Wadsworth & Brooks: 1986: p. 11
|
|
FORMULA
|
a(n)=(2^n-1)^4
|
|
EXAMPLE
|
a(1)=(2^1-1)^4=1 because only one tuple of length one, namely ({}) has an
empty intersection of its sole entry.
|
|
MAPLE
|
for k from 1 to 20 do (2^k-1)^4; od;
with (combinat):seq(mul(stirling2(n, 2), k=1..4), n=2..17); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Dec 16 2007
|
|
CROSSREFS
|
Sequence in context: A037211 A038676 A016840 this_sequence A085877 A123219 A018223
Adjacent sequences: A128829 A128830 A128831 this_sequence A128833 A128834 A128835
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
Peter C. Heinig (algorithms(AT)gmx.de), Apr 13 2007
|
|
|
Search completed in 0.002 seconds
|
