Wskaż bijekcje

Teoria liczb, teoria grafów, indukcja
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij Thank icon

Wskaż bijekcje

Postprzez zwolo1711 » 12 Sie 2017, 18:13

Witam serdecznie,
Mam problem z tym zadaniem:

Niech [math]. Wskazać bijekcję między A i B, B i C oraz A i C:

A - zbiór całkowitoliczbowych rozwiązań równania [math] takich że [math] dla każdego [math];
B - zbiór ciągów binarnych złożonych z n-1 jedynek i k - n zer;
C - zbiór ciągów binarnych złożonych z n-1 zer i k - n jedynek;
zwolo1711
Witam na forum
Witam na forum
 
Posty: 4
Dołączenie: 12 Sie 2017, 18:08
Płeć: On
Otrzymane podziękowania: 0

Postprzez kerajs » 13 Sie 2017, 14:21

Ponieważ zapis słowny pewnie będzie wymagał objaśnień to od razu podam przykład:
n=3,k=5
A : rozwiązania równania:
1,1,3
1,2,2
1,3,1
2,1,2
2,2,1
3,1,1
C: ciągi zawierają 3-1=2 zer i 5-3=2 jedynek
ilość wszystkich ciągów to:
[math]
0011
0101
0110
1001
1010
1100

Transformacja C w A:
każde zero zastępujemy przecinkiem;
0011 → ,,11
0101 → ,1,1
0110 → ,11,
jeśli występują serie jedynek to wpisuję ich sumę
0011 → ,,11 → ,,2
0101 → ,1,1 → ,1,1
0110 → ,11, → ,2,
do każdego z n (tu trzech) miejsc odseparowanych przecinkiem dodaję 1. Jeśli miejsce było puste to wpisuję tam wcześniej zero
0011 → ,,11 → ,,2 → 0,0,2 → 1,1,3
0101 → ,1,1 → ,1,1 → 0,1,1 → 1,2,2
0110 → ,11, → ,2, → 0,2,0 → 1,3,1
Transformacja A w C:
1,1,3 → 0,0,2 → ,,11 → 0011
1,2,2 → 0,1,1 → ,1,1 → 0101
1,3,1 → 0,2,0 → ,11, → 0110
Powyższy przepis jest jednoznaczny i jest on szukaną bijekcją miedzy A i C

np:
3,2,1,4,1,2 → 2,1,0,3,0,1 → 11,1,,111,,1 → 201003001
201003001 → 11,1,,111,,1 → 2,1,0,3,0,1 → 3,2,1,4,1,2

Bijekcją między A i B jest podobny przepis, a bijekcja między B i C to zamiana zer w jedyni, a jedynek w zera.
kerajs
Expert
Expert
 
Posty: 455
Dołączenie: 14 Lis 2016, 15:38
Płeć: On
Otrzymane podziękowania: 191

Re: Wskaż bijekcje

Postprzez zwolo1711 » 13 Sie 2017, 15:22

Cześć,

Dzięki wielkie za odpowiedź mam tylko jedno pytanie, czy bijekcja między A i B to nie jest to samo ?
Ponieważ jest n-1 jedynek czyli 3-1=2 jedynek i k-n zer czyli 5-3=2 zer
tak samo było w A i C ?

i jeżeli chodzi o bijekcję między B i C to rozumiem że wystarczy tylko taki zapis i wszystko ?

0011 1100
0101 1010
0110 -> 1001
1001 0110
1010 0101
1100 0011
zwolo1711
Witam na forum
Witam na forum
 
Posty: 4
Dołączenie: 12 Sie 2017, 18:08
Płeć: On
Otrzymane podziękowania: 0

Postprzez kerajs » 13 Sie 2017, 16:42

Warto dodać że liczność zbiorów A,C (i B) jest taka sama:
Liczbę k traktuję jak k koralików. Między nimi jest k-1 przerw. Ilość rozwiązań równania dla n niewiadomych w liczbach naturalnych dodatnich to wybór n-1 przerw z k-1 możliwych:
[math]
czyli tyle co możliwych ciągów zerojedynkowych ze zbioru C (i także B)

Każdą przerwę traktuję jak zero, a ilość koralików między przerwami to ilość jedynek. Do ciągu wpisuję o jedną jedynkę mniej niż ich jest w ciągu, a gdy była tylko jedna jedynka to nic nie wpisuję między zerami (przerwami). To bardziej esencjonalny opis powyższej bijekcji z przykładu.

Tak, bijekcja A i B to niemal to samo:
Każdą przerwę traktuję jak jedynkę, a ilość koralików między przerwami to ilość kolejnych zer. Do ciągu wpisuję o jedno zero mniej niż ich jest w ciągu, a gdy było tylko jedno zero to nic nie wpisuję między jedynkami (przerwami).

Zapis bywa problematyczny przy niektórych prowadzących. Wtedy forma zapisu jest układana pod jego wymagania. Zwykle wystarczy pokazanie odwzorowania lub słowny jego opis.
kerajs
Expert
Expert
 
Posty: 455
Dołączenie: 14 Lis 2016, 15:38
Płeć: On
Otrzymane podziękowania: 191


Powróć do Pomocy! - matematyka dyskretna



Kto jest na forum

Użytkownicy przeglądający to forum: CommonCrawl [Bot] oraz 0 gości