Binomial koefficient

Binomialkoefficienten är koefficienten framför termen i expansionen av Newtonbinomialen i potenser av . Koefficienten vid betecknas eller och läser "binomial koefficient från by " (eller "antal kombinationer från by "): $(1+x)^{n}$ $x$ $x^{k}$ $\textstil {\binom {n}{k))$ $\textstil C_n^k$ $n$ $k$ $n$ $k$

(1+x)^{n}={\binom {n}{0}}+{\binom {n}{1}}x+{\binom {n}{2}}x^{2} +\ldots +{\binom {n}{n}}x^{n}=\summa _{k=0}^{n}{\binom {n}{k}}x^{k}

för naturliga krafter . $n$

Binomialkoefficienter kan också definieras för godtyckliga reella exponenter . I fallet med ett godtyckligt reellt tal, definieras de binomiska koefficienterna som koefficienterna för expansionen av ett uttryck till en oändlig potensserie : $n$ $n$ $(1+x)^{n}$

{\displaystyle (1+x)^{n}=\summa _{k=0}^{\infty }{\binom {n}{k))x^{k))

där, i fallet med icke-negativa heltal , alla koefficienter på försvinner och därför är denna expansion en ändlig summa. $n$ $\textstil {\binom {n}{k))$ $k>n$

I kombinatorik tolkas binomialkoefficienten för icke-negativa heltal och som antalet kombinationer av med , det vill säga som antalet alla (icke-strikta) delmängder ( sampel ) av storlek i en -elementuppsättning . $\textstil {\binom {n}{k))$ $n$ $k$ $n$ $k$ $k$ $n$

Binomialkoefficienter uppstår ofta i problem inom kombinatorik och sannolikhetsteori . En generalisering av binomialkoefficienter är multinomialkoefficienter .

Explicita formler

Genom att beräkna koefficienterna i potensserieexpansionen kan man få explicita formler för binomialkoefficienterna . $(1+x)^{n}$ $\textstil {\binom {n}{k))$

För alla reella tal och heltal : $n$ $k$

{\binom {n}{k}}={\begin{cases}{\frac {n(n-1)(n-2)\cdot \ldots \cdot (n-k+1)}{ k!}},&k\geqslant 0\\0,&k<0\end{fall}}

där betecknar factorial av . $k!$ $k$

För icke-negativa heltal och formlerna är också giltiga: $n$ $k$

{\binom {n}{k}}={\begin{cases}{\frac {n!}{k!(nk)!}}),&0\leqslant k\leqslant n\\0,&k > n\end{fall}}

För negativa heltalsexponenter är de binomiska expansionskoefficienterna : ${\displaystyle (1+x)^{-n))$

{\binom {-n}{k}}={\begin{cases}(-1)^{k}\cdot {\frac {(n+k-1)!}{k!(n- 1)!}},&k\geqslant 0\\0,&k<0\end{cases}}

Pascals triangel

Identitet:

{n \choose k}={n-1 \choose k-1}+{n-1 \choose k}

låter dig ordna binomialkoefficienterna för icke-negativa heltal , i form av Pascals triangel, där varje tal är lika med summan av två högre: $n$ $k$

{\begin{matrix}n=0:&&&&&1&&&&\\n=1:&&&&1&&1&&&\\n=2:&&&1&&2&&1&&\\\n=3:&&1&&3&&3&&1&\\n=4:&1&&4&&6&&4&&ts &\dos &vs \vdots &&\vdots &\end{matris}}

Den triangulära tabellen som Pascal föreslagit i hans Treatise on the Arithmetic Triangle (1654) skiljer sig från den som är skriven här genom en rotation av 45°. Tabeller för att visa binomialkoefficienter var kända tidigare ( Tartaglia , Omar Khayyam ).

Om i varje linje i Pascals triangel alla siffror divideras med (detta är summan av alla siffror på raden ), då kommer alla linjer, när de går till oändligheten, att ta formen av en normalfördelningsfunktion . $2^{n}$ $n$

Egenskaper

Genererar funktioner

För ett fast värde är genereringsfunktionen för sekvensen av binomialkoefficienter : $n$ ${\tbinom {n}{0)),\;{\tbinom {n}{1)),\;{\tbinom {n}{2)),\dots$

\sum _{k=0}^{\infty }{\binom {n}{k}}x^{k}=(1+x)^{n}

