โจทย์ต้นไม้

[นายสบาย]

โจทย์ จะมีกี่วิธีที่จำนวนเต็มบวกตั้งแต่ 1 ถึง n ไปใส่ในในต้นไม้โดยที่สอดคล้องกับสมบัติที่ว่า ทุกๆรากของต้นไม้ A ต้องมากกว่า B และ C เสมอ (ภาพประกอบด้านซ้าย)

มาเพื่อนเอามาให้ช่วยคิด ไม่รู้ว่าคิดยังไงเหมือนกันคับ

[MINGA]

$n!$ ครับ วิธีการคิดก็คือ ใส่ตัวเลขจากมากไปน้อยครับ
$n$ ใส่ได้ที่เดียว, $n-1$ ใส่ได้สองที่,...,$1$ ใส่ได้ $n$ ตำแหน่งครับ

[นายสบาย]

ข้อความเดิมเขียนโดยคุณ MINGA

$n!$ ครับ วิธีการคิดก็คือ ใส่ตัวเลขจากมากไปน้อยครับ
$n$ ใส่ได้ที่เดียว, $n-1$ ใส่ได้สองที่,...,$1$ ใส่ได้ $n$ ตำแหน่งครับ

1 นี่ใส่ได้ทุก $n$ ตำแหน่งเลยหรอคับ ที่ตำแหน่งบน ถ้าใส่ 1 ก็ขัดกับสมบัติของต้นไม้นิคับ

[polsk133]

ไม่เข้าใจโจทย์ครับว่า แต่ละตัวต้องมีราก2รากเท่านั้นหรอครับ แบบนี้ n=2 ได้0วิธีใช่ไหมครับ เพราะใส่ช่องบนสุด2 ช่องลงมามีแค่1ช่อง ใส่ไม่ได้

[MINGA]

ข้อความเดิมเขียนโดยคุณ นายสบาย

1 นี่ใส่ได้ทุก $n$ ตำแหน่งเลยหรอคับ ที่ตำแหน่งบน ถ้าใส่ 1 ก็ขัดกับสมบัติของต้นไม้นิคับ

ผมเข้าใจว่าทุกจุดไม่จำเป็นต้องมีกิ่งสองกิ่งครบ ลองดูตัวอย่าง n=3
3 - ต้องใส่ตำแหน่งบนสุด
2 - ใส่ได้สองตำแหน่ง ซ้ายหรือขวาของเลข 3
1 - ใส่ได้สามตำแหน่ง ซ้ายหรือขวาของ 2 หรือ ต่อข้างล่าง 1

[นายสบาย]

ข้อความเดิมเขียนโดยคุณ polsk133

ไม่เข้าใจโจทย์ครับว่า แต่ละตัวต้องมีราก2รากเท่านั้นหรอครับ แบบนี้ n=2 ได้0วิธีใช่ไหมครับ เพราะใส่ช่องบนสุด2 ช่องลงมามีแค่1ช่อง ใส่ไม่ได้

คือที่ผมเข้าใจตอนแรก คือ รากที่แตกออกมาต้องมีสองรากเสมอ
แต่ที่ท่าน MINGA ตอบคงถูกละคับ จะแตกรากไปทางไหนก็ได้

ข้อความเดิมเขียนโดยคุณ MINGA

ผมเข้าใจว่าทุกจุดไม่จำเป็นต้องมีกิ่งสองกิ่งครบ ลองดูตัวอย่าง n=3
3 - ต้องใส่ตำแหน่งบนสุด
2 - ใส่ได้สองตำแหน่ง ซ้ายหรือขวาของเลข 3
1 - ใส่ได้สามตำแหน่ง ซ้ายหรือขวาของ 2 หรือ ต่อข้างล่าง 1

ขอบคุณครับ

[นายสบาย]

ไปเจอคำตอบมาแล้วคับ

โจทย์ต้นไม้นี่คล้ายๆกับโจทย์พวกคอมพิวเตอร์เลย คำตอบก็ตามนี่เลย ลิงค์