← defterler · MATH 323 Combinatorics + Calculus

Kombinatorik Defteri

Ders notlarının sadeleştirilmiş hâli. Her konu önce günlük dille, sonra formülle, sonra adım adım örnekle anlatılıyor. Sınav İngilizce olduğu için önemli terimlerin İngilizcesi de yanında.

1. Sırayla gitKonular birbirinin üstüne kuruluyor. 1'den başla, atlama.
2. Önce kendin dene"Sen dene" kutularında cevabını yaz, kontrol et. Takılırsan önce ipucuna bak, sonra çözüme.
3. İşaretleBir konuyu anladığında en alttaki butona bas. Soldaki çubuk ilerler.
4. Renk kapısıHer doğru cevap +1, her biten konu +3 jeton kazandırır. 3 jeton = yeni bir bulmaca bölümü. Sağ alttaki butondan ya da Konu 0'daki bölüm haritasından aç.
yavaş yavaş, sırayla. sen yaparsın ♡
Konu 0 · Ödül

Renk kapısı: bütün bölümler

100 bulmaca bölümü · doğru cevaplarla açılır

nasıl çalışırHer doğru cevap +1 jeton, her biten konu +3 jeton kazandırır. Yeni bir bölüm 3 jeton. Bitirdiğin bölümleri istediğin kadar bedavaya tekrar oynayıp yıldızlarını artırabilirsin.
★ bitti · tekrar oynasıradakikilitli

Konu 1 · Isınma

Faktöriyel ve "kaç farklı yol var?" sorusu

Factorial

kısacaKombinatorik tek bir soruyu sorar: "Bunu kaç farklı şekilde yapabilirim?" Listeyi tek tek yazmak yerine akıllıca saymanın yollarını öğreneceğiz.

En çok kullanacağımız araç faktöriyel. demek, 'den 1'e kadar bütün sayıları çarpmak demek:

0! = 1 bir tanımdır. "Hiç kimseyi dizmenin 1 yolu var: hiçbir şey yapmamak."
12345678
12624120720504040320

ilk 6 tanesini ezberle, quizde hız kazandırır

Sadeleştirme hilesi

Büyük faktöriyeli, küçüğüne kadar aç. Gerisi sadeleşir:

sen dene

kaçtır?

Çözüm
sen dene

kaçtır?

Çözüm
Konu 2 · Temel

Toplama kuralı ve çarpma kuralı

Addition rule & Product rule

kısaca"VEYA" gördüğünde topla, "VE / sonra" gördüğünde çarp. Bütün dersin temeli bu iki cümle.

Toplama kuralı: ya bu ya şu

Bir kafede 3 çeşit çay, 4 çeşit kahve var. Bir içecek seçeceksin. Ya çay ya kahve alırsın, ikisi aynı anda olmaz. Seçenek sayısı .

Şart: kümeler çakışmayacak (pairwise disjoint), yani bir seçenek iki grupta birden olmayacak.

Çarpma kuralı: önce bu, sonra şu

3 tişörtün, 2 pantolonun var. Bir tişört ve bir pantolon giyeceksin. Her tişört için 2 pantolon seçeneği var, yani kombin.

1. adım yolla, 2. adım yolla, … yapılabiliyorsa

Kutucuk yöntemi: Her adım için bir çizgi çiz, üstüne o adımda kaç seçenek olduğunu yaz, sonra hepsini çarp. Derste hep bunu yapıyoruz.

Ex5 basamaklı kaç doğal sayı vardır? (How many 5-digit natural numbers are there?)

91–9
(0 olamaz)
100–9
100–9
100–9
100–9

90 000

ExRakamları farklı (distinct digits) 5 basamaklı kaç doğal sayı vardır?

91–9
90 geri geldi,
1. rakam gitti
82 rakam
kullanıldı
7
6

27 216

ikinci kutu neden 9? 0 artık kullanılabilir ama ilk kutuya koyduğumuz rakam kullanılamaz: 10 − 1 = 9

ExRakamları farklı, 5 basamaklı kaç çift sayı vardır?

Sorun şu: son basamak (çift olmalı) ile ilk basamak (0 olamaz) birbirini etkiliyor. Son basamak 0 ise ilk basamak için bir kısıt kalkıyor. O yüzden durumlara ayırıyoruz:

  1. Durum 1: son basamak 0. İlk basamak 1–9 arası, 9 seçenek. Sonra 8, 7, 6.
  2. Durum 2: son basamak 2, 4, 6 ya da 8 (4 seçenek). İlk basamak: 0 olamaz, son basamaktaki rakam da olamaz, yani 8 seçenek. Ortadakiler 8, 7, 6.
  3. Durumlar çakışmıyor, topla: 13 776
Altın kural

Her zaman en kısıtlı kutudan başla. Burada önce son basamağa, sonra ilk basamağa karar verdik, en son da serbest olanlara. Kısıtlar birbirini etkiliyorsa durumlara ayır. Durumlar arası toplama, durum içi çarpma.

Bonus: bölen sayısı

Bir sayının asal çarpanlarına ayrılmış hâli ise, pozitif bölen sayısı:

Neden? Bir bölen kurarken her asal için "kaçıncı kuvvetini alayım?" diye seçim yaparsın. için arasından seçenek var ve öbür asallar için de aynısı geçerli. Çarpma kuralı.

Örnek: , bölen sayısı . Gerçekten de bölenler 1, 2, 3, 4, 6, 8, 12, 24.

distinct farklıdigit rakam/basamakeven / odd çift / tekat least one en az birdivisor bölen
sen dene

Rakamları farklı, 4 basamaklı kaç tek sayı vardır?

İpucu
Önce son basamak (1, 3, 5, 7, 9 → 5 seçenek), sonra ilk basamak (0 olamaz, son rakam olamaz).
Çözüm
Son: 5. İlk: 0 değil, sondaki değil → 8. Ortadakiler: 8 ve 7.
sen dene

3 basamaklı sayıların kaç tanesinde en az bir tane 7 rakamı vardır?

İpucu
"En az bir" gördüğünde tersini say: Tümü − hiç 7 olmayanlar.
Çözüm
Tümü: . Hiç 7 yok: . Cevap .
sen dene

360'ın kaç pozitif böleni vardır?

Çözüm
, bölen sayısı
Konu 3 · Sıralama

Permütasyon: sırası önemli dizilişler

Permutations, r-permutations

kısacaPermütasyon = farklı nesneleri bir sıraya dizmek. "Ali–Ayşe–Can" ile "Can–Ali–Ayşe" farklı sayılır, çünkü sıra önemli.

Hepsini dizmek:

4 arkadaş fotoğraf için yan yana dizilecek. 1. yere 4 kişiden biri, 2. yere kalan 3 kişiden biri, sonra 2, sonra 1: .

ş

Bir kısmını dizmek:

8 koşucu yarışıyor. Altın, gümüş ve bronz kaç farklı şekilde dağıtılabilir? Altına 8, gümüşe 7, bronza 6 aday var: . Kutucuk yönteminde sadece 3 kutu çizdik.

ç kişiden tanesini seçip sıraya dizmek. Buna r-permutation denir.

kısa yol: n'den başla, geriye doğru r tane sayı çarp. P(8,3) = 8·7·6

Sıra önemli mi?

Her soruda kendine sor: "İki kişinin yerini değiştirirsem farklı bir sonuç olur mu?" Başkan ve yardımcı seçiyorsan olur, yani permütasyon. 3 kişilik ekip seçiyorsan olmaz, yani kombinasyon (Konu 6).

arrangement dizilimin a row sıra hâlindepermutation permütasyonlinear ordering doğrusal sıralama
sen dene

KİTAP kelimesinin harfleriyle (anlamlı ya da anlamsız) kaç farklı 5 harfli dizilim yazılabilir?

Çözüm
5 farklı harf:
sen dene

7 kişilik bir kulüpten başkan, başkan yardımcısı ve sekreter kaç farklı şekilde seçilir?

Çözüm
Görevler farklı, yani sıra önemli:
sen dene

1, 2, 3, 4, 5 rakamları kullanılarak rakamları farklı kaç tane 3 basamaklı sayı yazılır?

Çözüm
Konu 4 · Quiz'in 2. sorusu hep buradan

Yan yana olsun / olmasın

Consecutive, adjacent: block method & gap method

kısacaÜç tane yöntem var. Hepsi çok görsel:
Yan yana olsunlar → bantla yapıştır (blok).
Yan yana olmasınlar (iki kişi) → tümünden çıkar.
Hiçbiri yan yana olmasın (çok kişi) → aralara yerleştir (boşluk).

Yöntem 1 · Blok: yan yana olacakları yapıştır

Yan yana olması gerekenleri bantla yapıştırıp tek bir kişi gibi düşün. Sonra iki şeyi çarp: (blok + diğerleri) dizilişi × blokun kendi içindeki diziliş.

ExA, B, C, D, E, F, G, H harfleri kaç şekilde dizilir öyle ki…

  1. a) A ve B yan yana (consecutive): [AB] C D E F G H → 7 birim: . Blok içi AB ya da BA: . Cevap:
  2. b) A ve B yan yana değil: Tümü − yan yana olanlar
  3. c) A–B yan yana ve C–D yan yana: [AB] [CD] E F G H → 6 birim: , iki blok da kendi içinde 2'şer:
  4. d) A–B yan yana ve B–C yan yana: B ortada olmak zorunda: ABC ya da CBA. [ABC] D E F G H →
