1,2

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}.

Stanley, R.P.: Enumerative Combinatorics: Volume 1: Wadsworth & Brooks: 1986: p. 11

a(n)=(2^n-1)^3

a(1)=(2^1-1)^3=1 because only one tuple of length one, namely ({}) has an

empty intersection of its sole entry. a(2)=27 because the valid 2-tuples are: ({},{}),

({},{1}), ({},{2}), ({},{3}), ({},{1,2}), ({},{1,3}), ({},{2,3}), ({},{1,2,3}),

({1},{}), ({2},{}), ({3},{}), ({1,2},{}), ({1,3},{}), ({2,3},{}), ({1,2,3},{}),

({1},{2}), ({1},{3}), ({1},{2,3}), ({2},{1}), ({2},{3}), ({2},{1,3}), ({3},{1}),

({3},{2}), ({3},{1,2}), ({1,2},{3}), ({1,3},{2}), ({2,3},{1})

for k from 1 to 20 do (2^k-1)^3; od;

with(combinat):seq(mul(stirling2(n, 2), k=1..3), n=2..20); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Dec 16 2007

Cf. A060867.

Adjacent sequences: A128828 A128829 A128830 this_sequence A128832 A128833 A128834

Sequence in context: A038840 A032599 A016839 this_sequence A018797 A133050 A125439

easy,nonn

Peter C. Heinig (algorithms(AT)gmx.de), Apr 13 2007