cp's OEIS Frontend

A128832 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 is empty.

%I A128832 #21 May 15 2019 04:55:02
%S A128832 1,81,2401,50625,923521,15752961,260144641,4228250625,68184176641,
%T A128832 1095222947841,17557851463681,281200199450625,4501401006735361,
%U A128832 72040003462430721,1152780773560811521,18445618199572250625
%N A128832 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 is empty.
%C A128832 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 A128832 Stanley, R. P.: Enumerative Combinatorics: Volume 1: Wadsworth & Brooks: 1986: p. 11
%H A128832 <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (31,-310,1240,-1984,1024).
%F A128832 a(n) = (2^n - 1)^4.
%F A128832 G.f.: -x*(4*x+1)*(16*x^2+46*x+1)/((x-1)*(2*x-1)*(4*x-1)*(8*x-1)*(16*x-1)). [_Colin Barker_, Nov 17 2012]
%e A128832 a(1) = (2^1 - 1)^4 = 1 because only one tuple of length one, namely ({}), has an empty intersection of its sole entry.
%p A128832 for k from 1 to 20 do (2^k-1)^4; od;
%p A128832 with (combinat):seq(mul(stirling2(n,2),k=1..4),n=2..17); # _Zerinvary Lajos_, Dec 16 2007
%t A128832 LinearRecurrence[{31,-310,1240,-1984,1024},{1,81,2401,50625,923521},20] (* _Harvey P. Dale_, Mar 30 2019 *)
%Y A128832 Cf. A000225 (2^n-1), A000583 (n^4).
%K A128832 easy,nonn
%O A128832 1,2
%A A128832 Peter C. Heinig (algorithms(AT)gmx.de), Apr 13 2007