Интересная задача о треугольника Паскаля: значения кратные p

[Whitaker]

Добый вечер!
Попалась мне такая интересная задачка. Хотелось бы с Вами ее обсудить и разобрать.
Сколько не делящихся на простое число $p$ чисел стоит в первых $m$ строках треугольника Паскаля?

К сожалению я пока не знаю как ее решать, но недавно я читал статью Э. Б. Винберга "Удивительные арифметические свойства биномиальных коэффициентов", где доказывается теорема Люка.
Теорема Люка: Пусть числа $n$ и $k$ имеют следующие $p$-ичное представление:
$n=n_dp^d+n_{d-1}p^{d-1}+...+n_1p+n_0$
$k=k_dp^d+k_{d-1}p^{d-1}+...+k_1p+k_0$
(число цифр в $p$-ичной записи чисел $n$ и $k$, конечно, не обязано быть одинаковым, но мы можем для удобства сделать его формально одинаковым, приписав спереди к одному из чисел несколько нулей)
где $0\leq n_i,k_i<p$, где $i=0,1,..,d.$, тогда
$C_{n}^{k} \equiv C_{n_d}^{k_d}C_{n_{d-1}}^{k_{d-1}}...C_{n_1}^{k_1}C_{n_0}^{k_0} \pmod{p}$
Следствие: $C_{n}^{k}$ не делится на $p$ тогда и только тогда, когда $k_i \leq n_i$ при всех $i=0,1,...,d.$
P.S. Доказательство теоремы и само следствие я понял, но что-то аккуратно и правильно применить к задаче пока не могу.
Пожалуйста поделитесь идеями и соображениями.

С уважением, Whitaker.

-- Пн окт 03, 2011 18:59:33 --

Я думаю, что теорема Люка и его следствие к данной задаче неприменимы.
Мне кажется, что здесь нужно наоборот искать числа, которые делятся на простое число $p$.

[Null]

Я бы стал делать так:
1. Сколько чисел не кратных $p$ лежит в $\overline{k_d \dots k_0}_{(p)}$ строчке.
2. Сколько их в строчках 0..N Где N=
a) $p-1$
б) $p^k-1$
в) $p^k$
г) $a p^k$ где a цифра.
д) для любого N=$\overline{k_d \dots k_0}_{(p)}$

[Whitaker]

Наверное можно и решить вашим способом Null.
Но мне кажется есть более легкий метод. Нужно всего лишь определить количество элементов, делящиеся на простое число $p$.

-- Вт окт 04, 2011 07:50:41 --

Можете помочь с такой подзадачей:
Как определит при каких $n$ и $k$ биномиальный коэффициент $C_{n}^{k}$ делится на простое число $p$.
Очевидно, что $p\leq n$.
Но может быть есть еще что-то?

[Null]

Ну при сложении $k$ и $n-k$ в $p$ичной системе исчисления происходит переход через разряд.

[Sonic86]

Whitaker в сообщении #489296 писал(а):

$C_{n}^{k}$ делится на простое число $p$.

$v_p(x):=a \Leftrightarrow p^a||x$, $s_p(n)$ - сумма цифр $n$ в $p$-ичной системе счисления.
$v_p (n!) = \sum\limits_{r \geqslant 1} \left[ \frac{n}{p^r}\right] = \frac{n-s_p(n)}{p-1} \Rightarrow$
$v_p (C_n^k) = \sum\limits_{r \geqslant 1} \left[ \frac{n}{p^r}\right] - \left[ \frac{k}{p^r}\right] - \left[ \frac{n-k}{p^r}\right] = \sum\limits_{r \geqslant 1} \frac{s_p(k)+s_p(n-k)-s_p(n)}{p^r}$
$p \not | C_n^k \Leftrightarrow v_p(C_n^k)=0$
Можете попробовать с этим повозиться. Но зачем? Вы же фрактальный треугольник биномиальных коэффициентов по модулю видели? Почему бы не сделать через него так, как описал Null, тем более, что есть Excel, взяв $p=3;5$ можем в нем все увидеть - чисто геометрически.

[Whitaker]

Вы имеет ввиду по модулю $p$?
Извиняюсь, но я Вас не так уж понял что Вы имеет ввиду.

[Sonic86]

Whitaker в сообщении #489302 писал(а):

Извиняюсь, но я Вас не так уж понял что Вы имеет ввиду.

Имеется ввиду теорема (вроде бы Куммера) о том, что $v_p(C_n^k)$ равно числу переносов при сложении столбиком чисел $k,n-k$ в $p$-ичной системе счисления.

Чем Вам фрактальный треугольник не понравился?

[Whitaker]

Значит для решения задачи нужно знать теорему Куммера да?
Или еще есть всё-таки другой способ?
Что за фрактальный треугольник?
P.S. Эта задачка из книжки Виленкина

[Sonic86]

Whitaker в сообщении #489305 писал(а):

Что за фрактальный треугольник?

Разве в статье Винберга его нет? Просто треугольник Паскаля по модулю $p$. В Excele нарисуйте.

[Whitaker]

В статье Винберга есть теорема Куммера и треугольник по модулю 2, а по простому модулю нет его. Мне стыдно, но как рисовать в Excele я не знаю. Не подскажите?

[Sonic86]

Whitaker в сообщении #489308 писал(а):

В статье Винберга есть теорема Куммера и треугольник по модулю 2, а по простому модулю нет его. Мне стыдно, но как рисовать в Excele я не знаю. Не подскажите?

Ну вот же он, выше. На картинке даже формула видна.
Ну или фиг с ним с Exceleм - вон картинка, уже достаточно для анализа

[Whitaker]

У вас по модулю 3 да?

[Sonic86]

Whitaker в сообщении #489310 писал(а):

У вас по модулю 3 да?

Ага

[Whitaker]

Null скажите пожалуйста, а $\overline{k_d \dots k_0}_{(p)}$ что у Вас означает?

-- Вт окт 04, 2011 09:20:15 --

Sonic86 в сообщении #489303 писал(а):

Whitaker в сообщении #489302 писал(а):

Извиняюсь, но я Вас не так уж понял что Вы имеет ввиду.

Имеется ввиду теорема (вроде бы Куммера) о том, что $v_p(C_n^k)$ равно числу переносов при сложении столбиком чисел $k,n-k$ в $p$-ичной системе счисления.

Чем Вам фрактальный треугольник не понравился?

Что значит числу переносов при сложении стобликом в p-ичной системе?

-- Вт окт 04, 2011 09:30:44 --

Это же коэффициенты разложения числа k в $p$-ичной системе.

-- Вт окт 04, 2011 09:32:59 --

Null
А почему вы предлагаете считать количество чисел не кратных $p$ в k-й строчке?

[Null]

$\overline{k_d \dots k_0}_{(p)}=k_dp^d+k_{d-1}p^{d-1}+...+k_1p+k_0$

Количество чисел не кратных $p$ в первых $m$ строчках равно сумме их количеств по строчкам $0..m-1$