Комбинаторика казалось бы не сложная

[SVicc]

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

Начало понятно шестизначных чисел будет 729. Дальше стопор.

[integral2009]

SVicc в сообщении #671421 писал(а):

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

Начало понятно шестизначных чисел будет 729. Дальше стопор.

А откуда 729? Можете привести пример одного-двух таких шестизначных цифр?

[INGELRII]

Мне кажется, тут проще сделать так: обозначим $a_n$ количество чисел из $n$ цифр $1,2,3$, в которых две единицы не стоят подряд и которые оканчиваются на единицу; и обозначим $b_n$ все такие же числа из $n$ цифр, но не оканчивающиеся на единицу. Затем выведем рекуррентную формулу, выражающую $a_{n+1} , b_{n+1}$ через $a_n , b_n$ (там должны получиться линейные зависимости). После чего посчитать $a_2 , b_2$ (что гораздо проще), и по этим рекуррентным формулам дойти до $a_6, b_6$. После чего вычислить сумму $a_6+b_6$, что и будет ответом.

Можно при желании и общую формулу вывести.

[gris]

integral2009, всего чисел действительно $729=3^6$. Числа от $111111$ до $333333$. Несложно и вручную пересчитать. Либо включения-исключения, например.

[cool.phenon]

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

[TOTAL]

$k$ единиц можно расставить $C^k_{7-k}$ способами, поэтому $C^0_7 \cdot 2^6 + C^1_6 \cdot 2^5 +C^2_5 \cdot 2^4 +C^3_4 \cdot 2^3$

[SVicc]

TOTAL в сообщении #671474 писал(а):

$k$ единиц можно расставить $C^k_{7-k}$ способами, поэтому $C^0_7 \cdot 2^6 + C^1_6 \cdot 2^5 +C^2_5 \cdot 2^4 +C^3_4 \cdot 2^3$

А как посчитать сколько раз 1 повторяется как минимум 2 раза подряд?

[TOTAL]

SVicc в сообщении #671524 писал(а):

А как посчитать сколько раз 1 повторяется как минимум 2 раза подряд?

Кому надо это считать, пусть и считает.

[SVicc]

TOTAL в сообщении #671549 писал(а):

SVicc в сообщении #671524 писал(а):

А как посчитать сколько раз 1 повторяется как минимум 2 раза подряд?

Кому надо это считать, пусть и считает.

И на этом спасибо!