login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 3
1, 27, 343, 3375, 29791, 250047, 2048383, 16581375, 133432831, 1070599167, 8577357823, 68669157375, 549554511871, 4397241253887, 35181150961663, 281462092005375, 2251748274470911, 18014192351838207, 144114363443707903 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 17 03:42 EDT 2021. Contains 347478 sequences. (Running on oeis4.)