2025-11-11T16:10:09.893794

On the Combinatorics of Pseudo-Latin Squares

Pendleton
We introduce a new class of combinatorial objects called consecutive pseudo-Latin squares (CPLSs), a variant of Latin squares in which at least one row or column is in consecutive or reverse-consecutive order, but every element may not appear in every row or column. We derive exact and asymptotic formulas for the number of CPLSs of order $n$, showing that their proportion among all pseudo-Latin squares (PLSs) rapidly approaches zero as $n\to\infty$. We also analyze the distribution of CPLSs under uniform random sampling, and explore connections to algebraic structures, interpreting CPLSs as Cayley tables related to those of unital magmas. Finally, we supplement our theoretical results with Monte Carlo simulations for small values of $n$.
academic

সিউডো-ল্যাটিন বর্গের সমন্বয়বিদ্যা সম্পর্কে

মৌলিক তথ্য

  • পেপার আইডি: 2510.11980
  • শিরোনাম: সিউডো-ল্যাটিন বর্গের সমন্বয়বিদ্যা সম্পর্কে
  • লেখক: অ্যান্ড্রু পেন্ডলটন
  • শ্রেণীবিভাগ: math.CO (সমন্বয়বিদ্যা)
  • প্রকাশনার সময়: ২০২৫ সালের সেপ্টেম্বর (arXiv প্রাক-মুদ্রণ)
  • পেপার লিঙ্ক: https://arxiv.org/abs/2510.11980

সারসংক্ষেপ

এই পেপারটি একটি নতুন সমন্বয়বৈজ্ঞানিক বস্তু - ক্রমাগত সিউডো-ল্যাটিন বর্গ (CPLSs) প্রবর্তন করে, যা ল্যাটিন বর্গের একটি রূপান্তর যেখানে অন্তত একটি সারি বা স্তম্ভ ক্রমাগত বা বিপরীত ক্রমাগত ক্রমে থাকে, কিন্তু প্রতিটি উপাদান প্রতিটি সারি বা স্তম্ভে অপরিহার্যভাবে উপস্থিত থাকে না। লেখক n-ক্রমের CPLSs সংখ্যার জন্য সঠিক সূত্র এবং অসিম্পটোটিক সূত্র প্রতিপাদন করেছেন, প্রমাণ করেছেন যে n→∞ হলে, CPLSs সমস্ত সিউডো-ল্যাটিন বর্গ (PLSs) এর মধ্যে অনুপাত দ্রুত শূন্যের দিকে প্রবণ হয়। নিবন্ধটি সমান-র্যান্ডম নমুনার অধীনে CPLSs এর বিতরণ বিশ্লেষণ করে, বীজগণিত কাঠামোর সাথে সংযোগ অন্বেষণ করে, CPLSs কে একক ম্যাগমা (unital magmas) সম্পর্কিত ক্যালি সারণী হিসাবে ব্যাখ্যা করে। অবশেষে, মন্টে কার্লো সিমুলেশনের মাধ্যমে ছোট n মানের তাত্ত্বিক ফলাফল যাচাই করা হয়।

গবেষণা পটভূমি এবং প্রেরণা

১. সমস্যার উপস্থাপনা

এই গবেষণা ল্যাটিন বর্গের রূপান্তরের সমন্বয়বৈজ্ঞানিক বৈশিষ্ট্যের অন্বেষণ থেকে উদ্ভূত। ঐতিহ্যবাহী ল্যাটিন বর্গ প্রতিটি উপাদানকে প্রতিটি সারি এবং স্তম্ভে ঠিক একবার উপস্থিত হতে প্রয়োজন করে, যখন সিউডো-ল্যাটিন বর্গ এই সীমাবদ্ধতা শিথিল করে, বিভিন্ন সারি এবং স্তম্ভে উপাদানগুলি বিভিন্ন সংখ্যায় উপস্থিত হতে দেয়। লেখক বিশেষভাবে ক্রমাগত বৈশিষ্ট্য সহ সিউডো-ল্যাটিন বর্গে মনোনিবেশ করেন।

