|
|
A336246
|
|
Array read by upwards antidiagonals: T(n,k) is the number of ways to place n persons on different seats such that each person number p, 1 <= p <= n, differs from the seat number s(p), 1 <= s(p) <= n+k, k >= 0.
|
|
1
|
|
|
0, 1, 1, 2, 3, 2, 9, 11, 7, 3, 44, 53, 32, 13, 4, 265, 309, 181, 71, 21, 5, 1854, 2119, 1214, 465, 134, 31, 6, 14833, 16687, 9403, 3539, 1001, 227, 43, 7, 133496, 148329, 82508, 30637, 8544, 1909, 356, 57, 8, 1334961, 1468457, 808393, 296967, 81901, 18089, 3333, 527, 73, 9
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
T(n,0) = !n (subfactorial) is the number of derangements or fixed-point-free permutations, see A000166(n) below: n persons are placed on n seats such that no person sits on a seat with the same number. The generalization of a permutation is a variation (n persons and n+k seats such that k seats remain free). In this sense, T(n,k) is the number of fixed-point-free variations. I am rather sure that such variations have been examined, but I cannot find a reference.
Some subsequences T(n,k) with k=const:
|
|
LINKS
|
|
|
FORMULA
|
T(n,k) = (n+k-1)*T(n-1,k) + (n-1)*T(n-2,k) for n >= 2, k >= 0 with T(0,k)=1 and T(1,k)=k.
For n=0, there is one empty variation. T(0,k) is used for the recurrence only, not in the table. For n=1, the person can be placed on seat number 2..k+1 (if k > 0).
You also find the recurrence in the formula section of A000166 (k=0) and in the name section of the other sequences listed above (1 <= k <= 10). Some sequences have a different offset.
T(n,k) = Sum_{r=0..n} (-1)^r*binomial(n,r)*(n+k-r)!/k!.
Proofs see link.
|
|
EXAMPLE
|
For k=1, the n-tuples of seat numbers are:
- for n=1: 2 => T(1,1) = 1.
- for n=2: 21, 23, 31 => T(2,1) = 3,
21: person 1 sits on seat 2 and vice versa.
A counterexample is 13 because person 1 would sit on seat 1.
- for n=3: 214,231,234,241,312,314,341,342,412,431,432 => T(3,1) = 11.
Array begins:
0 1 2 3 4 ...
1 3 7 13 21 ...
2 11 32 71 134 ...
9 53 181 465 1001 ...
44 309 1214 3539 8544 ...
.. ... .... .... ....
|
|
PROG
|
(Maxima)
block(nr: 0, k: -1, mmax: 55,
/*First mmax terms are returned, recurrence used*/
a: makelist(0, n, 1, mmax),
while nr<mmax do
(v1:1, k: k+1, n:0, m: (k+1)*(k+2)/2,
while m<=mmax do (n:n+1,
if n=1 then v2: k else (v2: (n+k-1)*v1+(n-1)*v0, m: m+n+k-1),
if m<=mmax then (a[m]: v2, nr: nr+1, v0: v1, v1: v2))),
return(a));
(Maxima)
block(n: 1, k: 0, mmax: 55,
/*First mmax terms are returned, explicit formula used*/
a: makelist(0, n, 1, mmax),
for m from 1 thru mmax do (su: 0,
for r from 0 thru n do su: su+(-1)^r*binomial(n, r)*(n+k-r)!/k!,
a[m]: su, if n=1 then (n: k+2, k: 0) else (n: n-1, k: k+1)),
return(a));
|
|
CROSSREFS
|
Cf. A000166, A000255, A000153, A000261, A001909, A001910, A176732, A176733, A176734, A176735, A176736.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|