OFFSET
0,15
COMMENTS
Difference of 1st and 2nd leading diagonals (n > 0).
T(n,n) - T(n,n-1) = -1,0,0,3,5,10,14,21,27,36,44,...
= (-1) + (1+0) + (3+2) + (5+4) + (7+6) + (9+8) + ...
Cf. A176222(n) with 2 terms -1,0 prepended (moving its offset from 3 to 1).
LINKS
Michael De Vlieger, Table of n, a(n) for n = 0..11475 (rows n = 0..150, flattened)
FORMULA
EXAMPLE
Triangle array T(n,k)
n: {k<=n}
0: {1}
1: {1, 0}
2: {1, 0, 0}
3: {1, 0, 0, 0}
4: {1, 0, 0, 0, 3}
5: {1, 0, 0, 0, 15, 20}
6: {1, 0, 0, 0, 45, 120, 130}
7: {1, 0, 0, 0, 105, 420, 910, 924}
8: {1, 0, 0, 0, 210, 1120, 3640, 7392, 7413}
9: {1, 0, 0, 0, 378, 2520, 10920, 33264, 66717, 66744}
10: {1, 0, 0, 0, 630, 5040, 27300, 110880, 333585, 667440, 667476}
T(n,0) = 1 due to sole permutation in S_n with n fixed points, namely the identity permutation, with 0 non-fixed point cycles, an even number. (T(0,0)=1 relies on S_0 containing an empty permutation.)
T(n,1) = 0 due to no permutations in S_n with (n-1) fixed points.
T(n,2) = T(n,3) = 0 due to only non-unity partitions of 2 and 3 being of odd length, namely the trivial partitions (2),(3).
Example:
T(4,4) = 3 since S_4 contains 3 permutations with 0 fixed points and an even number of non-fixed point cycles, namely the derangements: (12)(34),(13)(24),(14)(23).
Worked Example:
T(7,6) = 910 permutations in S_7 with 1 fixed point and an even number of non-fixed point cycles.
T(7,6) = 910 possible (4,2)- and (3,3)-cycles of 7 items.
N(n,y) = possible y-cycles of n items.
N(n,y) = (n!/(n-k)!) / (M(y) * s(y)).
y = partition of k<=n with q parts = (p_1, p_2,..., p_i, ..., p_q)
s.t. k = Sum_{i=1..q} p_i.
Or:
y = partition of k<=n with d distinct parts, each with multiplicity m_j = (y_1^m_1, y_2^m^2, ..., y_j^m_j, ..., y_d^m_d)
s.t. k = Sum_{j=1..d) m_j*y_j.
M(y) = Product_{i=1..q} p_i = Product_{j=1..d} y_j^m_j.
s(y) = Product_{j=1..d} m_j! ("symmetry of repeated parts").
Note: (n!/(n-k)!) / s(y) = multinomial(n, {m_j}).
Therefore:
T(7,6) = N(7,y=(4,2)) + N(7,y=(3^2))
= (7!/(4*2)) + (7!/(3^2)/2!)
= 7! * (1/8 + 1/18)
= 5040 * (13/72)
T(7,6) = 910.
MAPLE
b:= proc(n, t) option remember; `if`(n=0, t, add(expand(`if`(j>1, x^j, 1)*
b(n-j, irem(t+signum(j-1), 2)))*binomial(n-1, j-1)*(j-1)!, j=1..n))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n, 1)):
seq(T(n), n=0..10); # Alois P. Heinz, Jun 04 2024
MATHEMATICA
Table[Table[n!/(n-k)!/2 * (Sum[(-1)^j/j!, {j, 0, k}] - ((k - 1)/k!)), {k, 0, n}], {n, 0, 10}]
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Julian Hatfield Iacoponi, Jun 04 2024
STATUS
approved