Stirling number

From Citizendium, the Citizens' Compendium

Jump to: navigation, search


This article is developing and not approved.
Main Article
Talk
Related Articles  [?]
Bibliography  [?]
External Links  [?]
 
http://en.citizendium.org/wiki?title=Stirling_number&printable=yes
This is a draft article, under development and not meant to be cited but you can help to improve it. These unapproved articles are 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

Retrieved from "http://en.citizendium.org/wiki/Stirling_number"
Views
Personal tools