login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A112091 Number of idempotent order-preserving partial transformations (of an n-element chain). 3
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; text; internal format)
OFFSET

0,2

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

D. Callan, T. Mansour, Enumeration of small Wilf classes avoiding 1324 and two other 4-letter patterns, arXiv:1705.00933 [math.CO] (2017), Table 2 No 200 (offset 1 then).

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 entries for 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, 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). 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] (* 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: A294819 A294820 A116782 * A108146 A116798 A279560

Adjacent sequences:  A112088 A112089 A112090 * A112092 A112093 A112094

KEYWORD

nonn,easy

AUTHOR

Abdullahi Umar, Aug 25 2008

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 12 16:38 EST 2017. Contains 295949 sequences.