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

의사-라틴 방진의 조합론에 관하여

기본 정보

논문 ID: 2510.11980
제목: On the Combinatorics of Pseudo-Latin Squares
저자: Andrew Pendleton
분류: math.CO (조합수학)
발표 시간: 2025년 9월 (arXiv 사전인쇄본)
논문 링크: https://arxiv.org/abs/2510.11980

초록

본 논문은 연속 의사-라틴 방진(CPLSs)이라는 새로운 조합 대상을 도입한다. 이는 라틴 방진의 변형으로, 최소한 하나의 행 또는 열이 연속 또는 역연속 순서를 가지지만, 각 원소가 모든 행이나 열에 반드시 나타나지는 않는 구조이다. 저자는 n차 CPLSs의 개수에 대한 정확한 공식과 점근 공식을 도출하였으며, n→∞일 때 CPLSs가 모든 의사-라틴 방진(PLSs) 중에서 차지하는 비율이 빠르게 0으로 수렴함을 증명하였다. 본 논문은 균등 무작위 표본 추출 하에서 CPLSs의 분포를 분석하고, 대수 구조와의 연결을 탐색하여 CPLSs를 단위원소 마그마(unital magmas)와 관련된 케일리 표로 해석한다. 마지막으로 몬테카를로 시뮬레이션을 통해 작은 n값에 대한 이론적 결과를 검증한다.

연구 배경 및 동기

1. 문제 제기

본 연구는 라틴 방진 변형의 조합론적 성질 탐색에서 비롯되었다. 전통적인 라틴 방진은 각 원소가 모든 행과 열에 정확히 한 번씩 나타나야 하지만, 의사-라틴 방진은 이 제약을 완화하여 원소가 서로 다른 행과 열에서 다양한 횟수로 나타날 수 있도록 허용한다. 저자는 특히 연속성 성질을 가진 의사-라틴 방진에 주목한다.

2. 연구 동기

게임 영감: 연구 영감은 donotfindthefox.com 웹사이트의 "FOX in Boxes" 게임에서 비롯되었으며, 이 게임은 4×4 격자에서 특정 단어를 피하면서 무작위로 문자를 배치하는 것을 포함한다
이론적 가치: 연속성은 조합 구조에서 중요한 성질이며, 의사-라틴 방진에서의 표현을 연구하는 것은 이론적 의의를 가진다
응용 전망: 라틴 방진 및 그 변형은 실험 설계, 암호학, 오류 정정 부호 등 다양한 분야에서 광범위한 응용을 가진다

3. 기존 연구의 한계

전통적인 라틴 방진 이론은 주로 완전히 균형잡힌 구조에 초점을 맞춘다
제약이 완화된 의사-라틴 방진, 특히 연속성과 같은 특수한 성질을 가진 변형에 대한 체계적인 이론 분석이 부족하다
이러한 대상들의 대규모 상황에서의 점근 거동에 대한 깊이 있는 이해가 결여되어 있다

핵심 기여

새로운 개념 정의: 연속 의사-라틴 방진(CPLSs)이라는 새로운 조합 대상을 처음으로 체계적으로 정의
정확한 계수 공식: n차 CPLSs 개수의 정확한 조합 공식 도출
점근 분석: CPLSs가 모든 PLSs 중에서 차지하는 비율이 $\frac{4n^{n+1}(n^2-n)!}{(n^2)!}$ 의 속도로 0으로 수렴함을 증명
확률 분포: 무작위 PLS에서 연속 행과 열의 개수에 대한 확률질량함수를 완전히 특성화
대수적 해석: CPLSs와 근처 단위원소 마그마 케일리 표 간의 대응 관계 수립
계산 검증: 대규모 몬테카를로 시뮬레이션을 통해 이론적 결과의 정확성 검증

방법론 상세 설명

작업 정의

의사-라틴 방진(PLS): n차 의사-라틴 방진은 다중집합 $\{1,1,\ldots,1,2,2,\ldots,n,n,\ldots,n\}$ 의 원소로 이루어진 n×n 배열로, 각 원소의 중복도는 n이다.

연속 의사-라틴 방진(CPLS): 최소한 하나의 행 또는 열이 연속 또는 역연속 순서인 의사-라틴 방진이다.

핵심 방법론 구조

1. 계수 이론 프레임워크

저자는 포함-배제 원리(PIE)를 주요 계수 도구로 채택한다:

$R$ 을 최소한 하나의 연속 행을 가진 n차 PLSs의 집합이라 하자
$C$ 를 최소한 하나의 연속 열을 가진 n차 PLSs의 집합이라 하자
그러면 $\Sigma_n = R \cup C$ 이고, $|\Sigma_n| = |R| + |C| - |R \cap C|$ 이다