Tuzak (d şıkkı)

[AB] ve [BC] diye iki ayrı blok yaparsan B'yi iki kere kullanmış olursun. Ortak eleman varsa tek büyük blok yap.

Yöntem 2 · Boşluk: önce serbestleri diz, kısıtlıları aralara koy

"Hiçbir iki kız yan yana olmasın" gibi sorularda önce kısıtsız grubu diz. Onların arasında oluşan boşluklara kısıtlı olanları, her boşluğa en fazla bir kişi olacak şekilde yerleştir. Böylece ikisi asla yan yana gelemez.

_ E _ E _ E _ E _ E _

5 erkek dizince 6 boşluk oluşur (aralar + iki uç). n kişi → n+1 boşluk

Ex7 erkek, 3 kız bir sıraya dizilecek. (i) 3 kız tek bir blok olsun. (ii) İki uçta erkek olsun ve hiçbir iki kız yan yana olmasın.

  1. (i) Kızları yapıştır: [K K K] + 7 erkek = 8 birim → . Kızlar kendi içinde . Cevap:
  2. (ii) Önce 7 erkeği diz: . Uçlar erkek olacak, yani kızlar sadece iç boşluklara girebilir: E _ E _ E _ E _ E _ E _ E → 6 iç boşluk.
  3. 3 farklı kızı 6 boşluğa, her boşluğa en fazla 1 kız olacak şekilde koy: .
  4. Cevap: 604 800 (notlardaki ile aynı sayı)
Notlarda küçük bir hataWeek 1 notunda (b) şıkkının cevabı "16·7!" yazıyor. Doğrusu 6·7!, çünkü .
consecutive ardışık, yan yanaadjacent bitişiknext to each other yan yanablock blokend positions uçlar
sen dene

6 kişi sıraya dizilecek. A ile B yan yana olacak şekilde kaç diziliş vardır?

Çözüm
[AB] + 4 kişi = 5 birim: , blok içi :
sen dene

Aynı 6 kişi: A ile B yan yana olmayacak şekilde kaç diziliş vardır?

Çözüm
Tümü − yan yana:
sen dene

5 erkek ve 3 kız sıraya dizilecek. Hiçbir iki kız yan yana olmayacak. Kaç diziliş vardır?

İpucu
Önce erkekler. Bu sefer uçlar da serbest: 5 erkek → 6 boşluk.
Çözüm
Erkekler . 6 boşluğa 3 kız: . Cevap:
sen dene

4 farklı matematik ve 3 farklı fizik kitabı rafa dizilecek. Matematikler bir arada, fizikler bir arada olacak. Kaç diziliş vardır?

Çözüm
İki blok: [M] [F] → . Blok içleri: ve .
Konu 5 · Sıralama

Yuvarlak masa: dairesel sıralama

Circular permutations

kısacaYuvarlak masada "baş köşe" yok. Herkes bir sandalye kayarsa oturuş düzeni aynı sayılır. Bu yüzden bir kişiyi yerine sabitle, kalanları diz.

1, 2, 3, 4 masaya oturdu. Saat yönünde 1-2-3-4, 2-3-4-1, 3-4-1-2 ve 4-1-2-3 aslında aynı masa, sadece döndürülmüş. Düz sırada 4 farklı diziliş olan şey dairede tek dizilişe denk geliyor. O yüzden .

şşBirini sabitle. Onun sağından başlayarak kalan kişiyi düz sıra gibi diz.

Ex4 erkek ve 4 kız yuvarlak masaya oturacak. (a) Kaç şekilde? (b) Hiçbir iki erkek yan yana olmasın.

  1. (a) 8 kişi:
  2. (b) Boşluk yöntemi, daire versiyonu: Önce 4 erkeği masaya oturt: . Artık masa döndürülemez, çünkü erkekler yer tuttu.
  3. Erkeklerin arasında tam 4 boşluk var (dairede uç yok). 4 kızı bu 4 boşluğa diz: .
  4. Cevap: 144

genel hâli: n erkek n kız, erkekler yan yana değil → (n−1)!·n!

Tuzak

Kızları yerleştirirken tekrar yazma. Daireyi ilk grup zaten "sabitledi". İkinci grup artık düz sıra gibi ile dizilir.

circular table yuvarlak masasit around etrafına oturmakrotation döndürme
sen dene

6 kişi yuvarlak bir masaya kaç farklı şekilde oturabilir?

Çözüm
sen dene

6 kişi yuvarlak masaya oturacak, A ile B yan yana olacak. Kaç şekilde?

Çözüm
Blok + daire: [AB] + 4 kişi = 5 birim → , blok içi :
sen dene

5 erkek, 5 kız yuvarlak masaya kız–erkek sırayla (alternating) oturacak. Kaç şekilde?

Çözüm
Erkekler dairede . Aradaki 5 boşluğa kızlar .
Konu 6 · Seçme

Kombinasyon: sırası önemsiz seçimler

Combinations, ("n choose r")

kısacaKombinasyon = sadece "kimler" önemli, sıra önemli değil. {Ali, Ayşe, Can} ekibi ile {Can, Ali, Ayşe} ekibi aynı ekip.

Formül nereden geliyor?

4 kişiden (A, B, C, D) 2 kişilik ekip seçelim. Sıralı seçseydik olurdu. Ama AB ile BA aynı ekip, yani her ekibi 2 kere saymışız:

AB · AC · AD · BC · BD · CD → 12 / 2 = 6 ekip

Genel olarak kişilik her ekip, sıralı saymada kere sayılır. O yüzden 'e bölüyoruz:

Hızlı hesap: Üste 'den geriye tane sayı yaz, alta . Örnek: .

Bilmen gereken 3 küçük gerçek

  • (hiç kimseyi ya da herkesi seçmenin tek yolu var)
  • . Seçtiklerin ↔ dışarıda bıraktıkların. 5 kişiden 3'ünü seçmek, 2'sini dışarıda bırakmakla aynı şey. Bu yüzden olur, hesap kolaylaşır.

Ex4 öğretmen ve 7 öğrenciden (11 kişi) 5 kişilik bir komite seçilecek. Kaç şekilde seçilir eğer…

  1. (i) Kısıt yok:
  2. (ii) Tam 2 öğretmen (exactly): öğretmenlerden 2 ve öğrencilerden 3:
  3. (iii) En az 3 öğretmen (at least): ya 3 öğretmen ya 4 öğretmen olur, durumları topla:
  4. (iv) Belirli bir öğretmen ile belirli bir öğrenci birlikte olmasın: Tümü − ikisinin birlikte olduğu komiteler. İkisi içerideyse kalan 9 kişiden 3 kişi seçilir:
Anahtar kelimeler

exactly (tam) → grupları ayrı ayrı seç, çarp.
at least (en az) → durumlara ayırıp topla, ya da "tümü − istenmeyen" yap.
not both (ikisi birden olmasın) → tümü − ikisi birden.

0–1 dizileri (binary sequences)

Uzunluğu 7 olan, içinde 3 tane 0 ve 4 tane 1 bulunan kaç dizi var? 7 kutudan 0'ların gideceği 3 yeri seç, kalanlara 1 yaz: .

1 0 1 0 0 1 1 ← 0'lar 2., 4., 5. yerde

Eşleştirme (pairings): 2n kişiyi ikili gruplara ayırmak

1, 2, …, 2n kişisini ikililere ayırıyoruz. Her adımda kalanlar içindeki en küçük numaralı kişiye bir eş seç: ilk kişiye aday var, sonra kalanların en küçüğüne , …

6 kişi (n=3): 5·3·1 = 15 farklı eşleştirme.
committee komitechoose / select seçmekexactly tam olarakat least / at most en az / en fazlabinary sequence 0-1 dizisi
sen dene

10 kişilik bir sınıftan 3 kişilik bir proje grubu kaç şekilde seçilir?

Çözüm
sen dene

6 erkek ve 5 kızdan 4 kişilik bir komite seçilecek. Komitede en az bir kız olacak. Kaç şekilde?

İpucu
Tümü − hiç kız olmayan (hepsi erkek).
Çözüm
sen dene

Aynı soru: komitede tam 2 kız olacak. Kaç şekilde?

Çözüm
sen dene

Uzunluğu 8 olan ve tam olarak üç tane 1 içeren kaç 0–1 dizisi vardır?

Çözüm
1'lerin yerini seç:
sen dene

8 kişi tenis için 4 ikili takıma kaç farklı şekilde ayrılabilir?

Çözüm
:
Konu 7 · Quiz'in 1. sorusu hep buradan

Izgarada en kısa yollar

Shortest routes on a grid · Bijection principle

kısacaA'dan B'ye sadece sağa (R) ve yukarı (U) giderek ilerliyorsun. Her yol aslında R ve U harflerinden oluşan bir kelime. Yol saymak = kelime saymak.

5 sağ, 3 yukarı gitmen gereken bir ızgarada her en kısa yol tam olarak 5 R ve 3 U içerir. Örneğin RRURURRU. 8 harflik kelimede U'ların gideceği 3 yeri seçersen yol belli olur:

sağ, yukarı giden en kısa yol sayısı. Bijection principle: iki küme arasında birebir eşleme varsa eleman sayıları eşittir. Burada yollar ↔ kelimeler.
Dene: ızgara laboratuvarı
Bu yolun kelimesi:

