login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


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.: (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

a(n) = 1 + A030191(n-1). - R. J. Mathar, Jun 20 2011

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

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

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 5 11:27 EST 2021. Contains 341823 sequences. (Running on oeis4.)