|
|
A221876
|
|
T(n,k) is the number of order-preserving full contraction mappings (of an n-chain) with exactly k fixed points.
|
|
9
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
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
|
|
|
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.
|
|
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.
|
|
MATHEMATICA
|
T[n_, n_] = 1; T[n_, k_] := (n - k + 3)*2^(n - k - 2);
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|