Треугольник Паскаля: сколько нечетных чисел в строке m?

[Joker_vD]

Ну как откуда? Я посчитал количество единичек в строчках: в нулевой строке была одна единица, в первой две, во второй две, в третьей четыре...

[Whitaker]

Да я понял уважаемый Joker_vD!
Извините за глцпый вопрос. Оказывается в статье Винберга очень много интересного по данной теме. В частности, доказывается, что количество нечетных чисел есть степень двойки.
P.S. Большое спасибо за то, что скинули ссылку на статью!

-- Сб сен 24, 2011 09:51:49 --

В данной статье написано следующее:
Пусть $p$-простое число. Займемся вычислением $C_{n}^{k}$ по модулю $p$.
Разделим $n$ и $k$ на p c остатком:
$n=n'p+n_0, k=k'p+k_0, (0 \leq n_0,k_0<p)$
Докажем, что $C_{n}^{k} \equiv C_{n'}^{k'}C_{n_0}^{k_0} \pmod{p}$
Среди имеющихся $n$ предметов выделим $n'$ блоков по $p$ предметов в каждом блоке, оставив $n_0$ предметов вне блоков. Выборку $k$ предметов будем называть блочной, если она состоит из $k'$ целых боков и $k_0$ предметов вне блоков. Число блочных выборок равно $C_{n'}^{k'}C_{n_0}^{k_0}$.
Объясните пожалуйста два момента:
1) Я не совсем понял что означает блочная выборка. Хотя здесь написано, но непонятно мне.
2) И почему ее число равно $C_{n'}^{k'}C_{n_0}^{k_0}$
Больше всего интересует первый вопрос.

-- Сб сен 24, 2011 09:58:46 --

Поэтому нам достаточно доказать, что число остальных выборок делится на $p$.
Что здесь имеется в виду под словом остальные выборки?

[Whitaker]

Еще непонятно почему при $0<l<p$ $C_{p}^{l}$ делится на $p$. Вроде бы легко, но не получается никак.

[nnosipov]

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

Еще непонятно почему при $0<l<p$ $C_{p}^{l}$ делится на $p$. Вроде бы легко, но не получается никак.

Вот это-то точно легко. Напишите формулу для $C_p^l$ через факториалы и посмотрите на неё. Что Вы видите в числителе?

[Whitaker]

$C_p^l=\dfrac{p!}{l!(p-l)!}=\dfrac{p \cdot (p-1) \cdot ...\cdot (p-l+1)}{1 \cdot 2 \cdot ....\cdot l}$
П.С. число $p$ - простое.

[Whitaker]

Я сделал так: $C_p^l=\dfrac{C_{p-1}^{l}}{p-l}\cdot p$.
Но будет ли целым числом выражение $\dfrac{C_{p-1}^{l}}{p-l}$?

-- Сб сен 24, 2011 14:03:02 --

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

В данной статье написано следующее:
Пусть $p$-простое число. Займемся вычислением $C_{n}^{k}$ по модулю $p$.
Разделим $n$ и $k$ на p c остатком:
$n=n'p+n_0, k=k'p+k_0, (0 \leq n_0,k_0<p)$
Докажем, что $C_{n}^{k} \equiv C_{n'}^{k'}C_{n_0}^{k_0} \pmod{p}$
Среди имеющихся $n$ предметов выделим $n'$ блоков по $p$ предметов в каждом блоке, оставив $n_0$ предметов вне блоков. Выборку $k$ предметов будем называть блочной, если она состоит из $k'$ целых боков и $k_0$ предметов вне блоков. Число блочных выборок равно $C_{n'}^{k'}C_{n_0}^{k_0}$.
Объясните пожалуйста два момента:
1) Я не совсем понял что означает блочная выборка. Хотя здесь написано, но непонятно мне.
2) И почему ее число равно $C_{n'}^{k'}C_{n_0}^{k_0}$
Больше всего интересует первый вопрос.

-- Сб сен 24, 2011 09:58:46 --

Поэтому нам достаточно доказать, что число остальных выборок делится на $p$.
Что здесь имеется в виду под словом остальные выборки?

[nnosipov]

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

Но будет ли целым числом выражение $\dfrac{C_{p-1}^{l}}{p-l}$?

Будет, но не в этом дело. Лучше проанализируйте равенство $l!C_p^l=p(p-1)\ldots(p-l+1)$. Его правая часть делится на $p$. Значит, ...

[Whitaker]

Уважаемый nnosipov я уже понял. Оказывается там очень легко.

[nnosipov]

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

там очень легко

Очень рад, что наши мнения совпали

[Whitaker]

nnosipov в сообщении #485990 писал(а):

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

там очень легко

Очень рад, что наши мнения совпали

Я тоже

[yk2ru]

Есть такое свойство Треугольника Паскаля: Сумма чисел n-й строки Треугольника Паскаля равна $2^n$.
Я заметил такое свойство: если от центрального числа в строке (если их два, берём любой из них) сначала вычесть числа, находящихся через один от него, затем прибавить к сумме чиcла, находящихся через один от последних и так продолжить до начала\конца строки , то также получим степень двойки.

Примеры:
Берём например такую строку $1, 5, 10, 10, 5, 1$, получаем $-1 + 10 - 5 = 2^2$.
Для строки $1, 6, 15, 20, 15, 6, 1$, получаем $-6 + 20 - 6 = 2^3$.
Для строки $1, 8, 28, 56, 70, 56, 28, 8, 1$, получаем $1 - 28 + 70 - 28 + 1 = 2^4$.

Знаете ли вы о таком свойстве? Как лучше записать это в виде единой формулы?

[ИСН]

$|(1+i)^{2n}|=2^n$

-- Вс, 2011-10-16, 17:15 --

ну или там отдельно - Re, Im...

[yk2ru]

ИСН в сообщении #493127 писал(а):

$|(1+i)^{2n}|=2^n$

-- Вс, 2011-10-16, 17:15 --

ну или там отдельно - Re, Im...

Формула таким образом получается только для чётных строк Треугольника Паскаля. В примерах была и нечётная строка. Там уже нужно брать или Re или Im от результата, вроде одинаковые по модулю они получаются.

[yk2ru]

Формулу можно записать так:
${n\choose m}-{n\choose {m-2}}-{n\choose {m+2}}+{n\choose {m-4}}+{n\choose {m+4}}-{n\choose {m-6}}-{n\choose {m+6}}+\ldots=2^m$, где $m = [n/2]$ и соответственно все числа вида $m-k$ и $m+k$ не меньше нуля и не больше $n$.
Для нечётных строк также верно:
${n\choose m}-{n\choose {m-2}}-{n\choose {m+2}}+{n\choose {m-4}}+{n\choose {m+4}}-{n\choose {m-6}}-{n\choose {m+6}}+\ldots=2^{m-1}$, где $m = [n/2]+1$

А если все минусы в левой части формул заменить на плюсы, то также получаем степень двойки.
Не так ли? И связано ли это тут с комплексными числами?

-- Вс окт 16, 2011 21:43:40 --

То есть верна также формула:
${n\choose m}+{n\choose {m-2}}+{n\choose {m+2}}+{n\choose {m-4}}+{n\choose {m+4}}+{n\choose {m-6}}+{n\choose {m+6}}+\ldots=2^{n-1}$, где $n>0$ и $m = [n/2]$ или $m = [n/2]+1$

[yk2ru]

О делении определённых разностей на степени простых чисел:
http://kvant.mccme.ru/1970/06/arifmetik ... oeffic.htm
Страницы 23 - 25.