২. গবেষণা প্রেরণা

  • গেম অনুপ্রেরণা: গবেষণার অনুপ্রেরণা donotfindthefox.com ওয়েবসাইটের "FOX in Boxes" গেম থেকে আসে, যা ৪×৪ গ্রিডে নির্দিষ্ট শব্দ বানানো এড়াতে অক্ষর র্যান্ডমভাবে স্থাপনের সাথে জড়িত
  • তাত্ত্বিক মূল্য: ক্রমাগততা সমন্বয়বৈজ্ঞানিক কাঠামোতে একটি গুরুত্বপূর্ণ বৈশিষ্ট্য, এবং সিউডো-ল্যাটিন বর্গে এর কর্মক্ষমতা অধ্যয়ন তাত্ত্বিক তাৎপর্য রাখে
  • প্রয়োগের সম্ভাবনা: ল্যাটিন বর্গ এবং তাদের রূপান্তর পরীক্ষামূলক ডিজাইন, ক্রিপ্টোগ্রাফি, ত্রুটি সংশোধন কোডে ব্যাপক প্রয়োগ রয়েছে

৩. বিদ্যমান গবেষণার সীমাবদ্ধতা

  • ঐতিহ্যবাহী ল্যাটিন বর্গ তত্ত্ব প্রধানত সম্পূর্ণ ভারসাম্যপূর্ণ কাঠামোতে ফোকাস করে
  • শিথিল সীমাবদ্ধতার পরে সিউডো-ল্যাটিন বর্গের জন্য, বিশেষ করে বিশেষ বৈশিষ্ট্য (যেমন ক্রমাগততা) সহ রূপান্তর, পদ্ধতিগত তাত্ত্বিক বিশ্লেষণের অভাব রয়েছে
  • বৃহৎ-স্কেল পরিস্থিতিতে এই ধরনের বস্তুর অসিম্পটোটিক আচরণের গভীর বোঝার অভাব রয়েছে

মূল অবদান

১. নতুন ধারণা সংজ্ঞা: প্রথমবারের মতো ক্রমাগত সিউডো-ল্যাটিন বর্গ (CPLSs) এই নতুন সমন্বয়বৈজ্ঞানিক বস্তু পদ্ধতিগতভাবে সংজ্ঞায়িত করা হয়েছে ২. সঠিক গণনা সূত্র: n-ক্রমের CPLSs সংখ্যার জন্য সঠিক সমন্বয়বৈজ্ঞানিক সূত্র প্রতিপাদন করা হয়েছে ३. অসিম্পটোটিক বিশ্লেষণ: প্রমাণ করা হয়েছে যে CPLSs সমস্ত PLSs এর মধ্যে অনুপাত 4nn+1(n2−n)!(n2)!\frac{4n^{n+1}(n^2-n)!}{(n^2)!} এর গতিতে শূন্যের দিকে প্রবণ হয় ४. সম্ভাব্যতা বিতরণ: র্যান্ডম PLS এ ক্রমাগত সারি এবং স্তম্ভের সংখ্যার সম্ভাব্যতা ভর ফাংশন সম্পূর্ণভাবে চিহ্নিত করা হয়েছে ५. বীজগণিত ব্যাখ্যা: CPLSs এবং প্রায়-একক ম্যাগমা ক্যালি সারণীর মধ্যে সংযোগ স্থাপন করা হয়েছে ६. গণনামূলক যাচাইকরণ: বৃহৎ-স্কেল মন্টে কার্লো সিমুলেশনের মাধ্যমে তাত্ত্বিক ফলাফলের নির্ভুলতা যাচাই করা হয়েছে

পদ্ধতি বিস্তারিত

কাজের সংজ্ঞা

সিউডো-ল্যাটিন বর্গ (PLS): একটি n-ক্রমের সিউডো-ল্যাটিন বর্গ একটি n×n অ্যারে, যার উপাদান বহুসেট {1,1,…,1,2,2,…,n,n,…,n}\{1,1,\ldots,1,2,2,\ldots,n,n,\ldots,n\} থেকে আসে, যেখানে প্রতিটি উপাদানের বহুত্ব n।

ক্রমাগত সিউডো-ল্যাটিন বর্গ (CPLS): অন্তত একটি সারি বা স্তম্ভ ক্রমাগত বা বিপরীত ক্রমাগত ক্রমে থাকে এমন সিউডো-ল্যাটিন বর্গ।

