|
| |
|
|
A128865
|
|
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 contains exactly one element.
|
|
0
|
|
|
|
4, 108, 1372, 13500, 119164, 1000188, 8193532, 66325500, 533731324, 4282396668, 34309431292, 274676629500, 2198218047484, 17588965015548, 140724603846652, 1125848368021500, 9006993097883644, 72056769407352828, 576457453774831612
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
There is the following general formula: The number T(n,k,r) of n-tuples where each entry is chosen from the subsets of {1,2,..,k} such that the intersection of all n entries contains exactly r elements is: T(n,k,r) = C(k,r) * (2^n - 1)^(k-r). This may be shown by exhibiting a bijection to a set whose cardinality is obviously C(k,r) * (2^n - 1)^(k-r), namely the set of all k-tuples where each entry is chosen from subsets of {1,..,n} in the following way: Exactly r entries must be {1,..,n} itself (there are C(k,r) ways to choose them) and the remaining (k-r) entries must be chosen from the 2^n-1 proper subsets of {1,..,n}, i.e. for each of the (k-r) entries, {1,..,n} is forbidden (there are, independent of the choice of the full entries, (2^n - 1)^(k-r) possibilities to do that, hence the formula). The bijection into this set 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.
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = 4*(2^n-1)^3.
G.f.: 4*x*(8*x^2+12*x+1)/((x-1)*(2*x-1)*(4*x-1)*(8*x-1)). [Colin Barker, Nov 17 2012]
|
|
|
EXAMPLE
|
a(1)=4 because the four tuples of length one are ({1}), ({2}), ({3}), ({4}).
|
|
|
PROG
|
(Java) import java.io.*; import java.math.*; public class MakeSequence { public static void main(String[] args) { String s = new String(); BigInteger x; BigInteger one = new BigInteger("1"); BigInteger four = new BigInteger("4"); String help; try { BufferedWriter out = new BufferedWriter(new FileWriter("sequence.txt")); for (Integer k=1; k<51; ++k) { x = (((two.pow(k)).subtract(one)).pow(3)).multiply(four); help = x.toString(); s = help + ", "; out.write(s); } out.close(); } catch (IOException e) { } } }
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
Peter C. Heinig (algorithms(AT)gmx.de), Apr 17 2007
|
|
|
STATUS
|
approved
|
| |
|
|
