من أين تأتي القاعدة في العد اللاحق؟

Question

إذا تسلسل X لديه m رموز إذن X لديه 2^م العواقب المحتملة.

أين القاعدة (2) يأتي من؟

أصل هذا السؤال هو الفقرة التالية:

لقد حصلنا على تسلسلين مرتبين من الرموز، ونرغب في العثور على أطول تسلسل مشترك لـ $X$ و $ص$.

لاحقة ل $X$ انه ببساطة $X$ مع بعض (أو ربما كل أو لا شيء) عن عناصرها.على سبيل المثال، واحدة لاحقة من A; B; C; D; E; F; G سيكون B; C; E; G.

طول أطول بعد شائع من $X$ و $ص$ يعطي مقياس واحد عن مدى تشابه هذين التسلسلين.على سبيل المثال ، إذا كان التسلسل هما أزواج أساسية في خيوط الحمض النووي ، فقد نعتبرهما متشابهين إذا كان لديهم بعد فترة شائعة طويلة.

لو $X$ لديه $م$ الرموز و $ص$ لديه $ن$ رموز إذن $X$ و $ص$ يملك $2^م$ و $2^ن$ إمكانية إمكانية على التوالي.

Answer 1

يمكنك التفكير في نتيجة لاحقة $ص$ ل $X$ باعتبارها ناقلات مميزة $\chi_Y$ التي لديها $م$ عناصر، عنصر واحد لكل عنصر $X$.ال $i$-العنصر $\chi_Y$ يكون $1$ إذا $i$-العنصر $X$ هو أيضا في $ص$ و $0$ خلاف ذلك.

من السهل أن نرى أن هذا ازدراء:كل لاحقة $ص$ لديه ناقلات مميزة مميزة $\chi_Y$, ، وكل ناقل مميز $\chi_Y$ يرتبط بتسلسل مميز $ص$.

وهذا يعني أن عدد التبعيات $ص$ يساوي عدد المتجهات $\chi_Y$.منذ كل ناقلات $\chi_Y$ لديه $م$ العناصر، كل منها يمكن أن يكون واحدا من $2$ القيم الممكنة، هذا الرقم هو $2^م$.

مثال ملموس للتسلسل $X$, ، لاحقة $ص$, ، وناقلها المميز $\chi_Y$ هو ما يلي: