The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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. 3
 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 (list; table; graph; refs; listen; history; text; internal format)
 OFFSET 0,1 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. 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. 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). EXAMPLE 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. 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 PROG (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)) (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 CROSSREFS Cf. A034807, A213234, A127677, A047920, A000023, A000166, A105926, A331007, A102761, A000270. Sequence in context: A280454 A124645 A029409 * A014674 A015339 A137867 Adjacent sequences: A335388 A335389 A335390 * A335392 A335393 A335394 KEYWORD sign,easy,tabl AUTHOR William P. Orrick, Jun 04 2020 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified March 29 10:21 EDT 2023. Contains 361598 sequences. (Running on oeis4.)