

A055924


Exponential transform of Stirling1 triangle A008275.


2



1, 1, 2, 2, 6, 5, 6, 22, 30, 15, 24, 100, 175, 150, 52, 120, 548, 1125, 1275, 780, 203, 720, 3528, 8120, 11025, 9100, 4263, 877, 5040, 26136, 65660, 101535, 101920, 65366, 24556, 4140, 40320, 219168, 590620, 1009260
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

a(n,k) = number of sets of permutations of {1,...,n} with k total cycles.
Comments from David Callan, Sep 20 2007: (Start) a(n,k) = stirling1(n, k) * bell(k) counts the above sets of permutations. To see this, recall that stirling1(n, k) is the number of permutations of [n]={1,...,n} with k cycles and bell(k) is the number of set partitions of [k].
Given such a permutation and set partition, write the permutation in standard cycle form (smallest entry first in each cycle and first entries decreasing left to right). For example, with n=15 and k=6, {{10}, {6, 11}, {5, 7, 15}, {3, 13, 12, 8}, {2, 14, 9}, {1, 4}} is in this standard cycle form.
Then combine cycles as specified by the partition to form a set of lists. For example, the partition 156243 would yield {{10, 2, 14, 9, 1, 4}, {6, 11, 3, 13, 12, 8}, {5, 7, 15}}. The original first entries are now the record lefttoright lows.
Finally, apply to each list the well known transformation that sends # record lows to # cycles. The example yields {{4, 14, 1, 2, 10, 9}, {13, 11, 3, 6, 8, 12}, {7, 15, 5}}. This is a bijection to sets of lists (i.e. permutations) with a total of k cycles, as required. (End)


LINKS

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


FORMULA

E.g.f.: exp((1+x)^y1).
a(n, k) = stirling1(n, k) * bell(k).  Vladeta Jovovic, Feb 01 2003


EXAMPLE

1; 1,2; 2,6,5; 6,22,30,15; 24,100,175,150,52; ...
a(3,2)=6 because (12)(3), (12)(3), (13)(2), (13)(2), (23)(1), (23)(1).


CROSSREFS

Row sums of a(n, k) give A000262. Cf. A008275, A008297, A055925.
Sequence in context: A275142 A200226 A115255 * A156563 A201500 A054917
Adjacent sequences: A055921 A055922 A055923 * A055925 A055926 A055927


KEYWORD

sign,tabl


AUTHOR

Wouter Meeussen, Christian G. Bower, Jul 06 2000


STATUS

approved



