A221880 Number of order-preserving or order-reversing full contraction mappings (of an n-chain) with exactly 1 fixed point.
1, 2, 8, 22, 57, 136, 315, 710, 1577, 3460, 7527, 16258, 34917, 74624, 158819, 336766, 711777, 1500028, 3152991, 6611834, 13835357, 28894072, 60234843, 125363062, 260512857, 540599156, 1120345175, 2318984050, 4794555477, 9902285680, 20430920787, 42114540398
Offset: 1
Examples
a(3) = 8 because there are exactly 8 order-preserving or order-reversing full contraction mappings (of a 3-chain) with exactly 1 fixed point, namely: (111), (112), (222), (233), (333), (321), (322), (221).
Links
- A. D. Adeshola, V. Maltcev and A. Umar, Combinatorial results for certain semigroups of order-preserving full contraction mappings of a finite chain, arXiv:1303.7428 [math.CO], 2013.
- A. D. Adeshola, A. Umar, Combinatorial results for certain semigroups of order-preserving full contraction mappings of a finite chain, JMCC 106 (2017) 37-49
- Index entries for linear recurrences with constant coefficients, signature (5,-7,-1,8,-4).
Formula
a(n) = A221878(n,1).
G.f.: x*(1-3*x+5*x^2-3*x^3-3*x^4+x^5)/((1+x)*(1-3*x+2*x^2)^2). [Bruno Berselli, Mar 01 2013]
a(n) = -n+(2^(n-1)*(21*n+34)-8*(-1)^n)/36 for n>1, a(1)=1. [Bruno Berselli, Mar 01 2013]
Extensions
More terms from Bruno Berselli, Mar 01 2013