OFFSET
0,2
LINKS
Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
Index entries for linear recurrences with constant coefficients, signature (10,-35,50,-24).
FORMULA
a(n) = (1/2)(4^n - 3^n + 2^n + 1) = 3*StirlingS2(n+1,4) + 2*StirlingS2(n+1,3) + StirlingS2(n+1,2) + 1.
a(n) = C(2^n + 1,2) - (1/2)(3^n - 1) = StirlingS2(2^n + 1,2^n) - StirlingS2(n+1,3) - StirlingS2(n+1,2). - Ross La Haye, Jan 21 2008
G.f.: (1-8*x+21*x^2-17*x^3)/((1-x)*(1-2*x)*(1-3*x)*(1-4*x)). - Colin Barker, Jul 30 2012
EXAMPLE
a(2) = 6 because for P(A) = {{},{1},{2},{1,2}} we have for case 1 {{1},{1,2}}, {{2},{1,2}} and we have for case 2 {{},{}}, {{1},{1}}, {{2},{2}}, {{1,2},{1,2}}. There are 0 {x,y} of P(A) in this example that fall under case 0.
MATHEMATICA
LinearRecurrence[{10, -35, 50, -24}, {1, 2, 6, 23}, 30] (* Harvey P. Dale, Jul 04 2023 *)
PROG
(PARI) Vec((1-8*x+21*x^2-17*x^3)/((1-x)*(1-2*x)*(1-3*x)*(1-4*x)) + O(x^30)) \\ Michel Marcus, Oct 30 2015
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Ross La Haye, Jan 11 2008
STATUS
approved