För ett fast värde är den genererande funktionen för koefficientsekvensen : $k$ ${\tbinom {0}{k)),\;{\tbinom {1}{k)),\;{\tbinom {2}{k)),\dots$

\sum _{n}{\binom {n}{k}}y^{n}={\frac {y^{k}}{(1-y)^{k+1}}}

Den tvådimensionella genererande funktionen för binomialkoefficienterna för heltal är: $\tbinom{n}{k}$ $n,k$

\sum _{n,k}{\binom {n}{k}}x^{k}y^{n}={\frac {1}{1-y-xy}}

, eller .

\sum _{n=0}^{\infty }\sum _{k=0}^{n}{\binom {n}{k}}x^{k}y^{n}={ \frac {1}{1-y-xy}}

Delbarhet

Av Lukas-satsen följer att:

koefficienten är udda i den binära notationen av talet, enheter står inte i de siffror där det finns nollor i talet; $\textstil {\binom {n}{k))$ $\iff$ $k$ $n$
koefficienten är inte en multipel av ett primtal i -är representation av talet , alla bitar överstiger inte motsvarande bitar av talet ; $\textstil {\binom {n}{k))$ $sid$ $\iff$ $sid$ $k$ $n$
i en sekvens av binomialkoefficienter : $\textstil {\binom {n}{0)),\;{\binom {n}{1)),\;\ldots ,\;{\binom {n}{n))$
- alla tal är inte multiplar av ett givet primtal kan representeras som , där är ett naturligt tal ; $sid$ $\iff$ $n$ $mp^{k}-1$ $m<p$
- alla tal utom det första och sista är multipler av det givna primtal ; $sid$ $\iff$ $n=p^{k}$
- antalet udda tal är lika med potensen av två, vars exponent är lika med antalet enheter i talets binära notation ; $n$
- jämna och udda tal kan inte vara lika;
- antalet tal som inte är multipler av ett primtal är lika med , där talen är siffrorna i talets -ary notation ; och numret , där är könsfunktionen , är längden på den givna posten. $sid$ $(a_{1}+1)\cdots (a_{m}+1)$ ${\displaystyle a_{1},\;\ldots ,a_{m))$ $sid$ $n$ $\textstyle m=\lgolv \log _{p}{n}\rgolv +1$ $\lgolv\cdot\rgolv$

Grundläggande identiteter

${n \choose k}={n-1 \choose k-1}+{n-1 \choose k}$ .
${\binom {n}{k}}=(-1)^{k}{\binom {-n+k-1}{k}}$ .
${n \choose k}={n \choose nk}$ (symmetriregel).
${n \choose k}={\frac {n}{k}}{n-1 \choose k-1}$ (parentes).
${n \choose {\color {Green}m}}{{\color {Green}m} \choose n-{\color {Green}k}}={n \choose {\color {Green}k }}{{\color {Grön}k} \choose n-{\color {Grön}m}}$ (byte av index).
${\displaystyle (nk){n \choose k}=n{n-1 \choose k))$ .

Newtons binomial och konsekvenser

${\displaystyle {n \choose 0}+{n \choose 1}+\ldots +{n \choose n}=2^{n))$ , var . $n\in \mathbb {N}$
$\sum _{i+j=m}{\binom {n}{j}}{\binom {n}{i}}(-1)^{j}={\begin{cases}{\ binom {n}{m/2)),&{\text{if}}\ m\equiv 0{\pmod {2)),\\0,&{\text{if}}\ m\equiv 1{ \pmod {2}}.\end{cases}}$
$\sum_{j=k}^{n} \binom{n}{j} (-1)^j = (-1)^k \binom{n-1}{k-1}$ .
${n \choose 0}-{n \choose 1}+\ldots +(-1)^{n}{n \choose n}=0$ , var . $n\in \mathbb {N}$
En starkare identitet: , där . ${\displaystyle {n \choose 0}+{n \choose 2}+\ldots +{n \choose 2\lfloor n/2\rfloor }=2^{n-1))$ $n\in \mathbb {N}$
$\sum _{{k=-a}}^{{a}}(-1)^{{k}}{2a \choose k+a}^{3}={\frac {(3a)!}{ (a!)^{3}}}$ ,

men mer generellt

\sum _{k=-a}^{a}(-1)^{k}{a+b \choose a+k}{b+c \choose b+k}{c+a \choose c+k}={\frac {(a+b+c)!}{a!\,b!\,c!}}

