Форум
» Назад на решение задач по физике и термеху
Регистрация | Профиль | Войти | Забытый пароль | Присутствующие | Справка | Поиск

» Добро пожаловать, Гость: Войти | Регистрация
    Форум
    Математика
        Домино
Отметить все сообщения как прочитанные   [ Помощь ]
» Добро пожаловать на форум "Математика" «

Переход к теме
<< Назад Вперед >>
Одна страница
Модераторы: Roman Osipov, RKI, attention, paradise
  

Guest



Новичок

День добрый! Большинство могут составить формулу чтобы быстро подсчитать количество костяшек в домино. да и это собственно говоря ни к чему.
Задача состоит в том чтобы вывести общую формулу для подсчета костяшек в домино.
Например сколько костяшек будет в домино если костяшка будет состоять из n "квадратиков",  а число цифр используемое в одном квадратике k. (в обычном домино соответственно n=2, k=7)

Всего сообщений: Нет | Присоединился: Never | Отправлено: 26 апр. 2007 12:31 | IP
MEHT



Долгожитель

Что-то не получается получить общую формулу... хотя с первого взгляда казалось - простенькая задачка из комбинаторики
Но общий алгоритм её получения можно наметить.

Предполагаем, что расположение "квадратиков" с цифрами не зависят от расположения их в конкретной "костяшке" (это условие согласуется с обычным представлением о "нормальной" костяшке с двумя квадратиками), то есть, например, расположение цифр
1,2,1,4;
4,1,1,2; (или любые перестановки цифр этого набора)
представляют собой одну и ту же "костяшку".

Обозначим искомое колличество колличество "костяшек" через Sn(k).
Тогда для n=1, очевидно, будем иметь
S1(k) = k.

Для n=2 получаем сумму
S2(k) = k + (k-1) + (k-2) + ... + 1 = (k+1)*k/2;

для n=3
S3(k) = [k + (k-1) + (k-2) + ... + 1] + [(k-1) + (k-2) + (k-3) + ... + 1] +
+ [(k-2) + (k-3) + (k-4) + ... + 1] + ... + 1;

или же
S1(k) = k,
S2(k) = S1(k) + S1(k-1) + S1(k-2) + ... + S1(1),
S3(k) = S2(k) + S2(k-1) + S2(k-2) + ... + S2(1),

откуда напрашивается рекуррентная формула
Sn(k) = Sn-1(k) + Sn-1(k-1) + Sn-1(k-2) + ... + Sn-1(1).

Возможно, конечно, что всё это удастся свести к одной красивой формуле, но пока не вижу как это можно сделать.


(Сообщение отредактировал MEHT 28 апр. 2007 2:54)

-----
В математике нет символов для неясных мыслей. (Анри Пуанкаре)

Всего сообщений: 1548 | Присоединился: июнь 2005 | Отправлено: 28 апр. 2007 2:50 | IP
Guest



Новичок

А возможно ли эту формулу  Sn(k) = Sn-1(k) + Sn-1(k-1) + Sn-1(k-2) + ... + Sn-1(1) выразить через сумму для алгебраической последовательности.

И еще один вопрос как изменится формула если учесть что из костяшек домино будут исключаться только зеркальные костяшки? например: для костяшки 1,3,7,4 не может быть костяшки 4,7,3,1, но могут быть костяшки 1,3,4,7  1,7,3,4  и т.l.

Всего сообщений: Нет | Присоединился: Never | Отправлено: 28 апр. 2007 8:54 | IP
MEHT



Долгожитель


А возможно ли эту формулу  Sn(k) = Sn-1(k) + Sn-1(k-1) + Sn-1(k-2) + ... + Sn-1(1) выразить через сумму для алгебраической последовательности.

Я тут подробно рассмотрел суммы и в итоге всё же получил общую формулу. Можете подробнее поразбираться в её получении, - возможно, этот же результат можно получить и намного проще.

Для n=2 все ещё более-менее просто:
S2(k) = (k+1)*k/2
как сумма первых k членов арифм. прогрессии.

Для n=3 уже сложнее:
S3(k) = [(k+1)*k/2] + [k*(k-1)/2] + [(k-1)*(k-2)/2] + ... + [2*1/2] =
= k*(k+1)*(k+2)/6;

