A221876 -id:A221876 - cp's OEIS frontend

A221877 Triangle read by rows: T(n,k) = number of order-preserving or order-reversing full contraction mappings (of an n-chain) with height exactly k.

1, 2, 2, 3, 8, 2, 4, 18, 12, 2, 5, 32, 36, 16, 2, 6, 50, 80, 60, 20, 2, 7, 72, 150, 160, 90, 24, 2, 8, 98, 252, 350, 280, 126, 28, 2, 9, 128, 392, 672, 700, 448, 168, 32, 2, 10, 162, 576, 1176, 1512, 1260, 672, 216, 36, 2

Offset: 1

Abdullahi Umar, Feb 28 2013

Row sums are A221882.

			T(3,2) = 8 because there are exactly 8 order-preserving full contraction mappings (of a 3-chain) with exactly height 2, namely: (112), (122), (211), (221), (223), (233), (322), (332).
From _Paolo Xausa_, Aug 18 2025: (Start)
Triangle begins:
   1;
   2,   2;
   3,   8,   2;
   4,  18,  12,    2;
   5,  32,  36,   16,    2;
   6,  50,  80,   60,   20,    2;
   7,  72, 150,  160,   90,   24,   2;
   8,  98, 252,  350,  280,  126,  28,   2;
   9, 128, 392,  672,  700,  448, 168,  32,  2;
  10, 162, 576, 1176, 1512, 1260, 672, 216, 36, 2;
  ... (End)

Paolo Xausa, Table of n, a(n) for n = 1..11325 (rows 1..150 of triangle, flattened).
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

Cf. A221876, A221878, A221879, A221880, A221881, A221882.

A221877[n_, k_] := If[k == 1, n, 2*(n-k+1)*Binomial[n-1, k-1]];
Table[A221877[n, k], {n, 15}, {k, n}] (* Paolo Xausa, Aug 18 2025 *)

T(n,1) = n and T(n,k) = 2(n-k+1)*C(n-1,k-1) if k > 1.

Name edited by Paolo Xausa, Aug 18 2025

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

Original entry on oeis.org

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

Abdullahi Umar, Feb 28 2013

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

			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).

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).

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

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 *)

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

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]

More terms from Joerg Arndt, Mar 01 2013

A228526 Triangle read by rows: T(n,k) = sum of all parts of size k in all compositions (ordered partitions) of n.

Original entry on oeis.org

1, 2, 2, 5, 4, 3, 12, 10, 6, 4, 28, 24, 15, 8, 5, 64, 56, 36, 20, 10, 6, 144, 128, 84, 48, 25, 12, 7, 320, 288, 192, 112, 60, 30, 14, 8, 704, 640, 432, 256, 140, 72, 35, 16, 9, 1536, 1408, 960, 576, 320, 168, 84, 40, 18, 10, 3328, 3072, 2112, 1280, 720

Offset: 1

Omar E. Pol, Aug 28 2013

The equivalent sequence for partitions is A138785, see the first comment there.

			T(4,2) = 10 because there are 5 parts of size 2 in all compositions of 4, T(4,2) = 5*2 = 10 (see below):
---------------------------------------------------------
. Compositions                   Parts      Sum of parts
.     of 4        Diagram      of size 2     of size 2
---------------------------------------------------------
.                 _ _ _ _
.   1+1+1+1      |_| | | |         0             0
.     2+1+1      |_ _| | |         1             2
.     1+2+1      |_|   | |         1             2
.       3+1      |_ _ _| |         0             0
.     1+1+2      |_| |   |         1             2
.       2+2      |_ _|   |         2             4
.       1+3      |_|     |         0             0
.         4      |_ _ _ _|         0             0
.                                -----        ------
.                           Total  5            10
.
Triangle begins:
1;
2,       2;
5,       4,    3;
12,     10,    6,    4;
28,     24,   15,    8,   5;
64,     56,   36,   20,  10,   6;
144,   128,   84,   48,  25,  12,   7;
320,   288,  192,  112,  60,  30,  14,  8;
704,   640,  432,  256, 140,  72,  35, 16,  9;
1536, 1408,  960,  576, 320, 168,  84, 40, 18, 10;
3328, 3072, 2112, 1280, 720, 384, 196, 96, 45, 20, 11;
...

Column k is k*A045623. Row sums give A001787, n >= 1. Right border gives A000027.

Cf. A001792, A011782, A138785, A221876, A228525, A228527.

T(n,k) = k*A045623(n-k) = k*A221876(n,k), n >=1, 1<=k<=n.

A221878 Number of order-preserving or order-reversing full contraction mappings (of an n-chain) with exactly k fixed points.

Original entry on oeis.org

