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
Examples
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.
Links
- 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).
Programs
-
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 *) -
PARI
a(n) = 2^(n+1)-(2*n+1); \\ Altug Alkan, Apr 12 2018
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)
Comments