для n=4
S4(k) = [k*(k+1)*(k+2)/6] + [(k-1)*k*(k+1)/6] + ... [1*2*3/6] =
= k*(k+1)*(k+2)*(k+3)/24,

...... и т.д.;
замечая получающуюся закономерность, в итоге получаем общую формулу:

Sn(k) = [k*(k+1)*(k+2)*(k+3)* ... *(k+n-1)]/(n!) = [(k+n-1)!]/[(k-1)!*(n!)]

Строгое её доказательство можно попробовать провести методом мат. инудкции, но считаю это излишним.


И еще один вопрос как изменится формула если учесть что из костяшек домино будут исключаться только зеркальные костяшки? например: для костяшки 1,3,7,4 не может быть костяшки 4,7,3,1, но могут быть костяшки 1,3,4,7  1,7,3,4  и т.l.

Интересный вопрос... подумаю.


(Сообщение отредактировал MEHT 28 апр. 2007 13:47)

-----
В математике нет символов для неясных мыслей. (Анри Пуанкаре)

Всего сообщений: 1548 | Присоединился: июнь 2005 | Отправлено: 28 апр. 2007 13:45 | IP
MEHT



Долгожитель

Общее колличество "костяшек", состоящих из n "квадратиков" с k цифрами есть k^n. Сюда будут входить все возможные "костяшки" (разумеется также и зеркальные) начиная от [1,1,1,...1] и заканчивая [k,k,k,...k].

Очевидно, что на каждую "костяшку" найдется своя зеркальная. Если конкретная "зеркальная костяшка" не совпадёт с исходной, то её следует изъять из общего колличества k^n; если же какая-нибудь "костяшка" совпадет со своей зеркальной, то она будет единственной во всей совокумности k^n, и, следовательно, исключать её не нужно.

Найдем общее колличество совпадающих "зеркальных костяшек".
Тут следует различать два случая - когда число квадратиков n будет чётным и нечётным.

В случае чётного n совпадающая "зеркальная костяшка" будет выглядеть так:
[A,B,C,...,D,D,...,B,A],
где зеркальный "фрагмент" [A,B,C,...,D] будет состоять из n/2 квадратиков.

Все возможные переборы цифр этого "фрагмента"
(от [1,1,1,...,1] до [k,k,k,...,k])
однозначно определят все возможные совпадающие "зеркальные костяшки"; колличество таких совпадающих костяшек будет равно k^(n/2).


В случае нечётного n зеркальная костяшка будет выглядеть так:
[A,B,C,...,D,E,D,...,B,A],
где зеркальный "фрагмент" [A,B,C,...,D] будет состоять из (n-1)/2 квадратиков.

Все переборы значений цифр этого "фрагмента"
(от [1,1,1,...,1] до [k,k,k,...,k])
однозначно определят все совпадающие "зеркальные костяшки" для некоторого фиксированного значения E; колличество всех совпадающих "костяшек" будет равно k*k^[(n-1)/2] = k^[(n+1)/2].

Теперь, зная колличество совпадающих "костяшек", оставшееся колличество несовпадающих очевидно будет определятся разностью
[(k^n)-(k^(n/2))]           - для чётного n,
[(k^n)-(k^[(n+1)/2])]    - для нечётного n.

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

Sn(k) = [(k^n)+(k^(n/2))]/2           - для чётных n,
Sn(k) = [(k^n)+(k^[(n+1)/2])]/2    - для нечётных n.



(Сообщение отредактировал MEHT 29 апр. 2007 6:04)

-----
В математике нет символов для неясных мыслей. (Анри Пуанкаре)

Всего сообщений: 1548 | Присоединился: июнь 2005 | Отправлено: 29 апр. 2007 5:55 | IP

Отправка ответа:
Имя пользователя   Вы зарегистрировались?
Пароль   Забыли пароль?
Сообщение

Использование HTML запрещено

Использование IkonCode разрешено

Смайлики разрешены

Опции отправки

Добавить подпись?
Получать ответы по e-mail?
Разрешить смайлики в этом сообщении?
Просмотреть сообщение перед отправкой? Да   Нет
 

Переход к теме
<< Назад Вперед >>
Одна страница

Форум работает на скрипте © Ikonboard.com