Coeficient binomial

În matematică , coeficientul binomial ${n \choose k}$ ${\ displaystyle {n \ alege k}}$ ${n \ alege k}$ (care scrie „ $n$ ${\ displaystyle n}$ $n$ pe $k$ ${\ displaystyle k}$ $k$ ") este un număr întreg negativ definit prin următoarea formulă

{n \choose k}=C(n;k)={\frac {n!}{k!\cdot \left(n-k\right)!}},\qquad n,k\in \mathbb {N} ,0\leq k\leq n,

{\ displaystyle {n \ choose k} = C (n; k) = {\ frac {n!} {k! \ cdot \ left (nk \ right)!}}, \ qquad n, k \ in \ mathbb { N}, 0 \ leq k \ leq n,}

{\ displaystyle {n \ choose k} = C (n; k) = {\ frac {n!} {k! \ cdot \ left (nk \ right)!}}, \ qquad n, k \ in \ mathbb { N}, 0 \ leq k \ leq n,}

unde este $n!$ ${\ displaystyle n!}$ $n!$ este factorialul $n$ ${\ displaystyle n}$ $n$ . De asemenea, poate fi calculat folosind triunghiul Tartaglia . Oferă numărul de combinații simple de $n$ ${\ displaystyle n}$ $n$ elemente de clasă $k$ ${\ displaystyle k}$ $k$ .

De exemplu:

{5 \choose 3}={\frac {5!}{3!(5-3)!}}={\frac {5\cdot 4\cdot 3\cdot 2\cdot 1}{3\cdot 2\cdot 1\cdot (2\cdot 1)}}={120 \over 12}=10

{\ displaystyle {5 \ choose 3} = {\ frac {5!} {3! (5-3)!}} = {\ frac {5 \ cdot 4 \ cdot 3 \ cdot 2 \ cdot 1} {3 \ cdot 2 \ cdot 1 \ cdot (2 \ cdot 1)}} = {120 \ over 12} = 10}

{\ displaystyle {5 \ choose 3} = {\ frac {5!} {3! (5-3)!}} = {\ frac {5 \ cdot 4 \ cdot 3 \ cdot 2 \ cdot 1} {3 \ cdot 2 \ cdot 1 \ cdot (2 \ cdot 1)}} = {120 \ over 12} = 10}

este numărul de combinații de $5$ ${\ displaystyle 5}$ $5$ obiecte luate $3$ ${\ displaystyle 3}$ $3$ la un moment dat.

Proprietate

Coeficientul binomial are următoarele proprietăți:

${n \choose 0}={n \choose n}=1.$ ${\ displaystyle {n \ choose 0} = {n \ choose n} = 1.}$ ${\ displaystyle {n \ choose 0} = {n \ choose n} = 1.}$

Demonstrație formală:

{n \choose 0}={{n!} \over {0!(n-0)!}}={n! \over n!}=1

{\ displaystyle {n \ choose 0} = {{n!} \ over {0! (n-0)!}} = {n! \ peste n!} = 1}

{n \ alege 0} = {{n!} \ peste {0! (n-0)!}} = {n! \ peste n!} = 1

{n \choose n}={{n!} \over {n!(n-n)!}}={n! \over n!}=1.

{\ displaystyle {n \ choose n} = {{n!} \ over {n! (nn)!}} = {n! \ peste n!} = 1.}

{\ displaystyle {n \ choose n} = {{n!} \ over {n! (n-n)!}} = {n! \ peste n!} = 1.}

Dovadă combinatorie: combinațiile de

n

{\ displaystyle n}

n

elemente de lungime o

n

{\ displaystyle n}

n

ele sunt în mod evident doar una: respectiv mulțimea goală sau întregul set de

n

{\ displaystyle n}

n

elemente.

${n \choose 1}={n \choose n-1}=n.$ ${\ displaystyle {n \ choose 1} = {n \ choose n-1} = n.}$ ${\ displaystyle {n \ choose 1} = {n \ choose n-1} = n.}$

Demonstrație formală:

{n \choose 1}={{n!} \over {1!(n-1)!}}={{n!} \over {(n-1)![n-(n-1)]!}}={n \choose n-1}=n.

{\ displaystyle {n \ choose 1} = {{n!} \ over {1! (n-1)!}} = {{n!} \ over {(n-1)! [n- (n-1 )]!}} = {n \ alegeți n-1} = n.}

{\ displaystyle {n \ choose 1} = {{n!} \ over {1! (n-1)!}} = {{n!} \ over {(n-1)! [n- (n-1 )]!}} = {n \ alegeți n-1} = n.}

Dovadă combinatorie: există evident

n

{\ displaystyle n}

n

modalități de a alege un articol printre

n

{\ displaystyle n}

n

sau să lase unul afară.

${n \choose k}={n \choose n-k}$ ${\ displaystyle {n \ choose k} = {n \ choose nk}}$ ${n \ alege k} = {n \ alege n-k}$

Demonstrație formală:

{n \choose k}={{n!} \over {k!(n-k)!}}={{n!} \over {(n-k)![n-(n-k)]!}}={n \choose n-k}.

{\ displaystyle {n \ choose k} = {{n!} \ over {k! (nk)!}} = {{n!} \ over {(nk)! [n- (nk)]!}} = {n \ alegeți nk}.}

{\ displaystyle {n \ choose k} = {{n!} \ over {k! (nk)!}} = {{n!} \ over {(nk)! [n- (nk)]!}} = {n \ alegeți nk}.}

Dovada combinatorie: alegerile

k

{\ displaystyle k}

k

elementele sunt în corespondență unu-la-unu cu subseturile din

n-k

{\ displaystyle nk}

n-k

elemente lăsate deoparte.

${n+1 \choose k+1}={n \choose k+1}+{n \choose k}$ ${\ displaystyle {n + 1 \ alege k + 1} = {n \ alege k + 1} + {n \ alege k}}$ ${n + 1 \ alege k + 1} = {n \ alege k + 1} + {n \ alege k}$ , adică: ${n \choose k}={n-1 \choose k}+{n-1 \choose k-1}.$ ${\ displaystyle {n \ choose k} = {n-1 \ choose k} + {n-1 \ choose k-1}.}$ ${\ displaystyle {n \ choose k} = {n-1 \ choose k} + {n-1 \ choose k-1}.}$

(proprietate care permite construirea coeficienților binomiali cu triunghiul Tartaglia . Mai mult, această proprietate poate fi utilă pentru a arăta că

{n \choose k}

{\ displaystyle {n \ alege k}}

{n \ alege k}

este un număr întreg negativ care folosește principiul inducției pe

n

{\ displaystyle n}

n

, cu ipoteza că

{n \choose k}

{\ displaystyle {n \ alege k}}

{n \ alege k}

aparține numerelor întregi non-negative pentru fiecare

k\in \mathbb {N}

{\ displaystyle k \ in \ mathbb {N}}

{\ displaystyle k \ in \ mathbb {N}}

astfel încât

0\leq k\leq n

{\ displaystyle 0 \ leq k \ leq n}

{\ displaystyle 0 \ leq k \ leq n}

, și ca o teză pentru care același lucru este valabil și pentru

{n+1 \choose k}

{\ displaystyle {n + 1 \ alege k}}

{\ displaystyle {n + 1 \ alege k}}

; pentru

n=1

{\ displaystyle n = 1}

n = 1

avem asta

{1 \choose 0}={1 \choose 1}=1\in \mathbb {N}

{\ displaystyle {1 \ choose 0} = {1 \ choose 1} = 1 \ in \ mathbb {N}}

{\ displaystyle {1 \ choose 0} = {1 \ choose 1} = 1 \ in \ mathbb {N}}

).

Demonstrație formală:

{n \choose k+1}+{n \choose k}={{n!} \over {(k+1)!(n-k-1)!}}+{{n!} \over {k!(n-k)!}}

{\ displaystyle {n \ choose k + 1} + {n \ choose k} = {{n!} \ over {(k + 1)! (nk-1)!}} + {{n!} \ over { k! (nk)!}}}

{n \ choose k + 1} + {n \ choose k} = {{n!} \ over {(k + 1)! (nk-1)!}} + {{n!} \ over {k! ( nk)!}}

tinand cont de faptul ca

(n-k)!=(n-k)(n-k-1)!

{\ displaystyle (nk)! = (nk) (nk-1)!}

(n-k)! = (n-k) (n-k-1)!

și la fel

(k+1)!=(k+1)k!

{\ displaystyle (k + 1)! = (k + 1) k!}

(k + 1)! = (k + 1) k!

da ai

{n \choose k+1}+{n \choose k}={{n!} \over {(k+1)k!(n-k-1)!}}+{{n!} \over {(n-k)k!(n-k-1)!}}=

{\ displaystyle {n \ choose k + 1} + {n \ choose k} = {{n!} \ over {(k + 1) k! (nk-1)!}} + {{n!} \ over {(nk) k! (nk-1)!}} =}

{n \ choose k + 1} + {n \ choose k} = {{n!} \ over {(k + 1) k! (nk-1)!}} + {{n!} \ over {(nk ) k! (nk-1)!}} =

={(n-k){n!} \over {(k+1)(n-k)k!(n-k-1)!}}+{(k+1){n!} \over {(k+1)(n-k)k!(n-k-1)!}}

{\ displaystyle = {(nk) {n!} \ over {(k + 1) (nk) k! (nk-1)!}} + {(k + 1) {n!} \ over {(k + 1) (nk) k! (Nk-1)!}}}

= {(nk) {n!} \ over {(k + 1) (nk) k! (nk-1)!}} + {(k + 1) {n!} \ over {(k + 1) ( nk) k! (nk-1)!}}

prin urmare

{n \choose k+1}+{n \choose k}={(n-k+k+1){n!} \over {(k+1)k!(n-k)(n-k-1)!}}

{\ displaystyle {n \ choose k + 1} + {n \ choose k} = {(n-k + k + 1) {n!} \ over {(k + 1) k! (nk) (nk-1)! }}}

{n \ alege k + 1} + {n \ alege k} = {(n-k + k + 1) {n!} \ peste {(k + 1) k! (nk) (nk-1)!}}

{n \choose k+1}+{n \choose k}={{(n+1)!} \over {(k+1)!(n-k)!}}={n+1 \choose k+1}

{\ displaystyle {n \ choose k + 1} + {n \ choose k} = {{(n + 1)!} \ over {(k + 1)! (nk)!}} = {n + 1 \ choose k + 1}}

{n \ alege k + 1} + {n \ alege k} = {{(n + 1)!} \ peste {(k + 1)! (nk)!}} = {n + 1 \ alege k + 1 }

sau teza.

Dovadă combinatorie: Pentru a calcula numărul de combinații simple de

n+1

{\ displaystyle n + 1}

n + 1

elemente de lungime

k+1

{\ displaystyle k + 1}

k + 1

, alegem una dintre

n+1

{\ displaystyle n + 1}

n + 1

elemente, pe care le vom numi Pippo și împărțim combinațiile în două clase: cele care nu conțin Pippo și cele care îl conțin. Cardinalitățile celor două clase sunt date în mod evident de cei doi termeni ai celui de-al doilea membru al formulei pe care am vrut să o dovedim.

$2^{n}={n \choose 0}+{n \choose 1}+{n \choose 2}+\ldots +{n \choose n-1}+{n \choose n}=\sum _{k=0}^{n}{n \choose k}.$ ${\ displaystyle 2 ^ {n} = {n \ alege 0} + {n \ alege 1} + {n \ alege 2} + \ ldots + {n \ alege n-1} + {n \ alege n} = \ sum _ {k = 0} ^ {n} {n \ alege k}.}$ ${\ displaystyle 2 ^ {n} = {n \ alege 0} + {n \ alege 1} + {n \ alege 2} + \ ldots + {n \ alege n-1} + {n \ alege n} = \ sum _ {k = 0} ^ {n} {n \ alege k}.}$

Demonstrație formală:

pornind de la teorema binomului avem:

2^{n}=(1+1)^{n}=\sum _{k=0}^{n}{n \choose k}1^{(n-k)}1^{k}=\sum _{k=0}^{n}{n \choose k}

{\ displaystyle 2 ^ {n} = (1 + 1) ^ {n} = \ sum _ {k = 0} ^ {n} {n \ alege k} 1 ^ {(nk)} 1 ^ {k} = \ sum _ {k = 0} ^ {n} {n \ alege k}}

2 ^ {n} = (1 + 1) ^ {n} = \ sum _ {{k = 0}} ^ {n} {n \ alege k} 1 ^ {{(nk)}} 1 ^ {{k }} = \ sum _ {{k = 0}} ^ {n} {n \ alege k}

sau teza.

Dovadă combinatorie:

2^{n}

{\ displaystyle 2 ^ {n}}

2 ^ {{n}}

este numărul de subseturi ale unui set de

n

{\ displaystyle n}

n

elemente. Putem împărți aceste subgrupuri în clase, plasând în fiecare clasă cele de o anumită cardinalitate. Deoarece subseturile cardinalității

k

{\ displaystyle k}

k

sunt foarte

{n \choose k}

{\ displaystyle {n \ alege k}}

{n \ alege k}

, teza este imediat obținută.

Aplicații

Teorema binomului , sau binomul lui Newton, folosește coeficientul binomial pentru a exprima dezvoltarea unei puteri $n$ ${\ displaystyle n}$ $n$ -thth din orice binom conform următoarei formule:

(a+b)^{n}=\sum _{k=0}^{n}{n \choose k}a^{n-k}b^{k}.

{\ displaystyle (a + b) ^ {n} = \ sum _ {k = 0} ^ {n} {n \ alege k} a ^ {nk} b ^ {k}.}

{\ displaystyle (a + b) ^ {n} = \ sum _ {k = 0} ^ {n} {n \ alege k} a ^ {n-k} b ^ {k}.}

Numărul de diagonale ale unui poligon convex de $n$ ${\ displaystyle n}$ $n$ laturile pot fi exprimate conform următoarei formule: $d={n \choose 2}-n={\frac {n(n-3)}{2}}$ ${\ displaystyle d = {n \ alege 2} -n = {\ frac {n (n-3)} {2}}}$ $d = {n \ alege 2} -n = {\ frac {n (n-3)} {2}}$
Având un set $S.$ ${\ displaystyle S}$ $S.$ , astfel încât $|S|=n$ ${\ displaystyle | S | = n}$ $| S | = n$ , coeficientul binomial este utilizat pentru a calcula cardinalitatea setului de părți ale $S.$ ${\ displaystyle S}$ $S.$ , ${\mathcal {P}}(S)$ ${\ displaystyle {\ mathcal {P}} (S)}$ ${\ mathcal {P}} (S)$ :

|{\mathcal {P}}(S)|=\sum _{k=0}^{n}{n \choose k}=2^{n}.

{\ displaystyle | {\ mathcal {P}} (S) | = \ sum _ {k = 0} ^ {n} {n \ alege k} = 2 ^ {n}.}

{\ displaystyle | {\ mathcal {P}} (S) | = \ sum _ {k = 0} ^ {n} {n \ alege k} = 2 ^ {n}.}

Puterea $n$ ${\ displaystyle n}$ $n$ -thth dintr-un număr întreg $X$ ${\ displaystyle x}$ $X$ poate fi exprimat cu suma tuturor producătorilor posibili de $x-1$ ${\ displaystyle x-1}$ ${\ displaystyle x-1}$ coeficienți binomiali ${n \choose a}{a \choose b}{b \choose c}\ldots {i \choose j}{j \choose k}{k \choose l}$ ${\ displaystyle {n \ choose a} {a \ choose b} {b \ choose c} \ ldots {i \ choose j} {j \ choose k} {k \ choose l}}$ ${\ displaystyle {n \ choose a} {a \ choose b} {b \ choose c} \ ldots {i \ choose j} {j \ choose k} {k \ choose l}}$ , cu $n\geq a\geq b\geq c\geq \ldots \geq i\geq j\geq k\geq l$ ${\ displaystyle n \ geq a \ geq b \ geq c \ geq \ ldots \ geq i \ geq j \ geq k \ geq l}$ ${\ displaystyle n \ geq a \ geq b \ geq c \ geq \ ldots \ geq i \ geq j \ geq k \ geq l}$ . Exemplu:

4^{3}={3 \choose 3}{3 \choose 3}{3 \choose 3}+{3 \choose 3}{3 \choose 3}{3 \choose 2}+{3 \choose 3}{3 \choose 3}{3 \choose 1}+{3 \choose 3}{3 \choose 3}{3 \choose 0}+{3 \choose 3}{3 \choose 2}{2 \choose 2}+\ldots +{3 \choose 1}{1 \choose 1}{1 \choose 0}+{3 \choose 1}{1 \choose 0}{0 \choose 0}+{3 \choose 0}{0 \choose 0}{0 \choose 0}.

{\ displaystyle 4 ^ {3} = {3 \ alege 3} {3 \ alege 3} {3 \ alege 3} + {3 \ alege 3} {3 \ alege 3} {3 \ alege 2} + {3 \ alege 3} {3 \ alege 3} {3 \ alege 1} + {3 \ alege 3} {3 \ alege 3} {3 \ alege 0} + {3 \ alege 3} {3 \ alege 2} {2 \ alege 2} + \ ldots + {3 \ alege 1} {1 \ alege 1} {1 \ alege 0} + {3 \ alege 1} {1 \ alege 0} {0 \ alege 0} + {3 \ alege 0 } {0 \ alege 0} {0 \ alege 0}.}

{\ displaystyle 4 ^ {3} = {3 \ alege 3} {3 \ alege 3} {3 \ alege 3} + {3 \ alege 3} {3 \ alege 3} {3 \ alege 2} + {3 \ alege 3} {3 \ alege 3} {3 \ alege 1} + {3 \ alege 3} {3 \ alege 3} {3 \ alege 0} + {3 \ alege 3} {3 \ alege 2} {2 \ alege 2} + \ ldots + {3 \ alege 1} {1 \ alege 1} {1 \ alege 0} + {3 \ alege 1} {1 \ alege 0} {0 \ alege 0} + {3 \ alege 0 } {0 \ alege 0} {0 \ alege 0}.}

Extensii

Putem extinde coeficientul binomial în cazul în care $k$ ${\ displaystyle k}$ $k$ este negativ sau mai mare decât $n$ ${\ displaystyle n}$ $n$ , punând:

{n \choose k}=0,\qquad n,k\in \mathbb {Z} ,n>0,k<0

{\ displaystyle {n \ choose k} = 0, \ qquad n, k \ in \ mathbb {Z}, n> 0, k <0}

{\ displaystyle {n \ choose k} = 0, \ qquad n, k \ in \ mathbb {Z}, n> 0, k <0}

sau

k>n.

{\ displaystyle k> n.}

{\ displaystyle k> n.}

De asemenea, puteți extinde coeficientul la numere reale. În acest scop, poate fi convenabil să începeți cu observația că coeficientul binomial este, de asemenea, raportul dintre numărul de funcții injective dintr-un set de cardinalitate. $k$ ${\ displaystyle k}$ $k$ într-una de cardinalitate $n$ ${\ displaystyle n}$ $n$ (adică numărul de dispoziții simple ale $n$ ${\ displaystyle n}$ $n$ obiecte de clasă $k$ ${\ displaystyle k}$ $k$ ) și numărul de permutări ale $k$ ${\ displaystyle k}$ $k$ obiecte:

{n \choose k}={\frac {(n)_{k}}{k!}}={\frac {n!}{(n-k)!k!}}.

{\ displaystyle {n \ choose k} = {\ frac {(n) _ {k}} {k!}} = {\ frac {n!} {(nk)! k!}}.}

{\ displaystyle {n \ choose k} = {\ frac {(n) _ {k}} {k!}} = {\ frac {n!} {(n-k)! k!}}.}

Putem cere:

(a)_{k}=a(a-1)\cdots (a-k+1)=\prod _{i=0}^{k-1}(a-i),\qquad a\in \mathbb {C} ,k\in \mathbb {Z} ,k\geq 0,

{\ displaystyle (a) _ {k} = a (a-1) \ cdots (a-k + 1) = \ prod _ {i = 0} ^ {k-1} (ai), \ qquad a \ in \ mathbb {C}, k \ in \ mathbb {Z}, k \ geq 0,}

{\ displaystyle (a) _ {k} = a (a-1) \ cdots (a-k + 1) = \ prod _ {i = 0} ^ {k-1} (ai), \ qquad a \ in \ mathbb {C}, k \ in \ mathbb {Z}, k \ geq 0,}

de exemplu,

(4{,}5)_{3}=4{,}5\cdot 3{,}5\cdot 2{,}5=39{,}375.

{\ displaystyle (4 {,} 5) _ {3} = 4 {,} 5 \ cdot 3 {,} 5 \ cdot 2 {,} 5 = 39 {,} 375.}

{\ displaystyle (4 {,} 5) _ {3} = 4 {,} 5 \ cdot 3 {,} 5 \ cdot 2 {,} 5 = 39 {,} 375.}

Cu această convenție, avem:

{a \choose k}={\frac {(a)_{k}}{k!}}\qquad a\in \mathbb {C} ;k\in \mathbb {Z} ,k\geq 0,

{\ displaystyle {a \ choose k} = {\ frac {(a) _ {k}} {k!}} \ qquad a \ in \ mathbb {C}; k \ in \ mathbb {Z}, k \ geq 0,}

{\ displaystyle {a \ choose k} = {\ frac {(a) _ {k}} {k!}} \ qquad a \ in \ mathbb {C}; k \ in \ mathbb {Z}, k \ geq 0,}

de exemplu:

{4{,}5 \choose 3}={\frac {(4{,}5)_{3}}{3!}}={\frac {39{,}375}{6}}=6{,}5625.

{\ displaystyle {4 {,} 5 \ choose 3} = {\ frac {(4 {,} 5) _ {3}} {3!}} = {\ frac {39 {,} 375} {6}} = 6 {,} 5625.}

{\ displaystyle {4 {,} 5 \ choose 3} = {\ frac {(4 {,} 5) _ {3}} {3!}} = {\ frac {39 {,} 375} {6}} = 6 {,} 5625.}

Caz special

Se poate observa că pentru $k=2$ ${\ displaystyle k = 2}$ $k = 2$ coeficientul binomial este egal cu suma primului $n-1$ ${\ displaystyle n-1}$ $n-1$ numere naturale :

{n \choose 2}={\frac {n!}{(n-2)!2!}}={\frac {n(n-1)(n-2)!}{(n-2)!2}}={\frac {n(n-1)}{2}}=\sum _{i=1}^{n-1}i.

{\ displaystyle {n \ choose 2} = {\ frac {n!} {(n-2)! 2!}} = {\ frac {n (n-1) (n-2)!} {(n- 2)! 2}} = {\ frac {n (n-1)} {2}} = \ sum _ {i = 1} ^ {n-1} i.}

{\ displaystyle {n \ choose 2} = {\ frac {n!} {(n-2)! 2!}} = {\ frac {n (n-1) (n-2)!} {(n- 2)! 2}} = {\ frac {n (n-1)} {2}} = \ sum _ {i = 1} ^ {n-1} i.}

Bibliografie

Mauro Cerasoli, Franco Eugeni; Marco Protasi, Elemente de matematică discretă , Bologna, Zanichelli, 1988.
Giorgio Dall'Aglio, Calculul probabilității , Bologna, Zanichelli, 2003.
Sheldon M. Ross, Calculul probabilităților , Milano, Apogee, 2004.
Saunders Mac Lane, Garrett Birkhoff, Algebra , Milano, Mursia 1998

Elemente conexe

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere pe coeficient binomial

linkuri externe

( EN ) Coeficient binomial , în Encyclopedia Britannica , Encyclopædia Britannica, Inc.

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

V · D · M Combinatorial
Orientare generală	Combinatorică · Istoria combinatoriei · Matematică discretă · Secțiunea 05-XX din MSC
Noțiuni introductive	Permutații · Dispoziții · Combinații · Coeficienți binomiali · Partiții de numere întregi · Partiții de mulțimi finite - Identități și bijecții combinatorii
Configurări	Pătrat latin · pătrate magice · Desene Block · geometrii finite · Matroids - mozaicare · Polimini
Teoria graficelor	Copaci · Mers pe grafice ( Eulerian , Hamiltonian ) · Conexiune în grafice - grafice plane · Vopsirea graficelor și teorema celor patru culori ) · hipergrafe · Grafice și grupuri · digraf · Grafic al fluxului de numerar · Plimbări aleatorii pe grafice · omomorfismul graficelor · Algoritmi pe grafice
Combinatorie algebrică	Tabelul lui Young · funcții simetrice - serie de puteri formale · Funcții de generare · Polinoame ortogonale · Părți ale unui grup de structuri combinatorii - Aspecte algebră comutativă combinatorie
Alte domenii	Calculul umbrelor ( secvențe polinomiale de tip binomial · secvențe Sheffer ) - Combinatorial extremal