Вы здесь

Комбинаторика для 3-х элементов

Undefined

maria16   Дата: Четверг, 31.03.2011, 17:15 | Сообщение #1

Добрый день! Помогите, пожалуйста, описать таблицу в формулах комбинаторики. Задача такова: Есть три элемента, которые могут принимать значения 0, 1, 2. В зачет идут только строки, в которых цифры идут подрят (001, 012, 112 и т.д.). Строки с непоследовательными цифрами (200, 202 и т.д.) в зачет не идут.
В результате должно получится: Всего строк 27, Зачетных строк 21.

№п/п Элементы
=== C B A
01= 0 0 0 +
02= 0 0 1 +
03= 0 0 2 -
04= 0 1 0 +
05= 0 1 1 +
06= 0 1 2 +
07= 0 2 0 -
08= 0 2 1 +
09= 0 2 2 -
10= 1 0 0 +
11= 1 0 1 +
12= 1 0 2 +
13= 1 1 0 +
14= 1 1 1 +
15= 1 1 2 +
16= 1 2 0 +
17= 1 2 1 +
18= 1 2 2 +
19= 2 0 0 -
20= 2 0 1 +
21= 2 0 2 -
22= 2 1 0 +
23= 2 1 1 +
24= 2 1 2 +
25= 2 2 0 -
26= 2 2 1 +
27= 2 2 2 +

Admin   Дата: Понедельник, 04.04.2011, 12:49 | Сообщение # 2

Общее количество строк - это размещения с повторениями из трех элементов по три: 33.
Но "зачетные" строки подсчитываютсь последовательным анализом "если - то...". Тут формулы, по-моему, не получится.

maria16  Дата: Понедельник, 04.04.2011, 23:07 | Сообщение # 3

Я не математик. Помогите кто чем может! Очень нужно...

Еще нужно описать аналогично таблицу (или, как вы там говорите - размещения) для 5 элементов (0,1,2,3,4), порядок важен. По сути, насколько я понимаю, - это порядковые числа в пятеричной системе счисления. Но в зачет должны идти только строки, в которых цифры идут подрят (0012, 0102, 1123, 1234 и т.д.). Строки с непоследовательными цифрами (2004, 2022, 3004 и т.д.) в зачет не идут.

№п/п Элементы
==== D C B A
01=== 0 0 0 0 +
02=== 0 0 0 1 +
03=== 0 0 0 2 -
04=== 0 0 0 3 -
05=== 0 0 0 4 -
06=== 0 0 1 0 +
...
241== 1 4 3 1 -
242== 1 4 3 2 +
243== 1 4 3 3 -
244== 1 4 3 4 -
...

Общее число строк практически у меня получилось 625 (включая строку 0000). Это что, тоже размещения? Какой формулой получается это число?
И вообще, строка 0000 учитывается?

Admin Дата: Вторник, 05.04.2011, 16:45 | Сообщение # 4

Для не математиков: размещения из n элементов по k - это когда из имеющихся n различных элементов нужно выбрать и разместить их на k пронумерованных (порядок имеет значение) местах. В вашем случае каждый элемент можно выбирать по несколько раз, то есть размещения с повторениями, их общее количество kn.

Далее. То что вы назвали "цифры идут подряд", если верить вашему примеру, должно бы называться "соседние цифры отличаются не более чем на 1". Стоит все-таки определиться, что именно мы ищем. Так как для математика "цифры идут подряд" выглядит так: 012, 123, 234, и т. д.

P.S. Пользуясь случаем, так сказать. И для математиков, и для не математиков на первом месте должно быть правильное воспитание. Особенно в раннем возрасте. Так что приглашаем всех коллег-воспитателей (в т.ч. и будущих) на дистанционные курсы для воспитателей .

maria16  Дата: Среда, 06.04.2011, 10:59 | Сообщение # 5

1) Простите, ошиблась с количеством элементов; Изменения внесла прямо в прошлое сообщение.
Элементы: 0, 1, 2, 3, 4. Следовательно, n=5.
Позиции 4, следовательно, k=4.
Размещения с повторениями 4^5 = 4*4*4*4*4 = 1024.
Прописывая от руки, у меня получилось 625 вариантов. Я где-то ошиблась или вычисления по другой формуле?

