INKLUSION-EXKLUSIONSPRINCIPEN MEDELST GENERERANDE FUNKTIONER

ANDERS CLAESSON

Följande variant av Inexprincipen (inklusion-exklusionsprincipen) är i allt väsentligt identisk med den som Wilf ger i [1, s 110]. Låt Ω vara en ändlig mängd och antag att vi är givna en samling egenskaper {R_{i}}_{i∈J}, där R_{i} ⊆ Ω. Vi säger att ω ∈ Ω har egenskapen R_{i} om ω ∈ R_{i}. Den kvantitet, f(k), vi vill finna är antalet objekt i Ω med exakt k egenskaper. Notera att |∩_{i∈I} R_{i}| räknar antalet objekt som åtminstone har egenskaperna {R_{i}}_{i∈I} och sätt

g(k) = ∑_{\begin{matrix}I⊆J \\ |I|=k \end{matrix}} | ∩_{i∈I} R_{i}|

Då det vanligtvis är lättare att finna g än f vill vi uttrycka f i termer av g. Om vi definierar I(ω) = {i : ω ∈ R_{i}}, så kan vi skriva g(k) på följande vis

g(k) = ∑_{|I|=k} ∑_{\begin{matrix}ω∈Ω \\ I⊆I(w) \end{matrix}} 1

= ∑_{ω∈Ω} ∑_{\begin{matrix}I⊆I(w) \\ |I|=k \end{matrix}} 1

= ∑_{ω∈Ω} \binom{|I(ω)|}{k}

Således bidrar varje objekt som har exakt n egenskaper med \binom{n}{k} till g(k). Eftersom det finns f(k) objekt med exakt k egenskaper har vi visat

g(k) = ∑_{n} \binom{n}{k}f(n)

Låt G(x) = ∑_{k} g(k)x^{k} och multiplicera uttrycket ovan med x^{k} samt summera över k. Då får vi

G(x) = ∑_{k} ∑_{n} \binom{n}{k}f(n)x^{k}

= ∑_{n} f(n) ∑_{k} \binom{n}{k}x^{k}
= ∑_{n} f(n)(x + 1)^{n}

Alltså är G(x − 1) en genererande funktion för {f(n)}_{n}.

Problem 1. Visa följande identitet för Stirlingtalen av andra slaget:

k!S(n, k) = ∑_{i}(−1)^{i}\binom{k}{i}(k − i)^{n}

Lösning. En k-pseudopartition av en mängd M är en familj, π = {B_{1}, …, B_{k}}, av parvis disjunkta delmängder till M sådana att M = ∪_{i}B_{i}. Låt Ω vara mängden av alla ordnade k-pseudopartitioner av [n] och sätt R_{i} = {π ∈ Ω : B_{i} = ∅}. Med notation som ovan har vi

g(r) = ∑_{\begin{matrix}I⊆[k] \\ |I|=r \end{matrix}}| ∩_{i∈I} R_{i}| = \binom{k}{r}(k − r)^{n}

Den sista likheten följer av att det finns en naturlig bijektion mellan strängar av längd n i alfabetet [k] \ I och ordnade k-pseudopartitioner av [n] sådana att B_{i} = ∅ för varje i ∈ I. Låt G(x) = ∑_{r} g(r)x^{r}, då är G(x − 1), enligt inexprincipen, en genererande funktion för antalet π ∈ Ω med exakt r tomma block. Speciellt räknar den konstanta termen i G(x−1) antalet π ∈ Ω sådana att inget block i partitionen är tomt, d.v.s. antalet ordnade k-partitioner av [n]. Alltså har vi k!S(n, k) = G(−1), d.v.s.

k!S(n, k) = ∑_{i}(−1)^{i}\binom{k}{i}(k − i)^{n}

Problem 2. Låt S(n, k) och A(n, k) vara Stirlingtalen respektive de Eulerska talen. Visa att

A(n, i) = ∑_{k}(−1)^{n−k−i}\binom{n − k}{i}k!S(n, k)

