Citizendium - a community developing a quality, comprehensive compendium of knowledge, online and free.
Click here to join and contribute
CZ thanks our previous donors. Donate here. Treasurer's Financial Report

Stirling number

From Citizendium
Jump to: navigation, search
This article is developing and not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
This editable Main Article is under development and subject to a disclaimer.

In combinatorics, the Stirling numbers count certain arrangements of objects into a given number of structures. There are two kinds of Stirling number,depending on the nature of the structure being counted.

The Stirling number of the first kind S(n,k) counts the number of ways n labelled objects can be arranged into k cycles: cycles are regarded as equivalent, and counted only once, if they differ by a cyclic permutation, thus [ABC] = [BCA] = [CAB] but is counted as different from [CBA] = [BAC] = [ACB]. The order of the cycles in the list is irrelevant.

For example, 4 objects can be arranged into 2 cycles in eleven ways, so S(4,2) = 11:

  • [ABC],[D]
  • [ACB],[D]
  • [ABD],[C]
  • [ADB],[C]
  • [ACD],[B]
  • [ADC],[B]
  • [BCD],[A]
  • [BDC],[A]
  • [AB],[CD]
  • [AC],[BD]
  • [AD],[BC]

The Stirling number of the second kind s(n,k) counts the number of ways n labelled objects can be arranged into k subsets: cycles are regarded as equivalent, and counted only once, if they have the same elements, thus {ABC} = {BCA} = {CAB} = {CBA} = {BAC} = {ACB}. The order of the subsets in the list is irrelevant.

For example, 4 objects can be arranged into 2 subsets in seven ways, so s(4,2) = 7:

  • {ABC},{D}
  • {ABD},{C}
  • {ACD},{B}
  • {BCD},{A}
  • {AB},{CD}
  • {AC},{BD}
  • {AD},{BC}

References