login
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.
3

%I #64 Jul 23 2020 03:26:05

%S 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,

%T 221,530,579,672,783,916,1077,1280,1589,3708,4738,5397,6164,7061,8114,

%U 9359,10860,12979,29666,43387,48704,54773,61720,69697,78888,89527,101976,118663,266992

%N 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.

%C 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).

%C 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.

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

%C 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.

%H Mathematics Stack Exchange, <a href="https://math.stackexchange.com/questions/3674756/double-derangement-and-the-other-unfamous-kind-of-derangement">Double derangement and the other unfamous kind of derangement</a>.

%H J. Touchard, <a href="https://gallica.bnf.fr/ark:/12148/bpt6k31506/f631.item.zoom">Sur un problème de permutations</a>, Comptes Rendus Acad. Sci. Paris, 198 (1934) 631-633.

%H Max Wyman and Leo Moser, <a href="https://doi.org/10.4153/CJM-1958-045-6">On the problème des ménages</a>, Canadian Journal of Mathematics, 10 (1958) 468-480.

%F 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).

%F 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).

%F 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).

%F 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).

%F 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)

%F 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).

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

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

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

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

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

%e Array starts:

%e k/n | 0 1 2 3 4 5 6 7

%e -----------------------------------------------------------------------

%e 0 | 2 -1 0 1 2 13 80 579

%e 1 | 0 1 0 3 16 95 672 5397

%e 2 | 2 1 4 19 114 783 6164 54773

%e 3 | 4 7 24 137 916 7061 61720 602955

%e 4 | 18 35 168 1077 8114 69697 671736 7172007

%e 5 | 88 221 1280 9359 78888 749547 7913440 91815601

%e 6 | 530 1589 10860 89527 837794 8741875 100478588 1260186153

%e 7 | 3708 12979 101976 938181 9669196 110058257 1369406616 18475560567

%e 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.

%p T := proc(n,k) local t; t := proc(n, k) option remember;

%p simplify((n + k)!*hypergeom([-n], [-n - k], -1)) end:

%p if k = 0 then return 2*t(n, 0) fi;

%p add((-1)^j*(2*k)/(2*k-j)*binomial(2*k-j, j)*t(n, k-j), j=0 ..k) end:

%p seq(lprint(seq(T(n, k), k=0..7)),n=0..7); # _Peter Luschny_, Jul 22 2020

%o (Sage)

%o def f(k,n):

%o return sum((-1)^j*binomial(k,j)*factorial(n+k-j) for j in range(0,k+1))

%o def T(k,n):

%o if n==0:

%o return 2*f(k,0)

%o else:

%o 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))

%o (PARI)

%o f(k, n) = sum(j=0, k, (-1)^j*binomial(k, j)*(n+k-j)!);

%o 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)));

%o matrix(7, 7,n, k, T(n-1,k-1))

%o \\ _Michel Marcus_, Jun 26 2020

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

%K sign,easy,tabl

%O 0,1

%A _William P. Orrick_, Jun 04 2020