أوجد الشروط الواجب توافرها لـ n و h لكي نتمكن من رسم الشجر ثم أوجد عدد طرق الرسم من دون تكرار .
مثال : عندما n=5 و h=3 سنرسم الشجرة:
- لا تعليق
- untitled2.GIF (4.65 KiB) شوهد 728 مرات
أنظر : هناك رسمان فقط يمكن رسمهما ( كل رسم يحتوي 5 نقاط و ارتفاعه 3 ، كل فرع يخرج منه نقطتان أو لا تخرج منه نقطة)
تم إضافة السؤال مع بعض التعديل بتاريخ 15\10\2009
و أصغر من 
.
![\[
\begin{array}{l}
2h - 1 \le n \le 2^h - 1 \\
\\
n\,\,is\,\,odd \\
\\
Let \\
f\left( {p,q} \right) = \left\{ \begin{array}{l}
\left( \begin{array}{l}
p \\
q \\
\end{array} \right)\,\,\,\,\,\,\,if\,\,\,0 \le p \le q \\
0\,\,\,\,\,\,\,\,\,\,\,\,\,\,otherwise \\
\end{array} \right. \\
\\
u = 2^{h - 2} \\
\\
r = \frac{1}{2}\left( {4u - n - 1} \right) \\
\\
Then \\
\\
for\,\,\,any\,\,h\,\,,\,\,n \\
\\
if\,\,\underline{\underline {\,\underline{\underline {\,\left( {\,r \le 6\,} \right)}} }} \,\,\,then\,\,\,number\,\,of\,\,\,different\,\,\,graphs\,\,m_r \,\,\,shall\,\,be \\
\\
m_r = f\left( {u,r} \right) + f\left( {\frac{u}{2},1} \right)f\left( {u - 2,r - 3} \right) + f\left( {\frac{u}{2},2} \right)f\left( {u - 2,r - 6} \right) \\
\end{array}
\]](/xyz/latexrender/pictures/702162f1f0b3cd1cec6d5903c98dbd04.png "\[
\begin{array}{l}
2h - 1 \le n \le 2^h - 1 \\
\\
n\,\,is\,\,odd \\
\\
Let \\
f\left( {p,q} \right) = \left\{ \begin{array}{l}
\left( \begin{array}{l}
p \\
q \\
\end{array} \right)\,\,\,\,\,\,\,if\,\,\,0 \le p \le q \\
0\,\,\,\,\,\,\,\,\,\,\,\,\,\,otherwise \\
\end{array} \right. \\
\\
u = 2^{h - 2} \\
\\
r = \frac{1}{2}\left( {4u - n - 1} \right) \\
\\
Then \\
\\
for\,\,\,any\,\,h\,\,,\,\,n \\
\\
if\,\,\underline{\underline {\,\underline{\underline {\,\left( {\,r \le 6\,} \right)}} }} \,\,\,then\,\,\,number\,\,of\,\,\,different\,\,\,graphs\,\,m_r \,\,\,shall\,\,be \\
\\
m_r = f\left( {u,r} \right) + f\left( {\frac{u}{2},1} \right)f\left( {u - 2,r - 3} \right) + f\left( {\frac{u}{2},2} \right)f\left( {u - 2,r - 6} \right) \\
\end{array}
\]")
![\[
h = 5
\]](/xyz/latexrender/pictures/830e2c84dcb49e9560ac8c46e8a77ebe.png "\[
h = 5
\]")
أي لدينا 5 مستويات ![\[
S_{21}
\]](/xyz/latexrender/pictures/2b8b9718c7458b7d97fab08e4fc32ce0.png "\[
S_{21}
\]")
![\[
S_{21} = 1
\]](/xyz/latexrender/pictures/44977820404c7a6762161c7fae915a9e.png "\[
S_{21} = 1
\]")
![\[
S_{31} ,S_{32}
\]](/xyz/latexrender/pictures/fd3d2f2308d33037cb895bee4e16229b.png "\[
S_{31} ,S_{32}
\]")
![\[
S_{31} \left( {S_{31} - 1} \right) = 0
\]](/xyz/latexrender/pictures/30cf6373ac89effd29734f19a6d4ac11.png "\[
S_{31} \left( {S_{31} - 1} \right) = 0
\]")
![\[
S_{32} \left( {S_{32} - 1} \right) = 0
\]](/xyz/latexrender/pictures/bb5130d4d09a64178c3d81dee8f3acc8.png "\[
S_{32} \left( {S_{32} - 1} \right) = 0
\]")
![\[
S_{41} \left( {S_{41} - S_{31} } \right) = 0
\]](/xyz/latexrender/pictures/d817fcf66183791d2a8a1a70b2e4c66b.png "\[
S_{41} \left( {S_{41} - S_{31} } \right) = 0
\]")
![\[
S_{42} \left( {S_{42} - S_{31} } \right) = 0
\]](/xyz/latexrender/pictures/a3fd30f158026b7e4f83fe9a3e9d0000.png "\[
S_{42} \left( {S_{42} - S_{31} } \right) = 0
\]")
![\[
S_{43} \left( {S_{43} - S_{32} } \right) = 0
\]](/xyz/latexrender/pictures/93beb59a90db57ea2c885d9a687e8401.png "\[
S_{43} \left( {S_{43} - S_{32} } \right) = 0
\]")
![\[
S_{44} \left( {S_{44} - S_{32} } \right) = 0
\]](/xyz/latexrender/pictures/4c94dc11f58561e46b92c0da80c8048c.png "\[
S_{44} \left( {S_{44} - S_{32} } \right) = 0
\]")
![\[
S_{51} \left( {S_{51} - S_{41} } \right) = 0
\]](/xyz/latexrender/pictures/376f4cb8d8b458eba329f0873b9466a9.png "\[
S_{51} \left( {S_{51} - S_{41} } \right) = 0
\]")
![\[
S_{52} \left( {S_{52} - S_{41} } \right) = 0
\]](/xyz/latexrender/pictures/e85b32ce9d5ef54a62442bcc8f1f25b8.png "\[
S_{52} \left( {S_{52} - S_{41} } \right) = 0
\]")
![\[
S_{53} \left( {S_{53} - S_{42} } \right) = 0
\]](/xyz/latexrender/pictures/f393d752da59b4937829c74f76e92529.png "\[
S_{53} \left( {S_{53} - S_{42} } \right) = 0
\]")
![\[
S_{54} \left( {S_{54} - S_{42} } \right) = 0
\]](/xyz/latexrender/pictures/e9805f7cceb8f6aff715a505e17d9235.png "\[
S_{54} \left( {S_{54} - S_{42} } \right) = 0
\]")
![\[
S_{55} \left( {S_{55} - S_{43} } \right) = 0
\]](/xyz/latexrender/pictures/709f15d3c439cbc610768f311e34c3b7.png "\[
S_{55} \left( {S_{55} - S_{43} } \right) = 0
\]")
![\[
S_{56} \left( {S_{56} - S_{43} } \right) = 0
\]](/xyz/latexrender/pictures/60319c9b32f9a7be54d6da52dc89e5c3.png "\[
S_{56} \left( {S_{56} - S_{43} } \right) = 0
\]")
![\[
S_{57} \left( {S_{57} - S_{44} } \right) = 0
\]](/xyz/latexrender/pictures/f1a26e0688f1822761f744eb521d829c.png "\[
S_{57} \left( {S_{57} - S_{44} } \right) = 0
\]")
![\[
S_{58} \left( {S_{58} - S_{44} } \right) = 0
\]](/xyz/latexrender/pictures/b885b962dd25722e5be743065d3a1177.png "\[
S_{58} \left( {S_{58} - S_{44} } \right) = 0
\]")
![\[
\begin{array}{l}
a_1 = \left( {S_{31} + S_{41} + S_{51} - 3} \right) \\
a_2 = \left( {S_{31} + S_{41} + S_{52} - 3} \right) \\
a_3 = \left( {S_{31} + S_{42} + S_{53} - 3} \right) \\
a_4 = \left( {S_{31} + S_{42} + S_{54} - 3} \right) \\
a_5 = \left( {S_{32} + S_{43} + S_{55} - 3} \right) \\
a_6 = \left( {S_{32} + S_{43} + S_{56} - 3} \right) \\
a_7 = \left( {S_{32} + S_{44} + S_{57} - 3} \right) \\
a_8 = \left( {S_{32} + S_{44} + S_{58} - 3} \right) \\
\end{array}
\]](/xyz/latexrender/pictures/9298c3e37b00af9aa4ae38edbe89126a.png "\[
\begin{array}{l}
a_1 = \left( {S_{31} + S_{41} + S_{51} - 3} \right) \\
a_2 = \left( {S_{31} + S_{41} + S_{52} - 3} \right) \\
a_3 = \left( {S_{31} + S_{42} + S_{53} - 3} \right) \\
a_4 = \left( {S_{31} + S_{42} + S_{54} - 3} \right) \\
a_5 = \left( {S_{32} + S_{43} + S_{55} - 3} \right) \\
a_6 = \left( {S_{32} + S_{43} + S_{56} - 3} \right) \\
a_7 = \left( {S_{32} + S_{44} + S_{57} - 3} \right) \\
a_8 = \left( {S_{32} + S_{44} + S_{58} - 3} \right) \\
\end{array}
\]")
![\[
a_1 a_2 a_3 a_4 a_5 a_6 a_7 a_8 = 0
\]](/xyz/latexrender/pictures/db77d74f56d6eb14dbe40e3a480c3469.png "\[
a_1 a_2 a_3 a_4 a_5 a_6 a_7 a_8 = 0
\]")
![\[
\begin{array}{l}
S_{31} + S_{32} + S_{41} + S_{42} + S_{43} + S_{44} + S_{51} + S_{52} + \\
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, + S_{53} + S_{54} + S_{55} + S_{56} + S_{57} + S_{58} = \frac{{n - 3}}{2} \\
\end{array}
\]](/xyz/latexrender/pictures/1b33d17c287f60b3166cf1aeaf1dfb75.png "\[
\begin{array}{l}
S_{31} + S_{32} + S_{41} + S_{42} + S_{43} + S_{44} + S_{51} + S_{52} + \\
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, + S_{53} + S_{54} + S_{55} + S_{56} + S_{57} + S_{58} = \frac{{n - 3}}{2} \\
\end{array}
\]")