Vandermonde konvolution och konsekvenser

Convolution of Vandermonde :

{\displaystyle \sum _{k}{r \choose m+k}{s \choose nk}={r+s \choose m+n))

där en . Denna identitet erhålls genom att beräkna koefficienten vid i expansionen , med hänsyn till identiteten . Summan tas över alla heltal för vilka . För godtyckliga reella tal kommer antalet termer som inte är noll i summan att vara ändliga. $m,n\in \mathbb {Z} ,$ $r,s\in \mathbb {R}$ ${\displaystyle x^{m+n))$ ${\displaystyle (1+x)^{r}(1+x)^{s))$ ${\displaystyle (1+x)^{r+s}=(1+x)^{r}(1+x)^{s))$ $k$ $\textstyle {r \choose m+k}{s \choose nk}\neq 0$ $r$ $s$

Vandermonde convolution följd:

{n \choose 0}{a \choose a}-{n \choose 1}{a+1 \choose a}+\ldots +(-1)^{n}{n \choose n}{a+n \ välj a}=(-1)^{n}{a \choose n}

Mer allmän identitet:

\sum _{{i=0}}^{{p}}(-1)^{i}{p \choose i}\prod _{{m=1}}^{{n}}{i+s_ {m} \choose s_{m}}=0

om .

\summa _{{m=1}}^{n}{s_{m}}<p

En annan konsekvens av faltning är följande identitet: . ${\displaystyle {n \choose 0}^{2}+{n \choose 1}^{2}+\ldots +{n \choose n}^{2}={2n \choose n))$

Andra identiteter

${\frac {4}{n}}\sum _{k=1}^{n}k^{2}{\binom {2n}{n+k}}=2^{2n}$ , där är ett naturligt tal. $n$
$\sum _{k=1}^{n}{\frac {(-1)^{k-1}}{k}}{n \choose k}=\summa _{k=1}^ {n}{\frac {1}{k}}=H_{n}$ -th övertonstalet . _ $n$
Seriens multisektion ger en identitet som uttrycker summan av binomialkoefficienter med ett godtyckligt steg och offset som en finit summa av termer: $(1+x)^{n}$ $s$ $t$ $(0\leqslant t<s)$ $s$

{\binom {n}{t}}+{\binom {n}{t+s}}+{\binom {n}{t+2s}}+\ldots ={\frac {1}{ s}}\summa _{j=0}^{s-1}\left(2\cos {\frac {\pi j}{s}}\right)^{n}\cos {\frac {\pi (n-2t)j}{s}}

Det finns också jämlikheter:

{\begin{alignedat}{2}{\binom {n}{3}}&={\frac {n(n-1)(n-2)}{\color {Grön}2}}- \sum _{i=2}^{n-1}{(ni)(n-i+1)}=\\&=n(n-1)(n-2)-\summa _{i=2 }^{n-1}{(ni)({\color {Grön}2}n-i+1)}=\\&=3{\binom {n}{3}}-2{\binom {n }{3}};\\\end{alignedat}}

{\begin{alignedat}{2}{\binom {n}{4}}&={\frac {n(n-1)(n-2)(n-3)}{\color {Grön }2}}-\summa _{i=3}^{n-1}{(ni)\left(n(n-1)-\summa _{i_{0}=1}^{i-2} i_{0}\right)}=\\&=n(n-1)(n-2)(n-3)-\summa _{i=3}^{n-1}{(ni)\vänster ({\color {Grön}2}n(n-1)-\sum _{i_{0}=1}^{i-2}i_{0}\right)}=\\&=24{\binom {n}{4}}-23{\binom {n}{4}};\\\end{aligned}}

{\begin{alignedat}{2}{\binom {n}{5}}&={\frac {n(n-1)(n-2)(n-3)(n-4)} {\color {Grön}2}}-\\&-\summa _{i=4}^{n-1}{(ni)\left(n(n-1)(n-2)-\summa _ {i_{0}=1}^{i-3}\summa _{i_{1}=1}^{i_{0}}i_{1}\right)}=\\&=n(n-1 )(n-2)(n-3)(n-4)-\\&-\sum _{i=4}^{n-1}{(ni)\left({\color {Grön}2} n(n-1)(n-2)-\summa _{i_{0}=1}^{i-3}\summa _{i_{1}=1}^{i_{0}}i_{1 }\right)}=\\&=120{\binom {n}{5}}-119{\binom {n}{5}}.\end{alignedat}}

