|
|
A094374
|
|
a(n) = (3^n-1)/2 + 2^n.
|
|
5
|
|
|
1, 3, 8, 21, 56, 153, 428, 1221, 3536, 10353, 30548, 90621, 269816, 805353, 2407868, 7207221, 21588896, 64701153, 193972388, 581655021, 1744440776, 5232273753, 15694724108, 47079978021, 141231545456, 423677859153, 1271000023028, 3812932960221, 11438664662936
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Let P(A) be the power set of an n-element set A. Then a(n) = the number of pairs of elements {x,y} of P(A) for which either 0) x and y are disjoint and for which either x is a subset of y or y is a subset of x, or 1) x and y are disjoint and for which x is not a subset of y and y is not a subset of x, or 2) x = y. - Ross La Haye, Jan 11 2008
a(n) is the number of words of length n over the alphabet {0,1,2} with an even number of occurrences of the substring 01. - Daimon S. Mayorga, Sep 10 2020
|
|
LINKS
|
|
|
FORMULA
|
G.f.: (1-3x+x^2)/((1-x)*(1-2x)*(1-3x)).
a(n) = 6*a(n-1) - 11*a(n-2) + 6*a(n-3).
a(n) = Sum_{k=0..n} C(n,k)+2^k*C(n,k+1). - Paul Barry, Dec 04 2007
a(n) = StirlingS2(n+1,3) + 2*StirlingS2(n+1,2) + 1. - Ross La Haye, Jan 11 2008
|
|
MATHEMATICA
|
Table[(3^n-1)/2+2^n, {n, 0, 30}] (* or *) LinearRecurrence[{6, -11, 6}, {1, 3, 8}, 30] (* Harvey P. Dale, Jul 22 2013 *)
|
|
PROG
|
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|