NOTE: also see an addition combinatorial node, int_part, introduced later in this thread.
Attached are some nodes (described below) that may be useful for anyone doing projects involving combinatorics:
- factorial. Calculate exact value of n!
- n_choose_k. Calculate the binomial coefficient n choose k, the number of ways to choose k elements from a set of n elements
- combos. Generate a list of all possible ways to choose k items from a set of n elements
- stirling. Calculate the Stirling Number of the second kind S(n,k), the number of ways to partition a set with n elements into k partitions
- bell. Calculate the Bell Number B(n), the total possible partitions of a set with n elements
- partitions. Generate a list of all possible partitions of a set with n elements
How many rhyme schemes are there for a three-line poem?
- 000 = AAA = Roses are red / Violets are dead / Try tulips instead
- 001 = AAB = Roses are red / Violets are dead / Tulips are pink
- 011 = ABB = Roses are red / Violets are blue / Tulips are too
- 012 = ABC = Roses are red / Violets are blue / Tulips are pink
- 010 = ABA = Roses are red / Violets are blue / Tulips are dead
There are 2 schemes for a 2-line poem, 5 schemes for a 3-line poem, 15 schemes for a 4-line poem, and 52 schemes for a 5-line poem. 2, 5, 15, 52, 203, 877, 4140, 21147... are the Bell Numbers.
B(n) counts the total number of ways to partition a set of n elements. The partitions node lets you see the codes representing each one. You can use them, and the other nodes, for many things other than rhyme schemes.
The attached demo file contains examples showing some ways of using these nodes, with some additional nodes that may also be useful.
Notes
- factorial. n! = 1 x 2 x 3 ... x n. It's a tricky value to calculate because it grows so fast. 20! is the highest value that can be represented as an integer in Nodebox. 170! is the highest value that can be represented as a number. The factorial node outputs as a string in order to provide exact values even for 170! The add commas option shows the value with comma separators for easier reading; uncheck this if you want to use it in calculations.
- n_choose_k. The binomial coefficient has countless applications. If arranged in rows for each value of n, they form Pascal's triangle. The node accepts values of n and k from 0 to 170; if k exceeds n, the function returns 0. For more information, see https://en.wikipedia.org/wiki/Binomial_coefficient
- combos. This function returns a list of n choose k strings. Each string is a comma-separated list of element indices ranging from 0 to n-1. You can use the make_strings node to break each string into a list of indices, which you can then feed into a slice node to select a subset of objects (see the star-tips section of the attached demo). If k exceeds n the function will return an error message.
- stirling. Like n choose k, Stirling numbers can also form a triangle, but the values grow much faster. For high values of n, some numbers will exceed the maximum allowed value and return "Infinity" or "NaN" (Not a Number). If k exceeds n, the function returns 0. See https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind
- bell. Bell(n) is simply the sum of stirling(n,k) for k from 0 to n. Because it grows even faster than the factorial function, n is capped at a maximum value of 143. See https://en.wikipedia.org/wiki/Bell_number
- partitions. My partitions node returns partition codes for n values between 2 and 9. Each code is an n-digit number, with digits varying from 0 to n-1. The digit tells which partition each element belongs to. A 0 in the first place means that the first element belongs to partition 0; a code of 01001 indicates a set divided into two partitions with the first, third, and fourth items in partition 0 and the second and fifth items in partition 1. The partition patterns form a Gray code, which means that only one digit changes from each code to the next. The algorithm to generate this code was invented by Gideon Erlich and described by Donald Knuth in "The Art of Computer Programming Volume 4A".
The attached demo poster contains usage examples for all six functions, including star tips for the combos function and Genji-ko diagrams for the partitions function.
Some people are confused by the difference between combinations and partitions. As shown in the demo, there are 5 choose 3 = 10 ways to color three tips in a five-point star. But there are S(5,3) = 25 ways to partition a set of 5 tips into 3 different subsets (e.g. color them 3 different ways). The 5 choose 3 star patterns shown in the poster actually divide the set into 2 partitions (colored or not). But S(5,2) = 15, not 10, because there are also 5 ways to color just one tip (which also divides the set into two partitions). So combos show all the ways of choosing k elements from an n-item set, while partitions show all the ways of dividing that set into k different subsets.
S(5,3) tells us there are 25 ways to color star tips using 3 colors. If you look at the 52 codes produced by partitions(5), you will see that 25 of them include 0s, 1s, and 2s with no 3s or 4s. The first such code, 00012, indicates a star with the first 3 tips (starting from the southeast tip) assigned color 1, the next assigned color 2, and the last assigned color 3. You could use red, blue, and green for your three colors (red, red, red, blue, green). But if you changed the order of the colors (say blue, blue, blue, red, green), this would be considered the same partition. You could use any of the 3 colors for the first partition and either of the remaining 2 for the second partition, so there are 3! = 6 ways of ordering the colors for that partition. So the total number of distinct ways of coloring the tips of a 5-point star red, blue, and green with at least one instance of each color is S(5,3) * 3! = 25 * 6 = 150.
The Genji-ko patterns shown in the poster are an attractive and intuitive way to visualize partitions. In medieval Japan they were associated with an incense game involving 5 sticks of incense (see https://en.wikipedia.org/wiki/Kōdō#Monkō). The 52 possible ways of partitioning those sticks became associated with the chapters of The Tale of Genji, hence the name (there are actually 54 chapters in the novel, so 2 additional symbols were added). I was introduced to this in a charming book, which I heartily recommend: Once Upon a Prime by Sarah Hart.
Note: my genji_ko node works well for sets up to 7 elements, but will (rarely) make incorrect drawings for larger sets. There can be more than one way to draw these partitions; the choice is a matter of aesthetics. Several of the 5-element diagrams produced by my node are correct, but differ from the classic forms shown in the Wikipedia article.
I hope you find these nodes useful. If anyone sees this, PLEASE drop a quick reply and tell me which of these six nodes I should include in the next version of my Cartan Node Library.
All nodes in this demo are free to use without restriction. Happy Nodeboxing!
