Permutations of a binary search tree of height x

"How many permutations exist for a binary search tree with eight elements with a tree of height five?"

Recently I needed to determine the number of permutations that exist for a given input into a binary search tree with a height of x.  There are algorithms to determine this, but doing them by hand is tedious and error-prone, and I wasn't able to find a table online to check my answers against.  I wrote a small program to test all combinations for a given input; below are the resulting tables.

Elements (Rows), Tree Height (Columns), Permutations (Cells)

	1	2	3	4	5	6	7	8	9	10	11	12
2	2	0	0	0	0	0	0	0	0	0	0	0
3	2	4	0	0	0	0	0	0	0	0	0	0
4	0	16	8	0	0	0	0	0	0	0	0	0
5	0	40	64	16	0	0	0	0	0	0	0	0
6	0	80	400	208	32	0	0	0	0	0	0	0
7	0	80	2240	2048	608	64	0	0	0	0	0	0
8	0	0	11360	18816	8352	1664	128	0	0	0	0	0
9	0	0	55040	168768	104448	30016	4352	256	0	0	0	0
10	0	0	253440	1508032	1277568	479040	99200	11008	512	0	0	0
11	0	0	1056000	13501312	15727232	7345536	1950080	308480	27136	1024	0	0
12	0	0	3801600	121362560	197163648	112255360	36141952	7293440	915456	65536	2048	0

So, if one asks "How many permutations exist for a binary search tree with eight elements with a tree of height five?", you look up in the table and find that there are 8352 permutations possible.

Part of the process for determining the total permutations is to break the problem down.  You do this by computing the number of permutations with a given root value, and add all of the totals with a set root to come to the total number of permutations.  Below are the per-root tables.

Rows are height, columns are root values, cells are permutations.

Three Elements: {1,2,3}

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
Height at 0 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Height at 1 (total 2)	0	0	2	0	0	0	0	0	0	0	0	0	0	0
Height at 2 (total 4)	0	2	0	2	0	0	0	0	0	0	0	0	0	0
Height at 3 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0

Four Elements: {1,2,3,4}  

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
Height at 0 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Height at 1 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Height at 2 (total 16)	0	2	6	6	2	0	0	0	0	0	0	0	0	0
Height at 3 (total 8)	0	4	0	0	4	0	0	0	0	0	0	0	0	0
Height at 4 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0

Five Elements: {1,2,3,4,5}  

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
Height at 0 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Height at 1 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Height at 2 (total 40)	0	0	8	24	8	0	0	0	0	0	0	0	0	0
Height at 3 (total 64)	0	16	16	0	16	16	0	0	0	0	0	0	0	0
Height at 4 (total 16)	0	8	0	0	0	8	0	0	0	0	0	0	0	0
Height at 5 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0

Six Elements: {1,2,3,4,5,6}  

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
Height at 0 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Height at 1 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Height at 2 (total 80)	0	0	0	40	40	0	0	0	0	0	0	0	0	0
Height at 3 (total 400)	0	40	80	80	80	80	40	0	0	0	0	0	0	0
Height at 4 (total 208)	0	64	40	0	0	40	64	0	0	0	0	0	0	0
Height at 5 (total 32)	0	16	0	0	0	0	16	0	0	0	0	0	0	0
Height at 6 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0

Seven Elements: {1,2,3,4,5,6,7}  

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
Height at 0 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Height at 1 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Height at 2 (total 80)	0	0	0	0	80	0	0	0	0	0	0	0	0	0
Height at 3 (total 2240)	0	80	240	480	640	480	240	80	0	0	0	0	0	0
Height at 4 (total 2048)	0	400	384	240	0	240	384	400	0	0	0	0	0	0
Height at 5 (total 608)	0	208	96	0	0	0	96	208	0	0	0	0	0	0
Height at 6 (total 64)	0	32	0	0	0	0	0	32	0	0	0	0	0	0
Height at 7 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0

Eight Elements: {1,2,3,4,5,6,7,8}  

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
Height at 0 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Height at 1 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Height at 2 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Height at 3 (total 11360)	0	80	560	1680	3360	3360	1680	560	80	0	0	0	0	0
Height at 4 (total 18816)	0	2240	2800	2688	1680	1680	2688	2800	2240	0	0	0	0	0
Height at 5 (total 8352)	0	2048	1456	672	0	0	672	1456	2048	0	0	0	0	0
Height at 6 (total 1664)	0	608	224	0	0	0	0	224	608	0	0	0	0	0
Height at 7 (total 128)	0	64	0	0	0	0	0	0	64	0	0	0	0	0
Height at 8 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0

