مقالات

6.3: نظرية تعداد بوليا ريدفيلد - رياضيات


طور جورج بوليا وروبرت ريدفيلد بشكل مستقل نظرية لتوليد الوظائف التي تصف عمل المجموعة G على ألوان مجموعة S بواسطة مجموعة T عندما نعرف أن عمل G على S. المعرض ، وهكذا أصبح الموضوع معروفًا على نطاق واسع باسم نظرية بوليا ، على الرغم من أن نظرية بوليا ريدفيلد ستكون اسمًا أفضل. في هذا القسم نطور عناصر هذه النظرية.

الشكل 6.7: رسم بياني على ستة رؤوس.

فكرة تلوين مجموعة S لها العديد من التطبيقات. على سبيل المثال ، قد تكون المجموعة S هي المواضع في جزيء الهيدروكربون التي يشغلها الهيدروجين ، ويمكن أن تكون المجموعة مجموعة التماثلات المكانية للجزيء (أي مجموعة التباديل لذرات الجزيء التي تحرك حول الجزيء بحيث لا يمكن تمييز الجزيء في موضعه النهائي عن الجزيء الأصلي). يمكن بعد ذلك أن تكون الألوان جذرية (بما في ذلك الهيدروجين نفسه) يمكننا استبدالها بكل موضع هيدروجين في الجزيء. ثم يكون عدد مدارات الألوان هو عدد المركبات المختلفة كيميائيًا التي يمكننا إنشاؤها باستخدام هذه البدائل.

في الشكل 6.8 نعرض طريقتين مختلفتين لاستبدال ذرة الهيدروجين بجذر OH في الرسم البياني الكيميائي الذي قدمناه للبيوتان في الفصل 2. قمنا بتلوين رأس واحد من الدرجة 1 بجذر OH والباقي بالذرة H. هناك طريقتان مختلفتان فقط للقيام بذلك ، حيث يجب أن يتصل OH بـ "طرف" C أو "وسط" C. وهذا يوضح أن هناك شكلين مختلفين ، يُطلق عليهما أيزومرات للمركب المعروض. يُعرف هذا المركب باسم كحول البوتيل.

الشكل 6.8: الأيزومرين المختلفين لكحول البوتيل.

ملحوظة

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

لذا فكر بشكل حدسي في بعض "الشخصيات" التي تحتوي على أماكن لتلوينها. (فكر في وجوه المكعب ، والخرز على العقد ، والدوائر عند رؤوس n-gon ، وما إلى ذلك) كيف يمكننا تصوير التلوين؟ إذا قمنا بترقيم الأماكن المراد تلوينها ، لنقل من 1 إلى n ، فلدينا طريقة قياسية لتمثيل التلوين الخاص بنا. على سبيل المثال ، إذا كانت ألواننا هي الأزرق والأخضر والأحمر ، فإن (BBGRRGBG ) يصف تلوينًا نموذجيًا لثمانية أماكن من هذا القبيل. ما لم يتم ترقيم الأماكن بطريقة ما "بشكل طبيعي" ، فإن فكرة التلوين هذه تفرض بنية غير موجودة بالفعل. حتى لو كان الهيكل موجودًا ، فإن تصور ألواننا بهذه الطريقة لا "يجمع" أي سمات مشتركة للألوان المختلفة ؛ نحن ببساطة نتخيل كل الألوان الممكنة. لدينا مجموعة (فكر في الأمر على أنها تناسق في الشكل الذي تتخيله) تعمل على الأماكن. ثم تعمل تلك المجموعة بطريقة طبيعية على تلوين الأماكن ونحن مهتمون بمدارات الألوان. وبالتالي نريد صورة تجمع السمات المشتركة للألوان في مدار. تتمثل إحدى طرق تجميع أوجه التشابه بين الألوان في ترك الحروف التي نستخدمها كصور للألوان تنتقل كما فعلنا مع صورنا في الفصل 4 ؛ ثم تصبح صورتنا (BBGRRGBG ) (B ^ 3G ^ 3R ^ 2 ) ، لذا فإن صورتنا الآن تسجل ببساطة عدد المرات التي نستخدم فيها كل لون. فكر في الطريقة التي حددنا بها عمل المجموعة على ألوان المجموعة التي تعمل عليها المجموعة. ستلاحظ أن التمثيل باستخدام عنصر المجموعة لن يغير عدد مرات استخدام كل لون ؛ إنه ببساطة ينقل الألوان إلى أماكن مختلفة. وبالتالي فإن الصورة التي لدينا الآن لتلوين معين هي صورة مناسبة بنفس القدر لكل تلوين في مدار. أحد الأسئلة الطبيعية التي يجب طرحها هو "كم عدد المدارات التي لها صورة معينة؟"

