A221882 Number of order-preserving or order-reversing full contraction mappings of an n-chain.

1, 4, 13, 36, 91, 218, 505, 1144, 2551, 5622, 12277, 26612, 57331, 122866, 262129, 557040, 1179631, 2490350, 5242861, 11010028, 23068651, 48234474, 100663273, 209715176, 436207591, 905969638, 1879048165, 3892314084, 8053063651, 16642998242, 34359738337

Offset

1,2

Comments

a(n) = Sum A221877(n,k) = Sum A221878(n,k) = Sum A221881(n,k).

a(n) is also the order of the semigroup (monoid) of order-preserving or order-reversing full contraction mappings (of an n-chain).

References

A. D. Adeshola, V. Maltcev, and A. Umar, Combinatorial results for certain semigroups of order-preserving full contraction mappings of a finite chain, (submitted 2013).

Links

Table of n, a(n) for n=1..31.

Index entries for linear recurrences with constant coefficients, signature (6,-13,12,-4).

Formula

a(n) = (n+1)*2^(n-1) - n.

a(n) = +6*a(n-1) -13*a(n-2) +12*a(n-3) -4*a(n-4).

G.f.: x*(1-2*x+2*x^2-2*x^3)/(1-3*x+2*x^2)^2. [Bruno Berselli, Mar 01 2013]

Example

a(3) = 13 because there are exactly 13 order-preserving or order-reversing full contraction mappings of a 3-chain, namely: (111), (112), (211), (122), (221), (123), (321), (222), (223), (233), (322), (332), (333).

Prog

(PARI) a(n)=(n+1)<<(n-1)-n; \\ Charles R Greathouse IV, Feb 28 2013

Crossrefs

Cf. A045992, A221876, A221877, A221878, A221880, A221881.

Sequence in context: A350642 A079922 A053563 * A235996 A036636 A036643

Adjacent sequences: A221879 A221880 A221881 * A221883 A221884 A221885

Keyword

nonn,easy

Author

Abdullahi Umar, Feb 28 2013

Extensions

More terms from Joerg Arndt, Mar 01 2013

Status

approved