Подсчет количества цифр в записи числа

[Alik]

Это задача из моего диплома и ноги у нее ростут из количества топологий. Поскольку речь идет о реализации устройства живьем, р не может быть большим, иначе резко возрастают потери. Численное решение, которое дает MATLAB - это приемлимый инженерный подход, мне просто хотелось быть чуть строже. А Вам большое спасибо за формулу, если можно чуть подробней каким образом тут появился бином Ньютона. Буду также благодарен за ссылку на литературу

[Gafield]

Ну, если я понял пример правильно, то все просто. Пусть $k$ - количество 1 и -1. Тогда нулей будет $p-k$, их можно расставить на $p$ местах $C^{p-k}_p=C^k_p$ способами. На оставшихся $k$ местах расставляем 1 и -1 $2^k$ способами. Итого $2^kC^k_p$ вариантов.

[Alik]

Судя по вашим обозначениям $k$ - это количество 1 и -1 в одной строке, т.е. в записи одного числа.
Не очень понятно почему при общем количестве позиций $p$ нули можно расставить на каждой, а для 1 и -1 остается только $k$ мест? Хотя число перестановок 1 и -1 получилось $2^k$, Вы его перемножаете на перестановки для нулей. Что означает эта величина, ведь она, очевидно, для одной строки.
Если так, то почему в конечной формуле

$$ \sum_{k=1}^p\left[\frac{2^k C_p^k}{k+1}\right]. $$

Вы суммируете до $p$, а не по всем строкам $3^p$?
Далее после удачной подстановки производящей функции получилось найти нижнюю границу $x$, но ведь есть и верхняя

$$\frac{3^{p+1}-1}{2(p+1)}-1.$$

.
Таким образом сумма округленных значений лежит в этих пределах. Можно ли учесть округление на этапе суммирования и найти точное выражение для числа?

[Gafield]

Если я правильно понял пример, то $x(k)$ - количество чисел, имеющих ровно на $k$ местах 1 и -1. Именно оно и вычисляется: $x(k)=2^k C^k_p$. В частности, при $p=3$, если число содержит одну единицу или минус единицу, то на остальных двух местах стоят нули, имеется $C^1_3=3$ способа их расставить, и для каждого из этих способов можно поставить на оставшееся место либо 1 либо -1 это $2^1$ варианта. Итого $x(1)=2*3=6$ чисел. Аналогично $x(2)=12$, $x(3)=8$. Или под $x(k)$ подразумевалось что-то другое?

Округленное значение будет вести себя иррегулярно, и простой формулы, видимо, нет. Похоже только, что если $p+1$ - простое, то сумма будет равна верхней границе: $\left[\frac{3^{p+1}-1}{2(p+1)}-1 \right]$.

[maxal]

Можно воспользоваться очевидным свойством биномиальных коэффициентов: $\frac{1}{k+1}{p\choose k} = \frac{1}{p+1}{p+1\choose k+1}$.
Она позволит успростить сумму:

$$\sum_{k=1}^p\left\lfloor\frac{2^k}{k+1}{p\choose k}\right\rfloor = \sum_{k=1}^p\left\lfloor\frac{2^k}{p+1}{p+1\choose k+1}\right\rfloor$$

Отсюда, в частности, сразу следует, что если $p+1$ - простое, то частное получается целым для всех $k<p$ и взятие целой части для них можно отбросить, а для $k=p$ из малой теоремы Ферма следует, что $\lfloor 2^p/(p+1)\rfloor = (2^p-1)/(p+1)$ (предполагая, что $p>1$ или $p+1>2$). Или, другими словами, если просто отбросить целую часть у всех слагаемых, то придется еще вычесть $1/(p+1)$, то есть

$$\sum_{k=1}^p\frac{2^k}{p+1}{p+1\choose k+1} - \frac{1}{p+1} = \frac{1}{2(p+1)} \sum_{k=1}^p 2^{k+1} {p+1\choose k+1} - \frac{1}{p+1} = \frac{3^{p+1} - 1 - 2p}{2(p+1)} - \frac{1}{p+1} = \frac{3^{p+1} - 1}{2(p+1)}-1.$$

В общем же случае, нужно смотреть на разложение $p+1$ на простые и оценивать сумму по модулю простых степеней входящих в разложение (теорема Люка и т.п.) Или, возвращаясь к исходному выражению, можно заметить, что $\lfloor m/(k+1)\rfloor \geq (m-k)/(k+1)$ для всех целых $m$, и так как $\sum_{k=1}^p k/(k+1) = p+1 - H_{p+1}$ (гармоническое число), то