تمرين 310

لنفترض أننا رسمنا دوائر متطابقة عند رؤوس شكل سداسي منتظم. لنفترض أننا قمنا بتلوين هذه الدوائر بلونين ، أحمر وأزرق.

  1. ما عدد الطرق التي يمكننا من خلالها تلوين المجموعة {1 ، 2 ، 3 ، 4 ، 5 ، 6} باستخدام الألوان الأحمر والأزرق؟
  2. يتم تقسيم هذه الألوان إلى مدارات من خلال عمل مجموعة الدوران على السداسي. باستخدام تدويننا القياسي ، اكتب كل هذه المدارات ولاحظ عدد المدارات التي تحتوي على كل صورة ، بافتراض أن صورة التلوين هي نتاج متغيرات التنقل التي تمثل الألوان.
  3. باستخدام وظيفة الصورة للجزء السابق ، قم بتدوين عداد الصورة لمدارات ألوان رؤوس الشكل السداسي تحت تأثير مجموعة الدوران.

في المسألة 310 ج ، رأينا عداد صور لصور مدارات حركة مجموعة على ألوان. على النحو الوارد أعلاه ، نسأل عن عدد مدارات الألوان التي تحتوي على أي صورة معينة. يمكننا التفكير في دالة توليد متعددة المتغيرات تكون فيها الأحرف التي نستخدمها لتصوير الألوان الفردية هي المتغيرات ، ويكون معامل الصورة هو عدد المدارات التي تحتوي على تلك الصورة. توفر وظيفة التوليد هذه إجابة لسؤالنا الطبيعي ، وبالتالي فإن هذا النوع من وظيفة التوليد التي سنسعى إليها. نظرًا لأن نظرية CFB كانت أداتنا الأساسية لتحديد عدد المدارات التي لدينا ، فمن المنطقي التفكير فيما إذا كانت نظرية CFB لها نظير من حيث صور المدارات.

6.3.1 نظرية النقطة الثابتة المدارية

نظرية النقطة الثابتة المدارية

لنفترض الآن أن لدينا مجموعة G تعمل على مجموعة ولدينا وظيفة صورة على تلك المجموعة مع الميزة الإضافية التي لكل مدار من مدار المجموعة ، كل عناصرها لها نفس الصورة. في هذا الظرف نحدد صورة المدار أو المدار المتعدد ليكون صورة أي فرد من أعضائه. عداد المدار Orb (G ، S) هو مجموع صور المدارات. (لاحظ أن هذا هو نفس مجموع صور multiorbits.) عداد النقطة الثابتة Fix (G ، S) هو مجموع صور كل نقطة من النقاط الثابتة لكل عنصر من عناصر G. سنقوم ببناء دالة توليد تناظرية لنظرية CFB. كانت الفكرة الرئيسية لإثبات نظرية CFB هي محاولة حساب عدد العناصر بطريقتين مختلفتين (أي مجموع كل تعدد العناصر) في اتحاد كل multiorbits من مجموعة تعمل على مجموعة. لنفترض بدلاً من ذلك أننا نحاول حساب مجموع كل صور جميع العناصر في اتحاد العادات المتعددة لمجموعة تعمل على مجموعة. بالتفكير في كيفية ارتباط هذا المجموع بـ Orb (G ، S) و Fix (G ، S) ، ابحث عن نظير لنظرية CFB التي تربط هذين العددين. دولة وإثبات هذه النظرية.