Quiz'de çıkan 4 varyasyon

SoruNe yaparsın
C'den geçen (passing through C)
C'den geçmeyenTümü − C'den geçen
C'den geçen ama D'den geçmeyen
C veya D'den geçen (ikisinden de geçenleri iki kez saydın, bir kez çıkar)
Izgaranın bir parçası eksikTam dikdörtgen − eksik bölgeden geçmek zorunda olan yollar

Ex7×5'lik ızgarada (7 sağ, 5 yukarı) C noktası (3, 3)'te. (a) C'den geçen kaç yol var? (b) Kaç tanesi C'den geçmez?

  1. A → C: 3 sağ, 3 yukarı →
  2. C → B: 4 sağ, 2 yukarı →
  3. (a) Çarpma kuralı: 300
  4. (b) Tümü , C'den geçmeyen 492
Notlarda küçük bir yazım hatasıWeek 2 notunda " " yazıyor. Arada çarpma olmalı: . Sonuç doğru.
Tuzak

Mesafeleri hep noktadan noktaya say, kare sayma. C'nin koordinatı (3, 2) ise A'dan C'ye 3 sağ 2 yukarı gidersin. C'den B'ye ise "B'nin koordinatı − C'nin koordinatı" kadar gidersin. D, C'nin sol tarafında ya da aşağısındaysa ikisinden birden geçen yol yoktur ve o terim 0 olur.

shortest route / path en kısa yolpassing through -den geçengrid ızgararight / up sağ / yukarı
sen dene

4 sağ, 3 yukarı gidilen bir ızgarada A'dan B'ye kaç en kısa yol vardır?

Çözüm
sen dene

Aşağıdaki 6×4'lük ızgarada A'dan B'ye, C'den geçen kaç en kısa yol vardır?

Çözüm
A→C: 2 sağ 2 yukarı . C→B: 4 sağ 2 yukarı .
sen dene

Aynı ızgarada C'den geçmeyen kaç yol vardır?

Çözüm
Tümü .
sen dene · quiz seviyesi

5×5'lik ızgarada C = (2, 2), D = (4, 3). C veya D'den geçen kaç en kısa yol vardır?

İpucu
. C ve D'den birlikte geçen yol: A → C → D → B.
Çözüm

C→D: 2 sağ 1 yukarı, .

Cevap:

Konu 8 · Sıralama

Tekrarlı permütasyon: aynı harfler varsa

Arrangements with repetition (identical objects)

kısacaMARMARA'daki iki M'nin yerini değiştirirsen yeni bir kelime çıkmaz. Yani ile fazla saymış oluyoruz. Aynı olanların kendi aralarındaki dizilişlerine böl.

AABB harflerini dizelim: AABB, ABAB, ABBA, BAAB, BABA, BBAA. Toplam 6 tane. Formülle: . ✓

tane 1. tür (birbirinin aynı), tane 2. tür, …

ExMARMARA kelimesinin harfleriyle kaç farklı kelime yazılır?

  1. Harfleri say: M → 2, A → 3, R → 2. Toplam 7.
  2. 210

ANKARA: A→3, N, K, R tek → 6!/3! = 120

Neden doğru? (ikinci bakış) 7 boş kutu düşün. Önce A'ların gideceği 3 kutuyu seç: . Kalan 4 kutudan M'lerinkini seç: . Kalan 2 kutu R'lerin: . Hepsini çarpınca aynı formül çıkıyor. Izgara yolları da aslında bu konudan: RRRRRUUU kelimesinin dizilişi .

Ex1×7'lik bir şerit, 1×1 ve 1×2'lik parçalarla kaç farklı şekilde döşenir?

Kaç tane 1×2 kullandığına göre durumlara ayır. Her durumda bu parçaların dizilişi tekrarlı permütasyondur:

1×2 sayısı1×1 sayısıDiziliş
07
15
23
31

Toplam: 21

identical objects özdeş nesnelerwords kelimelertile döşemek
sen dene

KELEBEK kelimesinin harfleriyle kaç farklı dizilim yapılabilir?

Çözüm
K→2, E→3, L→1, B→1, toplam 7.
sen dene

1, 1, 1, 2, 2 rakamlarının hepsi kullanılarak kaç farklı 5 basamaklı sayı yazılır?

Çözüm
sen dene

1×6'lık şerit 1×1 ve 1×2 parçalarla kaç farklı şekilde döşenir?

Çözüm
0 tane 1×2: 1. 1 tane: . 2 tane: . 3 tane: 1. Toplam 13.
Konu 9 · Quiz'in 3b sorusu hep buradan

Denklemin kaç çözümü var? (yıldız ve çubuk)

Repeated selections · Stars and bars · Integer solutions

kısaca denkleminin negatif olmayan tam sayı çözümlerini saymak, 10 özdeş şekeri 4 çocuğa dağıtmakla aynı şey. = 1. çocuğun aldığı şeker sayısı.

Şekerleri ★ ile göster. 4 çocuğu ayırmak için 3 çubuk (|) yeter. Her dizilim bir çözüme karşılık gelir:

Dene: yıldız ve çubuk

Yani 10 yıldız + 3 çubuk = 13 sembolün dizilişini sayıyoruz. 13 yerden çubukların 3 yerini seç: .

çöün = toplam (yıldız), r = değişken sayısı, r − 1 = çubuk sayısı

formülü ezberleme, "n yıldız, r−1 çubuk" diye düşün

Tip 1 · Alt sınır var (, …)

Önce herkese payını ver, kalanı serbestçe dağıt. Matematikçe söylersek: yeni değişken tanımla, böylece olur.

Ex için…

  1. : Herkese 1 ver, kalır. →
  2. : dağıt, 4 kalır →
  3. : Negatif alt sınır "borç" gibi düşünülür: . Toplam →

Tip 2 · Üst sınır var ()

Üst sınırı doğrudan sayamayız. Tümü − sınırı aşanlar. ""in tersi "" olur ve bu bir alt sınırdır, Tip 1 ile çözülür.

Ex, ve .

  1. Tümü:
  2. olanlar: 9'u ver, 11 kalır →
  3. Cevap: 9261

Tip 3 · Çift / tek kısıtı

Çift: yaz. Tek: yaz. Denkleme koy, 2'ye böl, yeni bir "normal" denklem çıkar.

Ex

  1. Hepsi çift, : → →
  2. Hepsi pozitif tek: → → toplam 3 →
  3. 5 değişken, toplam 20, üçü çift ikisi tek: Önce hangi üçünün çift olacağını seç: . Sonra 'lerin toplamı → . Cevap
İki tuzak

"Pozitif çift" demek ≥ 2 demek, yani ve olur. Bu 'lere tekrar alt sınır uygulamayı unutma.
Önce tek–çift kontrolü yap: 5 tane tek sayının toplamı tektir, 40 olamaz. Böyle bir soruda cevap 0'dır.

Tekrarlı kombinasyon: aynı şeyi birden çok kez seçebiliyorsan

{A, B, C}'den 2 tane seçelim. Tekrar yoksa {A,B}, {A,C}, {B,C}: . Tekrar serbestse {A,A}, {B,B}, {C,C} de eklenir ve 6 olur. Sıra yine önemsiz.

Bu da aslında yıldız-çubuk sorusu. Her elemandan kaç tane aldığını yaz: . Genel olarak çeşitten tane seçmek, denkleminin çözüm sayısıdır:

çeşit, seçim, tekrar serbest, sıra önemsiz. Örnek: {1,2,3,4}'ten 3 tane:

Dağıtma problemleri: toplar ve kutular

"Kaç şekilde dağıtılır?" sorularında ilk soru şu: toplar birbirinden farklı mı, aynı mı?

DurumSayıNeden
farklı top, farklı kutuHer top için kutu seçeneği var, çarpma kuralı
özdeş top, farklı kutuSadece her kutuya kaç top düştüğü önemli: yıldız-çubuk

farklı toplar: "her top kendi kutusunu seçer". özdeş toplar: "her kutu kaç top aldı?"

Tuzak

'i ile karıştırma. Taban kutu sayısı, üs top sayısı: her top seçenekten birini seçiyor ve tane top var.

sen dene

4 çeşit dondurmadan 3 top alacaksın, aynı çeşitten birden fazla alabilirsin, sıra önemsiz. Kaç farklı seçim var?

Çözüm
çeşit, seçim:
sen dene

5 farklı mektup 3 posta kutusuna kaç farklı şekilde atılabilir?

Çözüm
Her mektup 3 kutudan birini seçer:
sen dene

5 özdeş top 3 farklı kutuya kaç şekilde dağıtılır?

Çözüm
non-negative negatif olmayan (≥ 0)positive pozitif (≥ 1)integer solutions tam sayı çözümleriidentical özdeş
sen dene

, denkleminin kaç çözümü vardır?

Çözüm
7 yıldız, 2 çubuk:
sen dene

Aynı denklem, ama .

Çözüm
Herkese 1 ver, 4 kalır:
sen dene

, ve .

İpucu
Tümü − ( olanlar).
Çözüm
sen dene

, her negatif olmayan çift sayı.

Çözüm
toplamı 5, 3 değişken:
sen dene

, her pozitif tek sayı.

Çözüm
: toplamı →
sen dene · tuzaklı

