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

[maxal]

А вы точно уверены, что вам нужна подматрица полного ранга именно размера $k\times k$, а не $k\times (p+1)$?
Если же все-таки первое, то есть такая тонкость: одна и та же подматрица может появляться в $M$ сразу в нескольких местах. Как в этом случае производить подсчет - с учетом кратности или нет?

[Alik]

maxal, Вы правы, мне нужны подматрицы размером $k\times (p+1)$ ранга $k$. Вернее максимальное количество таких подматриц коэффициентов, которые можно составить из

$$M$$

. Общее количество неизвестных соответствует позициям троичной расширенной матрицы $x_1, x_2, \dots, x_{p+1}$. При этом однако некоторые $x$ могут исчезать вследствии умножения на ноль, а количество оставшихся будет $k=2,3,\dots,p+1$.

[maxal]

Ну и последнее уточнение (надеюсь). А может вам нужны подматрицы размера $(p+1)\times (p+1)$ полного ранга?

С подматрицами $k\times (p+1)$ возможна такая проблема: вы нашли подматрицу $k\times (p+1)$ (для какого-то конкретного $k$) ранга $k$, но кто вам сказал, что в ней ровно $p+1-k$ нулевых столбцов и $k$ ненулевых, что соответствовало бы "исчезновению" $p+1-k$ переменных из системы, так что количество оставшихся будет равно $k$?
Нулевых столбцов в такой подматрице может вообще не быть, и у вас будет система из $p+1$ неизвестных и $k$ уравнениями ранга $k$, что, вообще говоря, не гарантирует существования решения при $k<p+1$.

[Alik]

В том то и дело, что мне нужны матрицы $k\times (p+1)$ ранга $k$, который определяет количество линейно-независимых строк (уравнений). Первый, описанный Вами случай когда исчезают $p+1-k$ переменных соответствует матрице $k\times k$ которая есть сжатая версия матрицы $k\times (p+1)$ без нулевых столбцов. Второй случай - это когда количество неизвестных больше, чем количество уравнений $k<p+1$. Я привык, что у таких систем решения нет, но как эта матрица может быть ранга $k$?

[Gafield]

Разговор пошел о ранге, хотя ранее упоминалась "решабельность". Так какая же постановка? Если речь идет все-таки об уравнениях, то можно ли сформулировать так: рассматриваются линейные неоднородные системы из $k$ уравнений с $p\ge k$ неизвестными, коэффициенты принадлежат множеству {-1,0,1}, а правая часть является столбцом из -1. Спрашивается, сколько (с точностью до перестановки строк?) существуют разрешимых систем такого вида для данных $p$ и $k$?

Если да, то чему принадлежат коэффициенты системы и решения? Прямой $\mathbb R$, группе $\mathbb Z_3$ или они еще откуда-нибудь? Опять же, на вопрос о разрешимости отвечает не ранг матрицы, а теорема Кронекера-Капелли.

[Alik]

Gafield, вопрос действительно о разрешимости, для удобства напишу все определения:

Система называется совместной, если она имеет хотя бы одно решение.
Совместная система называется определенной, если она имеет единственное решение.
Теорема Кронекера-Капелли: Для того чтобы система была совместна необходимо и достаточно чтобы ранг матрицы системы равнялся рангу расширенной матрицы.
Следствие: Если ранг указанных матриц равен числу неизвестных, то система определённая.

В данном случае рассматриваются линейные неоднородные системы из $k$ уравнений с $p+1$ неизвестными. Поскольку коэффициенты принадлежат множеству {-1,0,1} или группе $\mathbb Z_3$ некоторые неизвестные могут "исчезать", т.е. один или несколько столбцов будут равны нулю. Однако, коэффициент крайнего правого неизвестного $x_{p+1}$ всегда равен $-1$. Определим вектор

$$R$$

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

$$-1$$

. Столбец свободных членов содержит

$$-1$$

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

$$R$$

, на остальных местах стоят нули.
Спрашивается сколько существуют разрешимых систем для $p$ определяющего группу $\mathbb Z_3$ и переменной $k=2,3,\dots,p+1$ показывающей на число неизвестных с ненулевым коэффициентом.