سوف نسمي نظرية المشكلة 311 نظرية النقطة الثابتة المدارية. من أجل تطبيق نظرية النقطة الثابتة المدارية ، نحتاج إلى بعض الحقائق الأساسية حول عدادات الصور.

تمرين 312

افترض أن P1 و P2 عبارة عن وظائف صور في المجموعتين S1 و S2 بمعنى القسم 4.1.2. حدد P على S1 × S2 بواسطة P (x1، x2) = P1 (x1) P2 (x2). كيف ترتبط EP1 و EP1 و EP؟ (ربما تكون قد فعلت هذه المشكلة بالفعل في سياق آخر!)

تمرين 313

افترض أن Pi هي وظيفة صورة على مجموعة Si لـ i = 1 ،. ، ك. نحدد صورة k-tuple (x1، x2،.، xk) لتكون نتاج صور عناصرها ، أي Pb ((x1، x2،. xk)) = Y ki = 1 Pi (xi) . كيف يرتبط عداد الصورة EPb للمجموعة S1 × S2 × · · × Sk لجميع مجموعات k مع xi ∈ Si بعدادات الصور للمجموعات Si؟ في الحالة الخاصة التي يكون فيها Si = S لجميع i و Pi = P لكل i ، ما هو EPb (S k)؟

ممارسه الرياضه

• 314. استخدم نظرية النقطة الثابتة المدارية لتحديد عدّاد المدار للتلوين ، مع لونين (أحمر وأزرق) ، لست دوائر موضوعة عند رؤوس شكل سداسي يكون حرًا للتحرك في المستوى. قارن معاملات كثير الحدود الناتج مع المدارات المختلفة التي وجدتها في المسألة 310. 315. أوجد دالة التوليد (في المتغيرات R ، B) لتلوين وجوه المكعب بلونين (أحمر وأزرق). ماذا تخبرك وظيفة التوليد عن عدد طرق تلوين المكعب (حتى الحركة المكانية) بمجموعات مختلفة من اللونين؟

6.3.2 نظرية بوليا ريدفيلد

تتعامل نظرية تعداد بوليا (وريدفيلد) الشهيرة مع مواقف مثل تلك الموجودة في المسألتين 314 و 315 حيث نريد وظيفة توليد لمجموعة كل الألوان مجموعة S باستخدام مجموعة T من الألوان ، حيث تكون صورة التلوين هي منتج متعدد الألوان التي يستخدمها. نحن نفكر مرة أخرى في الألوان كمتغيرات. تتمثل نقطة السلسلة التالية من المشكلات في تحليل الحلول للمسألتين 314 و 315 لمعرفة ما رآه Pólya و Redfield (على الرغم من أنهما لم يروه في هذا الترميز أو باستخدام هذا المصطلح).

تمرين 316.

في المسألة 314 ، لدينا أربعة أنواع من عناصر المجموعة: الهوية (التي تحدد كل تلوين) ، والدوران خلال 60 أو 300 درجة ، والدوران خلال 120 و 240 درجة ، والدوران خلال 180 درجة. عداد النقطة الثابتة لمجموعة الدوران التي تعمل على تلوينات الشكل السداسي هو بحكم التعريف مجموع عدادات النقاط الثابتة للألوان التي تم تحديدها من خلال الهوية ، للألوان المثبتة بدورات 60 أو 300 درجة ، للألوان المثبتة بـ 120 أو 240 درجة تناوب ، وألوان ثابتة بزاوية 180 درجة. إلى الحد الذي لم تفعله بالفعل في مشكلة سابقة ، قم بتدوين كل من هؤلاء العدادين (واحد لكل نوع من التقليب) على حدة وعامل كل واحد (فوق الأعداد الصحيحة) بالكامل قدر الإمكان. 317. في المسألة 315 لدينا خمسة أنواع مختلفة من عناصر المجموعة. لكل نوع من العناصر ، إلى الحد الذي لم تقم به بالفعل في مشكلة سابقة ، قم بتدوين عداد النقاط الثابتة للعناصر من هذا النوع. حلل العدادين إلى عوامل كاملة قدر الإمكان.

تمرين 318

