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
|
|
|
Форум
Домино
