0,2

a(n+1)/2=A000225(n). Binomial transform is A002783. Binomial transform of 2-2*0^n+(-1)^n or 1,1,3,1,3,1,3,1...

Comments from Peter C. Heinig (algorithms(AT)gmx.de), Apr 17 2007: (Start) Number of n-tuples where each entry is chosen from the subsets of {1,2} such that the intersection of all n entries contains exactly one element.

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.

Examples: a(1)=2 because the two tuples of length one are: ({1}) and ({2}).

a(3)=14 because the fourteen tuples of length three are:

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

The image of this set of tuples under the bijection described in the comment is: ({1,2,3},{}), ({},{1,2,3}), ({1,2,3},{1}), ({1,2,3},{2}), ({1,2,3},{3}), ({1},{1,2,3}), ({2},{1,2,3}), ({3},{1,2,3}), ({1,2,3},{1,2}), ({1,2,3},{1,3}), ({1,2,3},{2,3}), ({1,2},{1,2,3}), ({1,3},{1,2,3}), ({2,3},{1,2,3}). Here exactly one entry is {1,..,n}={1,2,3} and the other is a proper subset. (End)

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

a(0)=1, a(1)=2, a(n)=2*a(n-1)+2 for n>1 . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Sep 28 2006

a(n)=Sum_[k, 0<=k<=n}2^k*A123110(n,k) . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Feb 09 2007

Row sums of triangles A131108 and A132046. - Gary W. Adamson (qntmpkt(AT)yahoo.com), Jun 15 2007

ZL := [S, {S=Prod(B, B), B=Set(Z, 1 <= card)}, labeled]: seq(combstruct[count](ZL, size=n), n=1..31); - Zerinvary Lajos, Mar 13 2007

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

Essentially the same as A000918. Cf. A127509, A131108, A132046.

Sequence in context: A009299 A072611 A000918 this_sequence A122958 A122959 A059076

Adjacent sequences: A095118 A095119 A095120 this_sequence A095122 A095123 A095124

easy,nonn

Paul Barry (pbarry(AT)wit.ie), May 28 2004

Edited by njas, Apr 25 2007