Rozmieszczanie krzyżyków w tabelce

[arek1357]

Czasem coś wpada do głowy nowego
Więc załóżmy, że mamy nieograniczoną liczbę wierszy a właściwie wystarczy tyle wierszy ile jest:

\(\displaystyle{ ak}\) więcej nie trzeba.Na razie nie będziemy się ograniczać w wierszach.
Węzły jak mówiłem wcześniej mogą być między dowolnymi kolumnami(to będą węzły podwójne)
a jak między trzema kolumnami to będą potrójne.
Skupmy się na razie dla \(\displaystyle{ a=3}\) dla większej ilości będzie podobnie.

Niech \(\displaystyle{ a_{ij}}\) będzie to ilość węzłów między i tą i jotą kolumną

\(\displaystyle{ a_{ijk}}\) węzeł między trzema kolumnami
w naszym przypadku dla trzech kolumn będzie prosto:

\(\displaystyle{ a_{12}=a}\)

\(\displaystyle{ a_{13}=b}\)

\(\displaystyle{ a_{23}=c}\)

\(\displaystyle{ a_{123}=e}\)

zauważmy jeszcze, że:

\(\displaystyle{ e \le min\{a,b,c\}}\)

\(\displaystyle{ 0 \le a,b,c \le 2}\)

i zachodzi coś takiego:

\(\displaystyle{ 9-(a+b+c)+e=z}\) (Wzór Sylwestra)

\(\displaystyle{ z=4,...9}\)

ilość rozwiązań tego równania będzie z dokładnością do permutacji \(\displaystyle{ a,b,c}\)

np:

\(\displaystyle{ 9-(2+2+1)+1}\)

to samo:

\(\displaystyle{ 9-(2+1+2)+1}\)

.......

Podobnie będzie dla większych przypadków(dla większej liczby \(\displaystyle{ a}\))


Oczywiście jeśli jest liczba wierszy mniejsza niż \(\displaystyle{ ak}\)

dochodzą dodatkowe ograniczenia



Czyli ogólny wzór będzie wyglądał mniej więcej tak:

\(\displaystyle{ ak-(a_{1}+a_{2}+...)+(b_{1}+b_{2}+...)-(c_{1}+c_{2}+...)...=z}\)

\(\displaystyle{ z}\)- ilość zajętych miejsc(wierszy)

Pierwszy nawias liczy-\(\displaystyle{ {k \choose 2}}\)- składników
Drugi nawias liczy-\(\displaystyle{ {k \choose 3}}\)- składników
itd...(poprawiłem z a na k -ilość kolumn)

Tyle jest niezależnych nawiasów (permutacji wierszy) ile jest rozwiązań nierówności:

\(\displaystyle{ a_{1}+a_{2}+... \le (a-1) \cdot {k \choose 2}}\)

gdzie:

\(\displaystyle{ a-1\ge a_{1} \ge a_{2} \ge ... \ge 0}\)

dla każdego nawiasu podobnie,tyle że dla następnego musi zachodzić:

( \(\displaystyle{ b_{1} \le min\{ a_{i} \}}\))- to raczej bym wyrzucił sprawdza się to ale dla ostatniego nawiasu

\(\displaystyle{ b_{1}+b_{2}+... \le b_{1} \cdot {k \choose 2}}\)

..............................................

\(\displaystyle{ a+1 \le z \le ak}\)


Czyli reasumując w permutacjach poziomych (wierszy) biorę każdą kolumnę krzyżyków inną,
Niezmiennikami permutacji poziomych są wspólne węzły.
Potem zliczając ilość rozwiązań równania , a właściwie równania i układu nierówności dostajemy ilość niezależnych układów krzyżyków! W permutacji poziomej!!

[vpprof]

Skupmy się na razie dla \(\displaystyle{ a=3}\) dla większej ilości będzie podobnie.

Niech \(\displaystyle{ a_{ij}}\) będzie to ilość węzłów między i tą i jotą kolumną

\(\displaystyle{ a_{ijk}}\) węzeł między trzema kolumnami
w naszym przypadku dla trzech kolumn będzie prosto:

Czyli rozumiem że \(\displaystyle{ w=ak,\ k=3,\ a=3}\). Ale wtedy czemu:

zauważmy jeszcze, że:

(…)

\(\displaystyle{ 0 \le a,b,c \le 2}\)

Chyba miało być \(\displaystyle{ 3}\)?

Muszę jeszcze wydrukować drugą część posta i pomyśleć, bo doczytałem na razie tylko do „dochodzą dodatkowe ograniczenia”

[arek1357]

\(\displaystyle{ w}\) nie musi być koniecznie równe ak i przeważnie nie będzie
kolumny wierszy się zazębiają i ja odliczam węzły czyli tzw. punkty stałe w permutacji wierszy


dla:

\(\displaystyle{ a=3}\)

niech \(\displaystyle{ k=3}\)

i wtedy:

\(\displaystyle{ ak=9}\)

(*) \(\displaystyle{ \begin{cases} 9-(a+b+c)+e=z \\

2 \ge a \ge b \ge c \ge 0 \\

e \le min\{a,b,c\} \\

z=4,...,9 \end{cases}}\)


