И опять задачка

← →
default © (2004-06-16 15:38) [0]

Если образовывать наборы по k чисел (a1,a2,...,ak) из
множества чисел (1,2,3,...,n), разрешая числам ai повторяться,
то таких наборов будет n^k. Для каждого такого набора отметим
наименьшее из ai. Докажите неожиданный результат, что сумма
наименьших ai во всех наборах равняетс просто
1^k+2^k+3^k+...+n^k-сумме k-х степеней первых n натуральных
чисел, т.е. n
____ ____
\min(a1,a2,...,ak)=\m^k
/___ /___
m=1

← →
Sha © (2004-06-16 16:46) [1]

Обозначим x(i) - количество наборов, в которых i=1..n является минимальным числом, тогда:
x(n) = 1^k
x(n-1) = 2^k - 1^k
x(n-2) = 3^k - 2^k
...........................
x(2) = (n-1)^k - (n-2)^k
x(1) = n^k - (n-1)^k

И, значит, искомая сумма
s = 1*x(1) + 2*x(2) + 3*x(3) + ... + n*x(n)
= n^k + (n-1)^k + ... + 2^k + 1^k

← →
default © (2004-06-16 16:56) [2]

x как получено не доказано

← →
Sha © (2004-06-16 17:19) [3]

default © (16.06.04 16:56) [2]

Ты в каком классе учишься? :)

x(n)=1 - т.к. существует единственный набор, в котором число n минимальное, это набор, в который входят только числа равные n.
Единицу имеем право записать как 1^k.

x(n-1) - эти наборы состоят из чисел >= n-1 (таких чисел 2 штуки: n и n-1), за исключением наборов, целиком состоящих из чисел >= n. По формуле размещений с повторениями первое слагаемое = 2^k, второе 1^k.

Дальше продолжи сам :)

← →
default © (2004-06-16 17:22) [4]

Sha © (16.06.04 17:19) [3]
мда...это же не мне нужно, я сказал чего нет в доказательстве...
можно было тогда вообще ничего не доказывать, и сказать "Ты в каком классе учишься? "бред

← →
Sha © (2004-06-16 17:30) [5]

default © (16.06.04 17:22) [4]

На мой взгляд, то, что ты спросил, в доказательстве присутствует.
Обрати внимание на порядок записи x(i): от n до 1, а не наоборот.
Не обижайся.

← →
default © (2004-06-16 17:32) [6]

Sha © (16.06.04 17:30) [5]
на что обижаться?я по-другому просто к выр-ию x приходил

← →
Sandman25 © (2004-06-16 17:33) [7]

Даже я понял, так что все нормально :)

Как по-другому?

сначала было
[1*n^(k-1)+1*n^(k-2)*(n-1)+1*n^(k-3)*(n-1)^2+...+1*(n-1)^(k-1)]+
[2*(n-1)^(k-1)+2*(n-1)^(k-2)*(n-2)+...+2*(n-2)^(k-1)]+...+n
потом применяя формулу суммы геом-ой прогр-ии получ-ся
"s = 1*x(1) + 2*x(2) + 3*x(3) + ... + n*x(n)"

И опять задачка Найти похожие ветки