[maxal]

Так вы решаете систему уравнений над $\mathbb Z_3$ ? И ранг тоже над этим полем вычисляется?
И что значит "для $p$ определяющего группу $\mathbb Z_3$" ?
И как $R$ связан с системами, что вы решаете?

Добавлено спустя 9 минут 46 секунд:

Alik писал(а):

Система называется совместной, если она имеет хотя бы одно решение.
Совместная система называется определенной, если она имеет единственное решение.
Теорема Кронекера-Капелли: Для того чтобы система была совместна необходимо и достаточно чтобы ранг матрицы системы равнялся рангу расширенной матрицы.
Следствие: Если ранг указанных матриц равен числу неизвестных, то система определённая.

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

Кроме того, как мне показалось, параметр $k$ у вас введен только для того, чтобы учитывать число реально присутствующих в системе неизвестных, но на самом деле вас интересует общее число "разрешимых" систем (то есть сумма по всем $k$ количеств таких систем). Если это так, то вам тем более нужно сформулировать в терминах рангов, не упоминая никакого $k$ вообще.

Добавлено спустя 2 минуты 13 секунд:

И еще рассмотрите какой-нибудь простенький пример типа $p=3$ и в явном виде укажите, что именно в этом случае вы хотите видеть в качестве ответа.

[Архипов]

Alik писал(а):

У меня такой вопрос: имеется ли общая формула для подсчета количества одинаковых цифр в записи целого числа представленного в позиционной системе счисления?
Допустим число 23412 в десятичном виде имеет две двойки, все остальные цифры встречаются один раз, тоже самое число в двоичной записи это 101101101110100, где количество единиц - 9, а количество нулей - 6.
Таким образом число переменных на выходе функции определяется числом позиций в представлении, не проблема написать программу для ее вычисления, но очевидных закономерностей в результатах не наблюдается.

А откуда числа берутся и для чего нужно считать количества цифр?
Статистическая, вероятностная или просто комбинаторная задача?
И зачем исследуется множество позиционных систем?

[Alik]

Попробую сформулировать еще раз.
Дано:
Матрица $M$ полного троичного разложения размером $3^p\times p$, где количество столбцов $p$ означает количество неизвестных $x_1, x_2, \dots, x_p$. Чтобы записать правую часть такой системы уравнений необходимо еще одно неизвестное $x_{p+1}$, его коэффициент всегда равен $-1$. В результате получается модифицированная матрица $M$ размером $3^p\times (p+1)$, где последний столбец $p+1$ состоит из $-1$. Формирование вектора-столбца свободных членов в правой части системы проиходит следующим образом. Определим строки в матрице $M$, где первая ненулевая цифра будет $-1$. Столбец свободных членов содержит $-1$ ровно в этих же строках, на остальных местах стоят нули.
Найти: Максимальное число разрешимых относительно $x_1, x_2, \dots, x_{p+1}$ систем уравнений, которые можно составить из исходной без учета кратности.
Простейший пример:

$$ \left[\begin{array}{cccc} -1&0&0&-1\\ 1&0&0&-1\\ \end{array} \right] \times \left[\begin{array}{cccc} x_1\\ x_{p+1}\\ \end{array} \right] = \left[\begin{array}{cccc} -1\\ 0\\ \end{array} \right] $$

[Архипов]

Alik писал(а):

У меня такой вопрос: имеется ли общая формула для подсчета количества одинаковых цифр в записи целого числа представленного в позиционной системе счисления?

Этот вопрос уже не актуален?

[maxal]

Alik
Вот теперь почти понятно, о чем речь. Только уточните над каким полем решаются системы уравнений - над $\mathbb R$ или мелькавшем тут $\mathbb Z_3$?

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

$$L(p)=\sum_{i=0}^{p-1} (p-i) 2^{3^i} - \frac{p(p-1)}{2}.$$

