A335391 Square array read by antidiagonals downwards: for n >= 2, T(k,n) is the number of permutations of [k+n] that differ in every position from both the identity permutation and a permutation consisting of k 1-cycles and one n-cycle.

2, -1, 0, 0, 1, 2, 1, 0, 1, 4, 2, 3, 4, 7, 18, 13, 16, 19, 24, 35, 88, 80, 95, 114, 137, 168, 221, 530, 579, 672, 783, 916, 1077, 1280, 1589, 3708, 4738, 5397, 6164, 7061, 8114, 9359, 10860, 12979, 29666, 43387, 48704, 54773, 61720, 69697, 78888, 89527, 101976, 118663, 266992

Offset: 0

Author

William P. Orrick, Jun 04 2020

Keywords

• sign
• easy
• tabl

Comments

The number of permutations of [k+n] that differ in every position from both the identity permutation and a permutation consisting of k 1-cycles and s cycles of lengths p_1, p_2, ... p_s, with p_j >= 2 and p_1+p_2+...+p_s = n, can be expressed as Sum T(k,p_1+-p_2+-...+-p_s), where the sum is over all 2^(s-1) choices of sign and where T(k,-n) = T(k,n) (Touchard).

The first of Touchard's formulas for T(k,n) involves A034807, the number of k-matchings of C_n (A213234 or A127677 with sign included) and A047920, the k-th differences of the factorial numbers.

A slightly different formula, due to Wyman and Moser in the k=0 case, involves A213234 and A000023.

The first column is twice A000166 (twice the number of derangements of [k]); the second column is A105926 (first differences of A000166); the third column is A331007 (with offset 2); the first row is A102761 (the ménage numbers); the second row is A000270.

Examples

			Array starts:
k/n |    0     1      2      3       4         5          6           7
-----------------------------------------------------------------------
0   |    2    -1      0      1       2        13         80         579
1   |    0     1      0      3      16        95        672        5397
2   |    2     1      4     19     114       783       6164       54773
3   |    4     7     24    137     916      7061      61720      602955
4   |   18    35    168   1077    8114     69697     671736     7172007
5   |   88   221   1280   9359   78888    749547    7913440    91815601
6   |  530  1589  10860  89527  837794   8741875  100478588  1260186153
7   | 3708 12979 101976 938181 9669196 110058257 1369406616 18475560567
There are T(1,3)=3 permutations that differ from 1234=(1)(2)(3)(4) and 1342=(1)(234) in every position: 2413, 3421, and 4123.
		

Links

• Mathematics Stack Exchange, Double derangement and the other unfamous kind of derangement.
• J. Touchard, Sur un problème de permutations, Comptes Rendus Acad. Sci. Paris, 198 (1934) 631-633.
• Max Wyman and Leo Moser, On the problème des ménages, Canadian Journal of Mathematics, 10 (1958) 468-480.

Crossrefs

Cf. A034807, A213234, A127677, A047920, A000023, A000166, A105926, A331007, A102761, A000270.

Programs

Maple

T := proc(n,k) local t; t := proc(n, k) option remember;
   simplify((n + k)!*hypergeom([-n], [-n - k], -1)) end:
   if k = 0 then return 2*t(n, 0) fi;
   add((-1)^j*(2*k)/(2*k-j)*binomial(2*k-j, j)*t(n, k-j), j=0 ..k) end:
seq(lprint(seq(T(n, k), k=0..7)),n=0..7); # Peter Luschny, Jul 22 2020

PARI

f(k, n) = sum(j=0, k, (-1)^j*binomial(k, j)*(n+k-j)!);
T(k, n) = if (n==0, 2*f(k, 0), sum(j=0, n, (-1)^j*(2*n)/(2*n-j)*binomial(2*n-j, j)*f(k, n-j)));
matrix(7, 7,n, k, T(n-1,k-1))
\\ Michel Marcus, Jun 26 2020

Sage

def f(k,n):
    return sum((-1)^j*binomial(k,j)*factorial(n+k-j) for j in range(0,k+1))
def T(k,n):
    if n==0:
        return 2*f(k,0)
    else:
        return sum((-1)^j*(2*n)/(2*n-j)*binomial(2*n-j,j)*f(k,n-j) for j in range(0,n+1))

Formula

T(k,0) = 2*nu(k,k), T(k,n>0) = Sum_{j=0..n} A213234(2*n,j)*nu(k,k+n-j) = Sum_{j=0..n} (-1)^j*2*n/(2*n-j)*binomial(2*n-j,j)*nu(k,k+n-j) where nu(k,k+n) = A047920(k+n,k) = Sum_{j=0..k} (-1)^j*binomial(k,j)*(k+n-j)! (Touchard).

T(k,n) = 2*cos(2*n * arccos(1/2*sqrt(x))) = 2*Chebyshev_T(2*n,sqrt(x)/2), where, after expanding in powers of x, x^m gets replaced by nu(k,k+m) (Touchard).

T(k,n) = 2*(-1)^n*Sum_{j=0..n} (-1)^j*(Product_{r=0..j} n^2-r^2)/(2*j)!*nu(k,k+j) (Touchard).

T(k,n) = 2*Integral_{x=0..oo} e^(-x^2) * (x^2-1)^k * x * ((x+sqrt(x^2-4))^(2*n)+(x-sqrt(x^2-4))^(2*n)) / 2^(2*n) dx (Touchard).

T(k,0) = 2*Sum_{j=0..h} binomial(h,j)*k(j), T(k,n) = Sum_{i>=0} A213234(n,i)*Sum_{j=0..h} binomial(h,j)*k(n-2*i+j) = Sum_{i>=0} (-1)^i*n/(n-i)*binomial(n-i,i)*Sum_{j=0..h} binomial(h,j)*k(n-2*i+j) where k(n) = A000023(n) = n! * Sum_{i=0..n} (-2)^i / i! (k=0 case due to Wyman and Moser)

T(k+1,n+1) = T(k,n)+T(k,n+1)+T(k,n+2): This holds for all integers n if one defines T(k,-n) = T(k,n).

T(k,0) = 2*A000166(k).

T(k,1) = A105926(k).

T(k,2) = A331007(k+2).

T(0,n) = A102761(n).

T(1,n) = A000270(n).