, her pozitif çift sayı.

Çözüm
Çift sayıların toplamı çifttir, 11 olamaz. Cevap 0.
Konu 10 · Chapter 2

Binom katsayıları ve binom teoremi

Binomial coefficients · Pascal's triangle · The binomial theorem

kısaca sayıları iki yerde karşımıza çıkar: seçim sayılarında ve açılımının katsayılarında. Aynı sayılar, iki farklı hikâye.

Pascal üçgeni

Her sayı, üstündeki iki sayının toplamı. Bir sayıya tıkla, hangi iki sayıdan geldiğini gör:

Dene: Pascal üçgeni
Bir sayıya tıkla.

Hikâyesi: kişiden kişi seçeceksin ve aralarında Ali var. Ya Ali seçilir (kalan kişiden seçilir) ya seçilmez (kalan kişiden seçilir). İki durumun toplamı.

Altküme sayısı:

elemanlı bir kümenin her elemanı için soru: "Altkümede var mı, yok mu?" Her eleman için 2 seçenek var, toplam . Her altküme bir 0–1 dizisine karşılık gelir: {1,2} ↔ 1100. Altkümeleri eleman sayısına göre de sayabiliriz. Sonuç:

Binom teoremi

Örnek: . Katsayılar 1, 3, 3, 1, yani Pascal'ın 3. satırı.

Neden? . Çarpımı açarken her parantezden ya ya seçersin. terimi, parantezin tanesinden seçince oluşur ve bunu yapmanın yolu vardır.

Katsayı bulma tarifi

  1. Genel terimi yaz:
  2. 'in kuvvetlerini topla
  3. İstenen kuvvete eşitle, 'yı bul
  4. Katsayıyı yaz (sayıları da unutma)

Ex açılımında 'un katsayısı nedir?

  1. Genel terim:
  2. 'in kuvveti:
  4. Katsayı:

Ex açılımında 'un katsayısı?

Her parantezden bir seçiyoruz, kuvvetler toplamı 10 olmalı: , . Toplam zaten 10 olduğu için üst sınır bir şey değiştirmiyor. Bu Konu 9'deki soruyla aynı: 1001

Önemli özdeşlikler (ne işe yaradıklarıyla)

ÖzdeşlikAkılda kalsın diye
Seçilenler ↔ dışarıda kalanlar
Ekip + lider: önce ekip sonra lider = önce lider sonra ekip
Önce m kişilik grup, içinden r lider = önce r lider, sonra grubun geri kalanı
Her boyutta ekip + lider. Ters sırayla: lider seç (n yol), geri kalan kişiden istediğin altkümeyi al ()
'in türevini iki kez al, koy
Vandermonde: m kız + n erkekten r kişi = (i kız, r − i erkek) durumlarının toplamı
Vandermonde'da
Hokey sopası: Pascal'da bir çapraz boyunca toplayınca altta bir yan sütuna düşersin

Ex olduğunu göster. (Notlarda üç farklı ispatı var.)

  1. 1. yol (özdeşlik): olduğu için toplam
  2. 2. yol (hikâye): kişiden bir ekip ve ekibe bir lider seç. Ekip boyutu ise yol vardır, hepsini topla. Ters sırayla: önce lider (n yol), sonra kalan kişiden istediğin kadarını al (). İkisi aynı şeyi saydığı için eşit.
  3. 3. yol (türev): . Türev al: . koy: .

kontrol: n = 5 → 5 + 20 + 30 + 20 + 5 = 80 = 5·2⁴ ✓

coefficient katsayıexpansion açılımclosed formula kapalı formülidentity özdeşliksubset altküme
sen dene

açılımında 'ün katsayısı nedir?

Çözüm
→ 80
sen dene

açılımında 'nin katsayısı nedir?

Çözüm
Genel terim . .
sen dene

kaçtır?

Çözüm
Hokey sopası: . Kontrol:
sen dene

kaçtır?

Çözüm
Konu 11 · Quiz'in 3a sorusu hep buradan

Binom toplamlarını hesaplama hileleri

Compute the sum · Find a closed formula

kısacaÖnüne ş gibi bir toplam gelirse amaç onu 'e benzetmek. Binom teoreminde koyunca:

4 hile

Ne görüyorsun?Ne koyarsın?Sonuç
(işaretler + − + −)
doğrudan
Sadece çift k'lar: ve ile iki açılımı topla, 2'ye böl

Çift indis hilesi neden çalışıyor? açılımında bütün terimler + işaretli. açılımında ise tek 'lı terimler − işaretli. İkisini toplayınca tek terimler birbirini götürür, çift terimler iki kez sayılır. Sonra 2'ye bölersin.

(1+a)ⁿ = C₀ + C₁a + C₂a² + C₃a³ + …
(1−a)ⁿ = C₀ − C₁a + C₂a² − C₃a³ + …
toplam = 2(C₀ + C₂a² + C₄a⁴ + …)

özel durum (a = 1): C(n,0) + C(n,2) + C(n,4) + … = 2ⁿ⁻¹

Ex için kapalı formül bul.

. Kontrol (n = 4): ✓

Ex

  1. , yani toplam
  2. Dikkat: son terim () eksik. Tam toplamı alıp eksik terimi çıkar.

Ex

  1. Sadece çift indisler var, .

Ex (sadece ilk yarı)

Simetri: . İlk yarının toplamı ise ikinci yarınınki olur, çünkü ortadaki terim bir kere sayılıyor. , buradan .

Tuzak

Her zaman başlangıç ve bitiş indisine bak. Bir terim eksikse önce tam toplamı al, sonra eksiği çıkar. Üs gibi garip görünüyorsa sabit kısmı dışarı al: .

sen dene

kaçtır?

Çözüm
sen dene

kaçtır?

Çözüm
Çift indisler, :
sen dene

kaçtır?

Çözüm
sen dene · quiz seviyesi

kaçtır?

Çözüm
Çift indis, :
Konu 12 · Tekrar

Soru tipini tanı: hangi formül?

The hardest part is choosing the right tool

kısacaFormülleri bilmek yetmez, en zor kısım hangisini kullanacağına karar vermek. Bir soru okuduğunda aşağıdaki soruları sırayla cevapla.
Konu 13 · Prova

Quiz provası

Past quizzes with full solutions

Elimizdeki 3 quiz'in hepsi aynı kalıpta: 1. soru ızgara yolları, 2. soru yan yana dizme, 3a binom toplamı, 3b denklem çözüm sayısı. Süreyi başlat, kâğıda çöz, sonra çözümlere bak. Gerçek sınavda "Show all work" yazıyor, yani her adımı yazmalısın.

45 dakika · 3 soru · 100 puan
45:00
1 · 30 puan

How many shortest routes are there from A to B passing through C but not passing through D?

Çözüm

Koordinatlar: C = (3, 2), D = (7, 4), B = (9, 6).

  1. A→C: 3 sağ 2 yukarı,
  2. C→B: 6 sağ 4 yukarı,
  3. C→D: 4 sağ 2 yukarı, . D→B: 2 sağ 2 yukarı,
  4. 1200
2 · 30 puan

A group of 10 people consisting of 5 girls and 5 boys are going to be arranged in a row. One of the boys is Ahmet and one of the girls is Beyza. How many arrangements are there such that Ahmet and Beyza are consecutive but there is no other pair of a boy and a girl who are consecutive?

Çözüm

Bir erkek bir kızın yanına sadece bir yerde geliyorsa, sıra tüm erkekler bir tarafta, tüm kızlar diğer tarafta olacak şekildedir ve sınırda Ahmet ile Beyza durur:

E E E E Ahmet Beyza K K K K veya K K K K Beyza Ahmet E E E E

Her iki durumda diğer 4 erkek , diğer 4 kız şekilde dizilir. Cevap: 1152

3a · 20 puan

Compute the sum

Çözüm

Sadece çift indisler, :

3b · 20 puan

How many solutions are there to the equation such that each is a positive even integer?

Çözüm
  1. , pozitif çift olduğu için .
  2. Herkese 1 ver: ,
  3. 11 628

kısa yol: xᵢ = 2yᵢ + 2 yaz, yᵢ ≥ 0 → toplam (40 − 12)/2 = 14

2. kısımQuiz 1 sonrası · vize konuları
Konu 14 · Vizede bir ispat sorusu kesin

Güvercin yuvası ilkesi

The Pigeonhole Principle

kısaca10 güvercin 9 yuvaya girerse en az bir yuvada 2 güvercin olur. Bu kadar basit bir cümleyle şaşırtıcı şeyler ispatlanır. "Show that there exist", "mutlaka vardır", "garanti" gördüğünde aklına bu gelsin.

notta yazıyor: "vizede 1 tane proof şeklinde gelir!"

= yukarı yuvarla.

Neden doğru? Her kutuda en fazla nesne olsaydı toplam en fazla olurdu. Ama elimizde nesne var. Çelişki.

  • 367 kişi arasında doğum günü aynı olan iki kişi mutlaka vardır (yılda en fazla 366 gün).
  • 61 kişi arasında aynı ayda doğmuş en az kişi vardır.