1, 0, 1, 1, 2, 1, 2, 8, 2, 1, 6, 22, 5, 2, 1, 14, 57, 12, 5, 2, 1, 34, 136, 28, 12, 5, 2, 1, 78, 315, 64, 28, 12, 5, 2, 1, 178, 710, 144, 64, 28, 12, 5, 2, 1, 398, 1577, 320, 144, 64, 28, 12, 5, 2, 1, 882, 3460, 704, 320, 144, 64, 28, 12, 5, 2, 1

Offset: 1

Abdullahi Umar, Feb 28 2013

Its row sum is A221882.

			T (4,0) = 6 because there are exactly 6 order-preserving or order-reversing full contraction mappings (of a 4-chain) with no fixed point, namely: (2111), (3321), (3322), (4321), (4322), (4443).
Triangle:
1,
0, 1,
1, 2, 1,
2, 8, 2, 1,
6, 22, 5, 2, 1,
14, 57, 12, 5, 2, 1,
34, 136, 28, 12, 5, 2, 1,
78, 315, 64, 28, 12, 5, 2, 1,
178, 710, 144, 64, 28, 12, 5, 2, 1,
398, 1577, 320, 144, 64, 28, 12, 5, 2, 1,
882, 3460, 704, 320, 144, 64, 28, 12, 5, 2, 1

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

Cf. A221876, A221877, A221879, A221880, A221881, A221882.

T(n,0) = T(n-1,1), T(n,1) = A059570(n) + A221876(n,1) - n and T(n,k) = A221876 if k > 1.

A221879 Triangle T(n,k) read by rows: Number of order-reversing full contraction mappings (of an n-chain) with 1 fixed point and height exactly k.

Original entry on oeis.org

1, 2, 0, 3, 2, 1, 4, 6, 4, 0, 5, 12, 12, 4, 1, 6, 20, 28, 18, 6, 0, 7, 30, 55, 52, 27, 6, 1, 8, 42, 96, 120, 88, 36, 8, 0, 9, 56, 154, 240, 230, 136, 48, 8, 1, 10, 72, 232, 434, 516, 400, 200, 60, 10, 0, 11, 90, 333, 728, 1036, 996, 650, 280, 75, 10, 1

Offset: 1

Abdullahi Umar, Feb 28 2013

Row sums are A059570.

			T (4,6) = 6 because there are exactly 6 order-reversing full contraction mappings (of a 4-chain) with 1 fixed point and of height exactly 2, namely: (3222), (2221), (2211), (4433), (4333), (3332).
Triangle starts:
  1,
  2, 0,
  3, 2, 1,
  4, 6, 4, 0,
  5, 12, 12, 4, 1,
  6, 20, 28, 18, 6, 0,
  7, 30, 55, 52, 27, 6, 1,
  8, 42, 96, 120, 88, 36, 8, 0,
  9, 56, 154, 240, 230, 136, 48, 8, 1,
  10, 72, 232, 434, 516, 400, 200, 60, 10, 0,
  11, 90, 333, 728, 1036, 996, 650, 280, 75, 10, 1
  ...

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

Cf. A059570 (row sums), A221876, A221877, A221878, A221880, A221881, A221882.

A221879 := proc(n,k)
    option remember ;
    if n<1 then
        0 ;
    elif n=1 then
        if k = 1 then
            1;
        else
            0 ;
        end if;
    else
        if n = 2 and k=2 then
            0;
        else
            (n-k+1)*binomial(n-2,k-1)+procname(n-2,k-2) ;
        end if;
    end if;
end proc:
seq(seq( A221879(n,k),k=1..n),n=1..20) ; # R. J. Mathar, Aug 15 2025

T(n, 1) = 1, T(2,2) = 0 and T(n,k) = (n-k+1)*C(n-2,k-1) + T(n-2,k-2) for k > 0.

Sum_{k=1..n} T(n,k) = A059570(n).

A221880 Number of order-preserving or order-reversing full contraction mappings (of an n-chain) with exactly 1 fixed point.

Original entry on oeis.org

1, 2, 8, 22, 57, 136, 315, 710, 1577, 3460, 7527, 16258, 34917, 74624, 158819, 336766, 711777, 1500028, 3152991, 6611834, 13835357, 28894072, 60234843, 125363062, 260512857, 540599156, 1120345175, 2318984050, 4794555477, 9902285680, 20430920787, 42114540398

Offset: 1

Abdullahi Umar, Feb 28 2013

			a(3) = 8 because there are exactly 8 order-preserving or order-reversing full contraction mappings (of a 3-chain) with exactly 1 fixed point, namely: (111), (112), (222), (233), (333), (321), (322), (221).

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 (5,-7,-1,8,-4).

Cf. A221876, A221877, A221878, A221879, A221881, A221882.

