Kombinatoryka
DM: Witam, mam następujący problem:
wyznaczyć ilość wszystkich możliwych rozwiązań równania:
x1 + x2 + x3 + x4 = 51
gdzie:
każdy z x ∊ N+
oraz
x1 > x2 > x3 > x4
Za pomocą funkcji tworzących udało mi się ograniczyć do 2783 rozwiązań, ale nie uwzględniają
one warunku
x1 > x2 > x3 > x4.
Dodatkowo dla każdego x udało mi się wyznaczyć możliwy przedział wartości:
15 ≥ x1 ≥45
3 ≥ x2 ≥23
2 ≥ x3 ≥ 15
1 ≥ x4 ≥ 11
Pytanie brzmi: jak uwzględnić warunek że kolejne x są rosnące, albo jaki jest inny sposób na to
zadanie?
3 maj 15:34
jc:
x4=y4
x3=x4+y3=y3+y4
x2=x3+y2=y2+y3+y4
x1=x3+y1=y1+y2+y3+y5
y1 + 2y2+3y3+4y4=51, yi ∊ Z+
Teraz prościej?
Funkcja tworząca (1+x+x2+...)(1+x2+x4+...)(1+x3+x6+x9+...)(1+x4+x8+...).
3 maj 15:51
jc: Pomiń jedynki w każdym iloczynie!
3 maj 16:03
jc: 672 ?
3 maj 16:05
DM: Tak odpowiedź to 672,
bardzo dziękuję za odpowiedź
zaraz zabieram się do analizy rozwiązania
3 maj 16:08
DM: dochodzę do momentu:
[y
41] (1−y
4)
−1(1−y
3)
−1(1−y
2)
−1(1−y)
−1
i co teraz?
przecież nie sprawdzę wszystkich kombinacji, kiedy wyrazy się sumują do 41?
dodatkowo:
3 maj 19:25
DM: Podbijam, nie wiem co z tym dalej robić...
4 maj 12:59
jc: Napisałem oczywisty programik.
def f(n,r):
if r==1: return 1
s = 0
k = 1
while n > r*k:
s += f(n−r*k,r−1)
k += 1
return s
print f(51,4)
−−−
Możesz szukać jakiś wzorów rekurencyjnych i liczyć ręcznie. Myślę, że nie jet to trudne.
4 maj 13:10
Pytający:
Zawsze możesz namalować tabelkę.
a
n=1
b
n=a
n+b
n−2
c
n=b
n+c
n−3
d
n=c
n+d
n−4
Tu masz analogiczny przykład z monetami (patrz początek i przykład z tabelką):
http://wazniak.mimuw.edu.pl/index.php?title=Matematyka_dyskretna_1/Wyk%C5%82ad_7:_Funkcje_tworz%C4%85ce
a
0=1, b
0=1, c
0=1, d
0=1
a
1=1, b
1=1, c
1=1, d
1=1
a
2=1, b
2=2, c
2=2, d
2=2
a
3=1, b
3=2, c
3=3, d
3=3
a
4=1, b
4=3, c
4=4, d
4=5
a
5=1, b
5=3, c
5=5, d
5=6
a
6=1, b
6=4, c
6=7, d
6=9
a
7=1, b
7=4, c
7=8, d
7=11
a
8=1, b
8=5, c
8=10, d
8=15
a
9=1, b
9=5, c
9=12, d
9=18
a
10=1, b
10=6, c
10=14, d
10=23
a
11=1, b
11=6, c
11=16, d
11=27
a
12=1, b
12=7, c
12=19, d
12=34
a
13=1, b
13=7, c
13=21, d
13=39
a
14=1, b
14=8, c
14=24, d
14=47
a
15=1, b
15=8, c
15=27, d
15=54
a
16=1, b
16=9, c
16=30, d
16=64
a
17=1, b
17=9, c
17=33, d
17=72
a
18=1, b
18=10, c
18=37, d
18=84
a
19=1, b
19=10, c
19=40, d
19=94
a
20=1, b
20=11, c
20=44, d
20=108
a
21=1, b
21=11, c
21=48, d
21=120
a
22=1, b
22=12, c
22=52, d
22=136
a
23=1, b
23=12, c
23=56, d
23=150
a
24=1, b
24=13, c
24=61, d
24=169
a
25=1, b
25=13, c
25=65, d
25=185
a
26=1, b
26=14, c
26=70, d
26=206
a
27=1, b
27=14, c
27=75, d
27=225
a
28=1, b
28=15, c
28=80, d
28=249
a
29=1, b
29=15, c
29=85, d
29=270
a
30=1, b
30=16, c
30=91, d
30=297
a
31=1, b
31=16, c
31=96, d
31=321
a
32=1, b
32=17, c
32=102, d
32=351
a
33=1, b
33=17, c
33=108, d
33=378
a
34=1, b
34=18, c
34=114, d
34=411
a
35=1, b
35=18, c
35=120, d
35=441
a
36=1, b
36=19, c
36=127, d
36=478
a
37=1, b
37=19, c
37=133, d
37=511
a
38=1, b
38=20, c
38=140, d
38=551
a
39=1, b
39=20, c
39=147, d
39=588
a
40=1, b
40=21, c
40=154, d
40=632
a
41=1, b
41=21, c
41=161,
d41=672
a
42=1, b
42=22, c
42=169, d
42=720
a
43=1, b
43=22, c
43=176, d
43=764
a
44=1, b
44=23, c
44=184, d
44=816
a
45=1, b
45=23, c
45=192, d
45=864
a
46=1, b
46=24, c
46=200, d
46=920
a
47=1, b
47=24, c
47=208, d
47=972
a
48=1, b
48=25, c
48=217, d
48=1033
a
49=1, b
49=25, c
49=225, d
49=1089
a
50=1, b
50=26, c
50=234, d
50=1154
a
51=1, b
51=26, c
51=243, d
51=1215
a
52=1, b
52=27, c
52=252, d
52=1285
a
53=1, b
53=27, c
53=261, d
53=1350
a
54=1, b
54=28, c
54=271, d
54=1425
a
55=1, b
55=28, c
55=280, d
55=1495
a
56=1, b
56=29, c
56=290, d
56=1575
a
57=1, b
57=29, c
57=300, d
57=1650
a
58=1, b
58=30, c
58=310, d
58=1735
a
59=1, b
59=30, c
59=320, d
59=1815
4 maj 15:02
