A183155 The number of order-preserving partial isometries (of an n-chain) of fix zero (fix of alpha = 0). Equivalently, the number of order-preserving partial derangement isometries (of an n-chain).

1, 1, 3, 9, 23, 53, 115, 241, 495, 1005, 2027, 4073, 8167, 16357, 32739, 65505, 131039, 262109, 524251, 1048537, 2097111, 4194261, 8388563, 16777169, 33554383, 67108813, 134217675, 268435401, 536870855, 1073741765

Offset

0,3

Comments

a(n) is also the number of dominating sets in the (n+1)-path complement graph. - Eric W. Weisstein, Apr 11 2018

For n > 1, a(n) is the number of integers < 3^(n-1) whose base-3 representation has at most 2 distinct digits. For example, a(4) = 23 counts all base-3 numbers with at most 3 digits except 102, 120, 201, 210. - Lorraine Lee, Sep 01 2025

Links

Table of n, a(n) for n=0..29.

Zachary Hamaker, Eric Marberg, and Brendan Pawlowski, Fixed-point-free involutions and Schur P-positivity, arXiv:1706.06665 [math.CO], 2017.

R. Kehinde and A. Umar, On the semigroup of partial isometries of a finite chain, arXiv:1101.0049 [math.GR], 2010.

Eric Weisstein's World of Mathematics, Dominating Set.

Eric Weisstein's World of Mathematics, Path Complement Graph.

Index entries for linear recurrences with constant coefficients, signature (4,-5,2).

Formula

a(n) = A183154(n,0).

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

a(0)=1; for n > 0, a(n) = 2*a(n-1) + 2*n - 3. - Vincenzo Librandi, Feb 05 2011

G.f.: (-1+3*x-4*x^2)/((2*x-1)*(x-1)^2). - R. J. Mathar, Feb 06 2011

From Elmo R. Oliveira, Mar 07 2025: (Start)

E.g.f.: exp(x)*(2*exp(x) - (1 + 2*x)).

a(n) = 4*a(n-1) - 5*a(n-2) + 2*a(n-3). (End)

Example

a(3) = 9 because there are exactly 9 order-preserving partial derangement isometries (on a 3-chain) , namely: empty map; 1-->2; 1-->3; 2-->1; 2-->3; 3-->1; 3-->2; (1,2)-->(2,3); (2,3)-->(1,2) - the mappings are coordinate-wise.

Mathematica

Table[1 + 2^(1 + n) - 2 (1 + n), {n, 0, 20}] (* or *)
LinearRecurrence[{4, -5, 2}, {1, 3, 9}, {0, 20}] (* or *)
CoefficientList[Series[(-1 + 3 x - 4 x^2)/((-1 + x)^2 (-1 + 2 x)), {x, 0, 20}], x] (* Eric W. Weisstein, Apr 11 2018 *)

Prog

(PARI) a(n) = 2^(n+1)-(2*n+1); \\ Altug Alkan, Apr 12 2018

Crossrefs

Cf. A000918 (first differences), A183154, A244331.

Sequence in context: A263330 A146440 A244331 * A305168 A274099 A147126

Adjacent sequences: A183152 A183153 A183154 * A183156 A183157 A183158

Keyword

nonn,easy

Author

Abdullahi Umar, Dec 28 2010

Status

approved