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.

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).

Links

Table of n, a(n) for n=1..73.

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.

Cf. A000088, A000612, A000665, A000666, A003180, A050535, A070166, A317794, A317795.

Sequence in context: A317239 A360174 A089596 * A105805 A330368 A194547

Adjacent sequences: A319873 A319874 A319875 * A319877 A319878 A319879

Keyword

nonn,tabf

Author

Gus Wiseman, Dec 12 2018

Status

approved