login
A319876
Irregular triangle read by rows where T(n,k) is the number of permutations of {1,...,n} whose action on 2-element subsets of {1,...,n} has k cycles.
3
1, 0, 2, 0, 2, 3, 1, 0, 0, 14, 0, 9, 0, 1, 0, 0, 24, 50, 20, 0, 15, 10, 0, 0, 1, 0, 0, 0, 264, 0, 340, 0, 40, 0, 60, 0, 15, 0, 0, 0, 1, 0, 0, 0, 720, 1764, 504, 0, 1120, 630, 0, 0, 70, 105, 105, 0, 0, 21, 0, 0, 0, 0, 1, 0, 0, 0, 0, 13488, 0, 14112, 0, 3724, 0
OFFSET
1,3
COMMENTS
The permutation
1 -> 1
2 -> 2
3 -> 4
4 -> 3
acts on unordered pairs of distinct elements of {1,2,3,4} to give
(1,2) -> (1,2)
(1,3) -> (1,4)
(1,4) -> (1,3)
(2,3) -> (2,4)
(2,4) -> (2,3)
(3,4) -> (3,4)
which has 4 cycles
(1,2)
(1,3) <-> (1,4)
(2,3) <-> (2,4)
(3,4)
so is counted under T(4,4).
FORMULA
A000088(n) = (1/n!) * Sum_k 2^k * T(n,k).
EXAMPLE
Triangle begins:
1
0 2
0 2 3 1
0 0 14 0 9 0 1
0 0 24 50 20 0 15 10 0 0 1
0 0 0 264 0 340 0 40 0 60 0 15 0 0 0 1
The T(4,4) = 9 permutations: (1243), (1324), (1432), (2134), (2143), (3214), (3412), (4231), (4321).
MATHEMATICA
Table[Length[Select[Permutations[Range[n]], PermutationCycles[Ordering[Map[Sort, Subsets[Range[n], {2}]/.Rule@@@Table[{i, #[[i]]}, {i, n}], {1}]], Length]==k&]], {n, 5}, {k, 0, n*(n-1)/2}]
CROSSREFS
Row n has A000124(n - 1) terms. Row sums are the factorial numbers A000142.
Sequence in context: A317239 A360174 A089596 * A105805 A330368 A194547
KEYWORD
nonn,tabf
AUTHOR
Gus Wiseman, Dec 12 2018
STATUS
approved