login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 1
3, 27, 147, 675, 2883, 11907, 48387, 195075, 783363, 3139587, 12570627, 50307075, 201277443, 805208067, 3221028867, 12884508675, 51538821123, 206156857347, 824630575107, 3298528591875, 13194126950403, 52776532967427 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

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.

LINKS

Table of n, a(n) for n=1..22.

FORMULA

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

G.f.: 3*x*(1+2*x)/(1-7*x+14*x^2-8*x^3). [Colin Barker, Feb 08 2012]

EXAMPLE

a(1)=3 because the three sequences of length one are: ({1}), ({2}), ({3}).

a(2)=27 because the twenty-seven sequences of length two are:

({1},{1}), ({2},{2}), ({3},{3}), ({1},{1,2}),

({1},{1,3}), ({2},{1,2}), ({2},{2,3}), ({3},{1,3}),

({3},{2,3}), ({1,2},{1}), ({1,3},{1}), ({1,2},{2}),

({2,3},{2}), ({1,3},{3}), ({2,3},{3}), ({1},{1,2,3}),

({2},{1,2,3}), ({3},{1,2,3}), ({1,2,3},{1}), ({1,2,3},{2}),

({1,2,3},{3}), ({1,2},{1,3}), ({1,3},{1,2}), ({1,2},{2,3}),

({2,3},{1,2}), ({1,3},{2,3}), ({2,3},{1,3}).

MAPLE

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

CROSSREFS

Cf. A128831, A128832, A128833, A095121.

Sequence in context: A285008 A001796 A174613 * A108142 A056263 A026093

Adjacent sequences:  A127506 A127507 A127508 * A127510 A127511 A127512

KEYWORD

nonn

AUTHOR

Peter C. Heinig (algorithms(AT)gmx.de), Apr 17 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 July 19 12:35 EDT 2019. Contains 325159 sequences. (Running on oeis4.)