a(n) = A221878(n,1).
a(n) = A059570(n) + A221876(n,1) - n.
G.f.: x*(1-3*x+5*x^2-3*x^3-3*x^4+x^5)/((1+x)*(1-3*x+2*x^2)^2). [Bruno Berselli, Mar 01 2013]
a(n) = -n+(2^(n-1)*(21*n+34)-8*(-1)^n)/36 for n>1, a(1)=1. [Bruno Berselli, Mar 01 2013]

More terms from Bruno Berselli, Mar 01 2013

A221881 Number of order-preserving or order-reversing full contraction mappings (of an n-chain) with (right) waist exactly k.

Original entry on oeis.org

1, 1, 3, 1, 5, 7, 1, 7, 13, 15, 1, 9, 21, 29, 31, 1, 11, 31, 51, 61, 63, 1, 13, 43, 83, 113, 125, 127, 1, 15, 57, 127, 197, 239, 253, 255, 1, 17, 73, 185, 325, 437, 493, 509, 511, 1, 19, 91, 259, 511, 763, 931, 1003, 1021, 1023

Offset: 1

Abdullahi Umar, Feb 28 2013

Row sums are A221882.

			T(5,2) = 9 because there are exactly 9 order-preserving or order-reversing full contraction mappings (of a 5-chain) with (right) waist exactly 2, namely: (11112), (11122), (11222), (12222), (21111), (22111), (22211), (22221), (22222).

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

Cf. A221876, A221877, A221878, A221879, A221880, A221882.

T(n,k) = 2*Sum_{p=1..k} C(n-1,p-1) - 1 for k >=1.

A228527 Triangle read by rows: T(n,k) is the sum of all parts of size k of the n-th section of the set of compositions ( ordered partitions) of any integer >= n.

Original entry on oeis.org

1, 1, 2, 3, 2, 3, 7, 6, 3, 4, 16, 14, 9, 4, 5, 36, 32, 21, 12, 5, 6, 80, 72, 48, 28, 15, 6, 7, 176, 160, 108, 64, 35, 18, 7, 8, 384, 352, 240, 144, 80, 42, 21, 8, 9, 832, 768, 528, 320, 180, 96, 49, 24, 9, 10, 1792, 1664, 1152, 704, 400, 216, 112, 56, 27, 10, 11

Offset: 1

Omar E. Pol, Sep 01 2013

In other words, T(n,k) is the sum of all parts of size k of the last section of the set of compositions (ordered partitions) of n.
For the definition of "section of the set of compositions" see A228524.
The equivalent sequence for partitions is A207383.

			Illustration (using the colexicograpical order of compositions A228525) of the four sections of the set of compositions of 4:
.
.            1      2        3          4
.            _      _        _          _
.           |_|   _| |      | |        | |
.                |_ _|   _ _| |        | |
.                       |_|   |        | |
.                       |_ _ _|   _ _ _| |
.                                |_| |   |
.                                |_ _|   |
.                                |_|     |
.                                |_ _ _ _|
.
For n = 4 and k = 2, T(4,2) = 6 because there are 3 parts of size 2 in the last section of the set of compositions of 4, so T(4,2) = 3*2 = 6, see below:
--------------------------------------------------------
.                         The last section      Sum of
.   Composition of 4        of the set of      parts of
.                         compositions of 4     size k
. --------------------   -------------------
.            Diagram             Diagram    k = 1 2 3 4
. ------------------------------------------------------
.            _ _ _ _                    _
.  1+1+1+1  |_| | | |         1        | |      1 0 0 0
.    2+1+1  |_ _| | |         1        | |      1 0 0 0
.    1+2+1  |_|   | |         1        | |      1 0 0 0
.      3+1  |_ _ _| |         1   _ _ _| |      1 0 0 0
.    1+1+2  |_| |   |     1+1+2  |_| |   |      2 2 0 0
.      2+2  |_ _|   |       2+2  |_ _|   |      0 4 0 0
.      1+3  |_|     |       1+3  |_|     |      1 0 3 0
.        4  |_ _ _ _|         4  |_ _ _ _|      0 0 0 4
.                                              ---------
.                      Column sums give row 4:  7,6,3,4
.
Triangle begins:
1;
1,       2;
3,       2,    3;
7,       6,    3,   4;
16,     14,    9,   4,   5;
36,     32,   21,  12,   5,   6;
80,     72,   48,  28,  15,   6,   7;
176,   160,  108,  64,  35,  18,   7,  8;
384,   352,  240, 144,  80,  42,  21,  8,  9;
832,   768,  528, 320, 180,  96,  49, 24,  9, 10;
1792, 1664, 1152, 704, 400, 216, 112, 56, 27, 10, 11;
...

Column 1 is A045891. Row sums give A001792.

Cf. A011782, A135010, A207383, A221876, A228350, A228366, A228370, A228524, A228526.

T(n,k) = k*A045891(n-k) = k*A228524(n,k), n>=1, 1<=k<=n.