İspat tarifi: 4 adım

  1. Nesneler ne? Genelde soruda verilen şeyler: noktalar, sayılar, kişiler.
  2. Kutuları kur. Asıl iş burada. Kutuları öyle kur ki aynı kutuya düşen iki nesne, istenen özelliği otomatik sağlasın.
  3. Say: nesne sayısı > kutu sayısı mı? Öyleyse ilke devreye girer.
  4. Bitir: Aynı kutudaki iki nesnenin neden istenen şeyi sağladığını bir cümleyle yaz.
Sayılar ipucu verir

Soru 10 nokta diyorsa şekli 9 parçaya bölmen gerekiyor. 5 nokta diyorsa 4 sınıf arıyorsun. Kutu sayısı neredeyse her zaman nesne sayısından 1 eksiktir.

Tip 1 · Geometri: şekli eşit parçalara böl

ExKenarı 3 cm olan bir kareden 10 nokta seçiliyor. Aralarındaki uzaklık en fazla cm olan iki nokta olduğunu gösterin.

  1. Kutular: Kareyi 1 cm'lik 9 küçük kareye böl.
  2. Say: 10 nokta > 9 kare. İlkeye göre iki nokta aynı küçük karededir.
  3. Bitir: 1 cm'lik bir karenin içindeki iki nokta arasındaki uzaklık en fazla köşegen kadardır: . ∎

Ex9 cm × 16 cm'lik bir dikdörtgenden 13 nokta seçiliyor. Uzaklığı en fazla 5 cm olan iki nokta vardır.

12 tane 3×4'lük parçaya böl. 13 > 12 olduğu için iki nokta aynı parçadadır. 3×4'lük dikdörtgenin köşegeni . ∎

Aynı fikir, sayı doğrusunda: aralığından sayı seçilirse olan iki sayı vardır. Aralığı uzunluğunda parçaya böl: . Aynı parçaya düşen iki sayının farkı 'den küçüktür.

Tip 2 · Tek/çift sınıfları (parite)

ExKoordinatları tam sayı olan noktalara lattice point denir. Herhangi 5 lattice point arasında, orta noktası da lattice point olan iki nokta vardır.

  1. ile 'nin orta noktası . Bunun tam sayı olması için aynı paritede (ikisi de tek ya da ikisi de çift) ve aynı paritede olmalı.
  2. Kutular: bir noktanın "parite tipi": (çift, çift), (çift, tek), (tek, çift), (tek, tek). Toplam 4 kutu.
  3. 5 nokta > 4 tip. Aynı tipte iki nokta vardır, onların orta noktası lattice point'tir. ∎

vizede çıkan versiyon: 2ˣ3ʸ5ᶻ biçiminde 9 sayı → (x, y, z)'nin parite tipi 2·2·2 = 8 kutu. Konu 17'da çözümü var.

Tip 3 · Kalanlar (mod n)

tam sayıdan ikisinin 'ye bölümünden kalan aynıdır (sadece farklı kalan var). Kalanları aynı olan iki sayının farkı 'ye bölünür.

ExHerhangi tam sayı arasından, toplamı 'ye bölünen bir grup seçilebileceğini gösterin.

  1. Sayılar olsun. Birikimli toplamları yaz: .
  2. Bunlardan biri 'ye bölünüyorsa iş biter.
  3. Bölünmüyorsa tane değeri, sıfır olmayan kalana () dağılır. İlkeye göre iki tanesinin kalanı aynıdır: , .
  4. Farkları olur ve bu toplam 'ye bölünür. ∎

Tip 4 · Akıllı kutular

Ex ve ise 'da biri diğerini bölen iki sayı vardır.

  1. Her pozitif tam sayı tek bir şekilde ( tek) yazılır: , , .
  2. Kutular: tek kısım . 1–100 arasında 50 tek sayı var, yani 50 kutu: , , …, .
  3. 51 > 50. İki sayı aynı kutuda: ve . Küçük olan büyük olanı böler. ∎

Ex, . 'nın elemanları toplamı eşit olan iki ayrık altkümesi vardır.

  1. Nesneler: 'nın bütün altkümeleri, tane.
  2. Kutular: olası toplamlar. En küçük toplam 0, en büyük . Yani 120 kutu.
  3. 128 > 120. Toplamı aynı iki farklı altküme vardır. Ortak elemanları ikisinden de çıkarınca toplamlar yine eşit kalır ve kümeler ayrık olur. ∎

ExHerhangi 6 kişi arasında ya birbirini tanıyan 3 kişi ya da birbirini tanımayan 3 kişi vardır.

  1. A kişisini al. Diğer 5 kişiyle ilişkisi "tanır" ya da "tanımaz". 2 kutuya 5 nesne → en az tanesi aynı türden.
  2. Genelliği bozmadan A, B, C ve D'yi tanısın.
  3. B, C, D'den herhangi ikisi birbirini tanıyorsa A ile birlikte tanışan üçlü olur. Hiçbiri tanımıyorsa B, C, D tanışmayan üçlüdür. ∎
show that there exist var olduğunu gösterinat least / at most en az / en fazlalattice point tam sayı koordinatlı noktaparity teklik/çiftlikdivisible by -e bölünebilirWLOG genelliği bozmadan
sen dene

Çekmecede 10 kırmızı ve 10 mavi çorap var. Karanlıkta en az kaç çorap çekersen aynı renkten bir çift garanti olur?

Çözüm
Kutular = renkler (2 tane). 3 çorap > 2 renk → iki çorap aynı renk. 2 çorap yetmez (bir kırmızı bir mavi gelebilir). Cevap 3.
sen dene

Kırmızı, mavi ve yeşil çoraplar var (her renkten bol). Aynı renkten 3 çorap garanti olsun diye en az kaç çorap çekmelisin?

Çözüm
kutu, istiyoruz, yani : . 6 çorap yetmez (her renkten 2 gelebilir).
sen dene

100 kişilik bir grupta aynı ayda doğmuş en az kaç kişi olduğu garantidir?

Çözüm
sen dene

kümesinden en az kaç sayı seçersen, toplamı 11 olan iki sayı garanti olur?

İpucu
Kutular: toplamı 11 olan çiftler.
Çözüm
Kutular {1,10}, {2,9}, {3,8}, {4,7}, {5,6}: 5 kutu. 6 sayı seçersen ikisi aynı kutuya düşer ve toplamları 11 olur. 5 sayı yetmez (1, 2, 3, 4, 5).
sen dene · ispat

Kenarı 2 cm olan bir kareden 5 nokta seçiliyor. Uzaklığı en fazla cm olan iki nokta vardır.

Çözüm
Kareyi 1 cm'lik 4 küçük kareye böl. 5 nokta > 4 kare, iki nokta aynı küçük karede. Uzaklıkları en fazla köşegen kadar: . ∎
sen dene · ispat

Herhangi tam sayıdan, farkı 'ye bölünen iki tane seçilebileceğini gösterin.

Çözüm
Kutular: 'ye bölümden kalanlar, yani ( kutu). sayı > kutu, iki sayının kalanı aynı. Kalanları aynı olan iki sayının farkı 'ye bölünür. ∎
Konu 15 · Konu 9'in devamı

Birden çok kısıt: içerme–dışlama

Inclusion–exclusion · Two kinds of objects · The ballot problem

kısacaTek üst sınırda "tümü − aşanlar" yapıyorduk. İki üst sınır olunca iki tarafı da aşanları çıkarırsın. Ama ikisini birden aşanları iki kere çıkarmış olursun, onları bir kere geri ekle. Konu 7'daki "C veya D" formülünün aynısı.
Tek sayıda kümeli terimler +, çift sayıda kümeli terimler −.

Ex, , , . Kaç çözüm var?

  1. Tümü:
  2. (A kümesi): 16 ver, 20 kalır →
  3. (B kümesi): 11 ver, 25 kalır →
  4. İkisi birden: ver, 9 kalır →
  5. 176
Önce kontrol et

İki sınırın birlikte aşılması mümkün mü? , sorusunda iki değişken aynı anda 21'i geçemez (). O yüzden geri eklenecek terim 0'dır ve cevap olur. Bu bir eski vize sorusu.

Ters çevirme hilesi

Bütün değişkenler üstten sınırlı ve toplam büyükse değişkeni tersine çevir. Örnek: , . dersen olur ve . Toplam 4 olduğu için sınırı kendiliğinden sağlanır: 70.

"tam doluya ne kadar kaldı?" diye düşün

İki tür nesne

Ex12 özdeş kırmızı top ve 7 özdeş beyaz top 4 kutuya dağıtılacak. (a) Kısıt yok. (b) Her kutuda kırmızı sayısı en az beyaz sayısı kadar.

  1. (a) Kırmızılar ve beyazlar birbirinden bağımsız dağıtılır, çarp:
  2. (b) Önce beyazları dağıt: .
  3. Sonra her kutuya içindeki beyaz kadar kırmızı koy. Toplam 7 kırmızı kullanılır, şart sağlanmış olur.
  4. Kalan 5 kırmızıyı serbestçe dağıt: . Cevap: 6720

Kalan kısıtı

Ex, , ve 'lerin 3'e bölümünden kalanları birbirinden farklı.

  1. Kalanlar 0, 1, 2 olmak zorunda. Hangi değişkenin hangi kalanı alacağı: durum.
  2. Bir durum: . Toplam → →
  3. Her durum aynı sayıyı verir: 168

Oy sayımı (ballot) problemi

Ex erkek ve kız () bir sırada duruyor. Baştan başlayarak teker teker odaya giriyorlar. Her an odadaki erkek sayısı kız sayısından az olmamalı. Kaç sıralama bunu mümkün kılar?