في المسألة 316 ، كل "نوع" من عناصر المجموعة له "نوع" من بنية الحلقة. على سبيل المثال ، الدوران بمقدار 180 درجة له ​​ثلاث دورات من الحجم الثاني. ما هو نوع تحلل الدورة الذي يمتلكه الدوران بمقدار 60 أو 300 درجة؟ ما هو نوع تحلل الدورة الذي يمتلكه الدوران خلال 120 أو 240 درجة؟ ناقش العلاقة بين هياكل الدورة والعداد المعامل للنقاط الثابتة للتباديل في المشكلة 316. تذكر أننا قلنا أن مجموعة من التباديل تعمل على مجموعة S إذا كان لكل عضو σ من G تبديل σ من S مثل أن σ ◦ ϕ = σ ◦ ϕ لجميع الأعضاء σ و من G. نظرًا لأن σ هي تبديل لـ S ، σ لها تحلل دورة كتقليب لـ S (وأيًا كان تحللها في مجموعة التقليب الأصلية ز).

تمرين 319

في المسألة 317 ، كل "نوع" من عناصر المجموعة له "نوع" من التحلل الدائري في عمل مجموعة دوران المكعب على وجوه المكعب. على سبيل المثال ، دوران المكعب خلال 180 درجة حول محور عمودي من خلال مراكز الوجوه العلوية والسفلية له دورتان بالحجم الثاني ودورتان بالحجم الأول.

إلى الحد الذي لم تفعله بالفعل في مشكلة سابقة ، أجب عن الأسئلة التالية. كم عدد هذه الدورات التي تمتلكها المجموعة؟ ما هي "الأنواع" الأخرى من عناصر المجموعة ، وما هي هياكل دائرتها؟ ناقش العلاقة بين تحلل الدورة وعداد العداد في المسألة 317. • 320. الطريقة المعتادة لوصف نظرية تعداد Pólya-Redfield تتضمن "مؤشر الدورة" أو "مؤشر الدورة" لمجموعة تعمل على مجموعة. لنفترض أن لدينا مجموعة G تعمل على مجموعة محدودة S. نظرًا لأن كل عنصر مجموعة σ يعطينا تبديلًا σ لـ S ، على هذا النحو فإنه يتحلل إلى دورات منفصلة كتقليب لـ S. لنفترض أن σ لديه دورات c1 من الحجم 1 ، دورات c2 من الحجم 2 ، ... ، دورات cn ذات الحجم n. إذن دورة أحادية الحدود هي z (σ) = z c1 1 z c2 2 · · · z cn n. مؤشر الدورة أو مؤشر دورة G الذي يعمل على S هو Z (G ، S) = 1 | G | X σ: σ∈G z (σ). • (أ) ما هو دليل دورة المجموعة D6 الذي يعمل على رؤوس شكل سداسي؟ (ب) ما هو مؤشر الدورة لمجموعة دورات المكعب التي تعمل على أوجه المكعب؟

تمرين 312: نظرية العد

كيف يمكنك حساب Orbit Enumerator لـ G الذي يعمل على تلوين S بواسطة مجموعة محدودة T من الألوان من مؤشر دورة G الذي يعمل على S؟ (استخدم t ، يُعتقد أنه متغير ، كصورة لعنصر t من T.) اذكر وأثبت النظرية ذات الصلة! هذه هي نظرية التعداد الشهيرة لبولا وريدفيلد.

تمرين 322

لنفترض أننا نصنع قلادة عن طريق توتير 12 قطعة من الأنابيب البلاستيكية ذات الألوان الزاهية على خيط وربط طرفي الخيط معًا. لدينا إمدادات وافرة من الأنابيب الزرقاء والخضراء والأحمر والأصفر المتاحة. أعط دالة توليد يكون فيها معامل BiGjRkY h هو عدد العقود التي يمكننا صنعها باستخدام i blues و j greens و k reds و h yellows. كم عدد المصطلحات التي ستكون لدالة التوليد هذه إذا قمت بتوسيعها بدلالة قوى B و G و R و Y؟ هل يعقل أن تفعل هذا التوسع؟ كم عدد هذه القلادات التي تحتوي على 3 ألوان زرقاء و 3 خضراء و 2 حمراء و 4 صفراء؟

