Wskaż bijekcje

[zwolo1711]

Witam serdecznie,
Mam problem z tym zadaniem:

Niech \(k \ge n \ge 1\). Wskazać bijekcję między A i B, B i C oraz A i C:

A - zbiór całkowitoliczbowych rozwiązań równania \(x_1 + ... + x_n = k\) takich że \(x_i \ge 1\) dla każdego \(1 \le i \le n\);
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;

[kerajs]

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:
\(\frac{((n-1)+(k-n))!}{(n-1)!(k-n)!}= \frac{4!}{2!2!}=6\)
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.

[zwolo1711]

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

[kerajs]

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:
\({ k-1 \choose n-1}= \frac{(k-1)!}{(n-1)!(k-n)!} =\frac{((n-1)+(k-n))!}{(n-1)!(k-n)!}\)
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.