2. 구성적 계수 방법

다음 단계를 통해 각 유형의 PLSs 개수를 계산한다:

연속 행/열 선택: 어떤 행 또는 열이 연속일지 결정
순서 결정: 연속 또는 역연속 배열 선택
나머지 위치 채우기: 남은 원소를 비연속 위치에 배치
PIE 적용: 중복 계산 회피

3. 핵심 보조정리 체계

보조정리 2.1: PLSs의 총 개수는 $|\Omega_n| = \frac{(n^2)!}{(n!)^n}$ 이다

보조정리 2.2: 최소한 하나의 연속 행을 가진 PLSs의 개수: $|R| = \sum_{i=1}^n (-1)^{i+1} \cdot 2^i \cdot \frac{n!(n^2-in)!}{(n-i)!^{n+1}i!}$

기술적 혁신점

1. 계층적 계수 전략

복잡한 계수 문제를 여러 계층으로 분해
서로 다른 개수의 연속 행과 열의 교집합을 체계적으로 처리
직접 계수의 조합론적 폭발을 교묘하게 회피

2. 대칭성 활용

90° 회전을 이용하여 행과 열 사이의 전단사 관계 수립
반사 등의 변환을 통해 중복 계산 단순화
홀수 차수와 짝수 차수의 차이를 특별히 처리

3. 점근 분석 기법

주도항 식별: 첫 번째 항 $2|R|$ 이 전체 표현식을 지배함을 증명
정확한 오차 추정: 점근 근사의 수렴 속도 제공

실험 설정

데이터 생성

무작위 PLSs 생성: 원소의 무작위 순열을 통해 균등 분포의 n차 PLSs 생성
규모 설정: n∈{3,4,5}에 대해 $10^8$ 회의 독립 시행 수행
검증 범위: 소규모에 대한 정확한 검증, 대규모에 대한 점근 거동 테스트

평가 지표

이론 vs 실험 확률 차이: 몬테카를로 추정과 이론 예측의 편차 측정
수렴성 분석: 반복 횟수 증가에 따른 수렴 거동 관찰
신뢰 구간: $\max\{5\sqrt{\frac{p(1-p)}{N}}, \frac{p}{100}\}$ 을 오차 한계로 사용

구현 세부사항

프로그래밍 언어: Python
난수 생성: 표준 라이브러리의 균등 난수 생성기 사용
병렬화: tqdm 라이브러리를 통한 진행 상황 추적
메모리 최적화: 생성된 모든 행렬 저장을 피하기 위한 스트림 처리

실험 결과

주요 결과

1. CPLS 확률 검증

작은 n값에 대해 이론 예측과 실험 결과가 높은 일치도를 보인다:

n	이론 확률 P(ω∈Σₙ)	실험 오차 범위
3	0.490476	±0.0016
4	0.090006	±0.0009
5	0.009760	±0.0003

2. 점근 근사 정확도

점근 공식 $S(n)$ 의 근사 품질은 n의 증가에 따라 빠르게 향상된다:

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

3. 확률질량함수 검증

연속 행과 열의 개수 분포에 대해, 모든 테스트 사례의 실험값이 이론 예측의 신뢰 구간 내에 위치한다.

제거 실험

1. 서로 다른 n값의 거동 차이

n=3: CPLSs가 여전히 상당한 비율을 차지(~49%)
n=4: 비율이 현저히 감소(~9%)
n≥5: 빠르게 0으로 수렴(<1%)

2. 연속 행 vs 연속 열

90° 회전 대칭성을 통해 행과 열의 기여도가 완전히 동등함을 검증한다.

3. 교집합항의 중요성

PIE 계산에서 고차 교집합항이 최종 결과에 미치는 기여도가 무시할 수 있는 수준임을 증명한다.

실험 발견

빠른 감소: CPLSs 비율의 감소 속도가 예상보다 빠르다
소규모 이상 현상: n≤4일 때 대규모 n과 다른 거동 패턴을 보인다
수치 안정성: $10^8$ 회 시행에서도 몬테카를로 추정이 높은 정확도를 유지한다

결론 및 논의

주요 결론

희소성 정리: CPLSs가 큰 n에서 극히 드물며, 비율이 $O(\frac{4n^{n+1}}{(n^2-n+1)^n})$ 의 속도로 0으로 수렴함을 증명
분포의 완전한 특성화: 연속 행과 열의 개수에 대한 완전한 확률질량함수 제공
대수적 대응: CPLSs와 근처 단위원소 마그마 간의 이론적 연결 수립