|
|
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, 1167348, -920808, 478842, -149040, 21147
(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.
|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 156-24-3 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 left-to-right 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
|
|
|
FORMULA
|
E.g.f.: exp((1+x)^y-1).
|
|
EXAMPLE
|
Triangle begins:
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
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|