Lösning. Låt π = {B_{1}, …, B_{k}} vara en ordnad partition av [n] och lista elementen i partitionen så att element tillhörande samma block är skrivna i fallande ordning. På så vis kan vi tolka π som en unik permutation π̂ = a_{1} ⋯ a_{n} i S_{n}. Vi säger att i är ett inre fall i π̂ om i är ett fall och det finns något block B_{j} så att a_{i}, a_{i+1} ∈ B_{j}. Notera att π̂ har n − k inre fall om och endast om π är en ordnad k-partition. Vidare observerar vi att givet π̂ och en indexmängd I innehållande de inre fallen i π̂, så kan vi rekonstruera π. Låt R_{i} vara mängden av alla permutationer i S_{n} med ett fall på plats i, då har vi visat

g(n − k) = ∑_{\begin{matrix}I⊆[n] \\ |I|=n−k \end{matrix}} | ∩_{i∈I} R_{i}| = k!S(n, k)

Om G(x) = ∑_{k} g(k)x^{k}, så är G(x−1) enligt inexprincipen en genererande funktion för antalet permutationer med exakt k fall, d.v.s.

G(x − 1) = ∑_{i} A(n, i)x^{i}

men vi har också

G(x − 1) = ∑_{k} k!S(n, k)(x − 1)^{n−k}

= ∑_{k} ∑_{i} k!S(n, k)\binom{n − k}{i}x^{i}(−1)^{n−k−i}

= ∑_{i} ∑_{k}(−1)^{n−k−i}\binom{n − k}{i}k!S(n, k)x^{i}

vilket implicerar

A(n, i) = ∑_{k}(−1)^{n−k−i}\binom{n − k}{i}k!S(n, k)

Problem 3. Låt c_{n}^{k} vara antalet partitioner av [2n] med k block som alla har ett jämnt antal element. Då är

E_{2n} = ∑_{k}(−1)^{n−k}k!c_{n}^{k}

där E_{m} är det m:te Eulertalet, d.v.s. antalet alternerande permutationer i S_{m}. Ge ett bevis för ovanstående identitet. Beviset skall också (med en liten modifiering) täcka följande identitet:

E_{2n−1} = ∑_{k}(−1)^{n−k}(k − 1)!c_{n}^{k}

Lösning. Låt

M = {a_{1} ⋯ a_{2n} ∈ S_{2n} : a_{2i−1} > a_{2i} för varje i ∈ [n]}

och associera till varje i ∈ [n − 1] en mängd R_{i} = {π ∈ M : a_{2i} > a_{2i+1}}. Tag en godtycklig ordnad k-partition π av [2n] sådan att varje block är av jämn storlek. Lista elementen i partitionen så att element tillhörande samma block är skrivna i fallande ordning. Då ser vi att π bestämmer en permutation π̂ i M. På liknande sätt som i lösningen till problem 2 finner vi en bijektion (I, π̂) ⟼ π, där 2I är mängden av jämna inre fall i π̂. Därav följer

g(n − k) = ∑_{\begin{matrix}I⊆[n−1] \\ |I|=n−k \end{matrix}} | ∩_{i∈I} R_{i}| = k!c_{n}^{k}

Om

G(x) = ∑_{k} g(k)x^{k} = ∑_{k} k!c_{n}^{k}x^{n−k}

så är G(x − 1) enligt inexprincipen en genererande funktion för antalet π ∈ M med exakt k jämna fall. Speciellt bestäms antalet alternerande permutationer av den konstanta termen i G(x − 1). Alltså har vi visat

E_{2n} = ∑_{k}(−1)^{n−k}k!c_{n}^{k}

Av ovanstående följer också

E_{2n−1} = ∑_{k}(−1)^{n−k}(k − 1)!c_{n}^{k}

Ty låt en partition av [2n] med k block som alla har ett jämnt antal element vara given. Identifiera det block som innehåller talet 2n och ta bort det från det blocket. Bilda nu en ordnad partition genom att ge det block som tidigare innehöll 2n index k och tilldela de övriga blocken var sitt index ur [k − 1]. Följ sedan det tidigare givna beviset.

Referenser

[1] Herbert S. Wilf, Generatingfunctionology, Academic Press, 1994.

Matematiska institutionen, Chalmers tekniska högskola och Göteborgs universitet, 412 96 Göteborg, E-postadress: claesson@math.chalmers.se