The OEIS is supported by the many generous donors to the OEIS Foundation.

 Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 60th year, we have over 367,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”). Other ways to Give
 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A128833 Number of n-tuples where each entry is chosen from the subsets of {1,2,3,4,5} such that the intersection of all n entries is empty. 2

%I #14 Aug 16 2021 15:31:33

%S 1,243,16807,759375,28629151,992436543,33038369407,1078203909375,

%T 34842114263551,1120413075641343,35940921946155007,

%U 1151514816750309375,36870975646169341951,1180231376725002502143,37773167607267111108607

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

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

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

%H Harvey P. Dale, <a href="/A128833/b128833.txt">Table of n, a(n) for n = 1..664</a>

%H <a href="/index/Rec">Index entries for linear recurrences with constant coefficients</a>, signature (63,-1302,11160,-41664,64512,-32768).

%F a(n)=(2^n-1)^5

%F G.f.: x*(1024*x^4+5760*x^3+2800*x^2+180*x+1)/((x-1)*(2*x-1)*(4*x-1)*(8*x-1)*(16*x-1)*(32*x-1)). [_Colin Barker_, Nov 17 2012]

%e a(1)=(2^1-1)^5=1 because only one tuple of length one, namely ({}) has an empty intersection of its sole entry.

%p for k from 1 to 20 do (2^k-1)^5; od;

%t (2^Range[20]-1)^5 (* or *) LinearRecurrence[{63,-1302,11160,-41664,64512,-32768},{1,243,16807,759375,28629151,992436543},20] (* or *) CoefficientList[Series[x (1024x^4+5760x^3+2800x^2+180x+1)/((x-1)(2x-1)(4x-1)(8x-1)(16x-1)(32x-1)),{x,0,20}],x] (* _Harvey P. Dale_, Aug 16 2021 *)

%Y Cf. A060867.

%K easy,nonn

%O 1,2

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

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

Last modified December 3 18:38 EST 2023. Contains 367540 sequences. (Running on oeis4.)