A128831 Number of n-tuples where each entry is chosen from the subsets of {1,2,3} such that the intersection of all n entries is empty.

1, 27, 343, 3375, 29791, 250047, 2048383, 16581375, 133432831, 1070599167, 8577357823, 68669157375, 549554511871, 4397241253887, 35181150961663, 281462092005375, 2251748274470911, 18014192351838207, 144114363443707903

Offset

1,2

Comments

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

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

Links

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Index entries for linear recurrences with constant coefficients, signature (15,-70,120,-64).

Formula

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

G.f.: 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)=(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})

Maple

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

Mathematica

Table[(2^n - 1)^3, {n, 30}] (* Vincenzo Librandi, Mar 04 2018 *)

Prog

(Magma) [(2^n-1)^3: n in [1..20]]; // Vincenzo Librandi, Mar 04 2018
(PARI) a(n) = (2^n-1)^3; \\ Altug Alkan, Mar 04 2018

Crossrefs

Cf. A060867.

Sequence in context: A226090 A032599 A016839 * A018797 A239220 A133050

Adjacent sequences: A128828 A128829 A128830 * A128832 A128833 A128834

Keyword

easy,nonn

Author

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

Status

approved