মূল পদ্ধতি স্থাপত্য

১. গণনা তত্ত্ব কাঠামো

লেখক প্রধান গণনা সরঞ্জাম হিসাবে অন্তর্ভুক্তি-বর্জন নীতি (PIE) ব্যবহার করেন:

  • RR কে অন্তত একটি ক্রমাগত সারি সহ n-ক্রমের PLSs সেট হতে দিন
  • CC কে অন্তত একটি ক্রমাগত স্তম্ভ সহ n-ক্রমের PLSs সেট হতে দিন
  • তাহলে Σn=R∪C\Sigma_n = R \cup C, এবং ∣Σn∣=∣R∣+∣C∣−∣R∩C∣|\Sigma_n| = |R| + |C| - |R \cap C|

२. গঠনমূলক গণনা পদ্ধতি

নিম্নলিখিত পদক্ষেপের মাধ্যমে বিভিন্ন ধরনের PLSs সংখ্যা গণনা করা হয়:

१. ক্রমাগত সারি/স্তম্ভ নির্বাচন: নির্ধারণ করুন কোন সারি বা স্তম্ভ ক্রমাগত হবে २. ক্রম নির্ধারণ: ক্রমাগত বা বিপরীত ক্রমাগত ব্যবস্থা নির্বাচন করুন ३. অবশিষ্ট অবস্থান পূরণ: অবশিষ্ট উপাদান অ-ক্রমাগত অবস্থানে রাখুন ४. PIE প্রয়োগ করুন: পুনরাবৃত্তি গণনা এড়ান

३. মূল লেমা সিস্টেম

লেমা २.१: PLSs মোট সংখ্যা ∣Ωn∣=(n2)!(n!)n|\Omega_n| = \frac{(n^2)!}{(n!)^n}

লেমা २.२: অন্তত একটি ক্রমাগত সারি সহ PLSs সংখ্যা: ∣R∣=∑i=1n(−1)i+1⋅2i⋅n!(n2−in)!(n−i)!n+1i!|R| = \sum_{i=1}^n (-1)^{i+1} \cdot 2^i \cdot \frac{n!(n^2-in)!}{(n-i)!^{n+1}i!}

প্রযুক্তিগত উদ্ভাবন বিন্দু

१. স্তরযুক্ত গণনা কৌশল

  • জটিল গণনা সমস্যা একাধিক স্তরে বিভক্ত করুন
  • বিভিন্ন সংখ্যক ক্রমাগত সারি এবং স্তম্ভের ছেদ পদ্ধতিগতভাবে পরিচালনা করুন
  • সরাসরি গণনার সমন্বয়বৈজ্ঞানিক বিস্ফোরণ চতুরভাবে এড়ান

२. প্রতিসাম্য ব্যবহার

  • ৯০° ঘূর্ণন ব্যবহার করে সারি এবং স্তম্ভের মধ্যে দ্বিমুখী সম্পর্ক স্থাপন করুন
  • প্রতিফলন এবং অন্যান্য রূপান্তরের মাধ্যমে পুনরাবৃত্তি গণনা সরল করুন
  • বিশেষভাবে বিজোড় এবং জোড় ক্রমের পার্থক্য পরিচালনা করুন

३. অসিম্পটোটিক বিশ্লেষণ কৌশল

  • প্রভাবশালী পদ চিহ্নিত করুন: প্রমাণ করুন যে প্রথম পদ 2∣R∣2|R| সম্পূর্ণ অভিব্যক্তি প্রভাবিত করে
  • নির্ভুল ত্রুটি অনুমান: অসিম্পটোটিক অনুমানের সংগ্রহের গতি প্রদান করুন

পরীক্ষামূলক সেটআপ

ডেটা উৎপাদন

  • র্যান্ডম PLSs উৎপাদন: উপাদান র্যান্ডম ক্রমাঙ্কনের মাধ্যমে সমান বিতরণকৃত n-ক্রমের PLSs উৎপাদন করুন
  • স্কেল সেটিং: n∈{३,४,५} এর জন্য १०८१०^८ স্বাধীন পরীক্ষা পরিচালনা করুন
  • যাচাইকরণ পরিসীমা: ছোট-স্কেল নির্ভুল যাচাইকরণ, বৃহৎ-স্কেল অসিম্পটোটিক আচরণ পরীক্ষা