Nine Elements: {1,2,3,4,5,6,7,8,9}  

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
Height at 0 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Height at 1 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Height at 2 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Height at 3 (total 55040)	0	0	640	4480	13440	17920	13440	4480	640	0	0	0	0	0
Height at 4 (total 168768)	0	11360	17920	22400	21504	22400	21504	22400	17920	11360	0	0	0	0
Height at 5 (total 104448)	0	18816	16384	11648	5376	0	5376	11648	16384	18816	0	0	0	0
Height at 6 (total 30016)	0	8352	4864	1792	0	0	0	1792	4864	8352	0	0	0	0
Height at 7 (total 4352)	0	1664	512	0	0	0	0	0	512	1664	0	0	0	0
Height at 8 (total 256)	0	128	0	0	0	0	0	0	0	128	0	0	0	0
Height at 9 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0

Ten Elements: {1,2,3,4,5,6,7,8,9,10}  

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
Height at 0 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Height at 1 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Height at 2 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Height at 3 (total 253440)	0	0	0	5760	40320	80640	80640	40320	5760	0	0	0	0	0
Height at 4 (total 1508032)	0	55040	102240	161280	201600	233856	233856	201600	161280	102240	55040	0	0	0
Height at 5 (total 1277568)	0	168768	169344	147456	104832	48384	48384	104832	147456	169344	168768	0	0	0
Height at 6 (total 479040)	0	104448	75168	43776	16128	0	0	16128	43776	75168	104448	0	0	0
Height at 7 (total 99200)	0	30016	14976	4608	0	0	0	0	4608	14976	30016	0	0	0
Height at 8 (total 11008)	0	4352	1152	0	0	0	0	0	0	1152	4352	0	0	0
Height at 9 (total 512)	0	256	0	0	0	0	0	0	0	0	256	0	0	0
Height at 10 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0

Eleven Elements: {1,2,3,4,5,6,7,8,9,10,11}  

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
Height at 0 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Height at 1 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Height at 2 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Height at 3 (total 1056000)	0	0	0	0	57600	268800	403200	268800	57600	0	0	0	0	0
Height at 4 (total 13501312)	0	253440	550400	1022400	1612800	2150400	2322432	2150400	1612800	1022400	550400	253440	0	0
Height at 5 (total 15727232)	0	1508032	1687680	1693440	1474560	1048320	903168	1048320	1474560	1693440	1687680	1508032	0	0
Height at 6 (total 7345536)	0	1277568	1044480	751680	437760	161280	0	161280	437760	751680	1044480	1277568	0	0
Height at 7 (total 1950080)	0	479040	300160	149760	46080	0	0	0	46080	149760	300160	479040	0	0
Height at 8 (total 308480)	0	99200	43520	11520	0	0	0	0	0	11520	43520	99200	0	0
Height at 9 (total 27136)	0	11008	2560	0	0	0	0	0	0	0	2560	11008	0	0
Height at 10 (total 1024)	0	512	0	0	0	0	0	0	0	0	0	512	0	0
Height at 11 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0

Twelve Elements: {1,2,3,4,5,6,7,8,9,10,11,12}  

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
Height at 0 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Height at 1 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Height at 2 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Height at 3 (total 3801600)	0	0	0	0	0	422400	1478400	1478400	422400	0	0	0	0	0
Height at 4 (total 121362560)	0	1056000	2787840	6054400	11246400	17952000	21584640	21584640	17952000	11246400	6054400	2787840	1056000	0
Height at 5 (total 197163648)	0	13501312	16588352	18564480	18627840	16220160	15079680	15079680	16220160	18627840	18564480	16588352	13501312	0
Height at 6 (total 112255360)	0	15727232	14053248	11489280	8268480	4815360	1774080	1774080	4815360	8268480	11489280	14053248	15727232	0
Height at 7 (total 36141952)	0	7345536	5269440	3301760	1647360	506880	0	0	506880	1647360	3301760	5269440	7345536	0
Height at 8 (total 7293440)	0	1950080	1091200	478720	126720	0	0	0	0	126720	478720	1091200	1950080	0
Height at 9 (total 915456)	0	308480	121088	28160	0	0	0	0	0	0	28160	121088	308480	0
Height at 10 (total 65536)	0	27136	5632	0	0	0	0	0	0	0	0	5632	27136	0
Height at 11 (total 2048)	0	1024	0	0	0	0	0	0	0	0	0	0	1024	0
Height at 12 (total 0)	0	0	0	0	0	0	0	0	0	0	0	0	0	0