A228524 Triangle read by rows: T(n,k) = total number of occurrences of parts k in the n-th section of the set of compositions (ordered partitions) of any integer >= n.

Original entry on oeis.org

1, 1, 1, 3, 1, 1, 7, 3, 1, 1, 16, 7, 3, 1, 1, 36, 16, 7, 3, 1, 1, 80, 36, 16, 7, 3, 1, 1, 176, 80, 36, 16, 7, 3, 1, 1, 384, 176, 80, 36, 16, 7, 3, 1, 1, 832, 384, 176, 80, 36, 16, 7, 3, 1, 1, 1792, 832, 384, 176, 80, 36, 16, 7, 3, 1, 1, 3840, 1792, 832, 384, 176, 80, 36, 16, 7, 3, 1, 1

Offset: 1

Omar E. Pol, Aug 26 2013

Here, define "n-th section of the set of compositions of any integer >= n" to be the set formed by all parts that occur as a result of taking all compositions (ordered partitions) of n and then remove all parts of the compositions of n-1, if n >= 1. Hence the n-th section of the set of compositions of any integer >= n is also the last section of the set of compositions of n. Note that by definition the ordering of compositions is not relevant. For the visualization of the sections here we use a dissection of the diagram of compositions of n in colexicographic order, see example.
The equivalent sequence for partitions is A182703.
Row n lists the first n terms of A045891 in decreasing order.

			Illustration (using the colexicograpical order of compositions A228525) of the four sections of the set of compositions of 4, also the first four sections of the set of compositions of any integer >= 4:
.
.            1      2        3          4
.            _      _        _          _
.           |_|   _| |      | |        | |
.                |_ _|   _ _| |        | |
.                       |_|   |        | |
.                       |_ _ _|   _ _ _| |
.                                |_| |   |
.                                |_ _|   |
.                                |_|     |
.                                |_ _ _ _|
.
For n = 4 and k = 2, T(4,2) = 3 because there are 3 parts of size 2 in all compositions of 4, see below:
--------------------------------------------------------
.                         The last section    Number of
.   Composition of 4        of the set of      parts of
.                         compositions of 4     size k
. --------------------   -------------------
.            Diagram             Diagram    k = 1 2 3 4
. ------------------------------------------------------
.            _ _ _ _                    _
.  1+1+1+1  |_| | | |         1        | |      1 0 0 0
.    2+1+1  |_ _| | |         1        | |      1 0 0 0
.    1+2+1  |_|   | |         1        | |      1 0 0 0
.      3+1  |_ _ _| |         1   _ _ _| |      1 0 0 0
.    1+1+2  |_| |   |     1+1+2  |_| |   |      2 1 0 0
.      2+2  |_ _|   |       2+2  |_ _|   |      0 2 0 0
.      1+3  |_|     |       1+3  |_|     |      1 0 1 0
.        4  |_ _ _ _|         4  |_ _ _ _|      0 0 0 1
.                                              ---------
.                      Column sums give row 4:  7,3,1,1
.
Triangle begins:
1;
1,       1;
3,       1,   1;
7,       3,   1,   1;
16,      7,   3,   1,  1;
36,     16,   7,   3,  1,  1;
80,     36,  16,   7,  3,  1,   1;
176,    80,  36,  16,  7,  3,   1,  1;
384,   176,  80,  36, 16,  7,   3,  1,  1;
832,   384, 176,  80, 36, 16,   7,  3,  1,  1;
1792,  832, 384, 176, 80, 36,  16,  7,  3,  1, 1;
3840, 1792, 832, 384,176, 80,  36, 16,  7,  3, 1, 1;
8192, 3840,1792, 832,384,176,  80, 36, 16,  7, 3, 1, 1;
...

Row sums give A045623. Every column gives A045891.

Cf. A011782, A182703, A221876, A228350, A228366, A228367, A228370, A228526, A228527.

T(n,k) = A045891(n-k), n >= 1, 1<=k<=n.

cp's OEIS Frontend

A221877 Triangle read by rows: T(n,k) = number of order-preserving or order-reversing full contraction mappings (of an n-chain) with height exactly k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A228526 Triangle read by rows: T(n,k) = sum of all parts of size k in all compositions (ordered partitions) of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A221878 Number of order-preserving or order-reversing full contraction mappings (of an n-chain) with exactly k fixed points.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A221879 Triangle T(n,k) read by rows: Number of order-reversing full contraction mappings (of an n-chain) with 1 fixed point and height exactly k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A221880 Number of order-preserving or order-reversing full contraction mappings (of an n-chain) with exactly 1 fixed point.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A221881 Number of order-preserving or order-reversing full contraction mappings (of an n-chain) with (right) waist exactly k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A228527 Triangle read by rows: T(n,k) is the sum of all parts of size k of the n-th section of the set of compositions ( ordered partitions) of any integer >= n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula