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

4, 16, 58, 196, 634, 1996, 6178, 18916, 57514, 174076, 525298, 1582036, 4758394, 14299756, 42948418, 128943556, 387027274, 1161475036, 3485211538, 10457207476, 31374768154, 94130595916, 282404370658, 847238277796

Offset: 1

Author

Aleksandar M. Janjic and Milan Janjic, Feb 08 2007

Keywords

• nonn
• easy

Comments

Previous name was: a(n) is the number of integers k less than 10^n such that the decimal representation of k lacks the digits 1,2,3,4,5,6 and at least one of digits 7,8,9.

Let P(A) be the power set of an n-element set A and R be a relation on P(A) such that for all x, y of P(A), xRy if either 0) x is a proper subset of y or y is a proper subset of x, 1) x is not a subset of y and y is not a subset of x and x and y are disjoint, or 2) x equals y. Then a(n) = |R|. [Ross La Haye, Mar 19 2009]

Examples

			a(8) = 18916.
		

Links

• Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets
• 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 (6,-11,6).

Crossrefs

Cf. A001047, A125630, A125948, A125947, A125946, A125945, A125940, A125909, A125908, A125880, A125897, A125904, A125858.

Programs

Maple

f:=n->3*3^n-3*2^n+1;

Mathematica

LinearRecurrence[{6,-11,6},{4,16,58},30] (* Harvey P. Dale, Sep 14 2018 *)

PARI

a(n) = 3*3^n - 3*2^n + 1; \\ Michel Marcus, Nov 30 2015

Formula

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

a(n) = 6*a(n-1)-11*a(n-2)+6*a(n-3). G.f.: -2*x*(3*x^2-4*x+2) / ((x-1)*(2*x-1)*(3*x-1)). [Colin Barker, Dec 10 2012]

a(n) = 3*A001047(n) + 1. - Hugo Pfoertner, Nov 22 2022

Extensions

New name from Hugo Pfoertner, Nov 22 2022