için E/K desenleri: EEEKKK · EEKEKK · EEKKEK · EKEEKK · EKEKEK → 5 desen.

Bunu ızgara yolu gibi düşün: erkek = sağa, kız = yukarı. Şart, yolun köşegenin üstüne hiç çıkmaması demek. "Kötü" yolları köşegenin bir üst çizgisine göre yansıtınca her kötü yol başka bir uç noktaya giden bir yola birebir karşılık gelir. Yine bijection!

Kişiler farklıysa ile çarp. : desen, sıralama.
sen dene

, . Kaç çözüm var?

İpucu
Üç tane "" kümesi var. İkili kesişimler mümkün mü? Üçlü?
Çözüm
Tümü . Tek bir : 8 kalır, , üç tane: 135. İki tanesi : 1 kalır, , üç çift: 9. Üçü birden imkânsız.
sen dene

, . Kaç çözüm var?

İpucu
Ters çevirme hilesi: .
Çözüm
, (ve kendiliğinden).
sen dene

8 özdeş elma ve 5 özdeş armut 3 çocuğa kaç farklı şekilde dağıtılır?

Çözüm
sen dene

4 erkek, 4 kız odaya teker teker giriyor, odadaki erkek sayısı hiçbir an kızlardan az olmamalı. Kaç farklı E/K deseni var?

Çözüm
, ya da
Konu 16 · Vize

Üreteç fonksiyonları

Generating functions

kısacaBir sayı dizisini () tek bir fonksiyonun içine paketliyoruz. 'in katsayısı = dizinin . terimi. sadece bir raf etiketi, değeri hiç önemli değil.
Örnek: dizi 1, 1, 1, … ise

Ezberlenecek seriler

FonksiyonAçılımDizi
çift n'de 1, tek n'de 0
sonlu

son satır notta da sarıyla işaretli: en önemlisi bu

Son satır neden yıldız-çubuk formülü? . Çarpımda her parantezden bir seçiyorsun. 'in katsayısı, () denkleminin çözüm sayısıdır, yani Konu 9'deki .

Sayma tarifi

  1. Her değişken için bir parantez yaz. İçine o değişkenin alabileceği değerleri 'in kuvveti olarak koy.
  2. Parantezleri çarp.
  3. Ortak kuvvetini dışarı al. Kalanları tablodaki serilere çevir.
  4. İstenen kuvvetin katsayısını oku.

Ex, tam sayı. Kaç çözüm var?

  3. 'in katsayısı = 'te 'ün katsayısı 105

Konu 9'deki "önce payını ver" yöntemiyle de aynı sonuç: 18 − 5 = 13 kalır

Ex, . Üst sınırlar olduğunda üreteç fonksiyonu çok işe yarar.

  2. Ortak çarpanları al ve sonlu seri formülünü kullan:
  3. Payı aç: . dışarıda olduğu için 'ün katsayısını arıyoruz.
  4. Paydaki her terim, 'den bir katsayı çeker:
  5. 15

Ex5 farklı zar atılıyor. Toplamın 12 gelme yolu kaç tanedir?

  1. Her zar 1–6:
  2. için 'nin katsayısı lazım. . Sadece ve işe yarar.
  3. 305

Ex, her pozitif tek sayı.

. : 969

Rekürans (recurrence) çözme

Bir dizi kendi önceki terimleriyle tanımlanmışsa ( gibi), üreteç fonksiyonu genel formülü bulmamızı sağlar.

Ex (). ve nedir?

  1. Çarp ve topla: İki tarafı ile çarp, için topla:
  2. f cinsinden yaz: Sol taraf . Sağ taraf . Yani
  3. f'yi çek: →
  4. Basit kesirlere ayır: . . koy: → . koy: → .
  5. Katsayıyı oku: → ,

kontrol: a₀ = 3 + 1 = 4 ✓, a₁ = 6 + 3 = 9 ✓, a₂ = 5·9 − 6·4 = 21 = 12 + 9 ✓

Tuzak

Toplamı 'den başlattığın için sol tarafta ve 'i, sağdaki toplamında da 'ı çıkarmayı unutma. Hataların çoğu burada yapılıyor.

Ex (notlardaki ikinci örnek)

  1. Ek terim:
  2. →
  3. Basit kesirler: . koy:

Ex, ()

  1. . İki tarafı ile çarp, için topla:
  2. Sol taraf , sağ taraf . Yani .
  3. Türevi kendisine eşit fonksiyon: . → →
Notta yarım kalmışBu son örnek notta adımında bitiyor. Yukarıdaki son iki adım çözümü tamamlıyor.
generating function üreteç fonksiyonusequence dizicoefficient katsayırecurrence relation indirgeme bağıntısıpartial fractions basit kesirlerdistinct dice farklı zarlar
sen dene

açılımında 'in katsayısı nedir?

Çözüm
sen dene

açılımında 'ün katsayısı nedir?

Çözüm
sen dene

3 farklı zar atılıyor. Toplamın 10 gelme yolu kaç tanedir?

Çözüm
içinde 'nin katsayısı:
sen dene

4 farklı zar atılıyor. Toplamın 10 gelme yolu kaç tanedir?

Çözüm
içinde 'nın katsayısı:
sen dene

, , , . Kaç çözüm var?

Çözüm
. :
sen dene · vize seviyesi

. Genel formülü üreteç fonksiyonuyla bul ve 'i hesapla.

İpucu
Çözüm

→ →

. : , . : , .

,

Konu 17 · Prova

Vize provası

Old midterm problems with full solutions

Notlarda iki set vize sorusu var. Konular karışık: dizme, seçme, binom özdeşliği, dağıtma ve bir tane güvercin yuvası ispatı. Kâğıda çöz, sonra çözümlere bak.

1

Find the number of ways of arranging the 26 letters of the English alphabet in a row such that A is somewhere to the left of B and C is somewhere to the left of D.

Çözüm
  1. A ve B için 2 yer seç: . Soldaki yer A'nın, sağdaki B'nin, yani yerleşim tek türlü.
  2. Kalan 24 yerden C ve D için 2 yer: , yine tek türlü.
  3. Kalan 22 harf:

simetriyle: dizilişlerin yarısında A, B'nin solunda; onların da yarısında C, D'nin solunda → 26!/4

1a

…such that B is somewhere between A and C.

Çözüm
A, B, C için 3 yer seç: . B ortadaki yere gider, A ile C uçlara 2 türlü yerleşir. Kalan 23 harf . Cevap
2

Let . Find the number of 2-element subsets of such that is divisible by 5 but not divisible by 10.

Çözüm
  1. 10'a bölünmemesi için çarpım çift olmamalı, yani ve ikisi de tek.
  2. 1–99 arası tek sayılar: 5'e bölünenler , . Bölünmeyenler , .
  3. Çarpım 5'e bölünsün: ya ikisi de 'dan ya biri 'dan biri 'den.
  4. 445
bonus · notta ek olarak var

Aynı için, çarpımı 4'e bölünen kaç tane 2 elemanlı altkümesi vardır?

Çözüm
4'e bölünen 25 sayı, "çift ama 4'e bölünmeyen" (2, 6, 10, …, 98) 25 sayı, tek 50 sayı var. Ya en az biri 4'e bölünür: . Ya da ikisi de "2 mod 4": . Toplam 2475. (Kontrol: .)
3

Determine all positive integers satisfying .

Çözüm
Pascal: sol taraf , simetriden bu 'e de eşit. . . r = 5 veya r = 6
4 · güvercin yuvası

10 points are chosen in a rectangle with side lengths 9 cm and 20 cm. Prove that there exist two chosen points whose distance is at most cm.

4×55×4
Çözüm

10 nokta var, yani 9 parça lazım. Dikdörtgeni 9 parçaya böl: üstte 5 tane 4×5'lik (genişlik 4, yükseklik 5), altta 4 tane 5×4'lük (genişlik 5, yükseklik 4). Toplam genişlik iki sırada da 20, yükseklik 5 + 4 = 9 ✓.

10 nokta > 9 parça, iki nokta aynı parçada. Uzaklıkları en fazla köşegen kadar: . ∎

5

Let be positive integers. Prove that .

Çözüm

Cebirle: (Konu 10'daki 4. özdeşlik). Toplam .

Hikâyeyle: kişiden bir ekip seç ( kişi), ekipten de kişilik bir yönetim seç. Ters sırayla: önce yönetimi seç (), sonra kalan kişiden ekibe girecekleri istediğin gibi seç (). ∎

6a

How many solutions are there to such that each is an integer with ?

Çözüm
  1. Tümü:
  2. Bir : 21 ver, 19 kalır → . 4 değişken için .
  3. İki değişken aynı anda olamaz (), geri eklenecek bir şey yok.
6b

Compute .

Çözüm
İç toplam hokey sopası: . Dış toplam
3. kısımCalculus · fonksiyon, limit, süreklilik, türev
Konu 18 · Calculus temeli

Fonksiyonlar: tanım kümesi, simetri, trigonometrik değerler

Domain & range · Even/odd functions · Increasing/decreasing · Trig values

kısacaFonksiyon bir makine: her 'e tek bir çıktı verir. Tanım kümesi (domain) makineye atabileceğin 'ler, değer kümesi (range) makineden çıkabilen değerler.

Tanım kümesini bulmak: 3 yasak

  • Kök içi negatif olamaz: için , yani
  • Payda sıfır olamaz: için
  • Logaritmanın içi pozitif olmalı: için

İki fonksiyonu birleştirince: , için iki tanım kümesinin kesişimi alınır. için ayrıca olan noktalar çıkarılır.

Ex, . 'nin tanım ve değer kümeleri?

  1. : , yani . Kök 0'dan başlayıp büyür: değer kümesi .
  2. : , yani . Değer kümesi .
  3. : kesişim . 'de değer , sonra artar: değer kümesi .
  4. , tanım kümesi yine , değer kümesi .
Tuzak

formülüne tek başına bakarsan de çalışıyor gibi görünür. Ama orada tanımsız olduğu için de tanımsızdır. Tanım kümesini sadeleştirmeden önce bul.

Simetri: çift ve tek fonksiyonlar

TürKuralGrafikÖrnek
Çift (even)-eksenine göre simetrik
Tek (odd)Orijine göre simetrik

Test etmek için yerine yaz ve sadeleştir. İkisi de değilse (örneğin , çünkü negatif 'te tanımsız) "simetri yok" dersin.

Trigonometrik değerler: birim çember

açı
sin
cos

sin satırı: √0/2, √1/2, √2/2, √3/2, √4/2. cos aynısının tersi

Diğer açılar için 3 adım: (1) açının hangi bölgede olduğunu bul, (2) -eksenine olan dar açıyı (referans açı) bul, (3) işareti bölgeye göre koy. 1. bölgede hepsi +, 2.'de sadece sin +, 3.'de sadece tan +, 4.'de sadece cos +.

, , , . Paydası 0 olan değer tanımsızdır.

Ex ve

  1. saat yönünde 120°, 3. bölgede. Referans açı . 3. bölgede sin negatif:
  2. = 150°, 2. bölgede, referans . tan 2. bölgede negatif:
domain / range tanım / değer kümesieven / odd çift / tekincreasing / decreasing artan / azalanundefined tanımsız
sen dene

kaçtır? (kesir olarak yazabilirsin, örn. -1/2)

Çözüm
210°, 3. bölge, referans , sin negatif:
sen dene

kaçtır?

Çözüm
300°, 4. bölge, referans , cos pozitif:
sen dene

'nin tanım ve değer kümesi nedir? çift mi, tek mi?

Çözüm
. Tanım kümesi , değer kümesi (en büyük değer 'da 2). : çift.
Konu 19 · Calculus

Limit: önce yerine koy, 0/0 çıkarsa teknik kullan

Limits · Indeterminate forms · One-sided limits (Adams 1.2)

kısaca şunu sorar: , 'ya çok çok yaklaşırken neye yaklaşıyor? 'nın kendisi önemli değil, hatta tanımsız bile olabilir.

Her limit sorusunda ilk adım

  1. Yerine koy. Bir sayı çıkarsa cevap o.
  2. çıkarsa belirsizlik var, aşağıdaki tekniklerden birini uygula, sonra tekrar yerine koy.
  3. çıkarsa limit sonlu değil. Sağdan ve soldan işarete bak: , ya da "yok".

4 teknik

T1Çarpanlara ayır, sadeleştir:

T2Kök varsa eşlenikle çarp:

Pay ve paydayı ile çarp. Pay olur:

T3Kesirler varsa payda eşitle:

. Yerine koy: . Sağdan , soldan : limit yok

T4Mutlak değer farkı:

Eşlenikle çarp ( olduğu için mutlak değer kalkar). Pay olur:

Tek taraflı limit

: soldan (a'dan küçük değerlerle) yaklaş. : sağdan yaklaş.

Ex neden yok?

Sağda , oran 1. Solda , oran . Tek taraflı limitler farklı olduğu için limit yok. Aynı mantıkla , .

Ex (), (). ve 'te limitler?

  1. : sol parça . : sağ parça . Farklılar, yok.
  2. sadece sağ parçada: iki taraftan da . var.
evaluate the limit limiti hesapladoes not exist yokone-sided tek taraflıindeterminate belirsiz
sen dene

Çözüm
Belirsizlik yok, yerine koy:
sen dene

Çözüm
Polinom, yerine koy:
sen dene

İpucu
0/0 çıkıyor. İkisinde de çarpanı var.
Çözüm
sen dene

İpucu
Eşlenikle çarp: .
Çözüm
Pay .
Konu 20 · Calculus

Trigonometrik limitler

The special limit

kısacaBütün trigonometrik limitler tek bir gerçeğe dayanır: çok küçük açılarda . Hile, ifadeyi bu kalıba benzetmek.
Kalıbın şartı: sinüsün içindeki ifade ile paydadaki ifade aynı olmalı.

İçerik eşleştirme: 'te içerik , payda . Paydayı yapmak için 2 ile çarpıp böl: . Genel kural: .

Ex

2

Ex

  1. Hepsini sin ve cos ile yaz:
  2. kullan:
  3. 3

Ex

'i ortak paranteze al: 2

Tuzak

sadece iken doğru. iken olur, çünkü pay ile arasında sıkışık kalırken payda büyür.

sen dene

Çözüm
sen dene

Çözüm
sen dene · zor

İpucu
ile çarp. .
Çözüm
Konu 21 · Calculus

Sonsuzda limit ve sonsuz limit

Limits at infinity · Infinite limits (Adams 1.3)

kısaca iken en hızlı büyüyen terim kazanır. Pay ve paydayı, paydadaki en büyük kuvvete böl. Küçük terimler 0'a gider.

Rasyonel fonksiyonlarda derece kuralı

Durum limitiÖrnek
pay derecesi < payda derecesi
dereceler eşitbaş katsayıların oranı
pay derecesi > payda derecesi ya da

Ex

  1. Kökün içinden çıkar:
  2. iken . Pay ve paydadaki 'ler sadeleşir:
En büyük tuzak

, yani iken . Örnek: . Burada olduğundan limit olur, değil.

Sınırlı terimler

ve her zaman ile arasında. gibi büyüyen bir şeye bölününce 0'a giderler:

belirsizliği

Ex

Payda eşitle: . Dereceler eşit: .

Ex

  1. Eşlenikle çarp:
  2. Paydadan çıkar: 2

Sonsuz limit: sayı/0

Payda 0'a giderken pay sıfır olmayan bir sayıya gidiyorsa sonuç olur. İşareti bulmak için 'ya çok yakın bir sayı dene:

  • : için payda , sonuç
  • : pay , payda küçük pozitif, sonuç
sen dene

Çözüm
Dereceler eşit, baş katsayılar:
sen dene

Çözüm
Eşlenik:
sen dene · tuzaklı

Çözüm
ve iken :
Konu 22 · Calculus

Süreklilik

Continuity · Continuous extension · Intermediate Value Theorem (Adams 1.4)

kısacaBir fonksiyon 'da sürekliyse grafiğini o noktada kalemi kaldırmadan çizebilirsin.
üYani (1) tanımlı, (2) limit var, (3) ikisi eşit.

Sol / sağ süreklilik: Sadece soldan limit 'ya eşitse "soldan sürekli", sadece sağdan eşitse "sağdan sürekli" denir.

Hazır bilgi: Polinomlar, , , her yerde süreklidir. Rasyonel fonksiyonlar paydanın sıfır olmadığı her yerde süreklidir. Sürekli fonksiyonların toplamı, çarpımı ve bileşkesi de süreklidir.

Ex (), (). Nerede sürekli?

Parçaların kendisi sürekli. Sadece 'e bak. Soldan limit , sağdan limit , . Sağdan sürekli ama soldan değil. Cevap: dışında her yerde sürekli, 'de sadece sağdan sürekli.

Sürekli genişleme: deliği kapatmak

Ex, 'de nasıl tanımlanmalı ki sürekli olsun?

. Sadeleşince olur. 'de limit . Fonksiyonu orada olarak tanımla.

Parametre bulma

Ex (), (). Her yerde sürekli olması için ?

Sınırda iki parça buluşmalı:

Ara Değer Teoremi

, 'de sürekliyse ile arasındaki her değeri alır. En çok kullanılan hâli: işaret değişiyorsa arada bir kök var.

Ex denkleminin 'te üç çözümü olduğunu gösterin.

polinom, yani sürekli. , , , . İşaret 3 kez değişiyor: , ve aralıklarının her birinde bir kök var. ∎

sen dene

(), (). Sürekli olması için kaç olmalı?

Çözüm
sen dene

, 'te hangi değerle tanımlanırsa sürekli olur?

Çözüm
Konu 23 · Calculus

Türevin tanımı ve teğet doğrusu

Tangent lines · Derivative from the definition · Differentiability (Adams 2.1–2.2)

kısacaTürev = grafiğe o noktada değen doğrunun eğimi. Yakındaki iki noktadan geçen doğrunun eğimini al, iki noktayı birbirine yaklaştır.
ğğNormal, teğete dik doğru. Dik doğruların eğimleri çarpımı .

Ex eğrisine 'de teğet doğru?

  1. . Nokta .
  3. Teğet: , yani

Ex eğrisinin 'e dik olan teğetleri hangi noktalarda?

  1. Tanımdan:
  2. 'ün eğimi 4. Dik doğrunun eğimi olmalı:
  3. Noktalar: ve

Ex'in teğetinin -eksenine paralel olduğu noktalar?

Tanımdan eğim . Paralel = eğim 0: . Noktalar ve .

Türev ne zaman yoktur?

  • Köşe noktalarında (grafik sivri döndüğünde): fonksiyonu 0'da süreklidir ama türevi yoktur, çünkü soldan eğim , sağdan .
  • Süreksizlik noktalarında. Türevlenebilir ⇒ sürekli, ama tersi doğru değil.

Ex 0'da nasıl tanımlanmalı ki sürekli olsun? Türevlenebilir olur mu?

: 'da , 'da . dersen hem sürekli hem türevlenebilir olur (iki taraftan da eğim 0).

sen dene

Tanımı kullanarak için 'ü bul.

Çözüm
sen dene

eğrisinin 'teki teğetinin eğimi kaçtır? (tanımla)

Çözüm
, eşlenikle
Konu 24 · Calculus

Türev kuralları

Power, product and quotient rules (Adams 2.3)

kısacaHer seferinde limitle uğraşmamak için kurallar var. Önce ifadeyi üslü sayılarla yaz, sonra kuralı uygula.
KuralFormül
Kuvvet (her reel için)
Sabit, toplam
Çarpım
Bölüm

bölüm kuralı ezber: "alttaki çarpı üstün türevi, eksi üstteki çarpı altın türevi, bölü alt kare"

ExÖnce sadeleştir:

. Kuvvet kuralı: .

Ex, ise 'de?

  1. Bölüm kuralı:
  2. koy:

Ex 'da?

Çarpım kuralı 4 çarpana genişler: her seferinde bir çarpanın türevini alıp diğerlerini aynen bırak, hepsini topla. 'da diğer çarpanlar 1 olduğundan sonuç türevlerin toplamı: 10

Ex'e 'de teğet ve normal?

  1. . 'de , .
  2. Teğet: . Normal (eğim ): .

Ex eğrisine teğet olan yatay doğrular?

. Bu noktalarda ve . İki yatay doğru: ve .

sen dene

için ?

Çözüm
,
sen dene

'de kaçtır?

Çözüm
, 'de
sen dene

için ?

Çözüm
, . .
Konu 25 · Calculus

Zincir kuralı ve trigonometrik türevler

The chain rule · Derivatives of trigonometric functions (Adams 2.4–2.5)

kısacaİç içe fonksiyonlarda dıştan içe doğru türev al ve çarp. Dıştakinin türevini al, içini aynen bırak, sonra içtekinin türevi ile çarp.
Örnek:
FonksiyonTürev

"co" ile başlayanların (cos, cot, csc) türevleri eksi işaretli

ExZincirle:

Exİki katlı zincir: ve

Ex

  1. Bölüm kuralı:
  2. Pay: . Sonuç:

Ex, , normalinin 'e paralel olduğu noktalar?

  1. Normal eğimi , yani teğet eğimi 8 olmalı.
  2. , aralıkta , yani
  3. Noktalar: ve

Ex'in türevinin ile arasında bir yerde sıfır olduğunu gösterin.

. Köşeli parantez sıfır olunca . Bu, ile 'nin ağırlıklı ortalaması olduğu için ikisinin arasındadır. ∎

tan ve cot'un yatay teğeti yok: ve , hiçbiri 0 olmaz.

sen dene

'da kaçtır?

Çözüm
, 'da 3
sen dene

'de kaçtır?

Çözüm
. :
sen dene

'te kaçtır?

Çözüm
sen dene

'te kaçtır?

Çözüm
. :
Konu 26 · Prova

Calculus alıştırma kâğıdı: tam çözümlü

Exercises sheet with full solutions

Elindeki 9 soruluk kâğıdın tamamı. Kâğıtta çözüm yoktu, hepsini burada çözdüm. Önce kendin dene, sonra çözüme bak.

1

Graph the functions. What symmetries, if any, do the graphs have? Specify the intervals over which the function is increasing and decreasing. (a) (b) (c) (d)

Çözüm
  • (a) Tek fonksiyon, orijine göre simetrik. 'da ve 'da ayrı ayrı artan. 0'da tanımsız olduğu için "her yerde artan" denmez.
  • (b) Çift fonksiyon, -eksenine göre simetrik. 'da artan, 'da azalan.
  • (c) Tek fonksiyon, orijine göre simetrik. 'da artan.
  • (d) Tanım kümesi , simetri yok. 'da azalan ( artar, ile çarpınca ters döner).
2

Find the domains and ranges of where , .

Çözüm

: → . : → .

: → . : → . (Konu 18'de ayrıntılı çözüm var.)

3

Find the domains and ranges of where , .

Çözüm
  • : tanım , değer (sabit fonksiyon, tek değer)
  • : tanım , değer (en küçük değer 'da 1)
  • : hiç sıfır olmadığından tanım . En büyük değer 'da 2, büyüdükçe 0'a yaklaşır ama ulaşmaz: değer
  • : tanım , değer
4

Find the function values. (a) (b) (c) (d) (e) (f)

Çözüm
  • (a)   (b) 135°, 2. bölge, cos negatif:
  • (c) : tanımsız
  • (d)   (e) : tanımsız
  • (f) , yani tanımsız
5

Find the limits: (a) (b) (c) (d) (e) (f) (g)

Çözüm

(a)   (b)   (c)   (d) (Konu 19'deki "sen dene"lerde adım adım var)

(e) Kökün içi 'a gider, sağdan yaklaştığımız için içi pozitif kalır:

(f) iken , oran .   (g) iken , oran .

6

Explain why the limit does not exist: (a) (b)

Çözüm

(a) Sağdan limit 1, soldan limit . Tek taraflı limitler eşit değil.

(b) Sağdan , soldan . Sonlu bir sayıya yaklaşmıyor ve iki taraf da farklı.

7

Let for and for . (a) Find and . (b) Does exist? (c) Find and . (d) Does exist?

Çözüm

(a) : . : . (b) Yok, çünkü .

(c) İkisi de . (d) Var, .

8

Find the limits (use ): (a) (b) (c)

Çözüm

(a)   (b)   (c) . Üçünün de adım adım çözümü Konu 20'da.

9

At what points are the functions continuous? (a) (b) (c) (d) for ,

Çözüm
  • (a) Payda 'de sıfır: olan her yerde sürekli.
  • (b) İki sürekli fonksiyonun toplamı: her yerde sürekli.
  • (c) , olduğu yerlerde tanımsız: ( tam sayı) dışında sürekli.
  • (d) için . limiti 5 ve : her yerde sürekli.
Sınav öncesi son bakış

Formül kartı

Cheat sheet

DurumFormülAkılda kalsın
n farklı şeyi dizmekn, n−1, …, 1 kutucuk
n'den r'sini sıralı seçmekBaşkan, yardımcı, sekreter
n'den r'sini sırasız seçmekEkip, komite
Yuvarlak masaBirini sabitle
Aynı nesneler varMARMARA
Yan yana olsunBlok yap, içini ayrıca dizBantla yapıştır
Yan yana olmasınTümü − yan yana, ya da boşluk yöntemin kişi → n+1 boşluk
Izgara yoluR/U kelimesi
C veya D'den geçenİki kez sayılanı çıkar
n yıldız, r−1 çubuk
Alt sınır Önce a'yı ver
Üst sınır Tümü − ()Tersini say
Çift / tek / Önce tek–çift kontrolü
Binom teoremiGenel terim → kuvvet eşitle
Pascal Üstteki ikisinin toplamı
Tüm katsayılarAltküme sayısı
Ana anahtar
Sadece çift kTekler birbirini götürür
Ekip + lider
Vandermonde
Hokey sopası Çapraz topla
Bölen sayısıHer asalın kuvvetini seç
2n kişiyi ikiliye ayırEn küçüğe eş seç
Vize konuları
Güvercin yuvasım nesne, r kutu → bir kutuda Kutu sayısı = nesne − 1
Geometrik güvercinŞekli parçalara böl, köşegen 10 nokta → 9 parça
Parite sınıflarık koordinat → kutuOrta nokta, tam kare
İçerme–dışlamaİki kez çıkanı geri ekle
Hepsi , toplam büyükTers çevir
Oy sayımım = n →
Üreteç fonksiyonu'in katsayısı =
Rekürans sonunda hep bu
Yıldız-çubuk
Sonlu seriÜst sınırlar
Rekürans → topla → → basit kesir'i çıkarmayı unutma
Tekrarlı kombinasyonn çeşitten r tane, tekrar serbest
Farklı toplar, r kutuHer top kutusunu seçer
Calculus
Tanım kümesikök içi , payda f+g, fg: kesişim
Çift / tek / y-ekseni / orijin simetrisi
Limit, 0/0çarpanlara ayır · eşlenik · payda eşitleÖnce yerine koy
Limit var mı?Tek taraflılar eşit olmalı
Trigonometrik limit
Sonsuzda limiten büyük kuvvete böl, 'da
SüreklilikParçalı: sınırda eşitle
Ara Değer Teoremiişaret değişiyorsa kök varSürekli olmalı
Türev tanımıTeğetin eğimi
Teğet / normalNormal eğimi
Kuvvet kuralıÖnce üslü yaz
Çarpım / bölüm / Alt kare
Zincir kuralıDıştan içe
Trig türevleri, , "co"lar eksi