|
| |
|
|
A161129
|
|
Triangle read by rows: T(n,k) is the number of non-derangements of {1,2,...,n} for which the difference between the largest and smallest fix points is k (n>=1; 0<=k<=n-1).
|
|
1
|
|
|
|
1, 0, 1, 3, 0, 1, 8, 3, 2, 2, 45, 8, 9, 8, 6, 264, 45, 44, 42, 36, 24, 1855, 264, 265, 256, 234, 192, 120, 14832, 1855, 1854, 1810, 1704, 1512, 1200, 720, 133497, 14832, 14833, 14568, 13950, 12864, 11160, 8640, 5040, 1334960, 133497, 133496, 131642, 127404
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
Row sums give the number of non-derangement permutations of {1,2,...,n} (A002467).
T(n,0)=A000240(n)=number of permutations of {1,2,...,n} with exactly 1 fixed point.
T(n,1)=A000240(n-1).
T(n,2)=A000166(n-1) (the derangement numbers).
T(n,3)=A018934(n-1).
Sum(k*T(n,k),k=0..n-1)=A161130(n).
|
|
|
REFERENCES
|
E. Deutsch and S. Elizalde, The largest and the smallest fixed points of permutations, arXiv:0904.2792v1, 2009.
|
|
|
LINKS
|
Table of n, a(n) for n=1..50.
|
|
|
FORMULA
|
T(n,0)=n*d(n-1); T(n,k) = (n-k)*Sum(d(n-2-j)*binom(k-1,j), j=0..k-1) for 1<=k<=n-1, where d(i)=A000166(i) are the derangement numbers.
|
|
|
EXAMPLE
|
T(4,1)=3 because we have 1243, 4231, and 2134; T(4,2)=2 because we have 1432 and 3214; T(5,4)=6 because we have 1xyz5 where xyz is any permutation of 234.
Triangle starts:
1;
0,1;
3,0,1;
8,3,0,1;
45,8,9,8,6;
264,45,44,42,36,24;
|
|
|
MAPLE
|
d[0] := 1: for n to 15 do d[n] := n*d[n-1]+(-1)^n end do: T := proc (n, k) if k = 0 then n*d[n-1] elif k < n then (n-k)*(sum(binomial(k-1, j)*d[n-2-j], j = 0 .. k-1)) else 0 end if end proc: for n to 10 do seq(T(n, k), k = 0 .. n-1) end do; # yields sequence in triangular form
|
|
|
CROSSREFS
|
A002467, A000240, A000166, A018934, A161130
Sequence in context: A216806 A172249 A208758 * A011074 A020816 A174860
Adjacent sequences: A161126 A161127 A161128 * A161130 A161131 A161132
|
|
|
KEYWORD
|
nonn,tabl
|
|
|
AUTHOR
|
Emeric Deutsch, Jul 18 2009
|
|
|
STATUS
|
approved
|
| |
|
|
