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

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, 320, 144, 64, 28, 12, 5, 2, 1, 704, 320, 144, 64, 28, 12, 5, 2, 1, 1536, 704, 320, 144, 64, 28, 12, 5, 2, 1, 3328, 1536, 704, 320, 144, 64, 28, 12, 5, 2, 1

Offset: 1

Author

Abdullahi Umar, Feb 28 2013

Keywords

• nonn
• easy
• tabl

Comments

Row sum is A001792(n-1).

The matrix inverse starts

1;

-2,1;

-1,-2,1;

0,-1,-2,1;

1,0,-1,-2,1;

2,1,0,-1,-2,1;

3,2,1,0,-1,-2,1;

4,3,2,1,0,-1,-2,1;

5,4,3,2,1,0,-1,-2,1;

6,5,4,3,2,1,0,-1,-2,1;

7,6,5,4,3,2,1,0,-1,-2,1; - R. J. Mathar, Apr 12 2013

...

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

Examples

			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).
Triangle begins:
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,
320, 144, 64, 28, 12, 5, 2, 1,
704, 320, 144, 64, 28, 12, 5, 2, 1,
1536, 704, 320, 144, 64, 28, 12, 5, 2, 1,
3328, 1536, 704, 320, 144, 64, 28, 12, 5, 2, 1,
...
Note that column k is column 1 shifted down by k positions.
Row 4 is [12, 5, 2, 1]: in the compositions of 4
[ 1]  [ 1 1 1 1 ]
[ 2]  [ 1 1 2 ]
[ 3]  [ 1 2 1 ]
[ 4]  [ 1 3 ]
[ 5]  [ 2 1 1 ]
[ 6]  [ 2 2 ]
[ 7]  [ 3 1 ]
[ 8]  [ 4 ]
there are 12 parts=1, 5 parts=2, 2 part=3, and 1 part=4.
- _Joerg Arndt_, Sep 01 2013
		

Links

• 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

Crossrefs

Cf. A001792, A221877, A221878, A221879, A221880, A221881, A221882.

Programs

Mathematica

T[n_, n_] = 1; T[n_, k_] := (n - k + 3)*2^(n - k - 2);
Table[T[n, k], {n, 1, 11}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jul 21 2018 *)

Formula

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

T(2*n+1,n+1) = T(n+1,1) = A045623(n) for n>=0.

T(n,k) = A045623(n-k), n>=1, 1<=k<=n. - Omar E. Pol, Sep 01 2013