|
| |
|
|
A112091
|
|
Number of idempotent order-preserving partial transformations (of an n-element chain).
|
|
2
| |
|
|
1, 2, 6, 21, 76, 276, 1001, 3626, 13126, 47501, 171876, 621876, 2250001, 8140626, 29453126, 106562501, 385546876, 1394921876, 5046875001, 18259765626, 66064453126, 239023437501, 864794921876, 3128857421876, 11320312500001
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,2
|
|
|
LINKS
| Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Laradji, A. and Umar, A. Combinatorial results for semigroups of order-preserving partial transformations, Journal of Algebra 278, (2004), 342-359.
Laradji, A. and Umar, A. Combinatorial results for semigroups of order-decreasing partial transformations, J. Integer Seq. 7 (2004), 04.3.8
Index to sequences with linear recurrences with constant coefficients, signature (6,-10,5).
|
|
|
FORMULA
| 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
G.f.: (2x-1)^2/((1-x)(1-5x+5x^2)). Convolution of A081567 with the sequence 1,-1,-1,-1 (-1 continued). [From R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Sep 06 2008]
a(n) = 1 +A030191(n-1). - R. J. Mathar, Jun 20 2011
a(0)=1, a(1)=2, a(2)=6, a(n)=6*a(n-1)-10*a(n-2)+5*a(n-3) [From Harvey P. Dale, Aug 20 2011]
|
|
|
EXAMPLE
| 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
|
|
|
MATHEMATICA
| 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] (* From Harvey P. Dale, Aug 20 2011 *)
|
|
|
PROG
| (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
(PARI) Vec((2*x-1)^2/(1-x)/(1-5*x+5*x^2)+O(x^99)) \\ Charles R Greathouse IV, Aug 21 2011
|
|
|
CROSSREFS
| Sequence in context: A116809 A116819 A116782 * A108146 A116798 A116821
Adjacent sequences: A112088 A112089 A112090 * A112092 A112093 A112094
|
|
|
KEYWORD
| nonn,easy
|
|
|
AUTHOR
| A. Umar (aumarh(AT)squ.edu.om), Aug 25 2008
|
|
|
EXTENSIONS
| More terms from Vincenzo Librandi, Aug 21 2011
|
| |
|
|