$$\frac{3^{p+1} + 1}{2(p+1)}-1 \geq \sum_{k=1}^p\left\lfloor\frac{2^k}{k+1}{p\choose k}\right\rfloor \geq \frac{3^{p+1} + 1}{2(p+1)} + H_{p+1} - p - 2 > \frac{3^{p+1} + 1}{2(p+1)} + \ln(p+1) - p - 2 .$$

Здесь стоит "+" в числителе поскольку для строгости пришлось вернуть ранее вычтенное $1/(p+1)$.

[Alik]

Формула

$$\frac{1}{k+1}{p\choose k} = \frac{1}{p+1}{p+1\choose k+1}$$

очевидно взята из "Concrete mathematics". Я, правда, не понял
1) почему из

$$\lfloor\frac{2^k}{p+1}{p+1\choose k+1}\rfloor$$

сразу следует, что если $p+1$ - простое, то частное получается целым для всех $k<p$
2) зачем рассматривать частный случай $k=p$ если все равно ощутимой пользы это не приносит?
3) что дает неравенство $\lfloor m/(k+1)\rfloor \geq (m-k)/(k+1)$ с точки зрения найденной ранее верхней границы

$$\frac{3^{p+1}-1}{2(p+1)}-1$$

,
можно ли сказать, что значение

$$\frac{3^{p+1} + 1}{2(p+1)} + \ln(p+1) - p - 2\ < \frac{3^{p+1} + 1}{2(p+1)}-1$$

ее уточняет?
4) Если да, то как аналогичным способом уточнить нижнюю границу?

[maxal]

Пресловутая формула практически очевидна, если вспомнить явную формулу биномиальных коэффиентов. "Конкретную математику" для таких пустяков привлекать необязательно.

1) Опять же из явной формулы ${m\choose n}=\frac{m!}{n!(n-m)!}$ следует, что для простого $m$ и $1\leq n\leq m-1$ биномиальный коэффициент ${m\choose n}$ делится на $m$.

2) Затем, что утверждение пункта 1) для слагаемого с $k=p$ (а точнее для биномиального коэффициента ${p+1\choose p+1}=1$), не работает. Поэтому его нужно рассматривать отдельно.

3) оно дает оценку погрешности верхней грани, то есть насколько далеко реальное значение может находиться от верхней грани. Если внимательно посмотрите на исходное неравенство, то оно там дается виде:
верхняя грань >= искомая сумма > нижняя грань
Вы же почему-то вырезали только левую и правую часть: "верхняя грань > нижняя грань" - это конечно же верное неравенство, но оно не несет смысловой нагрузки. Идея была именно зажать значение искомой суммы сверху и снизу.

4) Что вы вкладываете в понятие "уточнить"? Чем текущая нижняя оценка вас не устраивает?

[Alik]

Gafield, maxal, спасибо вам большое, я кажется со всеми премудростями разобрался. Только вот это решение оказалось самым общим случаем.
То, что я пытался спросить про уточнение связано с задачей когда нужно найти количество разложений начинающихся с "1" спереди от которой могут стоять нули.
В частности

1   0   1
0   1   -1
1   1   1

Я подозреваю, что их число будет такое же как и найденное в предыдущем случае

[maxal]

Alik писал(а):

То, что я пытался спросить про уточнение связано с задачей когда нужно найти количество разложений начинающихся с "1" спереди от которой могут стоять нули.

Разложение в каком интервале рассматриваются? Если, скажем, это все возможные разложения с $n$ разрядами, то ответом будет просто $\frac{3^n-1}{2}$, что легко понять из симметрии: первая ненулевая цифра будет 1 или -1 с равной частотой, исключая случай всех нулей (где вообще нет ненулевых цифр).

[Дядя Фёдор]

Если Вам нужно записать число

$$\matbb{X}$$

в основании $\alpha$
то его длина $L$будет

$$ \begin{equation*} \left[ \frac{ln{\mathbb{X}}}{ln{\alpha}}+1 \right] = L\end{equation}$$

цифр.
Действительно, при ровно $n$ цифрах числа $ \mathbb{X}$по основанию $\alpha$ можно получить (положительное число) до величины $\alpha^n-1$ включительно. При этом оно будет больше или равно $\alpha^{n-1}$.
Таким образом:

$$ \begin{equation} \alpha^{n-1} \leqq \mathbb{X} \leqq \alpha^n-1\end{equation}$$

И переходя к логарифмам по оcнованию $\alpha$ получаем ответ.

[Alik]