تمرين 323.

ما الذي يجب أن نستبدل به المتغيرات التي تمثل الألوان في العداد المداري لـ G التي تعمل على مجموعة ألوان S بمجموعة T من الألوان من أجل حساب العدد الإجمالي لمدارات G التي تعمل على مجموعة الألوان؟ ما الذي يجب أن نستبدله في المتغيرات في فهرس دورة المجموعة G التي تعمل على مجموعة S لحساب العدد الإجمالي لمدارات G التي تعمل على ألوان S بواسطة مجموعة T؟ ابحث عن عدد طرق تلوين وجوه المكعب بأربعة ألوان.

324. لدينا أعواد حمراء وخضراء وزرقاء كلها بنفس الطول ، مع عشرات العصي من كل لون. سنقوم بصنع الهيكل العظمي لمكعب عن طريق أخذ ثماني كتل متطابقة من طين النمذجة ودفع ثلاثة أعواد في كل كتلة بحيث تصبح الكتل هي رؤوس المكعب. (من الواضح أننا لن نحتاج إلى كل العصي!) ما هو عدد الطرق المختلفة التي يمكننا بها صنع المكعب؟ كم مكعب له أربعة حواف لكل لون؟ كم عدد الحواف التي لها حواف حمراء وأربعة خضراء وستة زرقاء؟

325. كم مكعب يمكننا صنعه في المسألة 324 إذا كانت كتل الصلصال يمكن أن تكون أيًا من أربعة ألوان؟

الشكل 6.9: شبكة كمبيوتر محتملة. 1 2 3 5 4 6

تمرين ∗ 326

في الشكل 6.9 ، نرى رسمًا بيانيًا بستة رؤوس. لنفترض أن لدينا ثلاثة أنواع مختلفة من أجهزة الكمبيوتر التي يمكن وضعها عند الرؤوس الستة للرسم البياني لتشكيل شبكة. ما هو عدد الطرق المختلفة التي يمكن أن توضع بها أجهزة الكمبيوتر؟ (لا يختلف رسمان بيانيان إذا تمكنا من إعادة رسم أحد الرسوم البيانية بحيث يكون متطابقًا مع الآخر.) وهذا يعادل تبديل الرؤوس بطريقة ما بحيث عندما نطبق التقليب على نقاط نهاية الحواف للحصول على مجموعة حافة جديدة ، مجموعة الحافة الجديدة تساوي المجموعة القديمة. يُطلق على مثل هذا التبديل اسم ذاتي الشكل للرسم البياني. ثم يكون موضعان على الكمبيوتر متماثلين إذا كان هناك شكل تلقائي للرسم البياني يحمل أحدهما إلى الآخر. تلميح عبر الإنترنت. تلميح ثانٍ عبر الإنترنت.

تمرين 327