মূল্যায়ন মেট্রিক্স

  • তত্ত্ব বনাম পরীক্ষা সম্ভাব্যতা পার্থক্য: মন্টে কার্লো অনুমান এবং তাত্ত্বিক পূর্বাভাসের মধ্যে বিচ্যুতি পরিমাপ করুন
  • সংগ্রহ বিশ্লেষণ: পুনরাবৃত্তি সংখ্যা বৃদ্ধির সাথে সংগ্রহ আচরণ পর্যবেক্ষণ করুন
  • আস্থা ব্যবধান: max⁡{5p(1−p)N,p100}\max\{5\sqrt{\frac{p(1-p)}{N}}, \frac{p}{100}\} ব্যবহার করুন ত্রুটি সীমা হিসাবে

বাস্তবায়ন বিবরণ

  • প্রোগ্রামিং ভাষা: পাইথন
  • র্যান্ডম সংখ্যা উৎপাদন: মান লাইব্রেরির সমান র্যান্ডম সংখ্যা উৎপাদক ব্যবহার করুন
  • সমান্তরালীকরণ: tqdm লাইব্রেরির মাধ্যমে অগ্রগতি ট্র্যাকিং বাস্তবায়ন করুন
  • স্মৃতি অপ্টিমাইজেশন: সমস্ত উৎপাদিত ম্যাট্রিক্স সংরক্ষণ এড়াতে স্ট্রিম প্রক্রিয়াকরণ

পরীক্ষামূলক ফলাফল

প্রধান ফলাফল

१. CPLS সম্ভাব্যতা যাচাইকরণ

ছোট n মানের জন্য, তাত্ত্বিক পূর্বাভাস এবং পরীক্ষামূলক ফলাফল অত্যন্ত সামঞ্জস্যপূর্ণ:

nতাত্ত্বিক সম্ভাব্যতা P(ω∈Σₙ)পরীক্ষামূলক ত্রুটি পরিসীমা
30.490476±0.0016
40.090006±0.0009
50.009760±0.0003

२. অসিম্পটোটিক অনুমান নির্ভুলতা

অসিম্পটোটিক সূত্র S(n)S(n) এর অনুমান গুণমান n বৃদ্ধির সাথে দ্রুত উন্নত হয়:

| n | |Σₙ|/S(n) | |---|----------| | 5 | 0.995 | | 6 | 0.9996 | | 7 | 0.99997 | | 8 | 0.999998 |

३. সম্ভাব্যতা ভর ফাংশন যাচাইকরণ

ক্রমাগত সারি এবং স্তম্ভের সংখ্যার বিতরণের জন্য, সমস্ত পরীক্ষামূলক ক্ষেত্র তাত্ত্বিক পূর্বাভাসের আস্থা ব্যবধানের মধ্যে পড়ে।

বিলোপন পরীক্ষা

१. বিভিন্ন n মানের আচরণ পার্থক্য

  • n=३: CPLSs এখনও উল্লেখযোগ্য অনুপাত দখল করে (~४९%)
  • n=४: অনুপাত উল্লেখযোগ্যভাবে হ্রাস পায় (~९%)
  • n≥५: দ্রুত শূন্যের দিকে প্রবণ (<१%)

२. ক্রমাগত সারি বনাম ক্রমাগত স্তম্ভ

९०° ঘূর্ণন প্রতিসাম্যের মাধ্যমে, সারি এবং স্তম্ভের অবদান সম্পূর্ণ সমান যাচাই করা হয়েছে।

३. ছেদ পদের গুরুত্ব

PIE গণনায় প্রমাণ করা হয়েছে যে উচ্চ-ক্রমের ছেদ পদগুলি চূড়ান্ত ফলাফলে নগণ্য অবদান রাখে।

পরীক্ষামূলক আবিষ্কার

