cp's OEIS Frontend

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.

%I A336246 #53 Sep 30 2021 04:24:57
%S A336246 0,1,1,2,3,2,9,11,7,3,44,53,32,13,4,265,309,181,71,21,5,1854,2119,
%T A336246 1214,465,134,31,6,14833,16687,9403,3539,1001,227,43,7,133496,148329,
%U A336246 82508,30637,8544,1909,356,57,8,1334961,1468457,808393,296967,81901,18089,3333,527,73,9
%N 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.
%C A336246 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.
%C A336246 Some subsequences T(n,k) with k=const:
%C A336246 T(n,0) = A000166(n);   T(n,1) = A000255(n);   T(n,2) = A000153(n-1);
%C A336246 T(n,3) = A000261(n-1); T(n,4) = A001909(n-3); T(n,5) = A001910(n-4);
%C A336246 T(n,6) = A176732(n);   T(n,7) = A176733(n);   T(n,8) = A176734(n);
%C A336246 T(n,9) = A176735(n);   T(n,10) = A176736(n).
%H A336246 Gerhard Kirchner, <a href="/A336246/a336246.pdf">Fixed-point-free variations</a>
%F A336246 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.
%F A336246 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).
%F A336246 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.
%F A336246 T(n,k) = Sum_{r=0..n} (-1)^r*binomial(n,r)*(n+k-r)!/k!.
%F A336246 Proofs see link.
%e A336246 For k=1, the n-tuples of seat numbers are:
%e A336246 - for n=1: 2 => T(1,1) = 1.
%e A336246 - for n=2: 21, 23, 31 => T(2,1) = 3,
%e A336246      21: person 1 sits on seat 2 and vice versa.
%e A336246      A counterexample is 13 because person 1 would sit on seat 1.
%e A336246 - for n=3: 214,231,234,241,312,314,341,342,412,431,432 => T(3,1) = 11.
%e A336246 Array begins:
%e A336246    0   1    2    3    4 ...
%e A336246    1   3    7   13   21 ...
%e A336246    2  11   32   71  134 ...
%e A336246    9  53  181  465 1001 ...
%e A336246   44 309 1214 3539 8544 ...
%e A336246   .. ... .... .... ....
%o A336246 (Maxima)
%o A336246 block(nr: 0, k: -1,  mmax: 55,
%o A336246     /*First mmax terms are returned, recurrence used*/
%o A336246    a: makelist(0, n, 1, mmax),
%o A336246    while nr<mmax do
%o A336246      (v1:1, k: k+1, n:0, m: (k+1)*(k+2)/2,
%o A336246       while m<=mmax do (n:n+1,
%o A336246        if n=1 then v2: k else (v2: (n+k-1)*v1+(n-1)*v0, m: m+n+k-1),
%o A336246        if m<=mmax then (a[m]: v2, nr: nr+1, v0: v1, v1: v2))),
%o A336246   return(a));
%o A336246 (Maxima)
%o A336246 block(n: 1, k: 0,  mmax: 55,
%o A336246     /*First mmax terms are returned, explicit formula used*/
%o A336246    a: makelist(0, n, 1, mmax),
%o A336246    for m from 1 thru mmax do (su: 0,
%o A336246      for r from 0 thru n do su: su+(-1)^r*binomial(n,r)*(n+k-r)!/k!,
%o A336246      a[m]: su, if n=1 then (n: k+2, k: 0) else (n: n-1, k: k+1)),
%o A336246   return(a));
%Y A336246 Cf. A000166, A000255, A000153, A000261, A001909, A001910, A176732, A176733, A176734, A176735, A176736.
%K A336246 nonn,tabl
%O A336246 1,4
%A A336246 _Gerhard Kirchner_, Jul 19 2020