Rook polynomial

Välkommen till Pluggakuten!

Hur definieras rook polynolials i din lärobok? Stämmer det med den här definitionen?

Tack snälla, definition stämmer

Underskatta inte möjligheten att det bara är ett feltryck. Om det går att kontrollera huruvida så är fallet, antingen genom att fråga uppgiftsskaparen eller genom att lösa problemet som om det hade varit fyra kvadrater längst ner till höger och jämföra med facit, skulle jag göra det. 

Hej,

Det är inget feltryck, hur blir det om du gör kvadraten till fyra mindre kvadrater? Du behöver inte skriva ner alla beräkningar utan enbart i form $r(x{)}_{mxn}$, m,n=>1 

Jag kan personligen inte algebraiska algoritmer eller finurliga representationer för att lösa detta problem så jag skulle bara brute-forca det med programmering.

Komplexiteten här kan inte vara så hög dock då de flesta 2x2-block inte kan påverka var man får lägga torn på mer än två andra 2x2-block så hela brädet reduceras till att bara vara en slags kartesisk komposition av ett 4x4-bräde och ett 2x6-bräde. Detta insåg jag efter att bara försöka placera ut torn. (Förutsatt att de två 2x1-rektanglarna egentligen ska forma ett 2x2-block. 

Jag kan inget om programmering utan jag använder enbart av matematiska algoritmer utan teknikens hjälp, vilket som, kan de inte stämma. Din reducering som du skrev ovan stämmer inte överens med den orginala brädan, exempelvis kan du placera en rook på flera sätt på den orginala brädan jämfört med din reducering? 

Jag tolkar bara de jag färgat som faktiska platser man kan stå på och att det ska finnas en extra linje längst ner till höger så att man får små kvadrater och inte två rektanglar. 

Just det färgade brädet ovan inser jag går att lösa för hand om man tillåts kolla upp några standardformler för rektangulära bräden. 

Har du haft sammanhang där du multiplicerat genererande polynom och vad det brukar motsvara för den operationen tycker jag ger en ganska rak lösning här?

Men vi har räknat för mycket  om vi gör kvadraten längs ner till höger till fyra små kvadrater. Hur tar vi bort de som är dubbelräkningen? 

Du har fortfarande inte återgett hur du vet att det inte är ett feltryck. Problemet blir elegant och lösbart med en enda kompakt formel om det är ett feltryck medan problemet blir (så vitt jag ser det) packat med specialfall och assymetrier om det inte är det. 

Men okej. Vad är regeln för hur man ska hantera en rektangulär ruta? Innebär ett torn placerat på en rektangulär ruta att alla andra rutor på nedersta två raderna är blockerade eller vad är regeln?

Regeln är att du kan placera två torn så länge dem inte tar ut varande vilket sker om du lägger ett torn på en ruta, sedan lägger du det andra tornet antigen horisontellt eller vertikalt i relation till den första rutan. 

För övrigt var detta en uppgift från en tenta, därav kan de inte vara feltryck. Jag har dubbelkollat med läraren under tentan. 

Okej. Tycker fortfarande rektangulära platser verkar väldigt knasigt men men. Per den regeln, vad ska man anse om följande arrangemang?

Du får inte glömma att du har tre fall, då du: 

1)  du placerar ett torn

2)  du placerar 2 torn

3)  du placerar 3 torn

Återigen, den där kvadraten med två rektanglar vet jag inte om man måste göra till fyra kvadrater för att kunna placera torn. Det är det som ställer till de för mig, och om vi gör de till en kvadrat med fyra mindre kvadrater, hur tar vi bort de vi har dubbelräknat? Men ja, de där är fyra fall som du kan placera två torn på.  

Är något av arrangemangen ovan acceptabla arrangemangmed 4 torn? Jag behöver bara få förtydligat om vad som gäller när torn sitter på rektanglarna. 

För att förtydliga lite grann om varför jag verkligen vill ha småkvadrater istället för rektanglar är att problemet då blir fruktansvärt enkelt.

Bara en fråga om att beräkna en produkt av två standardpolynom. Om jag försöker hantera rektangulära bitar så blir mina konstruktioner väldigt plottriga och jag med min metod blir jag tvungen att ta fram polynomet för tre bitar inklusive ett L-format bräde.

Det är nog fortfarande möjligt att göra för hand men är lite irriterande.

Reservation att jag inte förstår reglerna för rookproblemet då det här är första gången jag sett genererande polynom applicerade på det då något uppenbart fel kan ha smugit in sig. 

Jag tror inte de, eftersom vi kan inte vara säkra på om de två tornen tar ut varandra (de tornen som jag har markerat med röd färg), eftersom dessa kan betraktas som horisontellt placerade. Därmed tror jag vi behöver gör kvadraten till fyra kvadrat för att vara säkra på att de tornen inte är placerad horisontellt. Förstår du hur jag tänker, och för övrigt tack snälla för du tar din tid för att hjälpa mig. 

Vad blir rook polynomet med din metod? 

$p(x) = 1 + 12x + 30x^2$

$q(x) = 1 + 16x + 32 x^2 + 96x^3 + 24x^4$

$P(x) = p(x)q(x) =1 + 28 x + 254 x^2 + 960 x^3 + 2136 x^4 + 3168 x^5 + 720 x^6$

För den rektangelfria versionen. Du har nog rätt i att man kan ta detta polynom och göra några subtraktioner på termerna men jag kan inte se regeln. 

För att lösa den andra med rektangel skulle jag behöva hjälp med att bestämma $u(x)$, rookpolynomet för ett litet L-format bräde då detta inte är en standardform. 

Hej igen,

Ursäkta för mitt sena svar, men $u\left(x\right)=1+12x+38x^2+32x^3+4x^4$, vad blir svaret på din andra lösning nu när du vet u(x)?

Detta kan vara till en hjälp om du är säker på att din andra lösningen stämmer. Då kan jag jämföra ditt svar, med mina för att se vilken algoritm av mina generar samma svar som dig. 

Ser att x^2-termen i q(x) i mitt inlägg två inlägg tillbaka för har ett fel i sig. Ska vara 72x^2 istället för 32x^2 så borde varit

$P(x) = 1 + 28 x + 294 x^2 + 1440 x^3 + 3336 x^4 + 3168 x^5 + 720 x^6$

för den med 4-rektanglar istället för 2 kvadrater. Denna är jag alltså väldigt säker i metoden.

Om jag tar ditt u(x) som verkar rimligt och kör med

$p(x) = 1 + 12x + 30x^2$

$w(x) = 1 + 6x + 6x^2$

$u(x) = 1 + 12x + 38x^2 + 32x^3 + 4x^4$

$q'(x)=2x w(x) + u(x)=1 + 14 x + 50 x^2 + 44 x^3 + 4 x^4$

så fås

$P(x) = (2x w(x) + u(x))p(x) = 1 + 26 x + 248 x^2 + 1064 x^3 + 2032 x^4 + 1368 x^5 + 120 x^6$

där P(x) är för brädet med två rektangulära platser. 

Något reserverad inför eventuella missade termer någonstans men koefficienterna är i alla fall mindre än för 4-kvadrater så kanske i alla fall. Skulle säga 4:1 säker men förstås möjligt att förlora sådana odds också.