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
Examples
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).
Links
- Paolo Xausa, Table of n, a(n) for n = 1..3000
- A. D. Adeshola, V. Maltcev and A. Umar, Combinatorial results for certain semigroups of order-preserving full contraction mappings of a finite chain, arXiv:1303.7428 [math.CO], 2013.
- A. D. Adeshola, A. Umar, Combinatorial results for certain semigroups of order-preserving full contraction mappings of a finite chain, JMCC 106 (2017) 37-49
- Index entries for linear recurrences with constant coefficients, signature (6,-13,12,-4).
Programs
-
Mathematica
A221882[n_] := (n + 1)*2^(n - 1) - n; Array[A221882, 50] (* or *) LinearRecurrence[{6, -13, 12, -4}, {1, 4, 13, 36}, 50] (* Paolo Xausa, Aug 18 2025 *)
-
PARI
a(n)=(n+1)<<(n-1)-n; \\ Charles R Greathouse IV, Feb 28 2013
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).
a(n) = Sum_{k=1..n} A221877(n,k) = Sum_{k=0..n-1} A221878(n,k) = Sum_{k=1..n} A221881(n,k). [Edited by Paolo Xausa, Aug 18 2025]
G.f.: x*(1-2*x+2*x^2-2*x^3)/(1-3*x+2*x^2)^2. [Bruno Berselli, Mar 01 2013]
Extensions
More terms from Joerg Arndt, Mar 01 2013
Comments