رسمان بيانيان بسيطان على المجموعة [n] = {1 ، 2 ،. ، n} بمجموعات الحواف E و E0 (التي نعتقد أنها مجموعات من عنصرين لهذه المشكلة) يقال إنها متشابهة إذا كان هناك تبديل σ لـ [n] والتي ، في عملها من مجموعات مكونة من عنصرين ، يحمل E إلى E0. نقول إن رسمين بيانيين مختلفين إذا لم يكونا متشابهين. وبالتالي فإن عدد الرسوم البيانية المختلفة هو عدد مدارات مجموعة كل مجموعات المجموعات الفرعية المكونة من عنصرين من [n] تحت تأثير المجموعة Sn. يمكننا تمثيل الحافة التي تحددها وظيفتها المميزة (كما في المشكلة 33). أي أننا نحدد χE ({u، v}) = (1 إذا {u، v} ∈ E 0 بخلاف ذلك. وهكذا يمكننا أن نفكر في مجموعة الرسوم البيانية كمجموعة من الألوان ذات الألوان 0 و 1 من مجموعة جميع المجموعات الفرعية المكونة من عنصرين من [n]. وبالتالي فإن عدد الرسوم البيانية المختلفة مع مجموعة الرؤوس [n] هو عدد مدارات هذه المجموعة من الألوان تحت تأثير المجموعة المتماثلة Sn على مجموعة المجموعات الفرعية المكونة من عنصرين من [ n] استخدم هذا لإيجاد عدد الرسوم البيانية المختلفة على خمسة رؤوس. تلميح عبر الإنترنت.

6.4: المشاكل التكميلية

1. أظهر أن دالة من S إلى T لها معكوس (محدد في T) إذا وفقط إذا كانت انحرافًا.

2. كم عدد العناصر في المجموعة ثنائية السطوح D3؟ المجموعة المتماثلة S3؟ ماذا يمكنك أن تستنتج عن D3 و S3؟

3. رباعي السطوح هو شكل هندسي ثلاثي الأبعاد له أربعة رؤوس وستة حواف وأربعة أوجه مثلثة. لنفترض أننا بدأنا مع رباعي الوجوه في الفضاء ونفكر في مجموعة جميع التباديل لرؤوس رباعي السطوح التي تتوافق مع تحريك رباعي الوجوه في الفضاء وإعادته إلى موقعه الأصلي ، ربما مع الرؤوس في أماكن مختلفة.

  1. اشرح لماذا تشكل هذه التباديل مجموعة.
  2. ما هو حجم هذه المجموعة؟
  3. اكتب في صفين تدوينًا تبديلًا غير موجود في هذه المجموعة.

4. ابحث عن مجموعة فرعية من ثلاثة عناصر من المجموعة S3. هل يمكنك العثور على مجموعة فرعية مختلفة مكونة من ثلاثة عناصر من S3؟ 5. أثبت صحة أو إثبات خطأ باستخدام مثال مضاد: "في مجموعة التقليب ، (σϕ) n = σ nϕ n." 6. إذا كانت المجموعة G تعمل على مجموعة S ، وإذا كانت σ (x) = y ، فهل هناك أي شيء مثير للاهتمام يمكننا قوله عن المجموعات الفرعية Fix (x) و Fix (y)؟ 7. (أ) إذا كانت المجموعة G تعمل على مجموعة S ، فهل σ (f) = f ◦ σ تحدد إجراء جماعي على الوظائف من S إلى مجموعة T؟ لما و لما لا؟ (ب) إذا كانت المجموعة G تعمل على مجموعة S ، فهل σ (f) = f ◦ σ −1 تحدد إجراء جماعي على الوظائف من S إلى مجموعة T؟ لما و لما لا؟ (ج) هل أي من الإجراءات الجماعية المحتملة هو في الأساس نفس الإجراء الذي وصفناه في ألوان مجموعة ، أم أن هذا إجراء مختلف تمامًا؟ 8. ابحث عن عدد من الطرق لتلوين وجوه رباعي السطوح بلونين. 9. أوجد عدد الطرق لتلوين وجوه رباعي السطوح بأربعة ألوان بحيث يتم استخدام كل لون. 10. أوجد دليل دورة مجموعة التماثلات المكانية للرباعي السطوح المؤثرة على الرؤوس. ابحث عن فهرس الدورة لنفس المجموعة التي تعمل على الوجوه. 11. ابحث عن وظيفة التوليد لعدد من الطرق لتلوين وجوه رباعي السطوح باللون الأحمر والأزرق والأخضر والأصفر. 12. ابحث عن وظيفة التوليد لعدد من الطرق لتلوين وجوه المكعب بأربعة ألوان بحيث يتم استخدام الألوان الأربعة. 13. ما عدد الرسوم البيانية المختلفة الموجودة على ستة رؤوس ذات سبعة أضلاع؟ 14. أظهر أنه إذا كانت H مجموعة فرعية من المجموعة G ، فإن H تعمل على G بواسطة G (τ) = σ ◦ τ للجميع τ في H و τ في G. ما حجم مدار هذا الإجراء؟ كيف يرتبط حجم المجموعة الفرعية للمجموعة بحجم المجموعة؟


شاهد الفيديو: توماس مالتوس والنمو السكاني. الأحياء. علم البيئة (شهر اكتوبر 2021).