cp's OEIS Frontend

A127509 Number of n-tuples where each entry is chosen from the subsets of {1,2,3} such that the intersection of all n entries contains exactly one element.

%I A127509 #15 Jan 02 2025 14:53:37
%S A127509 3,27,147,675,2883,11907,48387,195075,783363,3139587,12570627,
%T A127509 50307075,201277443,805208067,3221028867,12884508675,51538821123,
%U A127509 206156857347,824630575107,3298528591875,13194126950403,52776532967427
%N A127509 Number of n-tuples where each entry is chosen from the subsets of {1,2,3} such that the intersection of all n entries contains exactly one element.
%C A127509 There is the following general formula: The number T(n,k,r) of n-tuples where each entry is chosen from the subsets of {1,2,..,k} such that the intersection of all n entries contains exactly r elements is: T(n,k,r) = C(k,r) * (2^n - 1)^(k-r). This may be shown by exhibiting a bijection to a set whose cardinality is obviously C(k,r) * (2^n - 1)^(k-r), namely the set of all k-tuples where each entry is chosen from subsets of {1,..,n} in the following way: Exactly r entries must be {1,..,n} itself (there are C(k,r) ways to choose them) and the remaining (k-r) entries must be chosen from the 2^n-1 proper subsets of {1,..,n}, i.e. for each of the (k-r) entries, {1,..,n} is forbidden (there are, independent of the choice of the full entries, (2^n - 1)^(k-r) possibilities to do that, hence the formula). The bijection into this set 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.
%H A127509 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (7,-14,8).
%F A127509 a(n) = 3*(2^n-1)^2.
%F A127509 G.f.: 3*x*(1+2*x)/(1-7*x+14*x^2-8*x^3). [_Colin Barker_, Feb 08 2012]
%e A127509 a(1)=3 because the three sequences of length one are: ({1}), ({2}), ({3}).
%e A127509 a(2)=27 because the twenty-seven sequences of length two are:
%e A127509   ({1},{1}), ({2},{2}), ({3},{3}), ({1},{1,2}),
%e A127509   ({1},{1,3}), ({2},{1,2}), ({2},{2,3}), ({3},{1,3}),
%e A127509   ({3},{2,3}), ({1,2},{1}), ({1,3},{1}), ({1,2},{2}),
%e A127509   ({2,3},{2}), ({1,3},{3}), ({2,3},{3}), ({1},{1,2,3}),
%e A127509   ({2},{1,2,3}), ({3},{1,2,3}), ({1,2,3},{1}), ({1,2,3},{2}),
%e A127509   ({1,2,3},{3}), ({1,2},{1,3}), ({1,3},{1,2}), ({1,2},{2,3}),
%e A127509   ({2,3},{1,2}), ({1,3},{2,3}), ({2,3},{1,3}).
%p A127509 for k from 1 to 41 do 3*(2^k-1)^2; od;
%t A127509 LinearRecurrence[{7,-14,8},{3,27,147},22] (* _James C. McMahon_, Jan 02 2025 *)
%Y A127509 Cf. A128831, A128832, A128833, A095121.
%K A127509 nonn
%O A127509 1,1
%A A127509 Peter C. Heinig (algorithms(AT)gmx.de), Apr 17 2007