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

Author

Gus Wiseman, Dec 12 2018

Keywords

• nonn
• tabf

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

Examples

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

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.

Programs

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}]

Formula

A000088(n) = (1/n!) * Sum_k 2^k * T(n,k).