Dopiero \(\displaystyle{ z \le w}\)

Nas interesuje \(\displaystyle{ z}\) a nie w bo dla \(\displaystyle{ w>z}\) nic nowego nie zajdzie.
Nas interesuje ilość zajętych wierszy w naszej macierzy puste wiersze nic nowego nie wnoszą.

\(\displaystyle{ a,b,c}\) - to ilość węzłów podwójnych między kolumnami: (to a to nie ilość krzyżyków w kolumnie) sorki za kolizję oznaczeń!

pierwszą i drugą,
pierwszą i trzecią,
drugą i trzecią,

\(\displaystyle{ e}\) - to ilość potrójnych węzłów między kolumnami:\(\displaystyle{ 1,2,3}\)- czyli wszystkimi kolumnami.

\(\displaystyle{ z}\) - to ilość zajętych wierszy!

Ilość rozwiązań układów równań i nierówności (*) daje nam rozwiązanie dla przypadku:

\(\displaystyle{ a=3, k=3}\)

Wiersze i kolumny puste odrzucamy, nas interesują tylko parami różne kolumny.
Bo tyle zostało po przejściu przez pierwsze sito czyli permutację kolumn.
W permutacji wierszy stałymi punktami są węzły! czyli punkty stałe między:
Dowolnymi dwiema kolumnami (podwójne) - ilość- \(\displaystyle{ {k \choose 2}}\)
Dowolnymi trzema kolumnami (potrójne) - ilość- \(\displaystyle{ {k \choose 3}}\)
...................................................
Wszystkimi kolumnami (po k krotne) - ilość- \(\displaystyle{ {k \choose k}=1}\)


Jeśli ilość węzłów by była równa - \(\displaystyle{ a}\) - to znaczyłoby że dwie kolumny są identyczne a my ten przypadek odrzucamy

i dlatego w przykładzie zaczynam od \(\displaystyle{ a=2}\) a nie od \(\displaystyle{ a=3}\) - sorki za zament ale to a
to nie jest ilość krzyżyków w kolumnie tylko ilość punktów wspólnych (mały zamęt i kolizja nazewnicza)



Weźmy jeszcze np. dla:

\(\displaystyle{ a=3,k=2}\)

\(\displaystyle{ x}\) - ilość wspólnych węzłów między pierwszą i drugą kolumną jak widać węzłów tych może być tylko: \(\displaystyle{ 0,1,2}\)

Przypadek \(\displaystyle{ x=3}\) odrzucamy bo kolumny by się pokryły a ten przypadek odrzucamy(kolumny różne)!

mamy:

\(\displaystyle{ 6-x=z}\)

\(\displaystyle{ 0\le x \le 2 , z=4,5,6}\)


Tylko trzy rozwiązania!


Problem otwarty zostaje jeszcze dla zależności liczb między poszczególnymi nawiasami...

[arek1357]

Doszedłem do punktu w którym permutacje wierszy sprowadzają się do tw. Sylwestra
węzły to nic innego jak części wspólne między poszczególnymi kolumnami, należy pamiętać, że kolumny już nie będą identyczne czyli część wspólna nie pokryje się z danym zbiorem
ryzykuję że ilość możliwości przy permutacji poziomej (wierszy) będzie:

\(\displaystyle{ S=ka- \sum_{}^{} x_{i,j}+ \sum_{}^{} x_{i,j,k}-....x_{1,2,3,...,n}}\)

gdzie nasze \(\displaystyle{ x}\) to inaczej węzły czyli części wspólne między poszczególnymi kolumnami
Oczywiście \(\displaystyle{ S}\) to ilość zajętych wierszy przez wszystkie krzyżyki i jest, że:

\(\displaystyle{ S \le w}\)

\(\displaystyle{ x_{i,j}<a}\)

Czyli ilość powyższych równań to ilość permutacji wierszy

Każda permutacja pozioma nie zmienia węzłów czyli \(\displaystyle{ x_{i,j,...,k}}\)(części wspólnych),
które z kolei spełniają tw. Sylwestra!

Natomiast permutacje kolumn (pionowe) określają permutacje z powtórzeniami grup parami różnych,
a w grupach identycznych kolumn

[vpprof]

Arturze, bardzo wielkie dzięki za to, że wciąż zajmujesz się tym problemem! Ja odłożyłem ten „projekt” na bok przez te kilka miesięcy, bo w międzyczasie okazało się, że nie będę operował na binarnych macierzach, tylko na takich, których elementy należą do jakiegoś podzbioru \(\displaystyle{ \NN}\), np. \(\displaystyle{ \left[ 1 ; 100 \right]}\). W tym przypadku zmienna określająca liczbę krzyżyków w kolumnie nie ma sensu. Do tego są gotowe jakieś teorie, bodajże Pólya na tym polu działał.

No i w sumie okazuje się, że w zasadzie nie muszę umieć policzyć ile będzie układów (tzn. nieizomorficznych macierzy) — ważne jest samo ich wygenerowanie.

Na razie nie zajmuję się tym, przepraszam za kłopot, ale wrócę do tego na pewno w przeciągu najbliższych — powiedzmy — dwóch lat

PS. Przyznaję pochwałę za włożoną pracę.