cp's OEIS Frontend

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.

%I A335391 #64 Jul 23 2020 03:26:05
%S A335391 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 A335391 221,530,579,672,783,916,1077,1280,1589,3708,4738,5397,6164,7061,8114,
%U A335391 9359,10860,12979,29666,43387,48704,54773,61720,69697,78888,89527,101976,118663,266992
%N 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.
%C A335391 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 A335391 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 A335391 A slightly different formula, due to Wyman and Moser in the k=0 case, involves A213234 and A000023.
%C A335391 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 A335391 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 A335391 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 A335391 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 A335391 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 A335391 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 A335391 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 A335391 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 A335391 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 A335391 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 A335391 T(k,0) = 2*A000166(k).
%F A335391 T(k,1) = A105926(k).
%F A335391 T(k,2) = A331007(k+2).
%F A335391 T(0,n) = A102761(n).
%F A335391 T(1,n) = A000270(n).
%e A335391 Array starts:
%e A335391 k/n |    0     1      2      3       4         5          6           7
%e A335391 -----------------------------------------------------------------------
%e A335391 0   |    2    -1      0      1       2        13         80         579
%e A335391 1   |    0     1      0      3      16        95        672        5397
%e A335391 2   |    2     1      4     19     114       783       6164       54773
%e A335391 3   |    4     7     24    137     916      7061      61720      602955
%e A335391 4   |   18    35    168   1077    8114     69697     671736     7172007
%e A335391 5   |   88   221   1280   9359   78888    749547    7913440    91815601
%e A335391 6   |  530  1589  10860  89527  837794   8741875  100478588  1260186153
%e A335391 7   | 3708 12979 101976 938181 9669196 110058257 1369406616 18475560567
%e A335391 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 A335391 T := proc(n,k) local t; t := proc(n, k) option remember;
%p A335391    simplify((n + k)!*hypergeom([-n], [-n - k], -1)) end:
%p A335391    if k = 0 then return 2*t(n, 0) fi;
%p A335391    add((-1)^j*(2*k)/(2*k-j)*binomial(2*k-j, j)*t(n, k-j), j=0 ..k) end:
%p A335391 seq(lprint(seq(T(n, k), k=0..7)),n=0..7); # _Peter Luschny_, Jul 22 2020
%o A335391 (Sage)
%o A335391 def f(k,n):
%o A335391     return sum((-1)^j*binomial(k,j)*factorial(n+k-j) for j in range(0,k+1))
%o A335391 def T(k,n):
%o A335391     if n==0:
%o A335391         return 2*f(k,0)
%o A335391     else:
%o A335391         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 A335391 (PARI)
%o A335391 f(k, n) = sum(j=0, k, (-1)^j*binomial(k, j)*(n+k-j)!);
%o A335391 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 A335391 matrix(7, 7,n, k, T(n-1,k-1))
%o A335391 \\ _Michel Marcus_, Jun 26 2020
%Y A335391 Cf. A034807, A213234, A127677, A047920, A000023, A000166, A105926, A331007, A102761, A000270.
%K A335391 sign,easy,tabl
%O A335391 0,1
%A A335391 _William P. Orrick_, Jun 04 2020