Var kommer det ifrån:

{\binom {n}{3}}={\frac {\sum \limits _{i=2}^{n-1}{(ni)(2n-i+1))){2} }={\frac {\sum \limits _{i=2}^{n-1}{(ni)\left(2A_{n}^{1}-{\binom {i-1}{1)) \right)}}{2}};

{\binom {n}{4}}={\frac {\sum \limits _{i=3}^{n-1}{(ni)\left(2n(n-1)-\summa \limits _{i_{0}=1}^{i-2}i_{0}\right)}}{23}}={\frac {\sum \limits _{i=3}^{n-1 }{(ni)\left(2A_{n}^{2}-{\binom {i-1}{2}}\right)}}{23}};

{\begin{alignedat}{2}&{\binom {n}{5}}={\frac {\sum \limits _{i=4}^{n-1}{(ni)\left (2n(n-1)(n-2)-\summa \limits _{i_{0}=1}^{i-3}\summa \limits _{i_{1}=1}^{i_{0 }}i_{1}\right)}}{119}}=\\&={\frac {\sum \limits _{i=4}^{n-1}{(ni)\left(2A_{n }^{3}-{\binom {i-1}{3}}\right)}}{119}};\\\end{alignedat}}

{\binom {n}{k}}={\frac {\sum \limits _{i=k-1}^{n-1}{(ni)\left(2A_{n}^{k -2}-{\binom {i-1}{k-2}}\right)}}{k!-1}}

var är antalet placeringar från till . $A_{n}^{k}$ $n$ $k$

Matrisrelationer

Om vi tar en kvadratisk matris, räknar elementen längs benen i Pascals triangel och roterar matrisen med något av de fyra hörnen, då är determinanten för dessa fyra matriser ±1 för vilken som helst , och determinanten för matrisen med spetsen på triangeln i det övre vänstra hörnet är 1. $N$ $N$

I matrisen upprepar siffrorna på diagonalen antalet rader i Pascals triangel ( ). Det kan sönderdelas till en produkt av två strikt diagonala matriser: den nedre triangulära och den som erhålls från den genom transponering: ${\begin{bmatrix}{\tbinom {i+j}{i}}\end{bmatrix}}$ $i+j=\mathrm {Const}$ $i,j=0,1,\dots$

{\begin{bmatrix}{\binom {i+j}{i}}\end{bmatrix}}=UU^{T}

var . Den inversa matrisen k har formen: $U={\begin{bmatrix}{\tbinom {i}{j}}\end{bmatrix}}$ $U$

U^{-1}={\begin{bmatrix}(-1)^{i+j}{\binom {i}{j}}\end{bmatrix}}

Således är det möjligt att sönderdela den inversa matrisen k till en produkt av två strikt diagonala matriser: den första matrisen är övre triangulär och den andra erhålls från den första genom att transponera, vilket gör att vi kan ge ett explicit uttryck för inversa element: ${\begin{bmatrix}{\tbinom {i+j}{i}}\end{bmatrix}}$

{\begin{bmatrix}{\binom {i+j}{i}}\end{bmatrix}}_{{m,n}}^{{-1}}=\summa _{{k=0}} ^{{p}}(-1)^{{m+n}}{\binom {k}{m}}{\binom {k}{n}}

, där , , , .

i

j

m

n=0\dots p

Elementen i en invers matris ändras när dess storlek ändras och till skillnad från en matris räcker det inte att tilldela en ny rad och kolumn. Matrisens kolumn är ett gradpolynom i argumentet , därför bildar de första p-kolumnerna en komplett bas i utrymmet av vektorer med längd +1, vars koordinater kan interpoleras med ett polynom av lika eller mindre grad . Den nedre raden av matrisen är ortogonal mot någon sådan vektor. ${\begin{bmatrix}{\tbinom {i+j}{i}}\end{bmatrix}}$ $j$ ${\begin{bmatrix}{\tbinom {i+j}{i}}\end{bmatrix}}$ $j$ $i$ $sid$ $p-1$ ${\begin{bmatrix}{\binom {i+j}{i}}\end{bmatrix}}_{{m,n}}^{{-1}}$

