From Jesse Nicholas comes a puzzle that is four small steps for a human, one giant leap for humankind:
You have 10 blocks with which to build four steps against a wall. The first step is one block high, the second is two blocks high, the third is three blocks high and the fourth is four blocks high.
However, the ground ever-so-slightly slopes down toward the wall, and both the floor and the blocks are a little bit slippery. As a result, whenever you place a block at ground level, it slides toward the wall until it hits the wall or another block. And when you place a block atop another block, it will similarly slide toward the wall until it hits the wall or another block.
Suppose the four blocks in the bottom row are labeled A, the three blocks in the second row are labeled B, the two blocks in the next row are labeled C and the topmost block is labeled D. One way to build the steps would be to place the blocks in the following order, one row at a time: A-A-A-A-B-B-B-C-C-D. You could alternatively place the blocks one column at a time: A-B-C-D-A-B-C-A-B-A. But you could not place them in the order A-B-B-A-A-A-B-C-C-D because that would mean at one point you have more blocks in the second row, B, than in the bottom row, A — a physical impossibility!
How many distinct ways are there to build these four steps using the 10 blocks?
Extra credit: Suppose you have precisely enough blocks to build a staircase with $N$ stairs. How many distinct ways are there to build this staircase?
Here are the earlier step builds:
The trivial build for one step is:
A
The last step or column is composed of blocks A and B. These blocks are appended to the first step build.
This yields:
A-A-B A-A-B A-B-A
Because of sliding, the first two are identical. The distinct builds for two steps are:
AAB ABA
The last step or column is composed of blocks A, B, and C. These blocks are appended to the first two steps builds.
Appending C to the build order yields:
A-A-B-C A-B-C-A A-B-A-C.
Appending B to the build order yields:
A-A-B-B-C A-A-B-B-C A-A-B-C-B A-B-C-A-B A-B-A-B-C A-B-A-C-B
Because of sliding, the first two are identical. After appending A to the build order and eliminating sliding duplicates there are 16 distinct builds for 3 steps:
print_ans(3)
AAABBC AAABCB AABABC AABACB AABBAC AABBCA AABCAB AABCBA ABAABC ABAACB ABABAC ABABCA ABACAB ABACBA ABCAAB ABCABA
The last step or column is composed of blocks A, B, C, and D. These blocks are appended to the first three steps builds.
Applying the steps above, there are 768 distinct builds for 4 steps. Here is a list of them:
print_ans(4)
AAAABBBCCD AAAABBBCDC AAAABBCBCD AAAABBCBDC AAAABBCCBD AAAABBCCDB AAAABBCDBC AAAABBCDCB AAAABCBBCD AAAABCBBDC AAAABCBCBD AAAABCBCDB AAAABCBDBC AAAABCBDCB AAAABCDBBC AAAABCDBCB AAABABBCCD AAABABBCDC AAABABCBCD AAABABCBDC AAABABCCBD AAABABCCDB AAABABCDBC AAABABCDCB AAABACBBCD AAABACBBDC AAABACBCBD AAABACBCDB AAABACBDBC AAABACBDCB AAABACDBBC AAABACDBCB AAABBABCCD AAABBABCDC AAABBACBCD AAABBACBDC AAABBACCBD AAABBACCDB AAABBACDBC AAABBACDCB AAABBBACCD AAABBBACDC AAABBBCACD AAABBBCADC AAABBBCCAD AAABBBCCDA AAABBBCDAC AAABBBCDCA AAABBCABCD AAABBCABDC AAABBCACBD AAABBCACDB AAABBCADBC AAABBCADCB AAABBCBACD AAABBCBADC AAABBCBCAD AAABBCBCDA AAABBCBDAC AAABBCBDCA AAABBCCABD AAABBCCADB AAABBCCBAD AAABBCCBDA AAABBCCDAB AAABBCCDBA AAABBCDABC AAABBCDACB AAABBCDBAC AAABBCDBCA AAABBCDCAB AAABBCDCBA AAABCABBCD AAABCABBDC AAABCABCBD AAABCABCDB AAABCABDBC AAABCABDCB AAABCADBBC AAABCADBCB AAABCBABCD AAABCBABDC AAABCBACBD AAABCBACDB AAABCBADBC AAABCBADCB AAABCBBACD AAABCBBADC AAABCBBCAD AAABCBBCDA AAABCBBDAC AAABCBBDCA AAABCBCABD AAABCBCADB AAABCBCBAD AAABCBCBDA AAABCBCDAB AAABCBCDBA AAABCBDABC AAABCBDACB AAABCBDBAC AAABCBDBCA AAABCBDCAB AAABCBDCBA AAABCDABBC AAABCDABCB AAABCDBABC AAABCDBACB AAABCDBBAC AAABCDBBCA AAABCDBCAB AAABCDBCBA AABAABBCCD AABAABBCDC AABAABCBCD AABAABCBDC AABAABCCBD AABAABCCDB AABAABCDBC AABAABCDCB AABAACBBCD AABAACBBDC AABAACBCBD AABAACBCDB AABAACBDBC AABAACBDCB AABAACDBBC AABAACDBCB AABABABCCD AABABABCDC AABABACBCD AABABACBDC AABABACCBD AABABACCDB AABABACDBC AABABACDCB AABABBACCD AABABBACDC AABABBCACD AABABBCADC AABABBCCAD AABABBCCDA AABABBCDAC AABABBCDCA AABABCABCD AABABCABDC AABABCACBD AABABCACDB AABABCADBC AABABCADCB AABABCBACD AABABCBADC AABABCBCAD AABABCBCDA AABABCBDAC AABABCBDCA AABABCCABD AABABCCADB AABABCCBAD AABABCCBDA AABABCCDAB AABABCCDBA AABABCDABC AABABCDACB AABABCDBAC AABABCDBCA AABABCDCAB AABABCDCBA AABACABBCD AABACABBDC AABACABCBD AABACABCDB AABACABDBC AABACABDCB AABACADBBC AABACADBCB AABACBABCD AABACBABDC AABACBACBD AABACBACDB AABACBADBC AABACBADCB AABACBBACD AABACBBADC AABACBBCAD AABACBBCDA AABACBBDAC AABACBBDCA AABACBCABD AABACBCADB AABACBCBAD AABACBCBDA AABACBCDAB AABACBCDBA AABACBDABC AABACBDACB AABACBDBAC AABACBDBCA AABACBDCAB AABACBDCBA AABACDABBC AABACDABCB AABACDBABC AABACDBACB AABACDBBAC AABACDBBCA AABACDBCAB AABACDBCBA AABBAABCCD AABBAABCDC AABBAACBCD AABBAACBDC AABBAACCBD AABBAACCDB AABBAACDBC AABBAACDCB AABBABACCD AABBABACDC AABBABCACD AABBABCADC AABBABCCAD AABBABCCDA AABBABCDAC AABBABCDCA AABBACABCD AABBACABDC AABBACACBD AABBACACDB AABBACADBC AABBACADCB AABBACBACD AABBACBADC AABBACBCAD AABBACBCDA AABBACBDAC AABBACBDCA AABBACCABD AABBACCADB AABBACCBAD AABBACCBDA AABBACCDAB AABBACCDBA AABBACDABC AABBACDACB AABBACDBAC AABBACDBCA AABBACDCAB AABBACDCBA AABBCAABCD AABBCAABDC AABBCAACBD AABBCAACDB AABBCAADBC AABBCAADCB AABBCABACD AABBCABADC AABBCABCAD AABBCABCDA AABBCABDAC AABBCABDCA AABBCACABD AABBCACADB AABBCACBAD AABBCACBDA AABBCACDAB AABBCACDBA AABBCADABC AABBCADACB AABBCADBAC AABBCADBCA AABBCADCAB AABBCADCBA AABBCCAABD AABBCCAADB AABBCCABAD AABBCCABDA AABBCCADAB AABBCCADBA AABBCCDAAB AABBCCDABA AABBCDAABC AABBCDAACB AABBCDABAC AABBCDABCA AABBCDACAB AABBCDACBA AABBCDCAAB AABBCDCABA AABCAABBCD AABCAABBDC AABCAABCBD AABCAABCDB AABCAABDBC AABCAABDCB AABCAADBBC AABCAADBCB AABCABABCD AABCABABDC AABCABACBD AABCABACDB AABCABADBC AABCABADCB AABCABBACD AABCABBADC AABCABBCAD AABCABBCDA AABCABBDAC AABCABBDCA AABCABCABD AABCABCADB AABCABCBAD AABCABCBDA AABCABCDAB AABCABCDBA AABCABDABC AABCABDACB AABCABDBAC AABCABDBCA AABCABDCAB AABCABDCBA AABCADABBC AABCADABCB AABCADBABC AABCADBACB AABCADBBAC AABCADBBCA AABCADBCAB AABCADBCBA AABCBAABCD AABCBAABDC AABCBAACBD AABCBAACDB AABCBAADBC AABCBAADCB AABCBABACD AABCBABADC AABCBABCAD AABCBABCDA AABCBABDAC AABCBABDCA AABCBACABD AABCBACADB AABCBACBAD AABCBACBDA AABCBACDAB AABCBACDBA AABCBADABC AABCBADACB AABCBADBAC AABCBADBCA AABCBADCAB AABCBADCBA AABCBCAABD AABCBCAADB AABCBCABAD AABCBCABDA AABCBCADAB AABCBCADBA AABCBCDAAB AABCBCDABA AABCBDAABC AABCBDAACB AABCBDABAC AABCBDABCA AABCBDACAB AABCBDACBA AABCBDCAAB AABCBDCABA AABCDAABBC AABCDAABCB AABCDABABC AABCDABACB AABCDABBAC AABCDABBCA AABCDABCAB AABCDABCBA AABCDBAABC AABCDBAACB AABCDBABAC AABCDBABCA AABCDBACAB AABCDBACBA AABCDBCAAB AABCDBCABA ABAAABBCCD ABAAABBCDC ABAAABCBCD ABAAABCBDC ABAAABCCBD ABAAABCCDB ABAAABCDBC ABAAABCDCB ABAAACBBCD ABAAACBBDC ABAAACBCBD ABAAACBCDB ABAAACBDBC ABAAACBDCB ABAAACDBBC ABAAACDBCB ABAABABCCD ABAABABCDC ABAABACBCD ABAABACBDC ABAABACCBD ABAABACCDB ABAABACDBC ABAABACDCB ABAABBACCD ABAABBACDC ABAABBCACD ABAABBCADC ABAABBCCAD ABAABBCCDA ABAABBCDAC ABAABBCDCA ABAABCABCD ABAABCABDC ABAABCACBD ABAABCACDB ABAABCADBC ABAABCADCB ABAABCBACD ABAABCBADC ABAABCBCAD ABAABCBCDA ABAABCBDAC ABAABCBDCA ABAABCCABD ABAABCCADB ABAABCCBAD ABAABCCBDA ABAABCCDAB ABAABCCDBA ABAABCDABC ABAABCDACB ABAABCDBAC ABAABCDBCA ABAABCDCAB ABAABCDCBA ABAACABBCD ABAACABBDC ABAACABCBD ABAACABCDB ABAACABDBC ABAACABDCB ABAACADBBC ABAACADBCB ABAACBABCD ABAACBABDC ABAACBACBD ABAACBACDB ABAACBADBC ABAACBADCB ABAACBBACD ABAACBBADC ABAACBBCAD ABAACBBCDA ABAACBBDAC ABAACBBDCA ABAACBCABD ABAACBCADB ABAACBCBAD ABAACBCBDA ABAACBCDAB ABAACBCDBA ABAACBDABC ABAACBDACB ABAACBDBAC ABAACBDBCA ABAACBDCAB ABAACBDCBA ABAACDABBC ABAACDABCB ABAACDBABC ABAACDBACB ABAACDBBAC ABAACDBBCA ABAACDBCAB ABAACDBCBA ABABAABCCD ABABAABCDC ABABAACBCD ABABAACBDC ABABAACCBD ABABAACCDB ABABAACDBC ABABAACDCB ABABABACCD ABABABACDC ABABABCACD ABABABCADC ABABABCCAD ABABABCCDA ABABABCDAC ABABABCDCA ABABACABCD ABABACABDC ABABACACBD ABABACACDB ABABACADBC ABABACADCB ABABACBACD ABABACBADC ABABACBCAD ABABACBCDA ABABACBDAC ABABACBDCA ABABACCABD ABABACCADB ABABACCBAD ABABACCBDA ABABACCDAB ABABACCDBA ABABACDABC ABABACDACB ABABACDBAC ABABACDBCA ABABACDCAB ABABACDCBA ABABCAABCD ABABCAABDC ABABCAACBD ABABCAACDB ABABCAADBC ABABCAADCB ABABCABACD ABABCABADC ABABCABCAD ABABCABCDA ABABCABDAC ABABCABDCA ABABCACABD ABABCACADB ABABCACBAD ABABCACBDA ABABCACDAB ABABCACDBA ABABCADABC ABABCADACB ABABCADBAC ABABCADBCA ABABCADCAB ABABCADCBA ABABCCAABD ABABCCAADB ABABCCABAD ABABCCABDA ABABCCADAB ABABCCADBA ABABCCDAAB ABABCCDABA ABABCDAABC ABABCDAACB ABABCDABAC ABABCDABCA ABABCDACAB ABABCDACBA ABABCDCAAB ABABCDCABA ABACAABBCD ABACAABBDC ABACAABCBD ABACAABCDB ABACAABDBC ABACAABDCB ABACAADBBC ABACAADBCB ABACABABCD ABACABABDC ABACABACBD ABACABACDB ABACABADBC ABACABADCB ABACABBACD ABACABBADC ABACABBCAD ABACABBCDA ABACABBDAC ABACABBDCA ABACABCABD ABACABCADB ABACABCBAD ABACABCBDA ABACABCDAB ABACABCDBA ABACABDABC ABACABDACB ABACABDBAC ABACABDBCA ABACABDCAB ABACABDCBA ABACADABBC ABACADABCB ABACADBABC ABACADBACB ABACADBBAC ABACADBBCA ABACADBCAB ABACADBCBA ABACBAABCD ABACBAABDC ABACBAACBD ABACBAACDB ABACBAADBC ABACBAADCB ABACBABACD ABACBABADC ABACBABCAD ABACBABCDA ABACBABDAC ABACBABDCA ABACBACABD ABACBACADB ABACBACBAD ABACBACBDA ABACBACDAB ABACBACDBA ABACBADABC ABACBADACB ABACBADBAC ABACBADBCA ABACBADCAB ABACBADCBA ABACBCAABD ABACBCAADB ABACBCABAD ABACBCABDA ABACBCADAB ABACBCADBA ABACBCDAAB ABACBCDABA ABACBDAABC ABACBDAACB ABACBDABAC ABACBDABCA ABACBDACAB ABACBDACBA ABACBDCAAB ABACBDCABA ABACDAABBC ABACDAABCB ABACDABABC ABACDABACB ABACDABBAC ABACDABBCA ABACDABCAB ABACDABCBA ABACDBAABC ABACDBAACB ABACDBABAC ABACDBABCA ABACDBACAB ABACDBACBA ABACDBCAAB ABACDBCABA ABCAAABBCD ABCAAABBDC ABCAAABCBD ABCAAABCDB ABCAAABDBC ABCAAABDCB ABCAAADBBC ABCAAADBCB ABCAABABCD ABCAABABDC ABCAABACBD ABCAABACDB ABCAABADBC ABCAABADCB ABCAABBACD ABCAABBADC ABCAABBCAD ABCAABBCDA ABCAABBDAC ABCAABBDCA ABCAABCABD ABCAABCADB ABCAABCBAD ABCAABCBDA ABCAABCDAB ABCAABCDBA ABCAABDABC ABCAABDACB ABCAABDBAC ABCAABDBCA ABCAABDCAB ABCAABDCBA ABCAADABBC ABCAADABCB ABCAADBABC ABCAADBACB ABCAADBBAC ABCAADBBCA ABCAADBCAB ABCAADBCBA ABCABAABCD ABCABAABDC ABCABAACBD ABCABAACDB ABCABAADBC ABCABAADCB ABCABABACD ABCABABADC ABCABABCAD ABCABABCDA ABCABABDAC ABCABABDCA ABCABACABD ABCABACADB ABCABACBAD ABCABACBDA ABCABACDAB ABCABACDBA ABCABADABC ABCABADACB ABCABADBAC ABCABADBCA ABCABADCAB ABCABADCBA ABCABCAABD ABCABCAADB ABCABCABAD ABCABCABDA ABCABCADAB ABCABCADBA ABCABCDAAB ABCABCDABA ABCABDAABC ABCABDAACB ABCABDABAC ABCABDABCA ABCABDACAB ABCABDACBA ABCABDCAAB ABCABDCABA ABCADAABBC ABCADAABCB ABCADABABC ABCADABACB ABCADABBAC ABCADABBCA ABCADABCAB ABCADABCBA ABCADBAABC ABCADBAACB ABCADBABAC ABCADBABCA ABCADBACAB ABCADBACBA ABCADBCAAB ABCADBCABA ABCDAAABBC ABCDAAABCB ABCDAABABC ABCDAABACB ABCDAABBAC ABCDAABBCA ABCDAABCAB ABCDAABCBA ABCDABAABC ABCDABAACB ABCDABABAC ABCDABABCA ABCDABACAB ABCDABACBA ABCDABCAAB ABCDABCABA
print_ec()
0 steps require 0 blocks and have 1 unique build. 1 step requires 1 block and has 1 unique build. 2 steps require 3 blocks and have 2 unique builds. 3 steps require 6 blocks and have 16 unique builds. 4 steps require 10 blocks and have 768 unique builds. 5 steps require 15 blocks and have 292864 unique builds.
My algorithm computed the first 5 steps in less than 2 seconds, but 6 steps was testing my processing power (>12 hours, still nothing).
The pattern above seems to fit and follow A005118. Using that and A057863, I came up with the following equation for $B(N)$ to represent the number of distinct builds for $N$ steps.
$$B(N) = \frac{\left(\dfrac{N^2 + N}{2}\right)!}{\prod_{k=1}^{N}{\left(2k-1\right)!!}}$$Code can be found here.