cp's OEIS Frontend

A221876 T(n,k) is the number of order-preserving full contraction mappings (of an n-chain) with exactly k fixed points.

%I A221876 #50 Aug 15 2025 04:58:06
%S A221876 1,2,1,5,2,1,12,5,2,1,28,12,5,2,1,64,28,12,5,2,1,144,64,28,12,5,2,1,
%T A221876 320,144,64,28,12,5,2,1,704,320,144,64,28,12,5,2,1,1536,704,320,144,
%U A221876 64,28,12,5,2,1,3328,1536,704,320,144,64,28,12,5,2,1
%N A221876 T(n,k) is the number of order-preserving full contraction mappings (of an n-chain) with exactly k fixed points.
%C A221876 Row sum is A001792(n-1).
%C A221876 The matrix inverse starts
%C A221876 1;
%C A221876 -2,1;
%C A221876 -1,-2,1;
%C A221876 0,-1,-2,1;
%C A221876 1,0,-1,-2,1;
%C A221876 2,1,0,-1,-2,1;
%C A221876 3,2,1,0,-1,-2,1;
%C A221876 4,3,2,1,0,-1,-2,1;
%C A221876 5,4,3,2,1,0,-1,-2,1;
%C A221876 6,5,4,3,2,1,0,-1,-2,1;
%C A221876 7,6,5,4,3,2,1,0,-1,-2,1; - _R. J. Mathar_, Apr 12 2013
%C A221876 ...
%C A221876 T(n,k) is also the total number of occurrences of parts k in all compositions (ordered partitions) of n, see example. The equivalent sequence for partitions is A066633. _Omar E. Pol_, Aug 26 2013
%H A221876 A. D. Adeshola, V. Maltcev and A. Umar, <a href="http://arxiv.org/abs/1303.7428">Combinatorial results for certain semigroups of order-preserving full contraction mappings of a finite chain</a>, arXiv:1303.7428 [math.CO], 2013.
%H A221876 A. D. Adeshola, A. Umar, <a href="https://combinatorialpress.com/jcmcc/vol106/">Combinatorial results for certain semigroups of order-preserving full contraction mappings of a finite chain</a>, JMCC 106 (2017) 37-49
%F A221876 T(n,n) = 1, T(n,k) = (n-k+3)*2^(n-k-2) for n>=2 and n > k > 0.
%F A221876 T(2*n+1,n+1) = T(n+1,1) = A045623(n) for n>=0.
%F A221876 T(n,k) = A045623(n-k), n>=1, 1<=k<=n. - _Omar E. Pol_, Sep 01 2013
%e A221876 T(5,3) = 5 because there are exactly 5 order-preserving full contraction mappings (of a 5-chain) with exactly 3 fixed points, namely: (12333), (12334), (22344), (23345), (33345).
%e A221876 Triangle begins:
%e A221876 1,
%e A221876 2, 1,
%e A221876 5, 2, 1,
%e A221876 12, 5, 2, 1,
%e A221876 28, 12, 5, 2, 1,
%e A221876 64, 28, 12, 5, 2, 1,
%e A221876 144, 64, 28, 12, 5, 2, 1,
%e A221876 320, 144, 64, 28, 12, 5, 2, 1,
%e A221876 704, 320, 144, 64, 28, 12, 5, 2, 1,
%e A221876 1536, 704, 320, 144, 64, 28, 12, 5, 2, 1,
%e A221876 3328, 1536, 704, 320, 144, 64, 28, 12, 5, 2, 1,
%e A221876 ...
%e A221876 Note that column k is column 1 shifted down by k positions.
%e A221876 Row 4 is [12, 5, 2, 1]: in the compositions of 4
%e A221876 [ 1]  [ 1 1 1 1 ]
%e A221876 [ 2]  [ 1 1 2 ]
%e A221876 [ 3]  [ 1 2 1 ]
%e A221876 [ 4]  [ 1 3 ]
%e A221876 [ 5]  [ 2 1 1 ]
%e A221876 [ 6]  [ 2 2 ]
%e A221876 [ 7]  [ 3 1 ]
%e A221876 [ 8]  [ 4 ]
%e A221876 there are 12 parts=1, 5 parts=2, 2 part=3, and 1 part=4.
%e A221876 - _Joerg Arndt_, Sep 01 2013
%t A221876 T[n_, n_] = 1; T[n_, k_] := (n - k + 3)*2^(n - k - 2);
%t A221876 Table[T[n, k], {n, 1, 11}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Jul 21 2018 *)
%Y A221876 Cf. A001792, A221877, A221878, A221879, A221880, A221881, A221882.
%K A221876 nonn,easy,tabl
%O A221876 1,2
%A A221876 _Abdullahi Umar_, Feb 28 2013