Let \(\Lambda(n)\) denote the number of closed lambda-terms that can be written with at most \(n\) symbols, where terms that differ only by renaming bound variables are identified as the same object. The task is to compute \(\Lambda(2000)\) modulo \(10^9+7\).
A direct enumeration is hopeless at this scale. The effective strategy is to count terms by exact size, track how many binders are currently available, and postpone the cumulative sum until the very end.
For the exact-size dynamic program, define \(A_d(s)\) as the number of terms of exact size \(s\) that are built in a context with \(d\) available binders. The final answer is then
$$\Lambda(n)=\sum_{s=1}^{n} A_0(s).$$
The state \(d=0\) corresponds to closed terms, because at the outermost level there are no binders available for a free variable to reference.
Once \(\alpha\)-renaming is factored out, a variable occurrence is determined only by which enclosing abstraction it refers to. If the current context contains \(d\) surrounding binders, then there are exactly \(d\) valid variable choices.
That gives the variable contribution
$$d\mathbf{1}_{s=1},$$
where \(\mathbf{1}_{s=1}\) enforces that a variable has size \(1\). This is the same binder-depth viewpoint that underlies de Bruijn-style representations, but here we use it purely as a counting device.
The implementations encode the statement's size model in a very direct way. A variable has size \(1\). Wrapping a body in one abstraction adds \(5\) symbols. Forming an application of two subterms adds \(2\) symbols around the pair.
Therefore the exact-size counts satisfy the recurrence
$$A_d(s)=d\mathbf{1}_{s=1}+A_{d+1}(s-5)+\sum_{i=1}^{s-3} A_d(i)\,A_d(s-2-i),$$
with the usual convention that terms with non-positive or impossible sizes contribute \(0\). The application sum uses ordered pairs: exchanging the left and right child generally produces a different term.
Only finitely many depth states can matter for a target bound \(n\). To reach depth \(d\) from the top level, we must already have paid for \(d\) abstractions, which costs \(5d\) symbols. Even the cheapest completion below that point is a single variable of size \(1\).
Hence any contributing state must satisfy
$$5d+1\le n,$$
so the maximum relevant depth is
$$d_{\max}=\left\lfloor\frac{n-1}{5}\right\rfloor.$$
More generally, at depth \(d\) we only need exact sizes
$$1\le s\le n-5d.$$
This truncation is what makes the dynamic program finite and practical.
For fixed depth \(d\), define the ordered convolution
$$C_d(k)=\sum_{i+j=k} A_d(i)\,A_d(j).$$
Then the application contribution to size \(s\) is simply \(C_d(s-2)\). Recomputing that sum from scratch for every \(s\) would be wasteful, so the implementations maintain it incrementally while sweeping sizes upward.
After \(A_d(s)\) is known, it contributes to every future total \(C_d(s+u)\). If \(u\ne s\), the pair of size buckets \((s,u)\) can appear in both left-right orders, so the off-diagonal contribution is doubled. If \(u=s\), the product \(A_d(s)^2\) already counts all ordered pairs of two size-\(s\) terms, so no extra factor is needed.
At depth \(1\), there is exactly one size-\(1\) term, because the lone available binder can be referenced in exactly one way:
$$A_1(1)=1.$$
Therefore the first closed term appears at size \(6\), obtained by placing one abstraction around that size-\(1\) body:
$$A_0(6)=A_1(1)=1.$$
Next consider depth \(1\) and size \(4\). The only possibility is an application of two size-\(1\) variables, so
$$A_1(4)=A_1(1)\,A_1(1)=1.$$
Wrapping that in one abstraction gives the next closed term at size \(9\):
$$A_0(9)=A_1(4)=1.$$
Hence the first cumulative values are
$$\Lambda(6)=1,\qquad \Lambda(9)=2.$$
The same recurrence continues to produce the further small checkpoints
$$\Lambda(15)=20,\qquad \Lambda(35)=3166438,$$
which agree with the values used for implementation sanity checks.
The C++, Python, and Java implementations all follow the same recurrence. They start from the largest relevant depth \(d_{\max}=\lfloor(2000-1)/5\rfloor\) and move downward to depth \(0\). At any moment, only two depth layers are needed: the counts for the current depth and the counts for the next deeper depth.
For a fixed depth \(d\), the implementation sweeps the exact size \(s\) from \(1\) up to \(2000-5d\). Each value \(A_d(s)\) is assembled from three ingredients: the variable term \(d\mathbf{1}_{s=1}\), the abstraction term coming from depth \(d+1\) and size \(s-5\), and the application term read from the running convolution buffer at index \(s-2\).
After computing the count for size \(s\), the implementation updates the convolution buffer so that future sizes can reuse this new information immediately. All arithmetic is reduced modulo \(10^9+7\). Once depth \(0\) has been completed, the exact counts are prefix-summed to obtain \(\Lambda(1),\Lambda(2),\dots,\Lambda(2000)\), and the final reported value is \(\Lambda(2000)\).
At depth \(d\), the active size window is \(S=2000-5d\), and the incremental convolution updates cost \(O(S^2)\). Summing over all relevant depths gives
$$\sum_{d=0}^{\lfloor(2000-1)/5\rfloor} O\!\left((2000-5d)^2\right)=O(2000^3),$$
so the asymptotic running time is cubic in the target size bound \(n\). The memory usage is only linear, because the algorithm stores two exact-size arrays and one auxiliary convolution array, each of length \(O(n)\).
Sei \(\Lambda(n)\) die Anzahl geschlossener Lambda-Terme, die sich mit höchstens \(n\) Symbolen schreiben lassen, wobei Terme, die sich nur durch Umbenennung gebundener Variablen unterscheiden, als identisch gezählt werden. Gesucht ist \(\Lambda(2000)\) modulo \(10^9+7\).
Eine direkte Erzeugung aller Kandidaten ist bei dieser Größe aussichtslos. Deshalb zählen die Implementierungen Terme nach exakter Größe, verfolgen die aktuell verfügbaren Binder und bilden die kumulative Summe erst ganz am Ende.
Für die exakte Größen-Dynamik definieren wir \(A_d(s)\) als die Anzahl der Terme mit exakter Größe \(s\) in einem Kontext mit \(d\) verfügbaren Bindern. Die gesuchte Größe ist dann
$$\Lambda(n)=\sum_{s=1}^{n} A_0(s).$$
Der Zustand \(d=0\) entspricht geschlossenen Termen, denn auf äußerster Ebene gibt es keinen Binder, auf den eine freie Variable zeigen dürfte.
Wenn man \(\alpha\)-Umbenennungen herausfaktorisiert, ist ein Variablenvorkommen nur noch dadurch bestimmt, auf welche umschließende Abstraktion es verweist. In einem Kontext mit \(d\) umgebenden Bindern gibt es also genau \(d\) zulässige Variablenwahlen.
Damit entsteht der Variablenbeitrag
$$d\mathbf{1}_{s=1},$$
wobei \(\mathbf{1}_{s=1}\) erzwingt, dass eine Variable Größe \(1\) besitzt. Inhaltlich ist das dieselbe Sichtweise wie bei de-Bruijn-artigen Tiefeninformationen, nur dass wir sie hier direkt zum Zählen verwenden.
Die Implementierungen kodieren das Größenmodell der Aufgabe direkt. Eine Variable hat Größe \(1\). Eine Abstraktion fügt um ihren Rumpf \(5\) zusätzliche Symbole hinzu. Eine Applikation fügt um zwei Teilterme \(2\) zusätzliche Symbole hinzu.
Daraus folgt die Rekurrenz
$$A_d(s)=d\mathbf{1}_{s=1}+A_{d+1}(s-5)+\sum_{i=1}^{s-3} A_d(i)\,A_d(s-2-i).$$
Unmögliche oder nichtpositive Größen tragen wie üblich \(0\) bei. Die Applikationssumme zählt geordnete Paare, denn das Vertauschen von linkem und rechtem Teilterm liefert im Allgemeinen einen anderen Term.
Für ein Ziel \(n\) sind nur endlich viele Tiefenzustände überhaupt relevant. Um Tiefe \(d\) zu erreichen, müssen vom Ursprung aus bereits \(d\) Abstraktionen erzeugt worden sein, also Kosten von \(5d\) Symbolen. Selbst die billigste Fortsetzung darunter ist noch eine einzelne Variable der Größe \(1\).
Daher muss jeder beitragende Zustand
$$5d+1\le n$$
erfüllen, also ist die maximale relevante Tiefe
$$d_{\max}=\left\lfloor\frac{n-1}{5}\right\rfloor.$$
Allgemeiner benötigen wir in Tiefe \(d\) nur exakte Größen
$$1\le s\le n-5d.$$
Gerade diese Abschneidung macht die Dynamik endlich und praktikabel.
Für feste Tiefe \(d\) definieren wir die geordnete Faltung
$$C_d(k)=\sum_{i+j=k} A_d(i)\,A_d(j).$$
Dann ist der Applikationsbeitrag zur Größe \(s\) einfach \(C_d(s-2)\). Würde man diese Summe für jedes \(s\) neu berechnen, entstünde unnötige Mehrarbeit. Deshalb pflegen die Implementierungen sie inkrementell während des aufsteigenden Durchlaufs über \(s\).
Sobald \(A_d(s)\) bekannt ist, trägt es zu allen zukünftigen Summen \(C_d(s+u)\) bei. Für \(u\ne s\) können die Größenklassen \((s,u)\) in beiden Links-Rechts-Reihenfolgen auftreten, daher wird der außendiagonale Beitrag verdoppelt. Für \(u=s\) zählt das Produkt \(A_d(s)^2\) bereits alle geordneten Paare zweier Terme dieser Größe, also ist kein zusätzlicher Faktor nötig.
In Tiefe \(1\) gibt es genau einen Term der Größe \(1\), weil der einzige verfügbare Binder genau einmal referenziert werden kann:
$$A_1(1)=1.$$
Damit erscheint der erste geschlossene Term bei Größe \(6\), indem man einen Abstraktionsrahmen um diesen Rumpf legt:
$$A_0(6)=A_1(1)=1.$$
Betrachten wir nun Tiefe \(1\) und Größe \(4\). Die einzige Möglichkeit ist eine Applikation aus zwei Variablen der Größe \(1\), also
$$A_1(4)=A_1(1)\,A_1(1)=1.$$
Eine weitere umschließende Abstraktion liefert den nächsten geschlossenen Term bei Größe \(9\):
$$A_0(9)=A_1(4)=1.$$
Damit sind die ersten kumulativen Werte
$$\Lambda(6)=1,\qquad \Lambda(9)=2.$$
Dieselbe Rekurrenz erzeugt außerdem die weiteren kleinen Kontrollwerte
$$\Lambda(15)=20,\qquad \Lambda(35)=3166438,$$
die mit den in den Implementierungen verwendeten Plausibilitätsprüfungen übereinstimmen.
Die C++-, Python- und Java-Implementierungen folgen alle derselben Rekurrenz. Sie beginnen bei der größten relevanten Tiefe \(d_{\max}=\lfloor(2000-1)/5\rfloor\) und arbeiten sich bis Tiefe \(0\) nach oben. Zu jedem Zeitpunkt werden nur zwei Tiefenschichten gehalten: die Werte der aktuellen Tiefe und die Werte der nächsttieferen Schicht.
Für eine feste Tiefe \(d\) läuft die Implementierung die exakte Größe \(s\) von \(1\) bis \(2000-5d\) durch. Jeder Wert \(A_d(s)\) setzt sich aus drei Bausteinen zusammen: dem Variablenterm \(d\mathbf{1}_{s=1}\), dem Abstraktionsterm aus Tiefe \(d+1\) und Größe \(s-5\), sowie dem Applikationsterm, der aus dem laufenden Faltungspuffer an Position \(s-2\) gelesen wird.
Nachdem die Anzahl für Größe \(s\) berechnet ist, aktualisiert die Implementierung den Faltungspuffer, damit spätere Größen diesen neuen Beitrag sofort wiederverwenden können. Alle Rechnungen werden modulo \(10^9+7\) reduziert. Sobald Tiefe \(0\) fertig ist, werden die exakten Werte prefixweise aufsummiert, um \(\Lambda(1),\Lambda(2),\dots,\Lambda(2000)\) zu erhalten; ausgegeben wird schließlich \(\Lambda(2000)\).
In Tiefe \(d\) hat das aktive Größenfenster die Länge \(S=2000-5d\), und die inkrementellen Faltungsaktualisierungen kosten \(O(S^2)\). Über alle relevanten Tiefen summiert ergibt das
$$\sum_{d=0}^{\lfloor(2000-1)/5\rfloor} O\!\left((2000-5d)^2\right)=O(2000^3),$$
also asymptotisch kubische Laufzeit in der Zielgrenze \(n\). Der Speicherbedarf bleibt linear, weil nur zwei Größenfelder und ein zusätzlicher Faltungspuffer der Länge \(O(n)\) gehalten werden.
\(\Lambda(n)\), en fazla \(n\) sembolle yazılabilen kapalı lambda-terimlerin sayısını göstersin; yalnızca bağlı değişken adlarının yeniden adlandırılmasıyla farklı olan terimler aynı nesne kabul edilir. İstenen değer \(\Lambda(2000)\bmod(10^9+7)\) sonucudur.
Bu boyutta doğrudan üretim yapmak mümkün değildir. Bu yüzden implementasyonlar terimleri önce tam boylarına göre sayar, o anda kaç bağlayıcının erişilebilir olduğunu izler ve kümülatif toplamı en sonda alır.
Tam boy dinamik programı için \(A_d(s)\), \(d\) adet erişilebilir bağlayıcının bulunduğu bir bağlamda boyu tam olarak \(s\) olan terim sayısı olsun. Nihai büyüklük
$$\Lambda(n)=\sum_{s=1}^{n} A_0(s)$$
şeklindedir. Burada \(d=0\), dış seviyede serbest bir değişkenin bağlanabileceği hiçbir bağlayıcı kalmadığı için kapalı terimleri temsil eder.
\(\alpha\)-yeniden adlandırmaları dışarı attığımızda bir değişken görülmesinin tek önemli yanı, hangi dış lambda'ya işaret ettiğidir. Çevrede \(d\) adet kapsayıcı bağlayıcı varsa tam olarak \(d\) geçerli değişken seçeneği vardır.
Bu nedenle değişken katkısı
$$d\mathbf{1}_{s=1}$$
olur. Buradaki \(\mathbf{1}_{s=1}\), bir değişkenin boyunun \(1\) olduğunu zorlar. Bu bakış açısı içerik olarak de Bruijn tipi derinlik bilgisinin aynısıdır; burada onu doğrudan sayım amacıyla kullanıyoruz.
İmplementasyonların kodladığı boy modeli doğrudandır. Bir değişkenin boyu \(1\)'dir. Bir gövdenin etrafına tek bir soyutlama koymak \(5\) ek sembol getirir. İki alt terimden uygulama kurmak ise toplam \(2\) ek sembol getirir.
Dolayısıyla rekürans
$$A_d(s)=d\mathbf{1}_{s=1}+A_{d+1}(s-5)+\sum_{i=1}^{s-3} A_d(i)\,A_d(s-2-i)$$
şeklindedir. İmkansız veya pozitif olmayan boyların katkısı \(0\) kabul edilir. Uygulama toplamı sıralı çiftleri sayar; sol ve sağ alt terimi yer değiştirmek genel olarak farklı bir terim üretir.
Hedef sınır \(n\) için yalnızca sonlu sayıda derinlik durumu önemlidir. Tepe seviyesinden derinlik \(d\)'ye ulaşmak için zaten \(d\) tane soyutlama üretilmiş olmalıdır; bunun maliyeti \(5d\) semboldür. Bunun altında mümkün olan en ucuz tamamlama bile boyu \(1\) olan tek bir değişkendir.
Bu yüzden katkı verebilen her durum
$$5d+1\le n$$
koşulunu sağlamalıdır. Böylece en büyük gerekli derinlik
$$d_{\max}=\left\lfloor\frac{n-1}{5}\right\rfloor$$
olur. Daha genel olarak, derinlik \(d\)'de yalnızca
$$1\le s\le n-5d$$
boyları gerekir. Dinamik programı sonlu ve uygulanabilir yapan kesme tam olarak budur.
Sabit bir \(d\) derinliği için sıralı konvolüsyonu
$$C_d(k)=\sum_{i+j=k} A_d(i)\,A_d(j)$$
diye tanımlayalım. O zaman boyu \(s\) olan bir uygulamanın katkısı yalnızca \(C_d(s-2)\) olur. Bu toplamı her \(s\) için baştan hesaplamak gereksiz maliyet yaratacağı için implementasyonlar onu boy yükselirken artımlı olarak tutar.
\(A_d(s)\) hesaplandığı anda gelecekteki tüm \(C_d(s+u)\) toplamlarına katkı yapar. \(u\ne s\) iken \((s,u)\) boy çiftleri hem sol-sağ hem sağ-sol düzeninde oluşabildiği için köşegen dışı katkı iki kat alınır. \(u=s\) iken ise \(A_d(s)^2\) çarpımı zaten aynı boydaki iki terimin tüm sıralı çiftlerini saydığı için ek katsayı gerekmez.
Derinlik \(1\)'de boyu \(1\) olan tam bir terim sayısı tam olarak \(1\)'dir; çünkü eldeki tek bağlayıcıya yalnızca tek şekilde başvurulabilir:
$$A_1(1)=1.$$
Bu yüzden ilk kapalı terim boy \(6\)'da ortaya çıkar; tek yapılması gereken bu gövdenin etrafına bir soyutlama sarmaktır:
$$A_0(6)=A_1(1)=1.$$
Şimdi derinlik \(1\) ve boy \(4\)'e bakalım. Tek olasılık, boyu \(1\) olan iki değişkenin uygulamasıdır; dolayısıyla
$$A_1(4)=A_1(1)\,A_1(1)=1.$$
Bunun dışına bir soyutlama daha koyunca boy \(9\)'daki bir sonraki kapalı terim elde edilir:
$$A_0(9)=A_1(4)=1.$$
Böylece ilk kümülatif değerler
$$\Lambda(6)=1,\qquad \Lambda(9)=2$$
olur. Aynı rekürans daha ileri küçük kontrol değerlerini de üretir:
$$\Lambda(15)=20,\qquad \Lambda(35)=3166438.$$
Bu sayılar implementasyonların kullandığı sağlamlık kontrolleriyle uyuşur.
C++, Python ve Java implementasyonlarının hepsi aynı reküransı izler. Önce en büyük gerekli derinlik \(d_{\max}=\lfloor(2000-1)/5\rfloor\) bulunur ve oradan aşağı doğru \(0\)'a kadar inilerek hesap yapılır. Her anda yalnızca iki derinlik katmanını tutmak yeterlidir: mevcut derinliğin sayıları ve bir alt derinliğin sayıları.
Sabit bir \(d\) için algoritma tam boy \(s\) değerlerini \(1\)'den \(2000-5d\)'ye kadar tarar. Her \(A_d(s)\) üç parçadan kurulur: değişken terimi \(d\mathbf{1}_{s=1}\), derinlik \(d+1\)'den gelen ve boyu \(s-5\) olan soyutlama terimi, bir de yürüyen konvolüsyon tamponunda \(s-2\) konumundan okunan uygulama terimi.
Boy \(s\) için değer hesaplandıktan sonra konvolüsyon tamponu güncellenir; böylece daha büyük boylar bu yeni bilgiyi anında kullanabilir. Tüm aritmetik \(10^9+7\) modunda yapılır. Derinlik \(0\) tamamlanınca tam boy sayıları ön ek toplamına çevrilir ve \(\Lambda(1),\Lambda(2),\dots,\Lambda(2000)\) elde edilir; raporlanan değer \(\Lambda(2000)\)'dir.
Derinlik \(d\)'de etkin boy penceresi \(S=2000-5d\) uzunluğundadır ve artımlı konvolüsyon güncellemeleri \(O(S^2)\) zaman alır. Tüm derinlikler üzerinde toplam
$$\sum_{d=0}^{\lfloor(2000-1)/5\rfloor} O\!\left((2000-5d)^2\right)=O(2000^3)$$
olduğu için asimptotik zaman karmaşıklığı hedef sınır \(n\) bakımından kübiktir. Bellek kullanımı ise doğrusaldır; çünkü yalnızca iki tam-boy dizisi ve \(O(n)\) uzunluğunda bir yardımcı konvolüsyon dizisi saklanır.
Sea \(\Lambda(n)\) el número de términos lambda cerrados que pueden escribirse con a lo sumo \(n\) símbolos, identificando como un mismo objeto a los términos que solo difieren por el renombrado de variables ligadas. Hay que calcular \(\Lambda(2000)\) módulo \(10^9+7\).
Una generación directa de todos los candidatos es inviable a esta escala. Por eso las implementaciones cuentan términos por tamaño exacto, registran cuántos ligadores están disponibles en cada momento y dejan la suma acumulada para el final.
Para la programación dinámica por tamaño exacto, definimos \(A_d(s)\) como el número de términos de tamaño exacto \(s\) construidos en un contexto con \(d\) ligadores disponibles. La cantidad buscada es entonces
$$\Lambda(n)=\sum_{s=1}^{n} A_0(s).$$
El estado \(d=0\) representa términos cerrados, porque en el nivel exterior no hay ningún ligador al que pueda apuntar una variable libre.
Una vez que se factoriza el renombrado \(\alpha\), una aparición de variable queda determinada únicamente por cuál abstracción envolvente referencia. Si el contexto actual contiene \(d\) ligadores circundantes, entonces existen exactamente \(d\) elecciones válidas de variable.
Eso produce la contribución de variable
$$d\mathbf{1}_{s=1},$$
donde \(\mathbf{1}_{s=1}\) fuerza que una variable tenga tamaño \(1\). Esta es la misma idea conceptual que aparece en las representaciones tipo de Bruijn, pero aquí se usa directamente para contar.
Las implementaciones codifican el modelo de tamaño de la tarea de forma directa. Una variable tiene tamaño \(1\). Envolver un cuerpo con una abstracción añade \(5\) símbolos. Formar una aplicación a partir de dos subtérminos añade \(2\) símbolos alrededor del par.
Por tanto, los conteos exactos satisfacen
$$A_d(s)=d\mathbf{1}_{s=1}+A_{d+1}(s-5)+\sum_{i=1}^{s-3} A_d(i)\,A_d(s-2-i).$$
Como de costumbre, los tamaños imposibles o no positivos aportan \(0\). La suma de aplicación cuenta pares ordenados, porque intercambiar el subárbol izquierdo y el derecho normalmente produce un término distinto.
Para un límite objetivo \(n\), solo pueden importar un número finito de estados de profundidad. Para llegar a profundidad \(d\) desde la raíz, ya se ha pagado el coste de \(d\) abstracciones, es decir, \(5d\) símbolos. Incluso la continuación más barata por debajo de ese punto sigue siendo una sola variable de tamaño \(1\).
Así, cualquier estado que aporte algo debe cumplir
$$5d+1\le n,$$
de modo que la profundidad máxima relevante es
$$d_{\max}=\left\lfloor\frac{n-1}{5}\right\rfloor.$$
Más generalmente, en profundidad \(d\) solo hacen falta tamaños exactos
$$1\le s\le n-5d.$$
Este recorte es precisamente lo que vuelve finita y práctica a la programación dinámica.
Para una profundidad fija \(d\), definimos la convolución ordenada
$$C_d(k)=\sum_{i+j=k} A_d(i)\,A_d(j).$$
Entonces la contribución de las aplicaciones al tamaño \(s\) es simplemente \(C_d(s-2)\). Recalcular esa suma desde cero para cada \(s\) sería caro, así que las implementaciones la mantienen de forma incremental mientras recorren los tamaños en orden creciente.
En cuanto se conoce \(A_d(s)\), ese valor contribuye a todos los futuros totales \(C_d(s+u)\). Si \(u\ne s\), las clases de tamaño \((s,u)\) pueden aparecer en ambos órdenes izquierda-derecha, por lo que la contribución fuera de la diagonal se duplica. Si \(u=s\), el producto \(A_d(s)^2\) ya cuenta todos los pares ordenados de dos términos de tamaño \(s\), así que no hace falta ningún factor adicional.
En profundidad \(1\) existe exactamente un término de tamaño \(1\), porque el único ligador disponible puede referenciarse de una sola manera:
$$A_1(1)=1.$$
Por ello, el primer término cerrado aparece en tamaño \(6\), al colocar una abstracción alrededor de ese cuerpo de tamaño \(1\):
$$A_0(6)=A_1(1)=1.$$
Ahora miremos profundidad \(1\) y tamaño \(4\). La única posibilidad es una aplicación de dos variables de tamaño \(1\), luego
$$A_1(4)=A_1(1)\,A_1(1)=1.$$
Al envolverlo en una abstracción se obtiene el siguiente término cerrado, de tamaño \(9\):
$$A_0(9)=A_1(4)=1.$$
Por tanto, los primeros valores acumulados son
$$\Lambda(6)=1,\qquad \Lambda(9)=2.$$
La misma recurrencia sigue produciendo los controles pequeños adicionales
$$\Lambda(15)=20,\qquad \Lambda(35)=3166438,$$
que coinciden con los valores usados para validar la implementación.
Las implementaciones en C++, Python y Java siguen exactamente la misma recurrencia. Empiezan desde la mayor profundidad relevante \(d_{\max}=\lfloor(2000-1)/5\rfloor\) y descienden hasta \(0\). En cada instante solo hacen falta dos capas de profundidad: los conteos de la profundidad actual y los de la siguiente profundidad más interna.
Para una profundidad fija \(d\), la implementación recorre el tamaño exacto \(s\) desde \(1\) hasta \(2000-5d\). Cada valor \(A_d(s)\) se arma con tres ingredientes: el término de variable \(d\mathbf{1}_{s=1}\), el término de abstracción que llega desde profundidad \(d+1\) y tamaño \(s-5\), y el término de aplicación leído en el búfer de convolución en la posición \(s-2\).
Después de calcular el valor de tamaño \(s\), la implementación actualiza el búfer de convolución para que los tamaños futuros reutilicen inmediatamente esa nueva información. Toda la aritmética se reduce módulo \(10^9+7\). Una vez terminada la profundidad \(0\), los conteos exactos se convierten en sumas prefijas para obtener \(\Lambda(1),\Lambda(2),\dots,\Lambda(2000)\), y el valor reportado es \(\Lambda(2000)\).
En profundidad \(d\), la ventana activa de tamaños tiene longitud \(S=2000-5d\), y las actualizaciones incrementales de la convolución cuestan \(O(S^2)\). Al sumar sobre todas las profundidades relevantes se obtiene
$$\sum_{d=0}^{\lfloor(2000-1)/5\rfloor} O\!\left((2000-5d)^2\right)=O(2000^3),$$
de modo que el tiempo asintótico es cúbico en el límite objetivo \(n\). La memoria es lineal, porque el algoritmo solo conserva dos arreglos de tamaños exactos y un arreglo auxiliar de convolución, todos de longitud \(O(n)\).
记 \(\Lambda(n)\) 为长度不超过 \(n\) 个符号的闭 lambda 项个数，并且把只在绑定变量改名上不同的项视为同一个对象。题目要求计算 \(\Lambda(2000)\bmod(10^9+7)\)。
在 \(n=2000\) 这样的规模下，直接枚举所有候选项完全不可行。有效做法是先按“精确长度”计数，再记录当前上下文里有多少个可引用的绑定器，最后才把这些精确计数累加成 \(\Lambda(n)\)。
为了进行精确长度动态规划，定义 \(A_d(s)\) 为：在一个拥有 \(d\) 个可用绑定器的上下文中，长度恰好为 \(s\) 的 lambda 项数量。最终目标就是
$$\Lambda(n)=\sum_{s=1}^{n} A_0(s).$$
其中 \(d=0\) 正好表示闭项，因为在最外层没有任何绑定器可供自由变量去引用。
一旦把 \(\alpha\)-改名视为同一对象，变量出现时真正重要的就不再是变量名本身，而是它指向哪一个外层抽象。如果当前上下文中一共有 \(d\) 个外层绑定器，那么合法的变量选择就恰好有 \(d\) 种。
因此变量项带来的贡献是
$$d\mathbf{1}_{s=1},$$
这里的 \(\mathbf{1}_{s=1}\) 表示变量项长度必须是 \(1\)。这种状态描述本质上与 de Bruijn 风格的“绑定深度”编码一致，只不过这里直接把它作为计数工具来使用。
实现所对应的长度模型非常直接。一个变量的长度是 \(1\)。把一个子项包进一层抽象，会额外增加 \(5\) 个符号。把两个子项组合成一次应用，会额外增加 \(2\) 个符号。
于是精确长度计数满足递推
$$A_d(s)=d\mathbf{1}_{s=1}+A_{d+1}(s-5)+\sum_{i=1}^{s-3} A_d(i)\,A_d(s-2-i).$$
这里默认所有不可能的长度或非正长度贡献都为 \(0\)。应用这一项统计的是有序对子，因为交换左子项和右子项通常会得到不同的 lambda 项。
对于给定的目标上界 \(n\)，真正有贡献的深度状态只有有限个。因为从最外层走到深度 \(d\)，意味着沿途至少已经放入了 \(d\) 个抽象，仅这一部分就消耗了 \(5d\) 个符号。即使再往下放最便宜的内容，也至少还需要一个长度为 \(1\) 的变量。
所以任何可能贡献到最终答案的状态都必须满足
$$5d+1\le n.$$
这就给出最大相关深度
$$d_{\max}=\left\lfloor\frac{n-1}{5}\right\rfloor.$$
同理，在深度 \(d\) 上只需要处理
$$1\le s\le n-5d$$
这些精确长度。正是这种截断，让动态规划既是有限的，也是可执行的。
对固定深度 \(d\)，定义有序卷积
$$C_d(k)=\sum_{i+j=k} A_d(i)\,A_d(j).$$
那么长度为 \(s\) 的应用项贡献就可以直接写成 \(C_d(s-2)\)。如果对每个 \(s\) 都从头重算这项求和，代价会很高，因此实现采用“边扫长度、边维护卷积”的方式来复用已经算出的结果。
一旦 \(A_d(s)\) 已知，它就会对所有未来的 \(C_d(s+u)\) 产生贡献。当 \(u\ne s\) 时，大小桶 \((s,u)\) 既可以出现在左-右顺序，也可以出现在右-左顺序，所以非对角项需要乘以 \(2\)。当 \(u=s\) 时，\(A_d(s)^2\) 本身已经枚举了两个长度都为 \(s\) 的所有有序对子，因此不需要额外倍增。
在深度 \(1\) 时，长度为 \(1\) 的项恰好只有一个，因为唯一可引用的绑定器只有一种引用方式：
$$A_1(1)=1.$$
因此第一个闭项出现在长度 \(6\)，它来自于在这个长度 \(1\) 的主体外面再包一层抽象：
$$A_0(6)=A_1(1)=1.$$
再看深度 \(1\)、长度 \(4\)。唯一可能是把两个长度 \(1\) 的变量做一次应用，所以
$$A_1(4)=A_1(1)\,A_1(1)=1.$$
再往外包一层抽象，就得到长度 \(9\) 的下一个闭项：
$$A_0(9)=A_1(4)=1.$$
因此前几个累计值为
$$\Lambda(6)=1,\qquad \Lambda(9)=2.$$
同一个递推继续往前推，还会得到更大的小规模校验值
$$\Lambda(15)=20,\qquad \Lambda(35)=3166438,$$
这些数与实现中使用的正确性检查完全一致。
C++、Python 和 Java 三个实现都遵循同一条递推。它们先找到最大相关深度 \(d_{\max}=\lfloor(2000-1)/5\rfloor\)，然后从这个深度一路向下算到 \(0\)。在整个过程中，只需要同时保存两层深度状态：当前深度的精确长度计数，以及更深一层的精确长度计数。
对固定深度 \(d\)，实现会把长度 \(s\) 从 \(1\) 扫到 \(2000-5d\)。每个 \(A_d(s)\) 都由三部分组成：变量项 \(d\mathbf{1}_{s=1}\)，来自深度 \(d+1\) 且长度为 \(s-5\) 的抽象项，以及卷积缓冲区中索引 \(s-2\) 处给出的应用项。
每当某个长度 \(s\) 的计数算出来之后，实现就立刻更新卷积缓冲区，让更大的长度能够马上重用这份新信息。所有运算都对 \(10^9+7\) 取模。等到深度 \(0\) 全部完成，再对精确长度计数做前缀和，就得到 \(\Lambda(1),\Lambda(2),\dots,\Lambda(2000)\)，其中最终输出的是 \(\Lambda(2000)\)。
在深度 \(d\) 上，活跃长度窗口的大小为 \(S=2000-5d\)，而增量卷积更新的代价是 \(O(S^2)\)。对所有相关深度求和，得到
$$\sum_{d=0}^{\lfloor(2000-1)/5\rfloor} O\!\left((2000-5d)^2\right)=O(2000^3),$$
所以从渐近意义上说，时间复杂度对目标长度上界 \(n\) 是立方级的。空间复杂度只有 \(O(n)\)，因为算法只保存两个精确长度数组和一个辅助卷积数组，它们的长度都与 \(n\) 同阶。
Пусть \(\Lambda(n)\) обозначает число замкнутых лямбда-термов, которые можно записать не более чем \(n\) символами, причем термы, отличающиеся только переименованием связанных переменных, считаются одним и тем же объектом. Требуется вычислить \(\Lambda(2000)\) по модулю \(10^9+7\).
Прямое перечисление всех кандидатов при таком размере невозможно. Поэтому реализации считают термы по точной длине, отслеживают число доступных связок в текущем контексте и только в самом конце переходят к накопленной сумме.
Для динамики по точной длине определим \(A_d(s)\) как число термов точной длины \(s\), строящихся в контексте с \(d\) доступными связками. Тогда искомая величина равна
$$\Lambda(n)=\sum_{s=1}^{n} A_0(s).$$
Состояние \(d=0\) соответствует замкнутым термам, потому что на внешнем уровне нет ни одной связки, на которую могла бы сослаться свободная переменная.
После факторизации по \(\alpha\)-переименованию для появления переменной важно только то, на какую внешнюю абстракцию она указывает. Если в текущем контексте есть \(d\) окружающих связок, то существует ровно \(d\) допустимых выборов переменной.
Отсюда возникает вклад переменной
$$d\mathbf{1}_{s=1},$$
где \(\mathbf{1}_{s=1}\) означает, что длина переменной равна \(1\). По сути это тот же взгляд, что и в de Bruijn-подобных представлениях, только здесь он используется непосредственно для подсчета.
Размерная модель в реализациях задается напрямую. Переменная имеет длину \(1\). Если обернуть тело одной абстракцией, к длине добавляется \(5\) символов. Если построить аппликацию из двух подтермов, добавляется \(2\) символа.
Поэтому точные счетчики удовлетворяют рекуррентному соотношению
$$A_d(s)=d\mathbf{1}_{s=1}+A_{d+1}(s-5)+\sum_{i=1}^{s-3} A_d(i)\,A_d(s-2-i).$$
Как обычно, невозможные и неположительные длины дают вклад \(0\). Слагаемое аппликации считает упорядоченные пары, потому что перестановка левого и правого подтерма в общем случае меняет терм.
Для заданной верхней границы \(n\) реально важны лишь конечное число состояний по глубине. Чтобы добраться от корня до глубины \(d\), нужно уже потратить \(5d\) символов на \(d\) абстракций. Даже самое дешевое продолжение ниже этого места все равно требует еще хотя бы одну переменную длины \(1\).
Следовательно, любой вносящий вклад должен удовлетворять
$$5d+1\le n,$$
а максимальная релевантная глубина равна
$$d_{\max}=\left\lfloor\frac{n-1}{5}\right\rfloor.$$
Более того, на глубине \(d\) нужно рассматривать только точные длины
$$1\le s\le n-5d.$$
Именно это усечение делает динамику конечной и практически применимой.
Для фиксированной глубины \(d\) введем упорядоченную свертку
$$C_d(k)=\sum_{i+j=k} A_d(i)\,A_d(j).$$
Тогда вклад аппликаций в длину \(s\) равен просто \(C_d(s-2)\). Если пересчитывать эту сумму заново для каждого \(s\), получится лишняя работа, поэтому реализации поддерживают ее инкрементально по мере роста \(s\).
Как только становится известно \(A_d(s)\), оно начинает участвовать во всех будущих суммах \(C_d(s+u)\). Если \(u\ne s\), пары размерных классов \((s,u)\) могут появляться в обоих лево-правых порядках, поэтому внедиагональный вклад удваивается. Если \(u=s\), произведение \(A_d(s)^2\) уже учитывает все упорядоченные пары двух термов длины \(s\), так что дополнительный множитель не нужен.
На глубине \(1\) существует ровно один терм длины \(1\), потому что единственная доступная связка может быть выбрана только одним способом:
$$A_1(1)=1.$$
Поэтому первый замкнутый терм появляется при длине \(6\), если обернуть это тело одной абстракцией:
$$A_0(6)=A_1(1)=1.$$
Теперь рассмотрим глубину \(1\) и длину \(4\). Единственная возможность состоит в аппликации двух переменных длины \(1\), так что
$$A_1(4)=A_1(1)\,A_1(1)=1.$$
Если еще раз обернуть результат абстракцией, получаем следующий замкнутый терм длины \(9\):
$$A_0(9)=A_1(4)=1.$$
Следовательно, первые накопленные значения равны
$$\Lambda(6)=1,\qquad \Lambda(9)=2.$$
Та же рекурсия далее дает дополнительные малые контрольные значения
$$\Lambda(15)=20,\qquad \Lambda(35)=3166438,$$
и они совпадают с числами, используемыми для проверки корректности реализации.
Реализации на C++, Python и Java следуют одной и той же рекурсии. Сначала они находят максимальную релевантную глубину \(d_{\max}=\lfloor(2000-1)/5\rfloor\), а затем идут вниз до глубины \(0\). В каждый момент времени достаточно хранить только два слоя: значения на текущей глубине и значения на следующей, более глубокой.
Для фиксированной глубины \(d\) реализация перебирает точную длину \(s\) от \(1\) до \(2000-5d\). Каждое значение \(A_d(s)\) складывается из трех частей: переменного слагаемого \(d\mathbf{1}_{s=1}\), абстракционного слагаемого из глубины \(d+1\) и длины \(s-5\), а также слагаемого аппликации, которое считывается из буфера свертки по индексу \(s-2\).
После вычисления значения для длины \(s\) буфер свертки обновляется, чтобы большие длины могли сразу использовать новую информацию. Вся арифметика выполняется по модулю \(10^9+7\). Когда глубина \(0\) полностью обработана, точные счетчики превращаются в префиксные суммы \(\Lambda(1),\Lambda(2),\dots,\Lambda(2000)\), и выводится \(\Lambda(2000)\).
На глубине \(d\) активное окно длин имеет размер \(S=2000-5d\), а инкрементальные обновления свертки стоят \(O(S^2)\). Суммируя по всем релевантным глубинам, получаем
$$\sum_{d=0}^{\lfloor(2000-1)/5\rfloor} O\!\left((2000-5d)^2\right)=O(2000^3),$$
то есть асимптотическое время кубическое по целевой границе \(n\). Память остается линейной: хранятся только два массива точных длин и один вспомогательный массив свертки, все длины \(O(n)\).
لتكن \(\Lambda(n)\) عدد حدود lambda المغلقة التي يمكن كتابتها بما لا يزيد على \(n\) رمزًا، مع اعتبار الحدود التي تختلف فقط في إعادة تسمية المتغيرات المربوطة حدًا واحدًا. المطلوب هو حساب \(\Lambda(2000)\) بترديد \(10^9+7\).
التوليد المباشر لكل الحدود المرشحة غير عملي تمامًا عند هذا الحجم. لذلك تعتمد التطبيقات على عدّ الحدود بحسب الحجم الدقيق، وتتبع عدد الروابط المتاحة في السياق الحالي، ثم تؤجل الجمع التراكمي إلى النهاية.
لأجل برمجة ديناميكية بالحجم الدقيق، نعرّف \(A_d(s)\) بأنه عدد الحدود ذات الحجم الدقيق \(s\) داخل سياق يملك \(d\) روابط متاحة. وعندئذ تكون الكمية المطلوبة هي
$$\Lambda(n)=\sum_{s=1}^{n} A_0(s).$$
الحالة \(d=0\) تمثل الحدود المغلقة، لأنه لا يوجد في المستوى الخارجي أي رابط يمكن لمتغير حر أن يشير إليه.
بعد حذف أثر إعادة التسمية \(\alpha\)، لا يعود المهم في ظهور المتغير هو اسمه، بل أي تجريد خارجي يشير إليه. فإذا كان في السياق الحالي \(d\) روابط محيطة، فهناك بالضبط \(d\) اختيارات صحيحة للمتغير.
ومن هنا تأتي مساهمة المتغير
$$d\mathbf{1}_{s=1},$$
حيث تفرض \(\mathbf{1}_{s=1}\) أن يكون حجم المتغير مساويًا لـ \(1\). وهذه هي الفكرة نفسها الموجودة في تمثيلات من نمط de Bruijn، لكننا نستخدمها هنا مباشرة في العد.
نموذج الحجم الذي تعكسه التطبيقات مباشر جدًا. حجم المتغير هو \(1\). إحاطة جسم واحد بتجريد تضيف \(5\) رموز. وبناء تطبيق من حدين فرعيين يضيف \(2\) من الرموز.
لذلك تحقق أعداد الأحجام الدقيقة العلاقة
$$A_d(s)=d\mathbf{1}_{s=1}+A_{d+1}(s-5)+\sum_{i=1}^{s-3} A_d(i)\,A_d(s-2-i).$$
وكالمعتاد، الأحجام المستحيلة أو غير الموجبة تساهم بقيمة \(0\). وحد التطبيق هنا يحسب الأزواج المرتبة، لأن تبديل الحد الأيسر والحد الأيمن ينتج عادة حدًا مختلفًا.
بالنسبة إلى حد أعلى مستهدف \(n\)، لا توجد إلا حالات عمق منتهية يمكن أن تساهم في النتيجة. فلكي نصل من الجذر إلى عمق \(d\)، نكون قد دفعنا بالفعل كلفة \(d\) تجريدات، أي \(5d\) رموز. وحتى أرخص إكمال تحت هذا الموضع يحتاج على الأقل إلى متغير واحد حجمه \(1\).
إذًا يجب أن يحقق أي وضع يساهم
$$5d+1\le n,$$
ومن ثم يكون أكبر عمق ذي صلة هو
$$d_{\max}=\left\lfloor\frac{n-1}{5}\right\rfloor.$$
وبشكل أعم، عند العمق \(d\) لا نحتاج إلا إلى الأحجام الدقيقة
$$1\le s\le n-5d.$$
هذا الاقتصاص هو ما يجعل البرمجة الديناميكية منتهية وقابلة للتنفيذ.
لعمق ثابت \(d\)، نعرّف الالتفاف المرتب
$$C_d(k)=\sum_{i+j=k} A_d(i)\,A_d(j).$$
وعندئذ تصبح مساهمة التطبيق في الحجم \(s\) مساوية ببساطة لـ \(C_d(s-2)\). ولو أعدنا حساب هذا المجموع من الصفر لكل \(s\)، فسنهدر قدرًا كبيرًا من العمل، لذا تحافظ التطبيقات عليه تدريجيًا أثناء المرور التصاعدي على الأحجام.
بمجرد معرفة \(A_d(s)\)، فإنه يساهم في كل المجاميع المستقبلية \(C_d(s+u)\). وإذا كان \(u\ne s\)، فإن فئتي الحجم \((s,u)\) يمكن أن تظهرا في كلا الترتيبين يسار-يمين ويمين-يسار، لذا تتضاعف المساهمة خارج القطر. أما إذا كان \(u=s\)، فإن \(A_d(s)^2\) يحصي أصلًا كل الأزواج المرتبة لحدين كلاهما بحجم \(s\)، لذلك لا حاجة إلى عامل إضافي.
عند العمق \(1\) يوجد حد واحد فقط حجمه \(1\)، لأن الرابط الوحيد المتاح يمكن الإشارة إليه بطريقة واحدة فقط:
$$A_1(1)=1.$$
لذلك يظهر أول حد مغلق عند الحجم \(6\)، وذلك بوضع تجريد واحد حول هذا الجسم ذي الحجم \(1\):
$$A_0(6)=A_1(1)=1.$$
لننظر الآن إلى العمق \(1\) والحجم \(4\). الاحتمال الوحيد هو تطبيق متغيرين حجمهما \(1\)، ومن ثم
$$A_1(4)=A_1(1)\,A_1(1)=1.$$
وبإضافة تجريد خارجي آخر نحصل على الحد المغلق التالي عند الحجم \(9\):
$$A_0(9)=A_1(4)=1.$$
ومن ثم تكون أول القيم التراكمية
$$\Lambda(6)=1,\qquad \Lambda(9)=2.$$
والعلاقة نفسها تعطي أيضًا قيم تحقق صغيرة إضافية هي
$$\Lambda(15)=20,\qquad \Lambda(35)=3166438,$$
وهي متوافقة مع القيم المستخدمة في اختبارات سلامة التنفيذ.
تتبع تطبيقات C++ وPython وJava جميعها العلاقة نفسها. تبدأ من أكبر عمق ذي صلة \(d_{\max}=\lfloor(2000-1)/5\rfloor\) ثم تنزل حتى العمق \(0\). وفي أي لحظة لا نحتاج إلا إلى مستويين من العمق: قيم العمق الحالي وقيم العمق الأعمق التالي.
لعمق ثابت \(d\)، تمر الشيفرة على الحجم الدقيق \(s\) من \(1\) حتى \(2000-5d\). وتتكون كل قيمة \(A_d(s)\) من ثلاثة أجزاء: حد المتغير \(d\mathbf{1}_{s=1}\)، وحد التجريد القادم من العمق \(d+1\) والحجم \(s-5\)، وحد التطبيق المقروء من مخزن الالتفاف عند الفهرس \(s-2\).
وبعد حساب القيمة الخاصة بالحجم \(s\)، تحدّث الشيفرة مخزن الالتفاف لكي تستطيع الأحجام اللاحقة إعادة استخدام هذه المعلومة الجديدة فورًا. كل العمليات الحسابية تؤخذ بترديد \(10^9+7\). وبعد اكتمال العمق \(0\)، تتحول أعداد الأحجام الدقيقة إلى مجاميع بادئة تعطي \(\Lambda(1),\Lambda(2),\dots,\Lambda(2000)\)، وتكون القيمة المطبوعة هي \(\Lambda(2000)\).
عند العمق \(d\)، يكون طول نافذة الأحجام الفعالة هو \(S=2000-5d\)، وتكلفة تحديثات الالتفاف التدريجية هي \(O(S^2)\). وبالجمع على جميع الأعماق ذات الصلة نحصل على
$$\sum_{d=0}^{\lfloor(2000-1)/5\rfloor} O\!\left((2000-5d)^2\right)=O(2000^3),$$
أي إن زمن التنفيذ من حيث الرتبة الأسية هو تكعيبي في الحد المستهدف \(n\). أما الذاكرة فهي خطية فقط، لأن الخوارزمية تحتفظ بمصفوفتين للأحجام الدقيقة ومصفوفة التفاف مساعدة، وكلها بطول \(O(n)\).