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,1

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]

Links

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

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).

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

Example

a(8) = 18916.

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 *)

Prog

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

Crossrefs

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

Sequence in context: A282393 A034514 A263851 * A168583 A092688 A267466

Adjacent sequences: A126641 A126642 A126643 * A126645 A126646 A126647

Keyword

nonn,easy

Author

Aleksandar M. Janjic and Milan Janjic, Feb 08 2007

Extensions

New name from Hugo Pfoertner, Nov 22 2022

Status

approved