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

Links

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

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

R. Kehinde, 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

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. A183154, A000918 (first differences).

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