Предыдущая формула $$\sum_{k=1}^p\left\lfloor\frac{2^k}{k+1}{p\choose k}\right\rfloor\ говорит о том сколько уравнений можно составить используя $p$ позиций троичного представления при количестве неизвестных $k+1$. В моем случае есть "дополнительное" условие на каждую систему из $k+1$ уравнений: она должна быть решабельной. Первое что напрашивается - это отсутствие "сопряженных" строк. Так например при $k=2$ недопустима матрица коэффициентов

 0   -1   -1
 0    1    1
 1    0    1

Как это учесть в полученной формуле я не знаю, более того не уверен, что она этого не учитывает

[Alik]

Затишье на этом топике очевидно связано с тем, что я не могу четко сформулировать задачу. Попытаюсь исправиться.
Итак, имеется вся та же самая троичная запись количество позиций в которой равно

$$p$$

представленная в виде матрицы

$$M$$

. Она содержит строки с индексом

$$R$$

, где первая ненулевая цифра будет

$$-1$$

, количество таких строк равно

$$\frac{3^n-1}{2}$$

. Теперь к добаляем к матрице

$$M$$

еще один столбец, в котором

$$-1$$

стоит ровно на местах

$$R$$

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

$$M$$

увеличилось до

$$p+1$$

. В соответствии с предыдущим решением обозначим за

$$k$$

количество ненулевых элементов в каждой строке,

$$1\leq k\leq p+1$$

. Эта же переменная

$$k$$

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

$$E$$

. Из матрицы

$$M$$

можно составить подматрицы коэффициентов для решения системы

$$E$$

. Поскольку

$$1\leq k\leq p+1$$

таких подматриц будет много, требуется найти их число.

[maxal]

Ну, во-первых, вместо $k$, наверное, все-таки надо писать $k_i$, где $i$ - это номер строки, потому что в разных строках, вообще говоря, будет разное число ненулевых элементов.
Во-вторых, я так и не понял, какие именно подматрицы $M$ вас интересуют. Например, должны ли эти подматрицы быть квадратными (как вариант: фиксированного размера), невыродженными, содержать только ненулевые элементы и т.д. и т.п.? И как числа $k_i$ должны быть связаны с этими подматрицами или связаны ли вообще?

[maxal]

Кажется, немного начинает проясняться, но все равно есть непонятки.
Похоже, что $k$ у вас это фиксированный параметр, который вы последовательно полагаете равным $k=1,2,3,\dots,p+1$. Далее, похоже, что для каждого $k$ вы рассматриваете только те строки из $M$, которые содержат в точности $k$ ненулевых элементов. Для определенности положим $I_k$ равным множеству индексов таких строк.

Однако, связь с системой уравнений по-прежнему непонятна.
Вот например ранее вы писали:

Alik писал(а):

сколько уравнений можно составить используя $p$ позиций троичного представления при количестве неизвестных $k+1$. В моем случае есть "дополнительное" условие на каждую систему из $k+1$ уравнений: она должна быть решабельной. Первое что напрашивается - это отсутствие "сопряженных" строк. Так например при $k=2$ недопустима матрица коэффициентов

 0   -1   -1
 0    1    1
 1    0    1

Следует ли из этого, что вас интересуют подматрицы в точности размера $(k+1)\times (k+1)$ причем такие, что:

1) каждая строка подматрицы содержит в точности $k$ ненулевых элементов;

2) индексы строк, составляющих подматрицу, лежат в $I_k$ (или, другими словами, в тех же строках матрицы $M$ других ненулевых элементов, кроме тех, что попали в подматрицу, нет).

[Alik]

Попытаюсь еще раз, начистовую, извиняюсь если будут противоречия с предыдущими формулировками.
Имеется матрица троичного разложения

$$M$$

, количество столбцов в ней равно

$$p$$

, добавим к матрице столбец из $-1$. Таким образом, количество элементов в каждой строке увеличилось до

$$p+1$$

.
Пусть требуется решить систему уравнений с $k$ неизвестными, ее матрица коэффициентов должна быть размером ($k$x$k$) и, для "решабельности" иметь ранг $k$.
Сколько таких подматриц коэффициентов можно составить из строк матрицы

$$M$$

, если $k=2,3,\dots,p+1$?
В качестве небольшого примера при $k=4$
подматрица 4х4

    -1     0    -1    -1
     1     0    -1    -1
    -1    -1     1    -1
     0     1     1    -1

имеет ранг 4 и подходит
а подматрица 4х4

    -1     0    -1    -1
     1     0    -1    -1
    -1    -1     1    -1
     1    -1     1    -1

имеет ранг 3 и не подходит