१. দ্রুত হ্রাস: CPLSs অনুপাতের হ্রাস গতি প্রত্যাশিত থেকে দ্রুত २. ছোট n অসঙ্গতি: n≤४ সময় বড় n এর থেকে ভিন্ন আচরণ প্যাটার্ন প্রদর্শন করে ३. সংখ্যাগত স্থিতিশীলতা: এমনকি १०८१०^८ পরীক্ষার জন্য, মন্টে কার্লো অনুমান উচ্চ নির্ভুলতা বজায় রাখে

সম্পর্কিত কাজ

ল্যাটিন বর্গ তত্ত্ব

  • অয়লারের ३६ সামরিক অফিসার সমস্যা: ঐতিহাসিকভাবে ল্যাটিন বর্গ গবেষণা চালিত করা ক্লাসিক সমস্যা
  • আধুনিক উন্নয়ন: কোয়াসিগ্রুপ, পরীক্ষামূলক ডিজাইন, ত্রুটি সংশোধন কোডের সাথে সংযোগ
  • গণনা সমস্যা: ঐতিহ্যবাহী ল্যাটিন বর্গের গণনা এখনও একটি খোলা সমস্যা

সিউডো-ল্যাটিন বর্গ গবেষণা

  • নর্টনের কাজ: সিউডো-ল্যাটিন বর্গ ধারণা প্রথম প্রবর্তন, অর্থোগোনাল ল্যাটিন বর্গ গোষ্ঠী অধ্যয়নের জন্য ব্যবহৃত
  • বীজগণিত প্রয়োগ: ম্যাগমা তত্ত্বের সাথে সংযোগ

এই পেপারের অনন্য অবদান

  • প্রথমবারের মতো ক্রমাগত বৈশিষ্ট্য সহ সিউডো-ল্যাটিন বর্গ পদ্ধতিগতভাবে অধ্যয়ন করা হয়েছে
  • সঠিক গণনা তত্ত্ব স্থাপন করা হয়েছে
  • বীজগণিত কাঠামোর নতুন দৃষ্টিভঙ্গি প্রদান করা হয়েছে

উপসংহার এবং আলোচনা

প্রধান উপসংহার

१. বিরলতা উপপাদ্য: প্রমাণ করা হয়েছে যে CPLSs বড় n সময় অত্যন্ত বিরল, অনুপাত শূন্যের দিকে প্রবণ হওয়ার গতি O(4nn+1(n2−n+1)n)O(\frac{4n^{n+1}}{(n^2-n+1)^n})

२. বিতরণ সম্পূর্ণ চিহ্নিতকরণ: ক্রমাগত সারি এবং স্তম্ভের সংখ্যার সম্পূর্ণ সম্ভাব্যতা ভর ফাংশন প্রদান করা হয়েছে

३. বীজগণিত সংযোগ: CPLSs এবং প্রায়-একক ম্যাগমার মধ্যে তাত্ত্বিক সংযোগ স্থাপন করা হয়েছে

সীমাবদ্ধতা

१. গণনামূলক জটিলতা: সঠিক সূত্র জটিল সমন্বয়বৈজ্ঞানিক অভিব্যক্তি জড়িত, গণনা খরচ n এর সাথে দ্রুত বৃদ্ধি পায় २. প্রযোজ্য পরিসীমা: প্রধান ফলাফল ছোট থেকে মধ্যম-স্কেল পরিস্থিতিতে কেন্দ্রীভূত ३. বাস্তব প্রয়োগ: বাস্তব প্রয়োগ পরিস্থিতির সাথে সংযোগ এখনও আরও অন্বেষণ প্রয়োজন

ভবিষ্যত দিকনির্দেশনা

१. সাধারণীকরণ গবেষণা: অন্যান্য ধরনের "কাঠামোগত" সিউডো-ল্যাটিন বর্গ বিবেচনা করুন २. অ্যালগরিদম অপ্টিমাইজেশন: আরও দক্ষ গণনা এবং উৎপাদন অ্যালগরিদম বিকাশ করুন ३. প্রয়োগ অন্বেষণ: ক্রিপ্টোগ্রাফি, কোডিং তত্ত্বে সম্ভাব্য প্রয়োগ

গভীর মূল্যায়ন

সুবিধা

