|
| |
|
|
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
|
|
|
|
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).
|
|
|
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))
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
