Bell numbers: Difference between revisions
Thundergnat (talk | contribs) m (fix a few typos) |
Thundergnat (talk | contribs) m (sigh. another typo) |
||
Line 16: | Line 16: | ||
In general, the easiest way to find the Bell numbers is construct a '''[[wp:Bell_triangle|Bell triangle]]''', also known as an '''Aitken's array''' or '''Peirce triangle''', and read |
In general, the easiest way to find the Bell numbers is construct a '''[[wp:Bell_triangle|Bell triangle]]''', also known as an '''Aitken's array''' or '''Peirce triangle''', and read off the numbers in the first column of each row. |
||
;Task: |
;Task: |
Revision as of 23:55, 5 July 2019
Bell or exponential numbers are enumerations of the number of different ways to partition a set that has exactly n elements. Each element of the sequence Bn is the number of partitions of a set of size n where order of the elements and order of the partitions are non-significant. E.G.: {a b} is the same as {b a} and {a} {b} is the same as {b} {a}.
- So
- B0 = 1 trivially. There is only one way to partition a set with zero elements. { }
- B1 = 1 There is only one way to partition a set with one element. {a}
- B2 = 2 Two elements may be partitioned in two ways. {a} {b}, {a b}
- B3 = 5 Three elements may be partitioned in five ways {a} {b} {c}, {a b} {c}, {a} {b c}, {a c} {b}, {a b c}
- and so on.
In general, the easiest way to find the Bell numbers is construct a Bell triangle, also known as an Aitken's array or Peirce triangle, and read off the numbers in the first column of each row.
- Task
Write a routine (function, generator, whatever) to generate the Bell number sequence and call the routine to show here, on this page at least the first 15 and (if your language supports big Integers) 50th elements of the sequence.
If you do use the Bell triangle method to generate the numbers, also show the first ten rows of the Bell triangle.
- See also
Perl 6
<lang perl6> my @Aitkens-array = lazy [1], -> @b {
my @c = @b.tail; @c.push: @b[$_] + @c[$_] for ^@b; @c } ... *;
my @Bell-numbers = @Aitkens-array.map: { .head };
say "First fifteen and fiftieth Bell numbers:"; printf "%2d: %s\n", 1+$_, @Bell-numbers[$_] for flat ^15, 49;
say "\nFirst ten rows of Aitken's array:"; .say for @Aitkens-array[^10];</lang>
- Output:
First fifteen and fiftieth Bell numbers: 1: 1 2: 1 3: 2 4: 5 5: 15 6: 52 7: 203 8: 877 9: 4140 10: 21147 11: 115975 12: 678570 13: 4213597 14: 27644437 15: 190899322 50: 10726137154573358400342215518590002633917247281 First ten rows of Aitken's array: [1] [1 2] [2 3 5] [5 7 10 15] [15 20 27 37 52] [52 67 87 114 151 203] [203 255 322 409 523 674 877] [877 1080 1335 1657 2066 2589 3263 4140] [4140 5017 6097 7432 9089 11155 13744 17007 21147] [21147 25287 30304 36401 43833 52922 64077 77821 94828 115975]