2) Теперь о «цифрах подряд». Представьте, что полученные комбинации – это номерные (имеющие номер) слои, которые прочитываются слева направо.
0012 – представлены два слоя и два отсутствуют,
0102 – представлены два других слоя и два отсутствуют,
1123 – представлены три слоя, два из них одинаковые,
1234 – представлены все слои.
Слои отсутствовать могут, но не могут быть пропущены:
2004, 2022, 3014
2334 – тоже «подряд», но…это как дом – без 1-ого этажа не существует, он не может висеть в воздухе.
2444 – аналогично, не может быть дома без 1-ого и 3-его этажей.

Admin  Дата: Среда, 06.04.2011, 15:42 | Сообщение # 6

Сори, это я формулу вверх тормашками нарисовал. На самом деле, на перевое место n один из элементов, на второе n, тогда количество пар получится n*n, на третье место n, следовательно троек будет n*n*n = n3 и т. д. То есть в предыдущем сообщении формула должна быть nk. В вашем случае 54, то есть, действительно 625.

Admin Дата: Среда, 06.04.2011, 16:13 | Сообщение # 7

Ну вроде все понятно.
Вашу задачу сформулируем так:
"Найти количество строк, которые состоят только из наборов последовательных цифр."
Искать будем по количеству цифрв наборе:

1. Последовательности состоящие только из одной цифры.
Общее их количество, очевидно, 5 ({0}, {1}, {2}, {3}, {4}). Математики это называют сочетания из 5-ти элементов по 1 (C15).
Для каждого набора получим только 1 строку.

2. Последовательности состоящие из двух последовательных цифр.
Общее их количество, очевидно, 5 - 1 = 4 ({0;1}, {1;2}, {2;3}, {3;4}),
для каждого набора получим только 24 = 16 строк. (количество размещений с повторениями из 2 элементов по 4).
Но тут войдут и строки из одинаковых цифр по две в каждом наборе, их нужно исключить, то есть таких строк 4*(24 - 2) = 56.

и т. д.

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

maria16  Дата: Четверг, 07.04.2011, 09:37 | Сообщение # 8

!!! Начало обнадеживает! Я абсолютно поняла первый пункт.

По поводу «одинаковых строк из одинаковых цифр по две в каждом наборе» - может их не исключать? Как-нибудь пометить для начала… Не хотелось бы потерять что-то важное. Исключаются только строки с пропущенными слоями. Кстати, наборы {2,3} и {3,4}, кажется, не нужны, они ведь без "первых этажей"?...

Добавлено (07.04.2011, 09:37)
---------------------------------------------
Получается, что в зачет идут следующие наборы последовательностей:
{0;1}, {0;1;2}, {0;1;2;3}, {1;2}, {1;2;3}, {1;2;3;4}. И где-то нужно вставить слово "с повторениями".
Заполнение осуществляется всегда по четырем уровням.

Например, при ручном расписывании для {0;1} получаем:

D C B A
0 0 0 1 ## 0001 =4
0 0 1 0
0 1 0 0
1 0 0 0
---------------------------
0 0 1 1
0 1 0 1 ## 0011 =6
1 0 0 1
0 1 1 0
1 0 1 0
1 1 0 0
----------------------------
1 1 1 0 ## 0111 =4
1 1 0 1
1 0 1 1
0 1 1 1
----------------------------
1 1 1 1 ## 1111 =1

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

Admin Дата: Четверг, 07.04.2011, 10:39 | Сообщение # 9

Сори, не заметил, что пропустить нижние уровни нельзя. В этом случае не могу с Вами не согласиться.
Тогда и в первом пункте будем засчитвать только 0 0 0 0 и 1 1 1 1, то есть две последовательности.

По поводу последнего замечания, Вы забыли 0 0 0 0, по вашим рассуждениям, но включили 1 1 1 1.
Но обе эти последовательности уже учтены (подсчитаны) в пункте 1.

Так вот, если считать все выписанные Вами последовательности для набора {0;1} (включая 0 0 0 0) получится 16 = 24 - число размещений с повторениями из 2 элементов по 4.
Но, так как 0 0 0 0 и 1 1 1 1 уже учтены то формула получится 24 - 2. Так же, как и для набора {1;2} (1 1 1 1 посчитали, а 2 2 2 2 не идет в зачет). То есть для двух наборов из двух элементов ({0;1} и {1;2}) получим общее количество строк 2*(24 - 2).

