login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A180013
Triangular array read by rows: T(n,k) = number of fixed points in the permutations of {1,2,...,n} that have exactly k cycles; n>=1, 1<=k<=n.
1
1, 0, 2, 0, 3, 3, 0, 8, 12, 4, 0, 30, 55, 30, 5, 0, 144, 300, 210, 60, 6, 0, 840, 1918, 1575, 595, 105, 7, 0, 5760, 14112, 12992, 5880, 1400, 168, 8, 0, 45360, 117612, 118188, 60921, 17640, 2898, 252, 9, 0, 403200, 1095840, 1181240, 672840, 224490, 45360, 5460, 360, 10
OFFSET
1,3
COMMENTS
Row sums = n! which is the number of fixed points in all the permutations of {1,2,...,n}.
It appears that column k = 2 is A001048 (with different offset).
From Olivier Gérard, Oct 23 2012: (Start)
This is a multiple of the triangle of Stirling numbers of the first kind, A180013(n,k) = (n)*A132393(n-1,k).
Another interpretation is : T(n,n-k) is the total number of ways to insert the symbol n among the cycles of permutations of [n-1] with (n+1-k) cycles to form a canonical cycle representation of a permutation of [n]. For each cycle of length c, there are c places to insert a symbol, and for each permutation there is the possibility to create a new cycle (a fixed point).
(End)
LINKS
FORMULA
E.g.f.: for column k: x*(log(1/(1-x)))^(k-1)/(k-1)!.
T(n, k) = [x^k] (n+1)!*hypergeom([-n,1-x],[1],1) for n>0. - Peter Luschny, Jan 28 2016
EXAMPLE
T(4,3)= 12 because there are 12 fixed points in the permutations of 4 that have 3 cycles: (1)(2)(4,3); (1)(3,2)(4); (1)(4,2)(3); (2,1)(3)(4); (3,1)(2)(4); (4,1)(2)(3) where the permutations are represented in their cycle notation.
1
0 2
0 3 3
0 8 12 4
0 30 55 30 5
0 144 300 210 60 6
0 840 1918 1575 595 105 7
MAPLE
egf:= k-> x * (log(1/(1-x)))^(k-1) / (k-1)!:
T:= (n, k)-> n! * coeff(series(egf(k), x, n+1), x, n):
seq(seq(T(n, k), k=1..n), n=1..10); # Alois P. Heinz, Jan 16 2011
# As coefficients of polynomials:
with(PolynomialTools): with(ListTools): A180013_row := proc(n)
`if`(n=0, 1, (n+1)!*hypergeom([-n, 1-x], [1], 1)); CoefficientList(simplify(%), x) end: FlattenOnce([seq(A180013_row(n), n=0..9)]); # Peter Luschny, Jan 28 2016
MATHEMATICA
Flatten[Table[Table[(n + 1) Abs[StirlingS1[n, k]], {k, 0, n}], {n, 0, 9}], 1] (* Olivier Gérard, Oct 23 2012 *)
CROSSREFS
Cf. A000142, A001048. Diagonal, lower diagonal give: A000027, A027480(n+1).
Sequence in context: A327878 A337841 A298605 * A377657 A094067 A094112
KEYWORD
nonn,tabl
AUTHOR
Geoffrey Critzer, Jan 13 2011
EXTENSIONS
More terms from Alois P. Heinz, Jan 16 2011
STATUS
approved