Let \(A=\{a_1<a_2<\cdots<a_{12}\}\) be a candidate special sum set. The second special-sum rule already says that whenever one disjoint subset has more elements than another, its sum must be larger. Therefore the only remaining ambiguity comes from two disjoint subsets \(B\) and \(C\) with the same size. Problem 106 asks how many unordered pairs \((B,C)\) still need an explicit test for \(S(B)\neq S(C)\). The count depends only on the relative positions inside the ordered set, and for \(n=12\) the total is \(21384\).
The implementations work entirely with indices \(0,1,\dots,n-1\), not with the actual set values. That is the key invariant of the problem: once the set is strictly increasing, the question of whether two equal-size subsets are automatically ordered depends only on how their positions interleave.
If \(|B|\neq |C|\), the second special-sum condition already rules out equality. If \(|B|=|C|=1\), equality is impossible because all elements are distinct. So the only nontrivial cases are
$$|B|=|C|=k,\qquad 2\le k\le \left\lfloor\frac{n}{2}\right\rfloor.$$
Write the two subsets in sorted order:
$$B=\{b_1<b_2<\cdots<b_k\},\qquad C=\{c_1<c_2<\cdots<c_k\}.$$
If \(b_i<c_i\) for every \(i\), then each element chosen from \(B\) is smaller than the corresponding element chosen from \(C\), so
$$a_{b_1}+a_{b_2}+\cdots+a_{b_k}<a_{c_1}+a_{c_2}+\cdots+a_{c_k}.$$
The same argument works with the roles reversed when \(c_i<b_i\) for every \(i\). In either situation, the inequality between subset sums is automatic and no equality test is needed. A pair needs testing exactly when the coordinatewise comparison crosses, meaning that one position favors \(B\) and another favors \(C\).
First choose the \(2k\) positions involved, then split them into two unlabeled \(k\)-subsets. This gives
$$\binom{n}{2k}\cdot\frac{1}{2}\binom{2k}{k}$$
unordered disjoint pairs with \(|B|=|C|=k\).
Fix one chosen set of positions \(x_1<x_2<\cdots<x_{2k}\). Any split into two \(k\)-subsets can be encoded by a word of length \(2k\): write \(B\) if \(x_j\) goes into the first subset and \(C\) if it goes into the second. To count each unordered pair once, orient it so that \(x_1\in B\).
Under that orientation, the condition \(b_i<c_i\) for all \(i\) is equivalent to saying that in every prefix of the word, the number of \(B\)'s is at least the number of \(C\)'s. Before the first \(C\) appears there must already be one \(B\); before the second \(C\) appears there must already be two \(B\)'s; and so on. Those prefix-balanced words are Dyck words of semilength \(k\), so their count is the Catalan number
$$C_k=\frac{1}{k+1}\binom{2k}{k}.$$
Therefore, for each fixed set of \(2k\) positions, the number of unordered pairs that are automatically ordered is \(C_k\), and the number that really need testing is
$$\frac{1}{2}\binom{2k}{k}-C_k=\frac{k-1}{2(k+1)}\binom{2k}{k}.$$
Take four ordered positions \(x_1<x_2<x_3<x_4\). There are exactly three unordered splits into two pairs:
$$\{x_1,x_2\}\mid\{x_3,x_4\},\qquad \{x_1,x_3\}\mid\{x_2,x_4\},\qquad \{x_1,x_4\}\mid\{x_2,x_3\}.$$
The first two are automatic because one sorted pair is pointwise smaller than the other. The third is the only crossing configuration, so it is the only one that needs a genuine sum comparison. This matches
$$\frac{1}{2}\binom{4}{2}-C_2=3-2=1,$$
which is also the checkpoint value for \(n=4\).
Summing over all feasible subset sizes gives
$$T(n)=\sum_{k=2}^{\lfloor n/2\rfloor}\binom{n}{2k}\left(\frac{1}{2}\binom{2k}{k}-\frac{1}{k+1}\binom{2k}{k}\right).$$
For \(n=12\), the contributions are
$$\binom{12}{4}(3-2)=495,\qquad \binom{12}{6}(10-5)=4620,\qquad \binom{12}{8}(35-14)=10395,$$
$$\binom{12}{10}(126-42)=5544,\qquad \binom{12}{12}(462-132)=330,$$
so
$$T(12)=495+4620+10395+5544+330=21384.$$
The C++, Python, and Java implementations do not use the Catalan closed form directly. Instead, they compute the same quantity by explicit enumeration, which is still practical because the target instance is only \(n=12\).
For each \(k=2,3,\dots,\lfloor n/2\rfloor\), the implementation generates every \(k\)-subset of \(\{0,1,\dots,n-1\}\). The C++ version represents subsets through integer masks, the Python version uses combinations, and the Java version builds arrays recursively. In every case the stored subset is already sorted.
The nested loops inspect each unordered pair of generated subsets. First they discard any pair that is not disjoint. For the remaining pairs, they compare the sorted coordinates position by position. If all coordinates of one subset are smaller than the corresponding coordinates of the other, the pair is automatically ordered and is skipped. Only the crossing cases increase the counter.
One implementation also checks the smaller cases \(n=4\) and \(n=7\) before evaluating \(n=12\). The expected counts are \(1\) and \(70\), and the same formula above gives
$$T(7)=\binom{7}{4}(3-2)+\binom{7}{6}(10-5)=35+35=70.$$
Let \(M_k=\binom{n}{k}\). For a fixed \(k\), the direct enumeration examines \(\binom{M_k}{2}\) unordered pairs of \(k\)-subsets. The coordinatewise comparison costs \(O(k)\), and the overlap test is at worst \(O(k^2)\) in the tuple and array based versions, so a safe bound for the implemented approach is
$$O\!\left(\sum_{k=2}^{\lfloor n/2\rfloor}\binom{n}{k}^2\,k^2\right).$$
Memory usage is dominated by storing all \(k\)-subsets for the current size, namely \(O\!\left(\binom{n}{k}k\right)\), with the largest layer near \(k=n/2\). For the actual input \(n=12\), these costs are tiny, which is why the implementations can afford brute-force enumeration even though the mathematics collapses to a short summation.
Sei \(A=\{a_1<a_2<\cdots<a_{12}\}\) eine Kandidatenmenge für eine Spezial-Summenmenge. Die zweite Spezial-Summen-Bedingung sagt bereits, dass bei zwei disjunkten Teilmengen die größere Teilmenge auch die größere Summe haben muss. Damit bleibt als möglicher Zweifelsfall nur ein Paar disjunkter Teilmengen \(B\) und \(C\) gleicher Größe. Problem 106 fragt, wie viele ungeordnete Paare \((B,C)\) noch explizit auf \(S(B)\neq S(C)\) geprüft werden müssen. Diese Zahl hängt nur von den relativen Positionen in der geordneten Menge ab; für \(n=12\) ergibt sich \(21384\).
Die Implementierungen arbeiten vollständig mit Indizes \(0,1,\dots,n-1\) und nicht mit den eigentlichen Werten der Menge. Genau darin liegt das zentrale Invarianzprinzip dieses Problems: Sobald die Menge streng wachsend ist, hängt die Frage nach einem notwendigen Test nur davon ab, wie sich die Positionen der beiden Teilmengen ineinander verschachteln.
Falls \(|B|\neq |C|\), schließt die zweite Spezial-Summen-Bedingung Gleichheit sofort aus. Falls \(|B|=|C|=1\), ist Gleichheit ebenfalls unmöglich, weil alle Elemente verschieden sind. Nichttrivial sind also nur die Fälle
$$|B|=|C|=k,\qquad 2\le k\le \left\lfloor\frac{n}{2}\right\rfloor.$$
Schreibe die beiden Teilmengen sortiert als
$$B=\{b_1<b_2<\cdots<b_k\},\qquad C=\{c_1<c_2<\cdots<c_k\}.$$
Gilt \(b_i<c_i\) für jedes \(i\), dann ist jedes zu \(B\) gehörige Element kleiner als das entsprechende Element von \(C\), also
$$a_{b_1}+a_{b_2}+\cdots+a_{b_k}<a_{c_1}+a_{c_2}+\cdots+a_{c_k}.$$
Dasselbe Argument gilt vertauscht, wenn \(c_i<b_i\) für alle \(i\). In beiden Fällen ist die Summenordnung automatisch und kein Test nötig. Ein Paar muss genau dann geprüft werden, wenn der koordinatenweise Vergleich irgendwo die Richtung wechselt.
Zuerst wählt man die \(2k\) beteiligten Positionen und teilt sie dann in zwei unmarkierte \(k\)-Teilmengen. Das liefert
$$\binom{n}{2k}\cdot\frac{1}{2}\binom{2k}{k}$$
ungeordnete disjunkte Paare mit \(|B|=|C|=k\).
Fixiere eine gewählte Positionsmenge \(x_1<x_2<\cdots<x_{2k}\). Jede Aufteilung in zwei \(k\)-Teilmengen lässt sich durch ein Wort der Länge \(2k\) kodieren: Schreibe \(B\), wenn \(x_j\) zur ersten Teilmenge gehört, und \(C\), wenn \(x_j\) zur zweiten gehört. Damit ein ungeordnetes Paar nur einmal gezählt wird, orientiert man es so, dass \(x_1\in B\) gilt.
Unter dieser Orientierung ist die Bedingung \(b_i<c_i\) für alle \(i\) äquivalent dazu, dass in jedem Präfix des Wortes mindestens so viele \(B\) wie \(C\) vorkommen. Bevor das erste \(C\) erscheinen kann, muss es bereits ein \(B\) geben; vor dem zweiten \(C\) müssen es bereits zwei \(B\) sein; und so weiter. Genau diese präfixbalancierten Wörter sind Dyck-Wörter der Halblänge \(k\), also ist ihre Anzahl die Catalan-Zahl
$$C_k=\frac{1}{k+1}\binom{2k}{k}.$$
Für jede feste Auswahl der \(2k\) Positionen gibt es daher \(C_k\) automatisch geordnete ungeordnete Paare, und die Zahl der tatsächlich zu prüfenden Paare ist
$$\frac{1}{2}\binom{2k}{k}-C_k=\frac{k-1}{2(k+1)}\binom{2k}{k}.$$
Betrachte vier geordnete Positionen \(x_1<x_2<x_3<x_4\). Es gibt genau drei ungeordnete Aufteilungen in zwei Paare:
$$\{x_1,x_2\}\mid\{x_3,x_4\},\qquad \{x_1,x_3\}\mid\{x_2,x_4\},\qquad \{x_1,x_4\}\mid\{x_2,x_3\}.$$
Die ersten beiden sind automatisch entschieden, weil eines der sortierten Paare koordinatenweise kleiner ist als das andere. Nur die dritte Aufteilung ist eine Kreuzungskonfiguration und braucht daher einen echten Summenvergleich. Das stimmt mit
$$\frac{1}{2}\binom{4}{2}-C_2=3-2=1$$
überein; genau dies ist auch der Kontrollwert für \(n=4\).
Über alle zulässigen Teilmengengrößen summiert erhält man
$$T(n)=\sum_{k=2}^{\lfloor n/2\rfloor}\binom{n}{2k}\left(\frac{1}{2}\binom{2k}{k}-\frac{1}{k+1}\binom{2k}{k}\right).$$
Für \(n=12\) sind die Beiträge
$$\binom{12}{4}(3-2)=495,\qquad \binom{12}{6}(10-5)=4620,\qquad \binom{12}{8}(35-14)=10395,$$
$$\binom{12}{10}(126-42)=5544,\qquad \binom{12}{12}(462-132)=330,$$
also insgesamt
$$T(12)=495+4620+10395+5544+330=21384.$$
Die Implementierungen in C++, Python und Java verwenden die Catalan-Formel nicht direkt. Stattdessen berechnen sie dieselbe Anzahl durch explizite Enumeration, was bei \(n=12\) problemlos praktikabel ist.
Für jedes \(k=2,3,\dots,\lfloor n/2\rfloor\) wird jede \(k\)-Teilmenge von \(\{0,1,\dots,n-1\}\) erzeugt. Die C++-Version benutzt dafür Integer-Masken, Python verwendet Kombinationen und Java konstruiert die Arrays rekursiv. In allen drei Fällen liegen die Teilmengen bereits sortiert vor.
Die verschachtelten Schleifen betrachten jedes ungeordnete Paar erzeugter Teilmengen. Zuerst werden alle nicht-disjunkten Paare verworfen. Bei den verbleibenden Paaren werden die sortierten Positionen einander gegenübergestellt. Wenn jede Position der einen Teilmenge kleiner ist als die entsprechende Position der anderen, ist das Paar automatisch geordnet und wird übersprungen. Nur Kreuzungsmuster erhöhen den Zähler.
Eine Implementierung prüft vor \(n=12\) zusätzlich die kleineren Fälle \(n=4\) und \(n=7\). Die erwarteten Werte sind \(1\) und \(70\), und aus derselben Formel folgt
$$T(7)=\binom{7}{4}(3-2)+\binom{7}{6}(10-5)=35+35=70.$$
Sei \(M_k=\binom{n}{k}\). Für festes \(k\) betrachtet die direkte Enumeration \(\binom{M_k}{2}\) ungeordnete Paare von \(k\)-Teilmengen. Der koordinatenweise Vergleich kostet \(O(k)\), und der Disjunktheitstest kostet in den Tupel- und Array-Varianten im schlimmsten Fall \(O(k^2)\). Damit ist eine sichere Schranke für den implementierten Ansatz
$$O\!\left(\sum_{k=2}^{\lfloor n/2\rfloor}\binom{n}{k}^2\,k^2\right).$$
Der Speicherbedarf wird vom Vorhalten aller \(k\)-Teilmengen einer Größe dominiert, also \(O\!\left(\binom{n}{k}k\right)\), mit dem Maximum nahe \(k=n/2\). Für den konkreten Eingabefall \(n=12\) sind diese Kosten sehr klein; deshalb ist die brute-force Zählung in den Implementierungen völlig ausreichend, obwohl die Mathematik am Ende auf eine kurze Summe hinausläuft.
\(A=\{a_1<a_2<\cdots<a_{12}\}\) artan bir aday özel toplam kümesi olsun. İkinci özel-toplam kuralı, ayrık iki alt kümeden daha fazla elemana sahip olanın toplamının da daha büyük olması gerektiğini zaten söyler. Bu yüzden belirsizlik ancak aynı büyüklükteki ayrık iki alt küme \(B\) ve \(C\) için kalır. Problem 106, \(S(B)\neq S(C)\) sonucunu açıkça test etmemiz gereken sırasız \((B,C)\) çiftlerinin sayısını sorar. Bu sayı gerçek değerlerden değil, yalnızca sıralı küme içindeki göreli konumlardan etkilenir; \(n=12\) için sonuç \(21384\) olur.
Uygulamalar gerçek sayıların kendisiyle değil, yalnızca \(0,1,\dots,n-1\) indisleriyle çalışır. Problemin temel değişmezi budur: küme sıkı artan olduğu sürece, iki eşit boyutlu alt kümenin otomatik olarak sıralanıp sıralanmadığını belirleyen şey sadece konumların nasıl iç içe geçtiğidir.
Eğer \(|B|\neq |C|\) ise ikinci özel-toplam koşulu eşit toplam ihtimalini zaten ortadan kaldırır. Eğer \(|B|=|C|=1\) ise bütün elemanlar farklı olduğundan eşitlik yine imkansızdır. Dolayısıyla asıl zor kısım yalnızca
$$|B|=|C|=k,\qquad 2\le k\le \left\lfloor\frac{n}{2}\right\rfloor$$
durumlarıdır.
İki alt kümeyi sıralı biçimde yazalım:
$$B=\{b_1<b_2<\cdots<b_k\},\qquad C=\{c_1<c_2<\cdots<c_k\}.$$
Eğer her \(i\) için \(b_i<c_i\) ise, \(B\)'den seçilen her eleman \(C\)'deki karşılık gelen elemandan küçüktür; dolayısıyla
$$a_{b_1}+a_{b_2}+\cdots+a_{b_k}<a_{c_1}+a_{c_2}+\cdots+a_{c_k}.$$
Aynı argüman bütün \(i\)'ler için \(c_i<b_i\) olduğunda da geçerlidir. Bu iki durumda toplamların sırası otomatik belirlenir ve ayrıca eşitlik testi yapmak gerekmez. Gerçekten test gerektiren çiftler, koordinat bazındaki karşılaştırmanın bir yerde yön değiştirdiği, yani bazı konumlarda \(B\) öndeyken bazı konumlarda \(C\)'nin öne geçtiği desenlerdir.
Önce kullanılan \(2k\) konumu seçer, sonra bunları etiketlenmemiş iki \(k\)-alt kümeye ayırırız. Böylece
$$\binom{n}{2k}\cdot\frac{1}{2}\binom{2k}{k}$$
adet sırasız ayrık çift elde edilir.
Sabit bir \(x_1<x_2<\cdots<x_{2k}\) konum kümesi alalım. Bunu iki \(k\)-alt kümeye ayırmanın her yolu, uzunluğu \(2k\) olan bir sözcükle kodlanabilir: \(x_j\) birinci alt kümeye gidiyorsa \(B\), ikinciye gidiyorsa \(C\) yazalım. Her sırasız çifti tam bir kez saymak için yönü \(x_1\in B\) olacak şekilde seçelim.
Bu yönlendirme altında, her \(i\) için \(b_i<c_i\) koşulu ile her önekteki \(B\) sayısının en az \(C\) sayısı kadar olması eşdeğerdir. Birinci \(C\) gelmeden önce en az bir \(B\), ikinci \(C\) gelmeden önce en az iki \(B\) görülmüş olmalıdır; düzen tam olarak budur. Bu önek dengesi sağlayan sözcükler yarı uzunluğu \(k\) olan Dyck sözcükleridir ve sayıları Catalan sayısıdır:
$$C_k=\frac{1}{k+1}\binom{2k}{k}.$$
Demek ki sabit bir \(2k\) konum seçimi için otomatik sıralanan sırasız çift sayısı \(C_k\), gerçekten test gerektiren çift sayısı ise
$$\frac{1}{2}\binom{2k}{k}-C_k=\frac{k-1}{2(k+1)}\binom{2k}{k}$$
olur.
Dört sıralı konum alalım: \(x_1<x_2<x_3<x_4\). Bunları iki çifte ayırmanın tam üç sırasız yolu vardır:
$$\{x_1,x_2\}\mid\{x_3,x_4\},\qquad \{x_1,x_3\}\mid\{x_2,x_4\},\qquad \{x_1,x_4\}\mid\{x_2,x_3\}.$$
İlk iki durumda bir sıralı çift diğerinin koordinat bazında tamamen altındadır; dolayısıyla toplam sırası otomatik belirlenir. Sadece üçüncü desen çaprazlama içerir ve gerçek bir toplam karşılaştırması gerektirir. Bu da
$$\frac{1}{2}\binom{4}{2}-C_2=3-2=1$$
sonucuyla tam uyumludur; aynı değer \(n=4\) için kullanılan küçük kontrol sonucudur.
Bütün uygun alt küme boyutları üzerinden toplarsak
$$T(n)=\sum_{k=2}^{\lfloor n/2\rfloor}\binom{n}{2k}\left(\frac{1}{2}\binom{2k}{k}-\frac{1}{k+1}\binom{2k}{k}\right)$$
elde edilir. \(n=12\) için katkılar
$$\binom{12}{4}(3-2)=495,\qquad \binom{12}{6}(10-5)=4620,\qquad \binom{12}{8}(35-14)=10395,$$
$$\binom{12}{10}(126-42)=5544,\qquad \binom{12}{12}(462-132)=330,$$
olur; dolayısıyla
$$T(12)=495+4620+10395+5544+330=21384.$$
C++, Python ve Java uygulamaları Catalan kapalı formülünü doğrudan kullanmaz. Bunun yerine aynı sayımı açık enumerasyonla yaparlar; hedef örnek \(n=12\) olduğu için bu yaklaşım rahatlıkla yeterlidir.
Her \(k=2,3,\dots,\lfloor n/2\rfloor\) için \(\{0,1,\dots,n-1\}\) kümesinin bütün \(k\)-alt kümeleri üretilir. C++ sürümü tamsayı maskeleri kullanır, Python sürümü kombinasyon üretir, Java sürümü ise dizileri özyinelemeli kurar. Her durumda eldeki alt kümeler zaten sıralıdır.
İç içe döngüler üretilen alt kümelerin her sırasız çiftini gezer. Önce kesişimi olan çiftler atılır. Geri kalanlarda sıralı konumlar tek tek karşılaştırılır. Eğer bir alt kümenin bütün konumları diğer alt kümenin karşılık gelen konumlarından küçükse, bu çift otomatik sıralanmıştır ve sayılmaz. Sayaç yalnızca çaprazlama içeren desenlerde artar.
Uygulamalardan biri \(n=12\) sonucunu yazmadan önce \(n=4\) ve \(n=7\) için küçük doğrulamalar yapar. Beklenen değerler \(1\) ve \(70\)'tir; yukarıdaki aynı formül
$$T(7)=\binom{7}{4}(3-2)+\binom{7}{6}(10-5)=35+35=70$$
verir.
\(M_k=\binom{n}{k}\) olsun. Sabit bir \(k\) için doğrudan enumerasyon \(\binom{M_k}{2}\) adet \(k\)-alt küme çiftini inceler. Koordinat bazlı karşılaştırma \(O(k)\), kesişim testi ise tuple ve dizi tabanlı sürümlerde en kötü durumda \(O(k^2)\) maliyetlidir. Bu yüzden uygulanan yaklaşım için güvenli üst sınır
$$O\!\left(\sum_{k=2}^{\lfloor n/2\rfloor}\binom{n}{k}^2\,k^2\right)$$
şeklindedir. Bellek kullanımı, o anki boyut için bütün \(k\)-alt kümelerini saklamaktan gelir ve \(O\!\left(\binom{n}{k}k\right)\) mertebesindedir; en büyük katman \(k\approx n/2\) civarındadır. Gerçek girdi \(n=12\) olduğundan bu maliyetler çok küçüktür; bu nedenle matematik kısa bir toplama indirgenebilse de, doğrudan enumerasyon pratikte tamamen yeterlidir.
Sea \(A=\{a_1<a_2<\cdots<a_{12}\}\) un candidato a conjunto especial de suma. La segunda regla de estos conjuntos ya garantiza que, si dos subconjuntos disjuntos tienen distinto tamaño, entonces el de mayor cardinalidad tiene suma mayor. Por tanto, la única ambigüedad posible aparece entre dos subconjuntos disjuntos \(B\) y \(C\) del mismo tamaño. El Problema 106 pide contar cuántos pares no ordenados \((B,C)\) todavía requieren una comprobación explícita de \(S(B)\neq S(C)\). Ese conteo depende solo de las posiciones relativas dentro del conjunto ordenado, y para \(n=12\) vale \(21384\).
Las implementaciones trabajan únicamente con índices \(0,1,\dots,n-1\), no con los valores concretos del conjunto. Esa es la invariante central del problema: una vez que el conjunto es estrictamente creciente, decidir si dos subconjuntos del mismo tamaño quedan ordenados automáticamente depende solo del patrón de entrelazamiento de sus posiciones.
Si \(|B|\neq |C|\), la segunda condición especial ya descarta la igualdad de sumas. Si \(|B|=|C|=1\), la igualdad también es imposible porque todos los elementos son distintos. Así, los únicos casos no triviales son
$$|B|=|C|=k,\qquad 2\le k\le \left\lfloor\frac{n}{2}\right\rfloor.$$
Escribamos ambos subconjuntos en orden creciente:
$$B=\{b_1<b_2<\cdots<b_k\},\qquad C=\{c_1<c_2<\cdots<c_k\}.$$
Si \(b_i<c_i\) para todo \(i\), entonces cada elemento escogido en \(B\) es menor que el elemento correspondiente escogido en \(C\), y por tanto
$$a_{b_1}+a_{b_2}+\cdots+a_{b_k}<a_{c_1}+a_{c_2}+\cdots+a_{c_k}.$$
La misma idea funciona al revés cuando \(c_i<b_i\) para todo \(i\). En ambos casos, el orden de las sumas queda resuelto automáticamente y no hace falta una prueba de igualdad. Un par necesita prueba precisamente cuando la comparación coordenada a coordenada cambia de signo en algún punto.
Primero se eligen las \(2k\) posiciones que participan y luego se dividen en dos subconjuntos no etiquetados de tamaño \(k\). Eso produce
$$\binom{n}{2k}\cdot\frac{1}{2}\binom{2k}{k}$$
pares disjuntos no ordenados con \(|B|=|C|=k\).
Fijemos una elección concreta \(x_1<x_2<\cdots<x_{2k}\). Cualquier partición en dos subconjuntos de tamaño \(k\) puede codificarse con una palabra de longitud \(2k\): escribimos \(B\) si \(x_j\) va al primer subconjunto y \(C\) si va al segundo. Para contar cada par no ordenado una sola vez, orientamos la partición de modo que \(x_1\in B\).
Con esa orientación, la condición \(b_i<c_i\) para todo \(i\) equivale a exigir que en todo prefijo de la palabra haya al menos tantas letras \(B\) como letras \(C\). Antes de que aparezca la primera \(C\) ya debe haber aparecido una \(B\); antes de la segunda \(C\) ya deben haber aparecido dos \(B\); y así sucesivamente. Esas palabras equilibradas por prefijos son palabras de Dyck de semilongitud \(k\), y por tanto se cuentan con el número de Catalan
$$C_k=\frac{1}{k+1}\binom{2k}{k}.$$
En consecuencia, para cada conjunto fijo de \(2k\) posiciones, el número de pares no ordenados que quedan resueltos automáticamente es \(C_k\), y el número de pares que sí requieren prueba es
$$\frac{1}{2}\binom{2k}{k}-C_k=\frac{k-1}{2(k+1)}\binom{2k}{k}.$$
Tomemos cuatro posiciones ordenadas \(x_1<x_2<x_3<x_4\). Hay exactamente tres particiones no ordenadas en dos pares:
$$\{x_1,x_2\}\mid\{x_3,x_4\},\qquad \{x_1,x_3\}\mid\{x_2,x_4\},\qquad \{x_1,x_4\}\mid\{x_2,x_3\}.$$
Las dos primeras son automáticas porque uno de los pares ordenados es menor coordenada a coordenada que el otro. La tercera es la única configuración con cruce, así que es la única que necesita comparar sumas de verdad. Esto coincide con
$$\frac{1}{2}\binom{4}{2}-C_2=3-2=1,$$
que también es el valor de comprobación para \(n=4\).
Al sumar sobre todos los tamaños posibles de subconjunto se obtiene
$$T(n)=\sum_{k=2}^{\lfloor n/2\rfloor}\binom{n}{2k}\left(\frac{1}{2}\binom{2k}{k}-\frac{1}{k+1}\binom{2k}{k}\right).$$
Para \(n=12\), las contribuciones son
$$\binom{12}{4}(3-2)=495,\qquad \binom{12}{6}(10-5)=4620,\qquad \binom{12}{8}(35-14)=10395,$$
$$\binom{12}{10}(126-42)=5544,\qquad \binom{12}{12}(462-132)=330,$$
y por tanto
$$T(12)=495+4620+10395+5544+330=21384.$$
Las implementaciones en C++, Python y Java no aplican directamente la fórmula cerrada con Catalan. En cambio, calculan la misma cantidad por enumeración explícita, algo perfectamente viable porque el caso objetivo es solo \(n=12\).
Para cada \(k=2,3,\dots,\lfloor n/2\rfloor\), la implementación genera todos los subconjuntos de tamaño \(k\) de \(\{0,1,\dots,n-1\}\). La versión en C++ usa máscaras enteras, la de Python utiliza combinaciones y la de Java construye arreglos de forma recursiva. En todos los casos, los subconjuntos quedan almacenados en orden creciente.
Los bucles anidados recorren cada par no ordenado de subconjuntos generados. Primero descartan cualquier par que no sea disjunto. Después comparan las posiciones ordenadas una a una. Si todas las posiciones de un subconjunto son menores que las posiciones correspondientes del otro, el par queda automáticamente resuelto y se omite. Solo los patrones con cruce incrementan el contador.
Una de las implementaciones también valida los casos pequeños \(n=4\) y \(n=7\) antes de evaluar \(n=12\). Los valores esperados son \(1\) y \(70\), y la misma fórmula produce
$$T(7)=\binom{7}{4}(3-2)+\binom{7}{6}(10-5)=35+35=70.$$
Sea \(M_k=\binom{n}{k}\). Para un \(k\) fijo, la enumeración directa inspecciona \(\binom{M_k}{2}\) pares no ordenados de subconjuntos de tamaño \(k\). La comparación coordenada a coordenada cuesta \(O(k)\), y la prueba de disjunción cuesta como mucho \(O(k^2)\) en las versiones basadas en tuplas y arreglos. Una cota segura para el enfoque implementado es entonces
$$O\!\left(\sum_{k=2}^{\lfloor n/2\rfloor}\binom{n}{k}^2\,k^2\right).$$
La memoria está dominada por el almacenamiento de todos los subconjuntos de tamaño \(k\), es decir, \(O\!\left(\binom{n}{k}k\right)\), con el mayor nivel cerca de \(k=n/2\). Para el dato real \(n=12\), estos costos son mínimos; por eso la enumeración directa es suficiente aunque la matemática final se reduzca a una suma corta.
设 \(A=\{a_1<a_2<\cdots<a_{12}\}\) 是一个候选的特殊和集合。题目中的第二条特殊和规则已经保证：如果两个不相交子集的元素个数不同，那么元素更多的那个子集其和一定更大。因此真正还可能产生歧义的，只剩下大小相同的两个不相交子集 \(B\) 和 \(C\)。Problem 106 要求计算的是：到底有多少个无序对子 \((B,C)\) 还必须显式检验 \(S(B)\neq S(C)\)。这个数量只取决于它们在有序集合中的相对位置，而不取决于具体数值；当 \(n=12\) 时，总数是 \(21384\)。
三个实现都没有直接处理真实集合元素，而是只处理下标 \(0,1,\dots,n-1\)。这正是本题最重要的不变量：只要集合严格递增，两个等大小子集之间是否能被“自动判定”，完全由它们的位置交错方式决定。
如果 \(|B|\neq |C|\)，那么第二条特殊和条件已经排除了两者和相等的可能。如果 \(|B|=|C|=1\)，由于所有元素互不相同，和相等也不可能发生。所以真正非平凡的情况只有
$$|B|=|C|=k,\qquad 2\le k\le \left\lfloor\frac{n}{2}\right\rfloor.$$
把两个子集都按升序写成
$$B=\{b_1<b_2<\cdots<b_k\},\qquad C=\{c_1<c_2<\cdots<c_k\}.$$
如果对每个 \(i\) 都有 \(b_i<c_i\)，那么 \(B\) 中第 \(i\) 小的元素一定小于 \(C\) 中第 \(i\) 小的元素，于是
$$a_{b_1}+a_{b_2}+\cdots+a_{b_k}<a_{c_1}+a_{c_2}+\cdots+a_{c_k}.$$
如果对每个 \(i\) 都有 \(c_i<b_i\)，结论同样成立，只是大小关系反过来。这两种情况都不需要额外做和的相等性测试。真正需要检查的，恰恰是坐标逐位比较时发生“交叉”的那些模式，也就是有些位置上 \(B\) 更小，而另一些位置上 \(C\) 更小。
先从 \(n\) 个位置中选出参与的 \(2k\) 个位置，再把它们拆成两个无标号的 \(k\)-子集，于是无序不相交对子总数为
$$\binom{n}{2k}\cdot\frac{1}{2}\binom{2k}{k}.$$
固定一组位置 \(x_1<x_2<\cdots<x_{2k}\)。把它们分成两个 \(k\)-子集的任何方式，都可以编码成一个长度为 \(2k\) 的字符串：若 \(x_j\) 分到第一个子集就写 \(B\)，分到第二个子集就写 \(C\)。为了让每个无序对子只算一次，我们规定方向，使得 \(x_1\in B\)。
在这种定向下，“对所有 \(i\) 都有 \(b_i<c_i\)” 与下面的前缀条件完全等价：对这个字符串的任意前缀，其中的 \(B\) 个数都不少于 \(C\) 个数。理由很直接：在第一个 \(C\) 出现之前，至少要先出现一个 \(B\)；在第二个 \(C\) 出现之前，至少要先出现两个 \(B\)；一般地，在第 \(i\) 个 \(C\) 出现之前，必须已经有 \(i\) 个 \(B\)。满足这种前缀平衡条件的正是半长度为 \(k\) 的 Dyck 词，其数量是 Catalan 数
$$C_k=\frac{1}{k+1}\binom{2k}{k}.$$
因此，对每一组固定的 \(2k\) 个位置，能够自动判定的无序对子有 \(C_k\) 个，真正还需要测试的有
$$\frac{1}{2}\binom{2k}{k}-C_k=\frac{k-1}{2(k+1)}\binom{2k}{k}$$
个。
取四个有序位置 \(x_1<x_2<x_3<x_4\)。把它们分成两个二元子集的无序方式只有三种：
$$\{x_1,x_2\}\mid\{x_3,x_4\},\qquad \{x_1,x_3\}\mid\{x_2,x_4\},\qquad \{x_1,x_4\}\mid\{x_2,x_3\}.$$
前两种都是自动成立的，因为一边的有序下标逐位都小于另一边。第三种是唯一发生交叉的模式，所以它是唯一必须真正比较子集和的情况。这与公式
$$\frac{1}{2}\binom{4}{2}-C_2=3-2=1$$
完全一致；这也是 \(n=4\) 时的检查值。
把所有允许的 \(k\) 汇总起来，就得到
$$T(n)=\sum_{k=2}^{\lfloor n/2\rfloor}\binom{n}{2k}\left(\frac{1}{2}\binom{2k}{k}-\frac{1}{k+1}\binom{2k}{k}\right).$$
当 \(n=12\) 时，各项贡献分别是
$$\binom{12}{4}(3-2)=495,\qquad \binom{12}{6}(10-5)=4620,\qquad \binom{12}{8}(35-14)=10395,$$
$$\binom{12}{10}(126-42)=5544,\qquad \binom{12}{12}(462-132)=330,$$
于是
$$T(12)=495+4620+10395+5544+330=21384.$$
C++、Python 和 Java 实现并没有直接把 Catalan 闭式代入程序，而是用显式枚举把同一个组合计数算出来。因为目标规模只有 \(n=12\)，这种写法完全足够。
对每个 \(k=2,3,\dots,\lfloor n/2\rfloor\)，实现都会生成 \(\{0,1,\dots,n-1\}\) 的全部 \(k\)-子集。C++ 版本用整数位掩码表示子集，Python 版本直接调用组合生成器，Java 版本则递归构造数组。无论哪一种表示，子集内部都已经按升序排好。
双重循环遍历这些 \(k\)-子集的每一个无序对子。首先，凡是有公共元素的对子会立即跳过，因为题目只关心不相交子集。对剩下的对子，再逐位比较两个有序下标序列。如果一边在每一位上都小于另一边，那么这个对子已经自动有了严格的和大小关系，不必再测；只有发生交叉的模式才会使计数器加一。
其中一个实现会在计算 \(n=12\) 之前，先检查 \(n=4\) 和 \(n=7\) 这两个较小情形。对应答案分别是 \(1\) 和 \(70\)，而上面的同一公式也给出
$$T(7)=\binom{7}{4}(3-2)+\binom{7}{6}(10-5)=35+35=70.$$
记 \(M_k=\binom{n}{k}\)。对固定的 \(k\)，直接枚举要检查 \(\binom{M_k}{2}\) 个大小为 \(k\) 的无序子集对。逐位比较的代价是 \(O(k)\)，而在基于元组和数组的实现里，不相交性检查最坏是 \(O(k^2)\)。因此，对当前实现方式，一个稳妥的上界是
$$O\!\left(\sum_{k=2}^{\lfloor n/2\rfloor}\binom{n}{k}^2\,k^2\right).$$
空间方面，主要开销是保存某个 \(k\) 下的全部 \(k\)-子集，即 \(O\!\left(\binom{n}{k}k\right)\)，最大层出现在 \(k\) 接近 \(n/2\) 时。对实际输入 \(n=12\) 来说，这些成本都很小，因此虽然数学上已经能化成一条短求和，程序仍然完全可以使用直接枚举。
Пусть \(A=\{a_1<a_2<\cdots<a_{12}\}\) — кандидат на специальное множество сумм. Второе условие таких множеств уже гарантирует, что если две непересекающиеся подмножества имеют разную мощность, то сумма большего по размеру подмножества обязана быть больше. Значит, потенциальная неоднозначность возможна только для двух непересекающихся подмножеств \(B\) и \(C\) одинаковой мощности. В задаче 106 требуется посчитать, сколько неупорядоченных пар \((B,C)\) все еще нуждаются в явной проверке \(S(B)\neq S(C)\). Это число зависит только от относительных позиций элементов в упорядоченном множестве, а для \(n=12\) оно равно \(21384\).
Во всех реализациях используются не сами значения множества, а только индексы \(0,1,\dots,n-1\). Это и есть главный инвариант задачи: как только множество строго возрастает, вопрос о том, определяется ли порядок сумм автоматически, зависит лишь от того, как переплетаются позиции двух одинаковых по размеру подмножеств.
Если \(|B|\neq |C|\), то второе специальное условие сразу исключает равенство сумм. Если \(|B|=|C|=1\), равенство тоже невозможно, потому что все элементы различны. Поэтому нетривиальны только случаи
$$|B|=|C|=k,\qquad 2\le k\le \left\lfloor\frac{n}{2}\right\rfloor.$$
Запишем оба подмножества в отсортированном виде:
$$B=\{b_1<b_2<\cdots<b_k\},\qquad C=\{c_1<c_2<\cdots<c_k\}.$$
Если для каждого \(i\) выполнено \(b_i<c_i\), то \(i\)-й по величине элемент из \(B\) меньше \(i\)-го по величине элемента из \(C\), а значит
$$a_{b_1}+a_{b_2}+\cdots+a_{b_k}<a_{c_1}+a_{c_2}+\cdots+a_{c_k}.$$
Тот же довод работает и в обратную сторону, если для всех \(i\) выполнено \(c_i<b_i\). В обеих ситуациях порядок сумм известен заранее, и проверка на равенство не нужна. Проверять приходится ровно те пары, где покоординатное сравнение меняет направление: на одних местах впереди \(B\), а на других — \(C\).
Сначала выбираются \(2k\) используемых позиций, затем они разбиваются на два неразмеченных подмножества размера \(k\). Итого получаем
$$\binom{n}{2k}\cdot\frac{1}{2}\binom{2k}{k}$$
неупорядоченных непересекающихся пар с \(|B|=|C|=k\).
Зафиксируем один набор позиций \(x_1<x_2<\cdots<x_{2k}\). Любое разбиение на два \(k\)-подмножества можно закодировать словом длины \(2k\): пишем \(B\), если \(x_j\) идет в первое подмножество, и \(C\), если во второе. Чтобы не считать одну неупорядоченную пару дважды, выбираем ориентацию так, чтобы \(x_1\in B\).
При такой ориентации условие \(b_i<c_i\) для всех \(i\) эквивалентно тому, что в каждом префиксе слова число букв \(B\) не меньше числа букв \(C\). До появления первой буквы \(C\) должна уже встретиться одна \(B\); до второй \(C\) — уже две \(B\); и так далее. Именно такие префиксно-сбалансированные слова являются словами Дика полудлины \(k\), а их количество равно числу Каталана
$$C_k=\frac{1}{k+1}\binom{2k}{k}.$$
Значит, для каждого фиксированного набора из \(2k\) позиций автоматически упорядоченных неупорядоченных пар ровно \(C_k\), а действительно требующих проверки —
$$\frac{1}{2}\binom{2k}{k}-C_k=\frac{k-1}{2(k+1)}\binom{2k}{k}.$$
Возьмем четыре упорядоченные позиции \(x_1<x_2<x_3<x_4\). Существуют ровно три неупорядоченных разбиения на две пары:
$$\{x_1,x_2\}\mid\{x_3,x_4\},\qquad \{x_1,x_3\}\mid\{x_2,x_4\},\qquad \{x_1,x_4\}\mid\{x_2,x_3\}.$$
Первые два случая автоматические, потому что одна отсортированная пара покоординатно меньше другой. Третий вариант — единственная конфигурация с пересечением порядка, поэтому только она требует реального сравнения сумм. Это совпадает с формулой
$$\frac{1}{2}\binom{4}{2}-C_2=3-2=1,$$
что также является контрольным значением для \(n=4\).
Суммируя по всем допустимым размерам подмножеств, получаем
$$T(n)=\sum_{k=2}^{\lfloor n/2\rfloor}\binom{n}{2k}\left(\frac{1}{2}\binom{2k}{k}-\frac{1}{k+1}\binom{2k}{k}\right).$$
При \(n=12\) вклады равны
$$\binom{12}{4}(3-2)=495,\qquad \binom{12}{6}(10-5)=4620,\qquad \binom{12}{8}(35-14)=10395,$$
$$\binom{12}{10}(126-42)=5544,\qquad \binom{12}{12}(462-132)=330,$$
поэтому
$$T(12)=495+4620+10395+5544+330=21384.$$
Реализации на C++, Python и Java не используют формулу с числами Каталана напрямую. Вместо этого они вычисляют ту же величину явным перебором, что вполне приемлемо при целевом размере \(n=12\).
Для каждого \(k=2,3,\dots,\lfloor n/2\rfloor\) программа генерирует все \(k\)-подмножества множества \(\{0,1,\dots,n-1\}\). В версии на C++ подмножества кодируются битовыми масками, в Python используются комбинации, а в Java массивы строятся рекурсивно. Во всех трех вариантах подмножества уже хранятся в отсортированном виде.
Вложенные циклы перебирают каждую неупорядоченную пару сгенерированных подмножеств. Сначала отбрасываются все пары, которые не являются непересекающимися. Затем оставшиеся пары сравниваются покоординатно. Если одно подмножество на каждой позиции меньше другого, пара автоматически упорядочена и пропускается. Счетчик увеличивается только для пересекающихся шаблонов порядка.
Одна из реализаций дополнительно проверяет малые случаи \(n=4\) и \(n=7\) перед тем, как вычислять \(n=12\). Ожидаемые ответы равны \(1\) и \(70\), причем та же формула дает
$$T(7)=\binom{7}{4}(3-2)+\binom{7}{6}(10-5)=35+35=70.$$
Пусть \(M_k=\binom{n}{k}\). Для фиксированного \(k\) прямой перебор рассматривает \(\binom{M_k}{2}\) неупорядоченных пар \(k\)-подмножеств. Покоординатное сравнение стоит \(O(k)\), а проверка на непересечение в версиях на кортежах и массивах в худшем случае стоит \(O(k^2)\). Поэтому надежная верхняя оценка для реализованного подхода такова:
$$O\!\left(\sum_{k=2}^{\lfloor n/2\rfloor}\binom{n}{k}^2\,k^2\right).$$
Память в основном уходит на хранение всех \(k\)-подмножеств текущего размера, то есть \(O\!\left(\binom{n}{k}k\right)\), с максимальным слоем около \(k=n/2\). Для реального входа \(n=12\) эти расходы ничтожны, поэтому полный перебор в реализациях вполне разумен, хотя математически задача сводится к короткой сумме.
لتكن \(A=\{a_1<a_2<\cdots<a_{12}\}\) مجموعة مرشحة من نوع المجموع الخاص. الشرط الثاني في هذا النوع من المجموعات يضمن أصلًا أنه إذا كان لدينا مجموعتان جزئيتان منفصلتان بأحجام مختلفة، فإن المجموعة ذات العناصر الأكثر لا بد أن يكون مجموعها أكبر. لذلك فإن الغموض الحقيقي لا يبقى إلا عند زوجين منفصلين \(B\) و \(C\) لهما العدد نفسه من العناصر. تطلب المسألة 106 عدَّ الأزواج غير المرتبة \((B,C)\) التي ما زلنا نحتاج فيها إلى اختبار صريح للتأكد من أن \(S(B)\neq S(C)\). هذا العدد لا يعتمد على القيم الفعلية للعناصر، بل على مواقعها النسبية داخل المجموعة المرتبة فقط، ولحالة \(n=12\) تكون النتيجة \(21384\).
التطبيقات الثلاثة تعمل على الفهارس \(0,1,\dots,n-1\) بدلًا من القيم الحقيقية للعناصر. وهذه هي الفكرة الثابتة الأساسية في المسألة: ما دامت المجموعة مرتبة ترتيبًا تصاعديًا صارمًا، فإن معرفة ما إذا كان زوج من المجموعات الجزئية المتساوية الحجم يُحسم تلقائيًا أم لا تعتمد فقط على طريقة تشابك مواقع عناصره.
إذا كان \(|B|\neq |C|\)، فإن الشرط الثاني يستبعد مساواة المجموعين مباشرة. وإذا كان \(|B|=|C|=1\)، فالمساواة مستحيلة أيضًا لأن جميع العناصر مختلفة. إذن الحالات غير البديهية الوحيدة هي
$$|B|=|C|=k,\qquad 2\le k\le \left\lfloor\frac{n}{2}\right\rfloor.$$
لنكتب المجموعتين الجزئيتين بترتيب تصاعدي:
$$B=\{b_1<b_2<\cdots<b_k\},\qquad C=\{c_1<c_2<\cdots<c_k\}.$$
إذا تحقق \(b_i<c_i\) لكل \(i\)، فهذا يعني أن كل عنصر مختار في \(B\) أصغر من العنصر المناظر له في \(C\)، وبالتالي
$$a_{b_1}+a_{b_2}+\cdots+a_{b_k}<a_{c_1}+a_{c_2}+\cdots+a_{c_k}.$$
وينطبق المنطق نفسه مع تبديل الدورين إذا تحقق \(c_i<b_i\) لكل \(i\). في كلتا الحالتين يكون ترتيب المجموعين محسومًا سلفًا، ولا حاجة لاختبار مساواة فعلي. الأزواج التي تحتاج إلى اختبار هي بالضبط الأزواج التي يتغير فيها اتجاه المقارنة عنصرًا بعنصر؛ أي توجد مواضع يتقدم فيها \(B\) ومواضع أخرى يتقدم فيها \(C\).
نختار أولًا المواقع \(2k\) المشاركة، ثم نقسمها إلى مجموعتين غير معنونتين من الحجم \(k\). عدد الأزواج المنفصلة غير المرتبة الناتج هو
$$\binom{n}{2k}\cdot\frac{1}{2}\binom{2k}{k}.$$
ثبّت مجموعة مواقع معينة \(x_1<x_2<\cdots<x_{2k}\). كل طريقة لتقسيمها إلى مجموعتين من الحجم \(k\) يمكن ترميزها بكلمة طولها \(2k\): نكتب \(B\) إذا ذهب \(x_j\) إلى المجموعة الأولى، ونكتب \(C\) إذا ذهب إلى الثانية. ولكي نعد كل زوج غير مرتب مرة واحدة فقط، نختار الاتجاه بحيث يكون \(x_1\in B\).
مع هذا الاختيار، يصبح الشرط \(b_i<c_i\) لكل \(i\) مكافئًا لكون عدد رموز \(B\) في كل بادئة من الكلمة لا يقل عن عدد رموز \(C\). فقبل ظهور أول \(C\) يجب أن تكون قد ظهرت \(B\) واحدة على الأقل، وقبل ظهور ثاني \(C\) يجب أن تكون قد ظهرت رمزان من \(B\)، وهكذا. هذه الكلمات المتوازنة على مستوى البوادئ هي كلمات Dyck ذات نصف الطول \(k\)، وعددها هو عدد Catalan
$$C_k=\frac{1}{k+1}\binom{2k}{k}.$$
لذلك، لكل اختيار ثابت من \(2k\) موقعًا، يكون عدد الأزواج غير المرتبة التي تُحسم تلقائيًا هو \(C_k\)، بينما يكون عدد الأزواج التي تحتاج فعلًا إلى اختبار
$$\frac{1}{2}\binom{2k}{k}-C_k=\frac{k-1}{2(k+1)}\binom{2k}{k}.$$
خذ أربعة مواقع مرتبة \(x_1<x_2<x_3<x_4\). توجد ثلاث طرق غير مرتبة فقط لتقسيمها إلى زوجين:
$$\{x_1,x_2\}\mid\{x_3,x_4\},\qquad \{x_1,x_3\}\mid\{x_2,x_4\},\qquad \{x_1,x_4\}\mid\{x_2,x_3\}.$$
الحالتان الأوليان تُحسمان تلقائيًا لأن أحد الزوجين أصغر عنصرًا بعنصر من الآخر. أما الحالة الثالثة فهي النمط الوحيد الذي يحدث فيه تشابك، ولذلك فهي الوحيدة التي تتطلب مقارنة حقيقية للمجموعين. وهذا يطابق الصيغة
$$\frac{1}{2}\binom{4}{2}-C_2=3-2=1,$$
وهو أيضًا مقدار التحقق الصغير عند \(n=4\).
بجمع جميع الأحجام الممكنة للمجموعات الجزئية نحصل على
$$T(n)=\sum_{k=2}^{\lfloor n/2\rfloor}\binom{n}{2k}\left(\frac{1}{2}\binom{2k}{k}-\frac{1}{k+1}\binom{2k}{k}\right).$$
وعند \(n=12\) تكون المساهمات
$$\binom{12}{4}(3-2)=495,\qquad \binom{12}{6}(10-5)=4620,\qquad \binom{12}{8}(35-14)=10395,$$
$$\binom{12}{10}(126-42)=5544,\qquad \binom{12}{12}(462-132)=330,$$
ومن ثم
$$T(12)=495+4620+10395+5544+330=21384.$$
تطبيقات C++ و Python و Java لا تستخدم صيغة Catalan المغلقة مباشرة. بدلًا من ذلك، تحسب الكمية نفسها بعدٍّ صريح لكل الأنماط الممكنة، وهذا عملي تمامًا لأن الحالة المطلوبة هي فقط \(n=12\).
لكل \(k=2,3,\dots,\lfloor n/2\rfloor\)، يولّد التنفيذ جميع المجموعات الجزئية من الحجم \(k\) ضمن \(\{0,1,\dots,n-1\}\). إصدار C++ يستخدم أقنعة ثنائية صحيحة، وإصدار Python يستخدم التوافيق، وإصدار Java يبني المصفوفات بطريقة عودية. وفي كل حالة تكون المجموعة الجزئية المخزنة مرتبة مسبقًا.
تمر الحلقات المتداخلة على كل زوج غير مرتب من المجموعات الجزئية المولدة. أولًا تُحذف الأزواج التي ليست منفصلة. بعد ذلك تُقارن المواقع المرتبة عنصرًا بعنصر. إذا كانت جميع مواقع إحدى المجموعتين أصغر من المواقع المناظرة في المجموعة الأخرى، فالناتج محسوم تلقائيًا ويُتجاوز هذا الزوج. لا يزيد العداد إلا في حالات التشابك.
أحد التنفيذات يتحقق أيضًا من الحالتين الصغيرتين \(n=4\) و \(n=7\) قبل حساب \(n=12\). القيم المتوقعة هي \(1\) و \(70\)، والصيغة نفسها تعطي
$$T(7)=\binom{7}{4}(3-2)+\binom{7}{6}(10-5)=35+35=70.$$
ليكن \(M_k=\binom{n}{k}\). عند تثبيت \(k\)، يفحص العد المباشر \(\binom{M_k}{2}\) زوجًا غير مرتب من المجموعات الجزئية ذات الحجم \(k\). تكلفة المقارنة عنصرًا بعنصر هي \(O(k)\)، أما اختبار الانفصال ففي الإصدارات المعتمدة على الأزواج المرتبة والمصفوفات تكون كلفته في أسوأ الأحوال \(O(k^2)\). لذلك فإن حدًا علويًا آمنًا للتنفيذ الفعلي هو
$$O\!\left(\sum_{k=2}^{\lfloor n/2\rfloor}\binom{n}{k}^2\,k^2\right).$$
أما الذاكرة فتُستهلك أساسًا في تخزين جميع المجموعات الجزئية للحجم الحالي، أي \(O\!\left(\binom{n}{k}k\right)\)، ويظهر أكبر مستوى عندما يكون \(k\) قريبًا من \(n/2\). وبالنسبة إلى الإدخال الحقيقي \(n=12\)، تبقى هذه التكاليف صغيرة جدًا؛ ولهذا فإن العد المباشر في التطبيق مناسب تمامًا، رغم أن الاشتقاق الرياضي ينتهي إلى مجموع قصير.