maria16   Дата: Четверг, 07.04.2011, 11:32 | Сообщение # 10

Строка (0000) для таблицы учитывается только 1 раз. Для наборов {0;1;2}, {0;1;2;3} ее уже не учитываем.

Хотела прикрепить файл задачей (собрала туда все свои уточнения) + готовая таблица, под которую нужно подвести комбинаторное решение, но Excel не прикрепился...

______
Сорри, я не математик, мне очень трудно...

Admin   Дата: Четверг, 07.04.2011, 12:56 | Сообщение # 11

Ничего, условие задачи и так уже понятно.

Далее.
3. Наборы по три элемента ({0;1;2} и {1;2;3}). Для каждого из них в общей сложности будет 34 размещений. Но в этом количестве окажутся подсчитанными по 3 строки из одного элемента (например, 0 0 0 0, 1 1 1 1 и 2 2 2 2 для первого набора), некоторые из них уже подсчитаны на первом этапе, а остальные просто не идут в зачет. Кроме того, попадутся строки, состоящие только из двух цифр. Выбрать по две цифры из трех в каждом случае можно тремя способами ({0;1}, {1;2} и {0;2}), причем эти наборы либо уже учтены (например, 0 1 0 0), либо вообще не подходят (например 0 2 2 2). В пункте 2 мы установили, что их количество 24 - 2 для каждой из трех пар ({0;1}, {1;2} и {0;2}).
То есть для двоих наборов по три элемента ({0;1;2} и {1;2;3}) количество строк:
2*(34 - 3*(24 - 2) - 3).

4. Наконец для наборов {0;1;2;3} и {1;2;3;4} количество строк можно считать как количество перестановок из 4 элементов, так как мест 4 и цифр тоже 4 (все цифры должны быть в строке, строки отличаются только порядком цифр в строке). Число перестановок из 4-х элементов 4!=4*3*2*1.

Итого имеем:
Два набора по одной цифре ({0}, {1}), количество строк: 2;
Два набора по две цифры ({0;1}, {1;2}), количество строк: 2*(24 - 2);
Два набора по три цифры ({0;1;2}, {1;2;3}), количество строк: 2*(34 - 3*(24 - 2) - 3) = 2*(34 - 3*24 + 3);
Два набора по четыре цифры ({0;1;2;3}, {1;2;3;4}), количество строк: 2*4!.

Сложим и посчитаем общее количество
К = 2 + 2*(24 - 2) + 2*(34 - 3*24 + 3) + 2*4! = 2*(1 + 24 - 2 + 34 - 3*24 + 3 + 4!) = 2*(34 - 2*24 + 2 + 4!) = 2*(34 - 25 + 2 + 4!) = 2*(81 - 32 + 2 + 24) = 2*75 = 150.

maria16 Дата: Четверг, 07.04.2011, 14:34 | Сообщение # 12

Ну да, ответ сошелся....
Большое СПАСИБО!
В моей рукотворной таблице 149 зачетных вариантов (0000 я не учитывала).
Мне осталось разобраться в формуле...
Если можно, уточните, пожалуйста: Вы использовали размещения и перестановки, и/или что-то из них с повторением (в теории чтобы найти)?

А для n=4, k=3 теперь можете формулу сходу написать?
Элементы: 0,1,2,3
Слои: 3.

Ухожу на обдумывание. Еще раз СПАСИБО!

Admin Дата: Четверг, 07.04.2011, 16:04 | Сообщение # 13

Для n=4, k=3 по аналогии должна потучится следующая:
К = 2 + 2*(23 - 2) + 2*3! = 2*(1 + 23 - 2 + 3!) = 2*(23 - 1 + 3!) = 2*(8 - 1 + 6) = 26,
при общем количестве
nk = 43 = 64.

P. S. Только учтите, что полученная нами формула, если так можно выразится, только "наивное решение, основанное на элементарных комбинаторных объектах". Скорее всего существует абстрактное решение этой задачи с применением более сложного математического аппарата.

author: 
admin
Просмотров: 
401
Категория: