permütasyon-2

[bunyamin]

A={0,1,2,3,4,5,6} kümesinin alt kümelerinin kaç tanesin de herhangi iki ardışık tam sayı yoktur?
11   22     33       34     55

[alpercay]

Ağaç diyagram benzeri bir sayma yöntemi ile yanlış saymamışsam 33 bulunuyor.Boş kümeyi de dahil edersek 34 oluyor.

[bunyamin]

bununla ilgili herhangi bir formül varmı arkadaşlar
 

[ali ergin]

a={1,2,3...,n}  olmak üzere   A nın r li kombinasyonlarından ardışık tam sayılar olmayan
C(n-r+1,r}  tane alt  kümesi vardır.

C(7-1+1,1)=7
C(7-2+1,2)=15
C(7-3+1,3)=10
C(7-4+1,4)=1
toplam 33  tane

[Lokman Gökçe]

şöyle de düşünebiliriz...

istenen özellikteki alt kümelerden birisi boş kümedir. C(8,0) = 1 tane var.

bir elemanlı alt kümelere bakalım...bunlardan birisi {3}'tür. bu kümeyi şifresi AAABAAA ile ifade edebiliriz.B lerin yanyana gelmediği mümkün konumlar C(7,1) = 7 tane vardır.

iki elenamlı alt kümelere bakalım...bunlardan birisi {3,6} dır.bu kümeyi AAABAAB ile şifreleyelim. B harfleri yanyana gelmemesi durumu C(6,2) = 15 tane vardır.

üç elemanlı kümelere bakalım...bunlardan birisi {0,4,6} dır. bu kümeyi BAAABAB ile şifreleyelim. B harflerinin yanyana gelmemesi durumu C(5,3) = 10 tanedir.

dört elemanlı kümeleri inceleyelim. bunlardan birisi {0,2,4,6} dır (başka da yok) bunu da BABABAB ile şifreleyelim. B lerin yanyana gelmediği C(4,4) = 1 durum vardır.

sonuç olarak C(8,0) + C(7,1) + C(6,2) + C(5,3) + C(4,4) = 34 tanedir...

tübitak 2002 ilköğretim mat. olimpiyatı klasik sınavında sorulmuştu: A={1,2,3,...,11} kümesinin alt kümelerinin kaç tanesinde herhangi iki ardışık tamsayı yoktur? (yukarıdakine benzer şekilde yapılabilir)