|
%I #37 Sep 08 2022 08:45:21
%S 1,2,6,21,76,276,1001,3626,13126,47501,171876,621876,2250001,8140626,
%T 29453126,106562501,385546876,1394921876,5046875001,18259765626,
%U 66064453126,239023437501,864794921876,3128857421876,11320312500001
%N Number of idempotent order-preserving partial transformations (of an n-element chain).
%H Vincenzo Librandi, <a href="/A112091/b112091.txt">Table of n, a(n) for n = 0..1000</a>
%H D. Callan, T. Mansour, <a href="http://arxiv.org/abs/1705.00933">Enumeration of small Wilf classes avoiding 1324 and two other 4-letter patterns</a>, arXiv:1705.00933 [math.CO] (2017), Table 2 No 200 (offset 1 then).
%H Laradji, A. and Umar, <a href="http://dx.doi.org/10.1016/j.jalgebra.2003.10.023">A. Combinatorial results for semigroups of order-preserving partial transformations</a>, Journal of Algebra 278, (2004), 342-359.
%H Laradji, A. and Umar, A. <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Umar/um.html">Combinatorial results for semigroups of order-decreasing partial transformations</a>, J. Integer Seq. 7 (2004), 04.3.8
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (6,-10,5).
%F a(n) = ((sqrt(5))^(n - 1))*(((sqrt(5) + 1)/2)^n - ((sqrt(5) - 1)/2)^n)); a(n) = 1 + 5*(a(n-1) - a(n-2)), a(0) = 1, a(1) = 2.
%F G.f.: (1 - 2*x)^2/((1 - x)*(1 - 5*x + 5*x^2)). Convolution of A081567 with the sequence 1, -1, -1, -1 (-1 continued). - _R. J. Mathar_, Sep 06 2008
%F a(n) = 1 + A030191(n-1). - _R. J. Mathar_, Jun 20 2011
%F a(n) = 6*a(n-1) - 10*a(n-2) + 5*a(n-3); a(0) = 1, a(1) = 2, a(2) = 6. - _Harvey P. Dale_, Aug 20 2011
%F E.g.f.: exp(x) + (exp((5 + sqrt(5))*x/2) - exp((5 - sqrt(5))*x/2))/sqrt(5). - _Franck Maminirina Ramaharo_, Nov 09 2018
%e a(2) = 6 because there are exactly 6 idempotent order-preserving partial transformations (on a 2-element chain), namely: the empty map, (1)->(1), (2)->(2), (1,2)->(1,1), (1,2)->(1,2), (1,2)->(2,2); the mappings are coordinate-wise.
%t RecurrenceTable[{a[0]==1,a[1]==2,a[n]==1+5(a[n-1]-a[n-2])},a[n], {n,30}] (* or *) LinearRecurrence[{6,-10,5},{1,2,6},31] (* _Harvey P. Dale_, Aug 20 2011 *)
%o (Magma) [ n eq 1 select 1 else n eq 2 select 2 else n eq 3 select 6 else 6*Self(n-1)-10*Self(n-2)+ 5*Self(n-3): n in [1..30]]; // _Vincenzo Librandi_, Aug 21 2011
%o (PARI) Vec((2*x-1)^2/(1-x)/(1-5*x+5*x^2)+O(x^99)) \\ _Charles R Greathouse IV_, Aug 21 2011
%K nonn,easy
%O 0,2
%A _Abdullahi Umar_, Aug 25 2008
|