Это число дает число систем (определенных множеством индексов строк $I$ матрицы $M$), обладающих тем свойством, что для любого $i\in I$, если $M_{ij}=-1$ - это первый ненулевой элемент строки $i$, то в стоблце $j$ в этой системе могут присутствовать только числа $0$ и $-1$, причем если $M_{kj}=-1$ для какого-то $k\in I$, то $M_{kj}$ - это первый ненулевой элемент для строки $k$. Такие системы всегда разрешимы, так как сводятся к однородным.

Численные значения $L(p)$ для $p=1,2,\dots,5$:

2, 11, 531, 134218778, 2417851639229258617849376

[Alik]

maxal, наверное задачу можно сформулировать в понятиях поля, но я не специалист.
Зато я наконец-то понял в каком виде нужно рассматривать кратность:
подсистемы уравнений, которые приводят к одному и тому же $x_{p+1}$, т.е.

$$ \left[\begin{array}{cccc} -1&0&0&-1\\ 1&0&0&-1\\ \end{array} \right] \left[\begin{array}{cccc} 0&-1&0&-1\\ 0&1&0&-1\\ \end{array} \right] \left[\begin{array}{cccc} 0&0&-1&-1\\ 0&0&1&-1\\ \end{array} \right] \left[\begin{array}{cccc} -1\\ 0\\ \end{array} \right] $$

при подсчете считаются за одну.
Боюсь только, что ваше решение - оно для противоположного случая.

[Alik]

Похоже, что я нашел статью посвященную более общей проблеме разрешимости матриц такого вида.
Gwang-Yeon Lee and Bryan L. Shader, "Sign-consistency and Solvability of Constrained Linear Systems"
http://www.emis.de/journals/ELA/ela-art ... pp1-18.pdf
К сожалению прямой аналогии с моим "комбинаторным" случаем там не просматривается, может быть она есть в книгах
R. A. Brualdi and H. J. Ryser, "Combinatorial Matrix Theory," Cambridge University Press, 1991.
R. A. Brualdi and B. L. Shader, "Matrices of Sign–Solvable Linear Systems," Cambridge University Press, 1995.

[maxal]

Alik писал(а):

maxal, наверное задачу можно сформулировать в понятиях поля, но я не специалист.

Вопрос был не о формулировке, а том, какие решения $x_i$ вам нужны. Должны/могут ли они быть рациональными (поле $\mathbb{Q}$), целыми (кольцо $\mathbb{Z}$), или же система и ее решения рассматриваются по модулю 3 (поле $\mathbb{Z}_3$)?

Alik писал(а):

Зато я наконец-то понял в каком виде нужно рассматривать кратность:
подсистемы уравнений, которые приводят к одному и тому же $x_{p+1}$, т.е.

$$ \left[\begin{array}{cccc} -1&0&0&-1\\ 1&0&0&-1\\ \end{array} \right] \left[\begin{array}{cccc} 0&-1&0&-1\\ 0&1&0&-1\\ \end{array} \right] \left[\begin{array}{cccc} 0&0&-1&-1\\ 0&0&1&-1\\ \end{array} \right] \left[\begin{array}{cccc} -1\\ 0\\ \end{array} \right] $$

при подсчете считаются за одну.
Боюсь только, что ваше решение - оно для противоположного случая.

Но "подсистемы уравнений, которые приводят к одному и тому же $x_{p+1}$" не ограничиваются перестановкой столбцов (как в указанном выше примере). Если считать подматрицы с точностью до перестановки столбцов - это одно, а если требовать, чтобы $x_{p+1}$ были различны, - то это совсем другое (сводится просто к подсчету различных $x_{p+1}$). Уточните.
А решение я подправлю в соответствии.

[Alik]

Системы уравнений решаются над полем $\mathbb R$. Почему я привел пример перестановки столбцов, потому что это еще одно уточнение, которое родилось только наполовину .
Необходимо найти максимальное число различных $x_{p+1}$ так чтобы однажды найденные $x_1, x_2, \dots, x_p$ были одинаковыми. В случае нулевых столбцов лишь одна из перестановок даст требуемый $x_i$.