१. তাত্ত্বিক কঠোরতা: গাণিতিক প্রতিপাদন সম্পূর্ণ, প্রমাণ যুক্তি স্পষ্ট २. পদ্ধতি উদ্ভাবন: গঠনমূলক গণনা এবং অন্তর্ভুক্তি-বর্জন নীতি চতুরভাবে সংমিশ্রণ করা হয়েছে ३. পরীক্ষা পর্যাপ্ত: বৃহৎ-স্কেল মন্টে কার্লো যাচাইকরণ ফলাফল বিশ্বাসযোগ্যতা বৃদ্ধি করে ४. আন্তঃ-শৃঙ্খলা দৃষ্টিভঙ্গি: সমন্বয়বৈজ্ঞানিক সমস্যা এবং বীজগণিত কাঠামো সংযুক্ত করে

অপূর্ণতা

१. প্রয়োগ প্রেরণা: যদিও গেম অনুপ্রেরণা রয়েছে, বাস্তব প্রয়োগ মূল্য যথেষ্ট স্পষ্ট নয় २. গণনা দক্ষতা: বড় n মানের জন্য, সূত্রের গণনা অবাস্তব হয়ে ওঠে ३. সাধারণীকরণ: ফলাফল প্রধানত নির্দিষ্ট ক্রমাগত বৈশিষ্ট্যের জন্য, অন্যান্য কাঠামোগত বৈশিষ্ট্যে সাধারণীকরণের সম্ভাবনা সীমিত

প্রভাব

१. তাত্ত্বিক অবদান: সিউডো-ল্যাটিন বর্গ তত্ত্বের জন্য নতুন গবেষণা দিকনির্দেশনা প্রদান করে २. পদ্ধতি মূল্য: গণনা কৌশল অন্যান্য সমন্বয়বৈজ্ঞানিক কাঠামোতে প্রযোজ্য হতে পারে ३. পুনরুৎপাদনযোগ্যতা: সম্পূর্ণ কোড বাস্তবায়ন প্রদান করে, যাচাইকরণ এবং সম্প্রসারণ সহজতর করে

প্রযোজ্য পরিস্থিতি

१. সমন্বয়বিদ্যা গবেষণা: ল্যাটিন বর্গ রূপান্তরের তাত্ত্বিক ভিত্তি হিসাবে २. সম্ভাব্যতা বিশ্লেষণ: র্যান্ডম সমন্বয়বৈজ্ঞানিক কাঠামোর বৈশিষ্ট্য গবেষণা ३. অ্যালগরিদম ডিজাইন: বিশেষ সীমাবদ্ধতার অধীনে সমন্বয়বৈজ্ঞানিক অপ্টিমাইজেশন সমস্যা

তথ্যসূত্র

এই পেপারটি ১३টি গুরুত্বপূর্ণ তথ্যসূত্র উদ্ধৃত করে, যা ল্যাটিন বর্গের ঐতিহাসিক উন্নয়ন, আধুনিক প্রয়োগ এবং সম্পর্কিত তত্ত্ব অন্তর্ভুক্ত করে, বিশেষভাবে মনোযোগের যোগ্য:

  • ম্যাকে এবং অন্যান্য (२००७): ছোট ল্যাটিন বর্গ, কোয়াসিগ্রুপ এবং লুপের পদ্ধতিগত অধ্যয়ন
  • ভ্যান লিন্ট এবং উইলসন (१९९२): সমন্বয়বিদ্যা টিউটোরিয়ালে ল্যাটিন বর্গ অধ্যায়
  • নর্টন (१९५२): অর্থোগোনাল সারি ল্যাটিন বর্গ গোষ্ঠীর অগ্রগামী কাজ

সামগ্রিক মূল্যায়ন: এটি সমন্বয়বিদ্যা ক্ষেত্রে তাত্ত্বিক মূল্য সহ একটি কঠোর পেপার, যদিও প্রয়োগের সম্ভাবনা আরও অন্বেষণের জন্য অপেক্ষা করছে, তবে এর পদ্ধতি উদ্ভাবন এবং তাত্ত্বিক অবদান সম্পর্কিত গবেষণার জন্য মূল্যবান ভিত্তি প্রদান করে।