{\begin{bmatrix}{\binom {i+j}{i}}\end{bmatrix}}_{{p,n}}^{{-1}}=\summa _{{k=0}} ^{{p}}(-1)^{{p+n}}{\binom {k}{p}}{\binom {k}{n}}=(-1)^{{p+n} }{\binom {p}{n}}

\sum _{{n=0}}^{{p}}(-1)^{{p+n}}{\binom {p}{n}}{P}_{{a}}(n) =0

för , där är ett polynom av grad .

a<p

{Panorera)

a

Om en godtycklig längdvektor kan interpoleras med ett polynom av grad , då är punktprodukten med rader (numrerade från 0) i matrisen noll. Med hjälp av identiteten ovan och enheten av punktprodukten i den nedre raden av matrisen och den sista kolumnen i matrisen får vi: $p+1$ $i<p$ $i+1,i+2,\prickar ,s$ ${\begin{bmatrix}{\binom {i+j}{i}}\end{bmatrix}}_{{m,n}}^{{-1}}$ ${\begin{bmatrix}{\binom {i+j}{i}}\end{bmatrix}}_{{m,n}}^{{-1}}$ ${\begin{bmatrix}{\tbinom {i+j}{i}}\end{bmatrix}}$

\sum _{n=0}^{p}(-1)^{p+n}{\binom {p}{n}}{n}^{p}=p!

För en exponent större kan du ställa in den rekursiva formeln: $sid$

\sum _{n=0}^{p}(-1)^{p+n}{\binom {p}{n}}{n}^{p+a}=p!{P} _{2a}(p)={f}_{a}(p)

var är polynomet

{P}_{2a+2}(p)=\sum _{x=1}^{p}x{P}_{2a}(x);\quad a\geqslant 0;\quad { P}_{0}(p)=1

För att bevisa det, etablerar vi först en identitet:

{f}_{a}(p+1)=\sum _{x=0}^{a}{(p+1)}^{x+1}{f}_{ax}(p )

Om du behöver hitta en formel för inte alla exponenter, då:

{P}_{2a}(p)={\frac {p}{{2}^{a}}}{\binom {p+a}{a}}{Q}_{a-1 }(p);\quad a>0

Den högsta koefficienten är 1, det kommer att krävas a-1 värden för att hitta de andra koefficienterna: ${Q}_{{a-1}}(p)$

{Q}_{{a-1}}(p)=p(p+1){T}_{{a-3}}(p)

för .

a\equiv 1{\pmod {2));a\geqslant 3

Asymptotik och uppskattningar

${\binom {2n}{n}}\sim {\frac {2^{2n}}{\sqrt {\pi n}}}$ .
$\sum _{{k=0}}^{{m}}{\binom {n}{k}}\leqslant {\frac {n}{(n/2-m)^{2}}}2^ {{n-3}}$ at ( Chebyshevs ojämlikhet ). $m<{\frac {n}{2}}$
$\sum \limits _{{k=0}}^{{m}}{\binom {n}{k}}\leqslant 2^{{nH({\frac {m}{n}})))}$ , vid ( entropiuppskattning ), där är entropi . $m\leq {\frac {n}{2))$ $H(x)=-x\log _{2}x-(1-x)\log _{2}(1-x)$
$\sum _{{k=0}}^{{n/2-\lambda }}{\binom {n}{k}}\leqslant 2^{n}e^{{-2\lambda ^{2} /n}}$ ( Chernovs ojämlikhet ).

Det följer direkt av Stirlings formel att för är sant . $\alpha \in(0;1)$ $C_{n}^{{\alpha n}}\sim {\sqrt {{\frac {1}{2\pi \alpha (1-\alpha )n))))\left({{\frac {1 }{\alpha }}}\right)^{{\alpha n}}\left({{\frac {1}{1-\alpha }}}\right)^{{(1-\alpha )n} }=\left({{\frac {1}{\alpha ^{\alpha }{(1-\alpha )}^{{(1-\alpha )))}}+o(1)}\höger) ^{{n}}$

Heltalspolynom

Binomialkoefficienterna , ... är heltalspolynom av , det vill säga de tar heltalsvärden för heltalsvärden på , - detta är lätt att förstå, till exempel från Pascals triangel. Dessutom utgör de en bas för heltalsvärde polynom, där alla heltalsvärdade polynom uttrycks som linjära kombinationer med heltalskoefficienter. [ett] ${\tbinom {x}{0}}=1,{\tbinom {x}{1}}=x,{\tbinom {x}{2}}={\tfrac {x^{2}} {2}}-{\tfrac {x}{2}}$ $x$ $x$

