A183156 The number T(n) of isometries of all subspaces of the finite metric space {1,2,...,n} (as a subspace of the reals with the Euclidean metric).

1, 2, 7, 22, 59, 142, 319, 686, 1435, 2950, 5999, 12118, 24379, 48926, 98047, 196318, 392891, 786070, 1572463, 3145286, 6290971, 12582382, 25165247, 50331022, 100662619, 201325862, 402652399, 805305526, 1610611835, 3221224510, 6442449919, 12884900798

Offset: 0

Author

Abdullahi Umar, Dec 28 2010

Keywords

• nonn

Comments

Also the number of (not necessarily maximal) cliques in the n X n bishop graph. - Eric W. Weisstein, Jun 04 2017

Examples

			T(2) = 7 because there are exactly 7 partial isometries (on a 2-chain), namely: empty map; 1-->1; 1-->2; 2-->1; 2-->2; (1,2)-->(1,2); (1,2)-->(2,1) - the mappings are coordinate-wise.
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• R. Kehinde and A. Umar, On the semigroup of partial isometries of a finite chain, arXiv:1101.2558 [math.GR], 2011.
• Eric Weisstein's World of Mathematics, Bishop Graph
• Eric Weisstein's World of Mathematics, Clique
• Index entries for linear recurrences with constant coefficients, signature (5,-9,7,-2).

Crossrefs

Row sums of triangles A183157, A183158.

Cf. A295909 (cliques in the n X n black bishop graph).

Cf. A295910 (cliques in the n X n white bishop graph).

Programs

Magma

[3*2^(n+1)-(n+2)^2-1: n in [0..33]]; // Vincenzo Librandi, Oct 11 2017

Mathematica

LinearRecurrence[{5, -9, 7, -2}, {1, 2, 7, 22}, 40] (* Vincenzo Librandi, Oct 11 2017 *)
Table[3 2^(n + 1) - (n + 2)^2 - 1, {n, 0, 30}] (* Vincenzo Librandi, Oct 11 2017 *)
LinearRecurrence[{5, -9, 7, -2}, {2, 7, 22, 59}, {0, 20}] (* Eric W. Weisstein, Nov 29 2017 *)
CoefficientList[Series[(1 - 3 x + 6 x^2 - 2 x^3)/((-1 + x)^3 (-1 + 2 x)), {x, 0, 20}], x] (* Eric W. Weisstein, Nov 29 2017 *)

PARI

for(n=0,33,print1(3*(2^(n+1))-(n+2)^2-1,", "))

Formula

T(n) = 3*2^(n+1) - (n+2)^2 - 1, (n >= 0).

G.f.: (1 - 3*x + 6*x^2 - 2*x^3) / ( (2*x - 1)*(x - 1)^3 ). - R. J. Mathar, Jul 03 2011

a(n) = 5*a(n-1) - 9*a(n-2) + 7*a(n-3) - 2*a(n-4). - Eric W. Weisstein, Nov 29 2017

a(n) = A295909(n) + A295910(n) for n > 1. - Eric W. Weisstein, Nov 29 2017

a(n) = 2*a(n-1) + n^2 - 1. - Kritsada Moomuang, Oct 25 2019

Extensions

Renamed the sequence using more standard and widely-used terminology, James Mitchell, May 19 2012