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,2

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

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

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.

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

Example

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

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

Crossrefs

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

Sequence in context: A105084 A375100 A126125 * A128514 A323953 A126075

Adjacent sequences: A221873 A221874 A221875 * A221877 A221878 A221879

Keyword

nonn,easy,tabl

Author

Abdullahi Umar, Feb 28 2013

Status

approved