Samtidigt tillåter standardbasen , ... inte att uttrycka alla heltalspolynom om bara heltalskoefficienter används, eftersom den redan har bråkkoefficienter i potenserna . ${\displaystyle 1,x,x^{2))$ ${\tbinom {x}{2}}={\tfrac {x^{2}}{2}}-{\tfrac {x}{2}}$ $x$

Detta resultat generaliserar till polynom i många variabler. Nämligen, om ett polynom av grad har reella koefficienter och tar heltalsvärden för heltalsvärden för variablerna, då $R(x_1, \prickar, x_m)$ $k$

R(x_{1},\dots ,x_{m})=P\left({\binom {x_{1}}{1}},\dots ,{\binom {x_{1}}{ k)),\dots ,{\binom {x_{m}}{1)),\dots ,{\binom {x_{m}}{k}}\right)

där är ett polynom med heltalskoefficienter. [2] $P$

Beräkningsalgoritmer

Binomialkoefficienterna kan beräknas med den rekursiva formeln om värdena för lagras vid varje steg . Denna algoritm är särskilt effektiv om du behöver få alla värden för en fast . Algoritmen kräver minne ( vid beräkning av hela tabellen med binomialkoefficienter) och tid (förutsatt att varje tal upptar en minnesenhet och operationer med tal utförs per tidsenhet), där — « » är stor . ${\tbinom {n}{k}}={\tbinom {n-1}{k}}+{\tbinom {n-1}{k-1}}$ $n$ $\tbinom{n}{k}$ $k={\överlinje {0,1,\;\ldots ,n))$ $\tbinom{n}{k}$ $n$ $På)$ $O(n^{2})$ $O(n^{2})$ $O$ $o$

Med ett fast värde kan binomialkoefficienterna beräknas med en rekursiv formel med ett initialt värde på . Denna metod kräver minne och tid för att beräkna värdet . $k$ ${\tbinom {n}{k}}={\tfrac {n}{nk}}\cdot {\tbinom {n-1}{k}}$ ${\tbinom {k}{k}}=1$ $\tbinom{n}{k}$ $O(1)$ $På)$

Om du vill beräkna koefficienterna för ett fast värde kan du använda formeln för initialvillkoret . Vid varje iterationssteg reduceras täljaren med (startvärdet är ), och nämnaren ökas på motsvarande sätt med (startvärdet är ). Denna metod kräver minne och tid för att beräkna värdet . $\tbinom{n}{k}$ $n$ ${\tbinom {n}{k}}={\tfrac {n-k+1}{k}}\cdot {\tbinom {n}{k-1}}$ ${\tbinom {n}{0}}=1$ $ett$ $n$ $ett$ $ett$ $\tbinom{n}{k}$ $O(1)$ $Ok)$

Anteckningar

↑ Prasolov V. V. Kapitel 12. Heltalsvärdade polynom // Polynom . — M .: MTsNMO , 1999, 2001, 2003.
↑ Yu Matiyasevich. Hilberts tionde problem. - Vetenskap, 1993.

Litteratur

Binomial coefficients // Encyclopedic Dictionary of Brockhaus and Efron : i 86 volymer (82 volymer och 4 ytterligare). - St Petersburg. 1890-1907.
Fuks D., Fuks M. Arithmetic of binomial coefficients // Kvant . - 1970. - Nr 6 . - S. 17-25 .
Kuzmin OV Pascals triangel och pyramid: egenskaper och generaliseringar // Soros Educational Journal . - 2000. - T. 6 , nr 5 . - S. 101-109 .
Lando S. K. Shadow calculus // VIII Summer School "Modern Mathematics". — Dubna, 2008.
Vinberg E. B. Överraskande aritmetiska egenskaper hos binomialkoefficienter // Matematisk utbildning . - 2008. - Utgåva. 12 . — s. 33–42 .
Donald Knuth , Ronald Graham , Oren Patashnik . konkret matematik. Matematiska grunder för datavetenskap = Konkret matematik. En stiftelse för datavetenskap. - 2:a. — M .: Mir ; Binom. Kunskapslaboratoriet ; "Williams" , 1998-2009. - 703, 784 sid. — ISBN 95-94774-560-7 , 78-5-8459-1588-7.