[алгоритм] определитель и трeугольник пaскаля

Определитель = 1. Метод Гаусса. Причем тут треугольник Паскаля?

Да, обшибся. Не 1.

попробуй вычислить, применяя элементарные преобразования:

Сначала из j+1 столбца вычитаешь j-тый, проходя по j от n-1 до 1.
Там вроде останется матрица из одних единиц, у которой определитель равен 0.

Хотя я могу ошибаться, а расписывать влом :)

действительно не 0 :)

но попробуй преобразовать указанным мной методом, матрица значительно упростится

Определитель будет равен n.

Гоняешь несколько(n-1) раз вычитание столбцов по описанному выше методу, в результате получаешь нижнетреугольную матрицу с диагональю [1,1,...1,n], у которой det=n.

Не обшибся. Таки 1.

И всё же 1 :)

получится матрица с единичной диагональю

что там у нас в talks про второкурсника проскакивало? тут лучше )

нет, всё не то)

я понял как решать, когда сдам отпишу решение.

осталось тока формулу записать и доказать.

всё элементарно, хватило методички за 1 курс, 1 семестр по лин. алегбре. )

> Не обшибся. Таки 1.

Да, таки 1.

Биномиальный коэффициент {n\choose k} - это многочлен от n степени k с главным коэффициентом 1/k!, поэтому определитель данной матрицы - просто определитель Вандермонда для 0,1,2,...,n-1, умноженный на произведение всех 1/k!. Очевидно получается 1.

Если знать такое утверждение из алгебраической комбинаторики, то тоже очень просто. Пусть a_1, a_2, ... a_n, b_1, ..., b_n - целочисленные точки на плоскости и p_ij - количество путей по решетке (идущих, скажем, только вправо или вниз) из точки a_i в точку b_j. Тогда определитель матрицы (p_ij) - это количество наборов таких попарно непересекающихся путей из a_1 в b_1, из a_2 в b_2, ..., a_n в b_n. Если выбрать a_i=(0,i-1), b_i=(i-1,0), то матрица (p_ij) как раз данная. С другой стороны, есть только один набор непересекающихся путей: a_i->(i-1,i-1)->b_i. Поэтому определитель 1.

В общем, учите математику. Быдлокодерство поспеет.

так, решение не отпишу) ибо неправильно)

действительно получается всегда один. надо тока оформить это дело теперича.

а с определителем Вандермонда, не очень то и понял в чем его смысл..

с "утверждением из алгебраической комбинаторики" тоже слегка непонятно)

матрица Вандермонда - (a_i^{j-1})_{i,j = 1}^n

ее определитель = \prod (a_i - a_j)

пусть есть многочлены P_j(x) = c_j x^{j-1} + ...

тогда определитель матрицы (P_j(a_i))_{i,j = 1}^n по методу Гаусса равен опредетителю Вандермонда, умноженному на произведение всех c_j

{n \choose k} - многочлен степени k от n с главным коэффициентом 1/k!

Есть способ проще, на уровне 1-го курса.

это и так на уровне первого курса

хм.. с подобной задаче тоже недавно мучался, только я думал что матрица должна быть вида

|1 1 1 1|
|1 2 3 0|
|1 3 0 0|
|1 0 0 0|

и тогда надо вывести формулу умножения элементов стоящих по диагонали..
впринципе вывел. вот она, авось кому-нит пригодится \prod_{m=1}^n\ n(n-1)(n-2)*...*(n-m+1)/m!

даж работает)

но к сожжалению по заданию слегка не подходит, я так понимаю надо было найти определитель у матрицы вида

|1 1 1  1 |
|1 2 3  4 |
|1 3 6  10|
|1 4 10 20|

ну тут да, можно и использование определителя вондермонда искать, а можно и просто методом гаусса.. без всяких заморочек.

основная формула будет a_(ij) = a_(i-1 j) + a_(i j-1)

I_n = I_(n-1) = ... = I_1 = 1

Апосля некоторых преобразований матрица будет выглядеть примерно так

|1 0 0 0...
|0 1 2 3 ...
|0 ..
|0   ..


>Пусть a_1, a_2, ... a_n, b_1, ..., b_n - целочисленные точки на плоскости и p_ij - количество путей по решетке (идущих, скажем, только вправо или вниз) из точки a_i в точку b_j.

С алгебраической комбинаторикой незнаком, но что-то похожее пытался сделать.. 

представить элементы матрицы как точки на плоскости и между ними провести связи, только не вправо или вниз, а вообще все возможные варианты и потом что-нибудь с сочетаниями сообразить.. в итоге забил, чушь получалась, да и спать ночь хотелось)