text:
Xsquare And Chocolates Bars
/

## Dynamic Programming, Implementation

Problem
Editorial
Analytics

Xsquare loves to eat chocolates like we all do. Xsquare's father has given him a chocolate bar B of length N where each chocolate piece is either of strawberry flavour S or of caramel flavour C. Xsquare's mom does not want him to eat all the chocolates as she thinks that consumption of too many chocolates will make him chocoholic. Therefore, she decided to take some chocolates back from him. She has some empty boxes to keep chocolates. Each box can contain exactly three chocolates. No box can contain all the chocolates of same flavour. She has ordered Xsquare to return her back, the longest contiguous sub-bar of the original chocolate bar such that she can place every three consecutive chocolates from that contiguous chocolate bar in an empty box. Each empty box can accomodate exactly three chocolates, neither less, nor more. A sub-bar is defined as contiguous peices of chocolates in some particular range.

Xsquare agrees to whatever his mom has ordered. Now, he is wondering how many chocolates he is able to eat at the end after he returns the longest contiguous sub-bar.

Help him in accomplishing this task.

### Input :

First line of input contains a single integer T denoting the number of test cases. Each of the next T line of input contains a string B denoting the chocolate bar, where ith character in the jth line denotes the flavour of ith chocolate piece in jth chocolate bar.

### Output :

Output consists of T lines, each containing number of chocolates Xsquare manages to eat at the end.

### Constraints :

• 1 ≤ T ≤ 105
• 1 ≤ |B| ≤ 106
• String B consists of character 'S' and 'C' only.
• sum of |B| over all test cases does not exceed 106

• sum of |B| over all test cases does not exceed 106 : ( 40 pts )
• sum of |B| over all test cases does not exceed 106 : ( 60 pts )

### Warning :

Prefer to use scanf / printf instead of cin / cout .

SAMPLE INPUT
4
SSSSSSSSS
CCCCCCCCC
SSSSCSCCC
SSCCSSSCS

SAMPLE OUTPUT
9
9
3
0

Explanation

Test case 1 : Xsquare cannot return any such bar to his mom. So, he can eat all the chocolates. Test case 2 : Xsquare cannot return any such bar to his mom. So, he can eat all the chocolates. Test case 3 : Xsquare can return "SSCSCC" to his mom such that she can placed "SSC" in one box and "SCC" in other box. Therefore, xsquare can get only 3 chocolates at the end. Test case 4 : Xsquare can return "SSCCSSSCS" to his mom such that she can placed "SSC" in first box, "CSS" in second box and "SCS" in third box. Therefore, xsquare will not receive any chocolate at the end.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...


text:
Graham Beasley

2022-07-20

What is Cluster sampling and Explain with an example of research which uses cluster sampling.

Osvaldo Crosby

Expert

Population is the complete set of people or objects with certain common characteristics under the study. The sample is the subset of population used to estimate the population parameters. Since complete enumeration of population units is time consuming and requires high manpower and high cost so, with the help of sampling, overcoming these drawbacks to estimate the population parameters. There are various method of sampling like simple random sampling, systematic sampling, cluster sampling, stratified sampling and convenience sampling method.
Cluster Sampling is the method of sampling in which the total population is divided into some recognizable sub-divisions called as clusters and then we will randomly select the clusters as a sample and then study each unit of these drawn clusters.
- Since in this sampling method, the whole target population is divided into various groups( called as clusters) so, it consumes less work, time and cost.
- This method is quite convenient in nature and it is ease to implement.
- Since there could be large samples in each cluster so, the loss of accuracy in information per observation can be compensated.

format: plain


text:
Integrate with series

Calculus Level 5

If $$\large{f(x)=\displaystyle \sum^{\infty}_{n=0} \frac{(-x^2)^n}{(2n+1)!}}$$ such that the equation below is true for integers $$A$$ and $$B$$, find the value of $$A+B$$.

$\large{\displaystyle \int^{\frac{\pi}{2}}_{0} f(x)f\left (\frac{\pi}{2}-x \right )dx=\frac{A}{\pi^{B}}\displaystyle \int^{\pi}_{0} f(x) dx}$

×

Problem Loading...

Note Loading...

Set Loading...


text:
## LaTeX2WP, Princeton grad student seminar, and characteristic polynomial coefficients November 15, 2009

Posted by Phi. Isett in Uncategorized.

(It’ll be pretty cool if it catches on! But for me it probably means I will help to run the blog, and for this purpose I’ll definitely need the converter.)

I need to at least try to write some kind of math, so I’ll explain something which I think is cute: how to express the coefficients of a characteristic polynomial of a matrix in terms of sums of determinants of other matrices constructed from its entries.  Actually, I’ll first give an example which contains all the ideas. Consider the ${3 \times 3}$ matrix ${A}$ whose entries are… Let’s say

$\displaystyle A = \left( \begin{array}{ccc} 1 & 2 & 5 \\ 3 & 4 & 7 \\ 6 & 8 & 9 \end{array} \right)$

The characteristic polynomial ${\chi(x)}$ is the determinant of the matrix ${xI - A}$ where $I$ is the ${3 \times 3}$ identity matrix. ${\chi(x)}$ is a degree 3 polynomial with a leading coefficient 1. In terms of the ${\Lambda^3({\mathbb R}^3)}$, we have

$\displaystyle \begin{array}{c} x-1 \\ -3 \\ -6 \end{array} \wedge \begin{array}{c} -2 \\ x-4 \\ -8 \end{array} \wedge \begin{array}{c} -5 \\ -7 \\ x-9 \end{array} = \chi(x)\cdot e_1 \wedge e_2 \wedge e_3 . \ \ \ \ \ (1)$

I discussed the one-dimensional vector space ${\Lambda^3({\mathbb R}^3)}$ and its geometric meaning in a previous post about the Cauchy-Schwartz inequality and integration. We know that ${\chi(x) = x^3 + c_2 x^2 + c_1 x + c_0}$, where ${c_0 = \chi(0)}$, and plugging in ${0}$ into the above expression, we see that ${c_0 = (-1)^3 \det(A) = \det(-A)}$. The point of this entry is that we can calculate the other derivatives by differentiating, and use the multi-linearity of the wedge product to differentiate easily.  Below the fold I will give an example of how this computation works out, I will state what nice, general formula is proven by this method, and I will discuss the geometric meaning of this computation.  (And at the end I will ask a question about this LaTeX2WP/Python business which is still troubling me)

Characteristic Polynomial Coefficients

For example, ${c_1 = \chi'(0)}$, and ${\chi'(x)}$ can be obtained from 1 to see that

$\displaystyle \begin{array}{c} 1 \\ 0 \\ 0 \end{array} \wedge \begin{array}{c} -2 \\ x-4 \\ -8 \end{array} \wedge \begin{array}{c} -5 \\ -7 \\ x-9 \end{array} + \begin{array}{c} x-1 \\ -3 \\ -6 \end{array} \wedge \begin{array}{c} 0 \\ 1 \\ 0 \end{array} \wedge \begin{array}{c} -5 \\ -7 \\ x-9 \end{array} +$

$\displaystyle + \begin{array}{c} x-1 \\ -3 \\ -6 \end{array} \wedge \begin{array}{c} -2 \\ x-4 \\ -8 \end{array} \wedge \begin{array}{c} 0 \\ 0 \\ 1 \end{array} = \chi'(x) \cdot e_1 \wedge e_2 \wedge e_3$

and after performing some parallel shifts, this identity reduces to

$\displaystyle \begin{array}{c} 1 \\ 0 \\ 0 \end{array} \wedge \begin{array}{c} 0 \\ x-4 \\ -8 \end{array} \wedge \begin{array}{c} 0 \\ -7 \\ x-9 \end{array} + \begin{array}{c} x-1 \\ 0 \\ -6 \end{array} \wedge \begin{array}{c} 0 \\ 1 \\ 0 \end{array} \wedge \begin{array}{c} -5 \\ 0 \\ x-9 \end{array} +$

$\displaystyle + \begin{array}{c} x-1 \\ -3 \\ 0 \end{array} \wedge \begin{array}{c} -2 \\ x-4 \\ 0 \end{array} \wedge \begin{array}{c} 0 \\ 0 \\ 1 \end{array} = \chi'(x) \cdot e_1 \wedge e_2 \wedge e_3$

Giving the expression

$\displaystyle \chi'(x) = \det\left( \begin{array}{cc} x-4 & -8 \\ -7 & x-9 \end{array} \right) + \det \left( \begin{array}{cc} x-1 & -6 \\ -5 & x-9 \end{array} \right)$

$\displaystyle + \det\left( \begin{array}{cc} x-1 & -3 \\ -2 & x-4 \end{array} \right) = \mbox{tr} \Lambda^2(x - I A),$

and we can plug in ${0}$ to obtain ${c_1}$ as the sum of three ${2 \times 2}$ subdeterminants of ${A}$ .

Proceeding this way in the general case when $A : {\mathbb R}^n \to {\mathbb R}^n$ is linear and counting shared boundary faces, one shows that

$\displaystyle \frac{d}{dx} \mbox{tr} \Lambda^k(xI - A ) = (n-(k-1)) \mbox{tr} \Lambda^{k-1}(xI-A), \quad 1 \leq k \leq n$

(it is sufficient to prove this identity at x = 0).  The characteristic polynomial itself is, of course, $\mbox{tr} \Lambda^n(xI - A)$, so applying the above formula and Taylor expanding about $x = 0$, we obtain the explicit formula in terms of subdeterminants

$\displaystyle \chi(x) = \sum_{k=0}^n \mbox{tr} \Lambda^{n-k}(-A) \cdot x^k$

which can be compared to the expression involving the eigenvalues of $A$.

Now, the same formula holds for arbitrary commutative rings because only integers and natural quantities show up here, which allows us to use the result from ${\mathbb Z}[x_1, x_2, \ldots, x_l]$ (and the universal property of the polynomial ring) to pass to the general case (basically using indeterminants for the coefficients, and then plugging in arbitrary ring elements into the coefficients).

There is a nice geometric interpretation of the above procedure, which is most easily understood in the setting of the real numbers.  We know that the k’th exterior power $\Lambda^k({\mathbb R}^n)$ corresponds to k-parallelograms of vectors in ${\mathbb R}^n$ which remain equivalent under parallel shift, so it should be easy to see why the differentiation $\frac{d}{dx} \mbox{tr} \Lambda^k(xI - A )$ results in an expression involving parallelograms of dimension one less.  In the case $k = n$, think of the differentiation at $x = 0$ as a limit of difference quotients, where we compare the signed volumes of two nearby n-parallelograms, one of which being

$\eta = \displaystyle [-A](e_1 \wedge \ldots \wedge e_n)$

whatever the linear map $-A$ does to the standard basis parallelogram, and the other being the very nearby parallelogram

$\eta_x = \displaystyle [xI-A](e_1 \wedge \ldots \wedge e_n)$

with x a very small number.  Thinking of these parallograms as oriented regions in ${\mathbb R}^n$, the difference in signed volume is easily seen to be an integral supported on essentially the boundary of the parallelogram $\eta$.  Because the perturbation is linear, the quantity integrated on each face basically depends only on the direction of the face (in the limit as x goes to 0), and this is why, upon differentiating once, we obtain the expression we have seen for the fluxes through the faces of $\eta$.  The resulting expression ends up being particularly simple when the perturbation of $-A$ is in the direction of the identity as in our case, but the picture generalizes to perturbations in general directions, and so one has to go into more detail in order to understand precisely what this flux is for any particular perturbation (I believe it is basically the original volume form contracted with a certain vector field associated to the perturbation that ends up being integrated over the boundary).  When one differentiates twice, one similarly obtains integrals over the oriented (n-2)-dimensional boundaries of the $n-1$-dimensional faces, which share (n-2)-dimensional faces with each other (although in the general case it is much less obvious the answer should be supported on the boundary).  This sharing of faces results in the factor of $(n - (k-1))$ in the formula, which counts the number of k-dimensional faces which have each (k-1)-dimensional face as part of their boundary.

I hope the picture is clear.  This method of computation can be used to show that differentiating the determinant function at the identity matrix gives the trace of the perturbation direction (which one can in fact take as an intrinsic definition of trace, if he should desire) although that fact is more related to asymptotics at $x = \infty$ for the computation presented above.  By the way, does anybody know any different, intrinsic definitions of trace? (The more geometric, the better; I am very curious — this one I have given has the geometric meaning of a proportional rate of change of volumes of regions under the flow of a vector field, but I don’t know if there’s a better one.)

Welp.. The post seems to have turned out OK.  (A huge amount of gratitude goes out to Luca Trevisan for writing his program).  I am slowly learning that it can be better to edit the tex file than to edit the post itself.  I wonder if the excess of plus signs looks stupid.  I wanted to put some kind of brackets around the vectors in the wedges, but doing so turned out to be a disaster.

But now I have a technical question about how to use the program (or Python?), and I would be very grateful for help:

I’m using Windows Vista (sorry), and for this reason (combined with my own stupidity, my lack of Python knowledge, etc.) had a bit of a headache figuring out how to work this program.  What I ended up doing (and I’m pretty sure this is stupid, but if anyone knows what to do instead, please let me know) is I literally edited the file latex2wp.py, and in the main body of the code I actually put in the names of the files.  E.g.

inputfile = “C:\Users\[more stuff]\charPolCoeffs.tex”

outputfile = “C:\Users\[the same stuff]\charPolCoeffs.html”

I had opened the .py file directly through IDLE and was able to use the “Run Module” feature in that program.  It worked, but I don’t think this is what Luca had in mind, and in particular is not what he instructed (but since I’m not on Linux, I can’t exactly do as he instructed).  Namely, Luca suggested (assuming, I believe, that I was in the Linux command prompt) that I input into the command line:

python latex2wp.py charPolCoeffs.tex

When I put these things into the python command prompt (after the arrows >>> ) , I think it believed I was trying to define the variable named “python”…  And perhaps also the variable “latex2wp”, but it got very confused upon reaching the ‘.’  Basically, I don’t think it was aware what I was trying to do at all, nor was I aware of how to tell it to go run this ‘.py’ file in a distant directory with the ‘.tex’ file as a parameter.  I don’t know anything about how Python works so I don’t understand what was wrong exactly or how to fix it.  Any help would be greatly appreciated, although it looks like I can survive with the uncomfortable, makeshift solution of literally editing the document for a while.

Edit (15 Nov 2009):  I have included a discussion of the geometric meaning of the computation and a statement of the general result obtained by the method.


text:
## plate solving

Anything that doesn't fit into any of the other forums
brundog
Posts: 2
Joined: Wed Aug 08, 2018 7:11 pm

### plate solving

I recently started using sharpcap pro and am trying to configure my equipment to do plate solving. My mount is an explore scientific EXOSII PMC-8 that is ASCOM compatible. I am using a QHYS:-II-M camera. I have downloaded astrotortilla and configured it. I have set up my ASCOM mount with the PMC-8 driver. I am not sure if Sharpcap has autodetected Astrotortilla does anyone know what indication I should see? The "Find my location" button does NOT appear. Does anyone know how I can get Astrotortilla to find my location. Can Stellarium be used to find the objects I will be viewing, Thanks for any help.
Brundog

Posts: 2235
Joined: Sat Feb 11, 2017 3:52 pm
Location: Vale of the White Horse, UK
Contact:

### Re: plate solving

Hi,

you can adjust the configuration for the plate solver in the 'Plate Solving' page of the settings. It should detect the default install of AstroTortilla/ASPS/Ansvr automatically, but if you have customized the install or it fails to auto detect then you need to tell SharpCap the folder where the plate solver has installed the 'solve-field' tool.

I believe that you can use Stellarium to guide the mount (there is an addin called stellarium scope) but I never had much success getting it working. Others seem to like it though.

cheers,

Robin

Bayer
Posts: 1
Joined: Mon Aug 13, 2018 10:35 am

### Re: plate solving

Hi Robin, what was the problem you found using stellarium scope? Trying to figure out if it's worth the effort. Cheers.

Posts: 2235
Joined: Sat Feb 11, 2017 3:52 pm
Location: Vale of the White Horse, UK
Contact:

### Re: plate solving

I found it fiddly to set up and not particularly nice to use either. What it gained over Carte-du-Ciel on prettiness it lost in usability.

My choice now for planetarium software is the excellent (and free) SkytechX (http://skytechx.eu/)

cheers,

Robin

brundog
Posts: 2
Joined: Wed Aug 08, 2018 7:11 pm

### Re: plate solving

I want to configure all sky plate solver in the plate solving page of settings. Sharpcap does not automatically detect this program and I am not sure how to tell sharpcap where the "solve field" tool for all sky plate solver is located. The browse button doesn't help me and all I can find is the executable file.

Robin, thanks for the information about skytechX. It appears to be easy to set up and use.

Posts: 2235
Joined: Sat Feb 11, 2017 3:52 pm
Location: Vale of the White Horse, UK
Contact:

### Re: plate solving

Hi,

the last time I installed ASPS, the required file was installed in

Code: Select all

	C:\Users\<your user name>AppData\Local\Astrometry\bin

SharpCap will (should) auto detect ASPS if it installs to that location providing you run SharpCap as the same user that installed ASPS. If that's not working then maybe the install location has been changed in newer versions and I haven't noticed

cheers,

Robin

robrj
Posts: 62
Joined: Fri Feb 17, 2017 1:03 am

### Re: plate solving

Bayer wrote:
Tue Aug 21, 2018 1:56 pm
Hi Robin, what was the problem you found using stellarium scope? Trying to figure out if it's worth the effort. Cheers.
I got my Celestron setup working with Stellarium Scope. First, you need ASCOM drivers for your mount. Then install and start up StellariumScope and connect it to your mount. In Stellarium, you have to enable the "Telescope Control" plug-in (you don't need to configure it, just select it so it's enabled on startup). There's a button on StellariumScope that configures Stellarium for you automatically. Just click it and it sets it up. It's super easy. When you start a session, startup StellariumScope and connect to the mount. It should start Stellarium automatically but if it doesn't you can just doubleclick the Stellarium icon and it will connect. Then I just minimize StellariumScope. I've never tried Cartes Du Ciel.

ydots
Posts: 3
Joined: Sun Sep 16, 2018 8:43 pm

### Re: plate solving

Hi Robin,

ShapCap 3.1 (the latest version) does not detect Astrotortilla on my PC. I looked up the C:\Users\<username>\AppData\Local\Astrometry\bin\ and the C:\Cygwin paths, neither of these seem to have a solve-field file. How do I proceed? Please help.

Wilsmaboy
Posts: 4
Joined: Tue Oct 30, 2018 4:35 pm

### Re: plate solving

I am having precisely the same issue with Plate Solver and Astrotortilla - I have searched everywhere for this 'solve-field' location and it does not exist.

BlackWikkett
Posts: 73
Joined: Sat Jun 23, 2018 8:48 pm

### Re: plate solving

Hi,

I have Astrotortilla installed and SharpCap finds the "solve-Field" file here: C:\Users\%user%\AppData\Local\Astrometry\bin\
%user% = user name you login to your PC. My example is from Windows 10 PC but should be the same for versions of Windows back to Windows 7. If you had Astrotortilla working in the past you may want to reinstall the Application. You can reinstall without having to download all the fits data. If you're on Windows 10 some recent updates have done some weird stuff to user data some personal data even being deleted and or moved.

Hope this helps,
-Wikkett

### Who is online

Users browsing this forum: No registered users and 0 guests


text:
Interpreting algebraic notation

## Interpreting algebraic notation

Algebraic notation consists of letters and numbers. A letter is an unknown value. Each letter may be multiplied by a number; for example 3x means three lots of x. The number is always put before the letter.

When an unknown is multiplied by a number, the times sign is left out, so that 3 xx a is the same as 3a. This avoids mixing up the times sign x with the unknown value x.

One unknown can multiply another unknown. If the number of boxes of pencils is unknown (call that b), and the number of pencils in each box is unknown (call that p), then the total number of pencils in all the boxes is bp, or b x p. Note that the times sign is not written, and that the letters are placed in alphabetical order (this is a convention, as bp is actually the same as pb).

Algebra follows the same BIDMAS rules as arithmetic. Brackets are often used to control the sequence of operations in algebra.

## Example 1

A small convoy is moving animals from one zoo to another. There are three vans each carrying the same number of marmosets, and two vans each carrying the same number of rattlesnakes. Write down how many animals are being transported, using m for marmosets and r for rattlesnakes.

3 vans x m marmosets in each van

2 vans x r rattlesnakes

3 xx m + 2 xx r

Dropping the times sign gives 3m + 2r

## Example 2

There are four boxes of pens. Each box contains the same number of pens. There are seven boxes of crayons. Each box of crayons contains the same number of crayons.

Write the number of pens and crayons algebraically.

4 boxes with p pens in each box = 4 x p = 4p

7 boxes of crayons, with c crayons in each box = 7 x c = 7c

The crayons and the pens cannot be added together, because the value of p and the value of c could be different.


text:
# Magnetic properties of SO(5) superconductivity

Physics – Condensed Matter

Scientific paper

[ 0.00 ] – not rated yet Voters 0   Comments 0

## Details Magnetic properties of SO(5) superconductivity Magnetic properties of SO(5) superconductivity

17 pages, 7 figures

Scientific paper

10.1006/aphy.2002.6263

The distinction between type I and type II superconductivity is re-examined in the context of the SO(5) model recently put forth by Zhang. Whereas in conventional superconductivity only one parameter (the Ginzburg-Landau parameter $\kappa$) characterizes the model, in the SO(5) model there are two essential parameters. These can be chosen to be $\kappa$ and another parameter, $\beta$, related to the doping. There is a more complicated relation between $\kappa$ and the behavior of a superconductor in a magnetic field. In particular, one can find type I superconductivity, even when $\kappa$ is large, for appropriate values of $\beta$.

No associations

LandOfFree

## Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

## Rating

Magnetic properties of SO(5) superconductivity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Magnetic properties of SO(5) superconductivity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Magnetic properties of SO(5) superconductivity will most certainly appreciate the feedback.

Profile ID: LFWR-SCP-O-339374

All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.


text:
# How to devise an algorithm to arrange (resizable) windows on the screen to cover as much space as possible?

I would like to write a simple program that accepts a set of windows (width+height) and the screen resolution and outputs an arrangement of those windows on the screen such that the windows take the most space. Therefore it is possible to resize a window, while maintaining output size >= initial size and the aspect ratio. So for window $i$, I'd like the algorithm to return a tuple $(x, y, width, height)$.

I believe this is might be a variation of 2D Knapsack. I've tried going over results around the web but they mostly had a lot of background (and no implementation) that made it hard for me to follow.

I'm less interested in the fastest possible algorithm, but more in something that is practical for my specific need.

• If you are resizing a window, you are not "maintaining its initial size", just its aspect ratio, I presume.
– Emre
Apr 10 '12 at 23:56
• You can resize one window to cover the screen, what is the problem?
– user742
Apr 11 '12 at 7:34
• I second Saeed's comment. You need additional constraints like minimal sizes the goal of minimising the sum of resizings if you want to exclude trivial solutions. Nota bene: mathematicians seem to call tiling problems tessellations.
– Raphael
Apr 11 '12 at 10:09
• May be is better to say, you want maximize minimum viewable window area and minimize maximum viewable window area, but conflicts are allowed or not? Please edit your question to make it bug free, thinking about current problem statement is not easy.
– user742
Apr 11 '12 at 14:27
• @daniel.jackson: He suggests that you should strive for a constellation where the smallest window is as large as possible, i.e. you don't have really small windows. Mathematically, you can say you maximise $\min_{w \in W} \mathrm{size}(w)$ with $W$ the set of windows.
– Raphael
Apr 11 '12 at 19:57

Although your question does not say it, I'm assuming that you do not want windows to overlap.

One approach to this problem is to use a constraint solver such as Choco. One simply writes down the constraints encoding your problem, tunes the solver to act in a smart way, and then let it run. This means that all the thinking you need to do will be spent on finding a good way of encoding the problem, not on devising an algorithm and doing the programming and tuning. Here is a partial answer to get you started.

Assume that the screen size is by $x_{max}\times y_{max}$.

For each window, $W_i$, you'll have a set of variables $x_i, y_i, h_i, w_i$ and constraints

• $x_i,y_i,h_i,w_i\ge 0$
• $x_i + w_i \le x_{max}$
• $y_i + h_i \le y_{max}$
• Perhaps also some constraints on the minimal size of windows, e.g., $h_i\ge 100$ and so forth.
• Aspect constraints: If aspect ratio is 3:4, the constraint could be something like $4h_i - \epsilon \le 3 w_i \le 4 h_i + \epsilon$, where $\epsilon$ is some small non-zero error term to allow for non-perfect window sizes, as otherwise you'd over constraint the problem.

Now you need to take care of window overlap. For each pair of windows, $W_i, W_j$, where $i\neq j$, you'll generate constraints like the following, which capture that no corner of $W_j$ appears within $W_i$. For $(x,y)\in\{(x_j,y_j), (x_j+w_j,y_j), (x_j,y_j+h_j), (x_j+w_j,y_j+h_j)\}$, generate constraint:

• $\neg(x_i \le x\le x_i + w_j \wedge y_i\le y \le y_i+h_j)$.

The constraints specified thus far only describe non-overlapping windows that do not spill over the sides of the screen, that satisfy some minimal size constraints, and that preserve their aspect ratio.

In order to get a good fit, you need to specify a metric that captures what it means to be a good layout. One possibility is to assume that you want to keep windows roughly equal in size and/or that you want to minimize "white space". I do not think that this can be specified using Choco, but it may be possible with another constraint solve (someone else might be able to help here).

Choco does allow one to maximize wrt to an objective function specified as a single variable. Based on this idea, you could maximize the following:

• $\sum_i (h_i + w_i)$

by writing a constraint $\mathit{cost}=\sum_i (h_i + w_i)$ and telling Choco to maximize $\mathit{cost}$.

• This looks promising and I'll definitely play with Choco to see how this works, and how fast. Apr 12 '12 at 15:12
• But why phrase it that generally ? I think you can phrase the constraints as linear inequalities, which means that what you have is a vanilla linear program. Apr 13 '12 at 19:58
• @Suresh: Feel free to elaborate. I don't immediately see how to. Apr 13 '12 at 20:04

I started writing a prototype for a brute force solution, that hopefully can be optimized to a point where it will be practical.

First, some definitions: Let $W$ be the set of all windows. Each window $w$ is composed of $x_w, y_w, w_w, h_w$ for the x, y coordinates and the width and height. A window is initialized with a minimum width and height.

The input of the algorithm is the screen, $S$, which has a width and height and a list of windows.

It works roughly so:

void fit(W, S, i, n, result)
if i == n
if S.score() < result.score()
result = S
return

w = W[i]
foreach x, y in S.coordinates()
set w position to (x, y)
while S.put(w) # check that w doesn't overlap with S's other windows and add it
fit(W, S, i+1, n, result)
S.windows.pop()
w.grow()
w.restoresize()

There are a few things that should be improved:

• S.coordinates() is very slow right now. It iterates all points in S.width x S.height and checks if each one is in one of S's windows.

• S.put() checks if its parameter overlaps with the rest of S's windows by doing the test mentioned in Dave's answer. Maybe this can be improved by using interval trees?

• S.score() currently returns $\sum_{w \in S.windows} (h_w \cdot w_w)$ which is simply the area of all windows. It needs to take into account other variables to produce better layouts.

• The above function needs to try all permutations of $W$ to get the best possible result.

I am currently trying to figure out a suitable data structure to represent the screen and its windows, it needs to support these queries:

• return a list of coordinates where a given window can be positioned without overlapping with others
• insert window at position x, y (already verified that it doesn't overlap)
• return all windows


text:
## Generate emacs-lisp documentation

| categories: emacs_lisp | tags: | View Comments

Emacs has some pretty amazing features to get help on a function (describe-function), to navigate quickly to functions in an elisp file (speedbar and imenu). Other languages have tools for generating documentation for all the functions in a file, e.g. epydoc, javadoc, Doxygen,… I have not found an equivalent to this in emacs-lisp. Here, we explore some options to get something similar to this. Our goal will be to take an emacs-lisp file, and generate an org-file of documentation, and then convert that to PDF for reading.

Say we have a function, jmax-bibtex-next-entry, and we want some information about it. Here are three functions that give us the argument list, documentation string, and function definition.

(help-function-arglist 'jmax-bibtex-next-entry)

 &optional n
(documentation 'jmax-bibtex-next-entry)

Jump to the beginning of the next bibtex entry. N is a prefix
argument. If it is numeric, jump that many entries
forward. Negative numbers do nothing.

(symbol-function 'jmax-bibtex-next-entry)

 lambda (&optional n) Jump to the beginning of the next bibtex entry. N is a prefix\nargument. If it is numeric, jump that many entries\nforward. Negative numbers do nothing. (interactive P) (if (= (point) (save-excursion (bibtex-beginning-of-entry))) (progn (forward-char) (bibtex-next-entry))) (if (re-search-forward bibtex-entry-head nil t (and (numberp n) n)) (progn (bibtex-beginning-of-entry)))

That will not always be the code we wrote, but it is functionally similar.

So we could create an org-entry like this:

(defun fun2org (function-symbol)
(let ((args (help-function-arglist function-symbol))
(doc  (documentation function-symbol))
(code (symbol-function function-symbol)))
(format "** %s %s
%s

#+BEGIN_SRC emacs-lisp
%S
#+END_SRC
" function-symbol args doc code)))

(fun2org 'jmax-bibtex-next-entry)

** jmax-bibtex-next-entry (&optional n)
Jump to the beginning of the next bibtex entry. N is a prefix
argument. If it is numeric, jump that many entries
forward. Negative numbers do nothing.

#+BEGIN_SRC emacs-lisp
(lambda (&optional n) "Jump to the beginning of the next bibtex entry. N is a prefix
argument. If it is numeric, jump that many entries
forward. Negative numbers do nothing." (interactive "P") (if (= (point) (save-excursion (bibtex-beginning-of-entry))) (progn (forward-char) (bibtex-next-entry))) (if (re-search-forward bibtex-entry-head nil t (and (numberp n) n)) (progn (bibtex-beginning-of-entry))))
#+END_SRC

The code is not that beautifully indented, but it is optional.

For variables, there are similar functions to get their documentation:

(documentation-property 'jmax-bibtex-journal-abbreviations 'variable-documentation)

List of (string journal-full-name journal-abbreviation). Find abbreviations at http://cassi.cas.org/search.jsp.

The problem still is, you have to know the variable and function names in advance. I want to take a file, and generate this for each function, and variable.

I posted a question on StackOverflow on how to get the functions defined in a file. The most feasible suggestion was to use the variable load-history, which contains a history of the variables and functions loaded, and the files they are in.

Here is an example of getting the entries associated with jmax-bibtex.el

(cdr (assoc "/Users/jkitchin/Dropbox/kitchingroup/jmax/jmax-bibtex.el" load-history ))

(jmax-bibtex-journal-abbreviations
(defun . jmax-bibtex-generate-longtitles)
(defun . jmax-bibtex-generate-shorttitles)
(defun . jmax-stringify-journal-name)
(defun . jmax-set-journal-string)
jmax-nonascii-latex-replacements
(defun . jmax-replace-nonascii)
jmax-lower-case-words
(defun . jmax-title-case-article)
(defun . jmax-sentence-case-article)
(defun . jmax-bibtex-next-entry)
(defun . jmax-bibtex-previous-entry)
(defun . jmax-bibtex-mode-keys)
(provide . jmax-bibtex))

Each element in this case is either a variable, defun or provide. Here, we can use this to print some information about the variables defined in this file. I think it is sufficient to check if the element in the list is a symbol, because all the other elements are cons elements. I suppose there are other possibilities, including defcustom, defgroup, defalias, defsubst, and maybe others.

(dolist (element (cdr
(assoc
"/Users/jkitchin/Dropbox/kitchingroup/jmax/jmax-bibtex.el"
(when (symbolp element)
(princ
(format "%s
Documentation: %s

" element (documentation-property element 'variable-documentation)))))

jmax-bibtex-journal-abbreviations
Documentation: List of (string journal-full-name journal-abbreviation). Find abbreviations at http://cassi.cas.org/search.jsp.

jmax-nonascii-latex-replacements
Documentation: Cons list of non-ascii characters and their LaTeX representations

jmax-lower-case-words
Documentation: List of words to keep lowercase

We can handle functions by checking if an element is a cons cell with a first element of defun.

(dolist (element (cdr
(assoc
"/Users/jkitchin/Dropbox/kitchingroup/jmax/jmax-bibtex.el"
(when (and (consp element)
(eq (car element) 'defun))
(princ (format "%s is a function\n" (cdr element))))))

jmax-bibtex-generate-longtitles is a function
jmax-bibtex-generate-shorttitles is a function
jmax-stringify-journal-name is a function
jmax-set-journal-string is a function
jmax-replace-nonascii is a function
jmax-title-case-article is a function
jmax-sentence-case-article is a function
jmax-bibtex-next-entry is a function
jmax-bibtex-previous-entry is a function
jmax-bibtex-mode-keys is a function

So, we have the important pieces to mash up what I am looking for. Let us refine the goal. I want to create a PDF documentation of what is in an elisp file with a section on variables, and a section on functions.

(let* ((elements (cdr
(assoc
"/Users/jkitchin/Dropbox/kitchingroup/jmax/jmax-bibtex.el"
(vars (-filter 'symbolp elements))
(funcons (-filter (lambda (x)
(and (consp x)
(eq 'defun (car x))))
elements))
(funcs (mapcar 'cdr funcons)))
(switch-to-buffer "*org-doc*")
(erase-buffer)
(insert (format "#+TITLE: Documentation for %s
#+OPTIONS: toc:nil
\\maketitle
\\tableofcontents
" "/Users/jkitchin/Dropbox/kitchingroup/jmax/jmax-bibtex.el"))
(insert "* Variables\n")
(dolist (var (sort vars 'string-lessp))
(insert (format "** %s
Documentation: %s\n\n" var  (documentation-property var 'variable-documentation))))

(insert "* Functions\n\n")
(dolist (funcs (sort funcs 'string-lessp))
(insert (format "** %s %s
Documentation: %s

Code:
#+BEGIN_SRC emacs-lisp
%S
#+END_SRC
"
funcs
(or (help-function-arglist funcs) "")
(documentation funcs)
(symbol-function funcs))))

(org-mode)
(write-file "jmax-bibtex-doc.org")
(org-export-to-file 'latex "jmax-bibtex-doc.tex")
(org-latex-compile "jmax-bibtex-doc.tex")
(kill-buffer "*org-doc*")
(kill-buffer "jmax-bibtex-doc.org"))

Here is the resulting pdf: jmax-bibtex-doc.pdf . It is not too bad. The code is not beautiful, and it would take some work to get that looking nice. It might be nice to find all instances of '` and replace them with links to variable names, but I leave that for another day. There is also no information about the header comments, but I leave this for another day to.


text:
# Combinatorial tilings from finite subdivision rules

In this blog post I give an overview of infinite tilings generated using finite subdivision rules and show some koebepy that creates them. If you haven’t already, you may want to install koebepy. In a future post I plan to give a more in-depth tutorial on how to compute tilings using koebepy with this post serving as the necessary background.

This post gives a broad-strokes overview of combinatorial substitution tilings. The payoff at the end is a surprising theorem of R. Kenyon and K. Stephenson that shows the combinatorics of certain types of infinite tilings of the plain encode everything necessary to reconstruct their geometry. In other words, you can forget the geometry completely and play just a combinatorial game. Then compute a little conformal structure et voilá the geometry comes right back!

Nota Bene: The code used to produce the images in this blog post is built on the work of three of my fantastic former undergraduate students, Angelo Luna, Nicole Maguire, and Christian Fuller.

## Introduction

A substitution tiling is a recursively defined structure in which we start with a set of one or more prototiles along with a finite subdivision rule for each prototile that defines how to cut each prototile up into a finite number of subtiles each of which is a (sort of) copy of one of the starter prototiles. I’m being informal here on purpose because we are going to look at two types of substitution tilings, geometric substitution tilings and combinatorial substitution tilings, and the precise meaning of subtile is a little different in each.

### Geometric substitution tilings

In a geometric substitution tiling each prototile has a specified geometric shape and the subdivision rule cuts the shape up into scaled and translated copies of the prototiles. Importantly, each subtile is scaled by the same constant factor. A nice example is the chair tiling. On the left of the figure below you can see a “chair” prototile and on the right you can see the chair’s subdivision into four smaller chairs, each exactly 1/2 the scale (and thus 1/4 the area) of the original. Technically, the chair tiling contains four prototiles and subdivision rules–the one shown below as well as its 90°, 180°, and 270° rotations. Below you see on the left the dark blue prototile, and on the right its subdivision into two 1/4 scale copies of itself (also in dark blue) as well as a 1/2 scale of its 90°-rotated (yellow) and 270°-rotated prototiles.

Once we have defined our prototiles and finite subdivision rules, we can produce subdivisions by starting with one of our prototiles as an initial tile and recursively applying the subdivision rules to all of the current tiles in the tiling. We say that the initial prototile is the level 0 tiling. Each time we recursively apply the subdivision rules we increase our level by +1. Here are several levels of the chair tiling.

### Covering the plane via direct limits

Let us reproduce the same figure as above, except each time scaling the figure up by a factor of 2 so that the subtiles have the same size after subdivision as their parent supertiles did before subdivision.

In this case the tiling expands outwards from some scaling point. We continue this procedure each time selecting a scaling point on the interior of one of our tiles, subdividing all tiles by applying the appropriate subdivision rules, and then scaling everything out from our chosen scaling point. The limit of this procedure, which is called the direct limit, produces a geometric tiling of the entire plane into chairs in our case (or whatever tiles our tiling produces). The expansion of the chair tiling produces a special type of infinite tiling called an aperiodic tiling which lacks periodicity at any scale (a topic beyond our scope here). In fact, different choices of scaling point lead to different infinite aperiodic tilings of the plane giving us uncountably many ways to tile the plane aperiodically with chairs.

Now, it may seem like chairs have 6 sides and 6 corners; however, we have to be a bit careful here. Let’s look at the combinatorics of the tiling. Specifically, we’d like to think about the line segments that make up the tiling as edges in a planar graph. Vertices will be placed at the junction of multiple line segments in the subdivision. In the figure below I’ve placed large black circles representing the vertex at each junction. Can you spot the problem?

The problem is that though our dark blue tiles are geometrically similar they are not combinatorially similar. In fact, one is incident to 6 vertices (black circles) as we expected, but the other is incident to 8. This occurs because our subdivision rule matches one whole edge of the upper dark blue subtile with two other edges–one from the other dark blue subtile and one from the yellow subtile. One edge glued to two edges is throwing our combinatorics out of whack! From the point of view of our upper dark blue tile it sees one edge, but from the point of the view of the other blue and the yellow tile there are two edges. This simply cannot stand.

To fix this combinatorics-construction problem we will have to insist that combinatorially one edge is always just one edge, no matter which subtile’s point of view you are using to look at it. To fix the chair tiling’s combinatorics, because the subdivision rule seems to sometimes give rise to an octagonal chair, all chairs must be octagonal! Here’s the subdivision rule again annotated so that it shows the combinatorics:

Notice that now the prototile has been given 8 sides instead of 6. It just happens that two pairs of consecutive edges (namely along the left-hand side and bottom) are straight. Combinatorially, though, we don’t care about the geometry–we only care that we have an 8 sided shape. The subdivision rule now correctly divides the 8-sided chair up into four smaller 8-sided chairs. Importantly, in this version of the subdivision rule one edge is one edge–each edge is a full edge for both of the tiles incident to it. Everything is now consistent!

### From geometric to combinatorial…

What if we forgot the geometry for the moment and focused on just the combinatorics? Technically we will think of a combinatorial tiling as a CW-complex homeomorphic to a disk. Essentially we want to forget the geometry and just focus on what discrete pieces make up the tiling. Consider our subdivision rule for the chair again, this time with the vertices labeled:

Let’s now describe this subdivision rule combinatorially. We begin with an 8-sided prototile ABCDEFGH. The subdivision rule requires 13 additional vertices a, b, c, d, e, f, g, h, i, j, k, l, and m. The first 8 additional vertices are obtained by splitting edges of the prototile. AB splits to obtain a, BC splits to obtain b, CD splits to obtain c, and so on. The final 5 vertices i through m are new vertices on the interior of ABCDEFGH. The tile is subdivided into four prototiles AaBjklHh, CcDdijBb, kjidEemlk, and GgHlmeFf. Is this all the information we need? Not quite. We need to know how the vertices of the prototile map to the vertices of a subtile. For example, in subtile kjidEemlk, which vertex is analogous to the the C vertex in the prototile? Look back at the previous figure. Clearly the i corner of the subtile matches up with the C vertex of the prototile. Let’s do another. Which prototile vertex corresponds to the m vertex of subtile GgHlmeFf? Well, the m is the the seat of the chair, so it corresponds to the E vertex of the prototile.

For each vertex in each subtile, we need to know which vertex it corresponds to in the prototile. To simplify the description we are going to require that each subtile be given in a consistent orientation. Notice that the order in which we specified each subtile above corresponded to a counter-clockwise walk around its boundary. Furthermore, we listed the vertices of each subtile in the same orientation and beginning with the same vertex as the corresponding orientation and vertices of its prototile. Thus, when we define CcDdijBb as a subtile whose prototile is ABCDEFGH we are implicitly defining the mapping from subtile to prototile vertices to be C<->A, c<->B, D<->c, d<->D, i<->E, j<->F, B<->G, and b<->H.

Let’s define the combinatorial chair tiling in koebepy. To do this we set up a TilingRules object which we will use to define Prototile objects. Each Prototile has a name and stores two types of rules–split rules, which are used to split edges of the prototile to obtain new vertices, and new vertex rules, which are used to create new vertices on the interior of the tile. Finally each Prototile stores a list of subtiles which are defined by listing the prototile type and vertices of each subtile (the vertices of a subtile may be original vertices of the parent prototile or new vertices obtained via split or new vertex rules). We begin by creating a prototile named “chair” with vertices A, B, C, D, E, F, G, and H. We then tell the chair prototile how to create the vertices a, b, c, d, e, f, g, and h by splitting the edges of the prototile. Next we tell the chair prototile that it has four subtiles, each of type “chair” and list the vertices of each.

from koebe.algorithms.tiling import *
from koebe.geometries.euclidean2 import PointE2
from koebe.algorithms.tutteEmbeddings import tutteEmbeddingE2'

# The combinatorial chair tiling only has one prototile
rules = TilingRules()
chair = rules.createPrototile("chair", ["A", "B", "C", "D", "E", "F", "G", "H"])

# Edges that need to be split
(("B","C"), ("b")),
(("C","D"), ("c")),
(("D","E"), ("d")),
(("E","F"), ("e")),
(("F","G"), ("f")),
(("G","H"), ("g")),
(("H","A"), ("h"))))

# New vertices to create

# The subdivision subtiles:
("A","a","B","j","k","l","H","h"))
("G","g","H","l","m","e","F","f"))
("k","j","i","d","E","e","m","l"))
("C","c","D","d","i","j","B","b"))

This sets up the rules for our tiling, but doesn’t actually compute a tiling at any level. To compute a tiling we call the generateTiling method on our TilingRules object passing it the starting prototile and the recursion depth to compute to (recursion depth 3 corresponds to tiling level 4).

tiling = rules.generateTiling("chair", depth = 3)

The resulting object is a doubly-connected edge list (DCEL) data structure representing the tiling. The DCEL data structure will have to wait for another blog post, but for now suffice it to say that it stores representations of the vertices, edges, and faces (tiles) of our tiling. We can, for instance, find out how many vertices, edges, and tiles the chair tiling has at depth 3 (level 4) via the following.

print("The level 4 chair tiling has")
print(f"\t{len(tiling.verts)} vertices,")
print(f"\t{len(tiling.edges)} edges, and")
print(f"\t{len(tiling.faces)-1} tiles.")

The output of those three lines is:

The level 4 chair tiling has
225 vertices,
288 edges, and
64 tiles.

The astute reader may notice that we subtracted one from the number of faces to obtain the number of tiles. This is because the DCEL also represents the region surrounding the tiling as the “outer face” of the tiling.

But wait! All we have so far is combinatorial information. Nowhere have we given any geometry–it’s essentially just a graph. Let’s get some geometry using some graph drawing techniques. One way to draw a graph is to compute a Tutte embedding. koebepy’s tiling library has a built-in function for computing and drawing a Tutte embedding of the tiling (for those readers familiar with Tutte embeddings, the boundary vertices of the tiling are evenly along the unit circle for the initial conditions.) Here’s how to generate the Tutte embedding of our tiling along with the result.

tutteGraph = tutteEmbeddingE2(tiling)
TutteEmbeddedTilingViewer(
tiling,
tutteGraph,
showVertices=True
).show()

Of course, those tiles don’t look at all like chairs. Why would they? What’s a chair combinatorially? It’s really just a combinatorial octagon. And what does our subdivision rule do? It breaks up a combinatorial octagon into four combinatorial octagons. Nothing about it suggests a chair shape. Or does it? Let’s compute the level 6 subdivision, but color all tiles in the same level-3 supertile with the same color (randomly chosen for each supertile):

tiling = rules.generateTiling("chair", depth = 6)
tutteGraph = tutteEmbeddingE2(tiling)
TutteEmbeddedTilingViewer(
tiling,
tutteGraph,
).show()

Strange. Those supertiles are looking remarkably chair-like. Remember, we forgot the geometry of the chair tiling completely. Our geometry came from a Tutte embedding which is a generic method of graph drawing that has nothing to do with chair tilings. Then why do the super tiles look like chairs?

### …and from combinatorial to conformal…

A Tutte embedding is one way to get geometry from combinatorics. Another way is to find a circle packing. Informally, one variant of the circle packing theorem says that every abstract triangulation of a disk can be realized as a pattern of circles whose contact graph is isormorphic to the 1-skeleton of the original triangulation. (The contact graph of a set of interior disjoint circles is an abstract representation of the incidences between the circles. Each circle is represented as a vertex in the graph and whenever two circles are tangent, their corresponding vertices are connected by an edge.) The figure below shows an example. On the left you see a triangulation with 6 vertices (in this case it’s the 1-skeleton of an octahedron) and on the right (ignoring for the moment the outer circle) you see a pattern of 6 circles whose contact graph is isomorphic to the triangulation on the left.

The circle packing theorems (and I say theorems, because there are really a bunch of related results that deal with triangulations of different homotopy classes as well as different sets of boundary conditions and constraints) are existence and uniqueness theorems. To get to our version of the theorem requires a little bit of hyperbolic geometry.

#### A digression into hyperbolic geometry.

The hyperbolic plane is a two-dimensional non-Euclidean geometry. A full account of the hyperbolic plane is beyond the scope of this post, but I’ll give a quick crash course. If you are new to this, Henry Segerman and Saul Schleimer have a nice video describing different models for the hyperbolic plane and how they are related by projections in 3-space.

To obtain a non-Euclidean geometry, we throw out Euclid’s fifth postulate which in one incarnation says given a line L and a point p not on L there is a unique line L’ passing through p that is parallel to L. The key phrase here is a unique line. We obtain different geometries by changing the phrase is a unique line to something else. Elliptic geometry, which is spherical geometry except with antipodal points identified, is obtained by replacing is a unique line with is no line. In other words, there are no parallel lines in elliptic geometry! Consider walking in a “straight” line along the earth (and imagine the earth is perfectly spherical). Because of the curvature you will eventually walk all the way around the earth tracing out what we call a great circle and end up back where you started. But from your local point of view, you took the straightest path possible. What you think of as a “line” is really a great circle, but you have to be viewing the sphere at a much more global scale to see this. Key fact: all great circles intersect and thus if you and I start drawing “lines” in starting from different points on the sphere our paths will eventually cross, no matter what.

The hyperbolic plane is obtained by replacing is a unique line in Euclid’s fifth postulate with are infinitely many lines. Just as with the sphere example above we need to have a more global view to really be able to visualize this. What we want is a model of the hyperbolic plane in which we identify the words point and line with some objects that satisfy the normal axioms of geometry–things like two points determines a unique line, two lines either never meet (and are therefore parallel) or intersect at a unique point, etc. as well as our new infinitely-many-parallel-lines version of Euclid’s fifth postulate.

The model we will use is called the Poincaré disk model of the hyperbolic plane. We identify the points in our hyperbolic plane geometry with the points on the interior of the unit disk $U=\{ z | z\in\mathbb{C}, |z|<1 \}$ in the complex plane $\mathbb{C}$. A “line” in our geometry is the intersection of the interior of the unit disk with a circle that intersects the boundary $\partial U = \{z | z\in\mathbb{C}, |z|=1\}$ at a right angle. Here are two examples.

On the left figure above we have two lines, blue and yellow that intersect at a point, but neither intersect the red line. Thus both the yellow line and blue line are parallel to the red. In the right figure above we show a regular pentagon (red) and the supporting lines of its edges (blue).

There is a properly developed notion of distance in the hyperbolic plane. A nice explanation of how to develop this can be found here. For our purposes, only a vague understanding will be required. Recall that in a the Mercator projection of the world distances near the equator appear relatively smaller than distances near the poles–Greenland appears too large. One way to think about this is that starting from the equator as we move up towards the North pole or down towards the South pole our rulers grow so that more of the paper is involved with measuring out a given mile at the top and bottom of the map than in the center. The same thing happens in the Poincare disk model except in reverse. As we move outwards from the origin towards the boundary of the disk our ruler shrinks. In fact, if we measure the distance from the origin to a point that is approaching the boundary of the disk the distance approaches infinity, since we have to put smaller and smaller rulers down as we get closer to the boundary. According to the hyperbolic metric, the boundary of the disk is infinitely far away from any point in the disk.

So distances/lengths are compressing and lines appear to be curves. Is there any sanity to this model? In fact, there is. Two nice features of the Poincare disk are that it preserves angles and circles. In other words, whenever two hyperbolic lines meet at a hyperbolic point, the angle measure between them is exactly the Euclidean angle measure between their corresponding Euclidean circular arcs. Additionally, if we take a hyperbolic point $p$ and look at the locus of points a fixed hyperbolic distance of $r$ from that point we obtain a hyperbolic circle of radius $r$ centered at $p$. If we draw this circle in the hyperbolic plane, its representation to us is a Euclidean circle. However, unless the hyperbolic center $p$ is the origin, the Euclidean and hyperbolic centers won’t be the same point. Why is that? Its precisely because the ruler shrinks when it moves near the boundary of the unit disk. Thus the part of the unit disk between the origin and $p$ will have a larger ruler than on the other side of $p$. Thus, if we draw a unit circle centered at the origin and translate it outward towards the boundary of the disk, it will appear to us that the center is moving faster towards the disk than the circle (but this is an illusion, just like Greenland being larger than Africa on a Mercator map).

Consider the chain of blue circles in the figure above. Each blue circle has the same hyperbolic radius. From this you can see how as we move towards the boundary $\partial U$ the rulers are shrinking. If we wanted them to appear the same size to us, we would need to gradually increase their radii as their centers moved outwards from the origin. The red circle at the top of the disk gives a more extreme example of the compression of our ruler. Note how close the outer boundary the center of this circle (the small dot whose Euclidean coordinates are $0.95i$) appears to be. All points on the red circle are equidistant from this center point under the hyperbolic metric. Finally, imagine a process in which we move a circle center outwards towards the boundary while increasing its hyperbolic radius so that its Euclidean radius does not change. The limit of such a process is shown in the yellow circle. Here we have a set of points in Euclidean space that are tangent to $\partial U$ at a single point. This object is called a horocycle and can be loosely thought of as a circle with a center at infinity and an infinite radius. Horocycles will play a role in our discussion of tilings.

Key Takeaway: Going forward the most important points from this discussion to remember are that Euclidean circles on the interior of the unit disk correspond to hyperbolic circles in the Poincare disk model and Euclidean circles that are tangent to the boundary of the unit disk with interiors contained on the interior of the unit disk correspond to horocycles.

#### Maximal packings of the hyperbolic plane and conformal maps

Remember that when we first defined circle packings above, we had an outer circle that I told you to ignore? Let’s draw that same circle packing again, except this time we’re going to connect up hyperbolic circles/horocycle centers with hyperbolic lines/rays/segments instead of Euclidean circle centers with Euclidean segments.

Here our packing is made up of three horocycles (the circles tangent to the unit disk) and three finite circles. Our embedding of the contact graph has the three horocycle centers as points on the boundary of the unit disk. The edge between two neighboring horocycles becomes a hyperbolic line (yellow). The edge between a horocycle and neighboring finite circle becomes a hyberbolic ray (red), and the edge between two neighboring finite circles becomes a hyperbolic line segment (blue). This packing is called a maximal circle packing of the hyperbolic plane because all of the boundary vertices of our abstract triangulation are embedded as horocycles in the packing and all of the interior vertices are embedded as finite circles. We can now state the version of the circle packing theorem that is relevant to our study.

Circle Packing Theorem. Let $K$ be a abstract triangulation homeomorphic to a disk. Then there exists a maximal circle packing of the hyperbolic plane whose contact graph is isomorphic to the 1-skeleton of $K$. Furthermore this packing is unique up to Möbius transformations of $\mathbb{C}$ that map $U$ to itself.

Note the uniqueness part of the theorem. The Möbius transformations are the maps $M:\mathbb{C}\rightarrow\mathbb{C}$ that map circles to circles. These maps are also the conformal maps, or angle preserving maps, of $\mathbb{C}$ to $\mathbb{C}$. Suppose $M$ is a Möbius transformation that sends the set $U$ to itself. Since it maps circles to circles and $U$ to $U$, it will also map circular arcs on the interior of the unit disk to circular arcs on the interior of the unit disk. Interpreted in the framework of the Poincaré disk model this means that $M$ takes the set of hyperbolic lines to itself. In fact, $M$ is a hyperbolic isometry. Denote the hyperbolic distance between two points $z, w \in U$ by $d_{\mathbb{H}}(z, w)$. That $M$ is a hyperbolic isometry means that for all $z, w \in U$, $d_\mathbb{H}(z, w) = d_\mathbb{H}(M(z), M(w))$. Thus the circle packing theorem states that maximal circle packings of the hyperbolic plane are unique up to hyperbolic isometries!

### Infinite conformal tilings

It’s a bit tricky to define infinite conformal tilings in a precise and accessible way. For a reader who is really ready to tackle these fascinating objects, the place to go is [BS17]. My goal here is to give a very brief overview to pique your interest, but the mathematical background required for this section is going to be significantly higher than for the previous sections, and I’m not going to explain the basic concepts. Think of this section as a “why you might want to learn more” to people who already have the appropriate background. If you are without the appropriate background, you may want to skim this section and move on.

Go take a look at at Figure 3 again. The direct limit of our subdivide-and-scale procedure produces a subdivision of the plane into tiles, which we’ll denote by $T$. We’re now going to forget the geometry of this tiling and give the tiling a Riemannian structure via the following construction. For each tile $t$ with vertices $(v_0, \dots, v_{n-1})$, we star triangulate the tile by introducing a new vertex $v$ and replace the tile with triangles $\Delta_i = v v_i v_{i+1}$ for each $i$ (indices $\mod n$, of course). We place an equilateral metric on each triangle to obtain a Riemannian surface $S$. By the Poincaré-Koebe uniformization theorem this surface is conformally equivalent to either $\mathbb{C}$ or $U$.

We now apply one further limiting procedure–hex refinement. Hex refinement takes each equilateral triangle $ABC$ and subdivides it by introducing vertices $a$, $b$, and $c$ at the midpoints of the edges $BC$, $CA$, and $AB$ (respectively) and replaces the triangle with four equilateral triangles $Acb$, $cBa$, $baC$, and $abc$. Suppose we hex refine our structure $j$ times. Consider a particular tile $t$ in our original tiling $T$. After star triangulation, $t$ was subdivided into the $n-1$ triangles $\Delta_0, \dots, \Delta_{n-1}$. Each hex refinement subdivides each triangle into four, so after $j$ applications of hex refinement, our original tile $t$ is represented by $4^j n$ triangles. Let $S_j$ denote the surface obtained from $S$ after $j$ refinements. By the uniformization theorem there is a unique conformal map taking $S_j$ to $\mathbb{C}$ or $U$.

We are now going to look at where this map takes all of the $4^j n$ triangles that came from subdividing $t$. These cover some polygonal region of $\mathbb{C}$ or $U$, which we’ll denote by $P_j(t)$. Now, let’s take the limit as $j$ goes to infinity. The polygons $P_j(t)$ converge to a curvilinear polygon, denoted $P_\infty(t)$ with $n$ vertices whose edges are segments of analytic curves. The original vertices of $t$ map directly onto the vertices of $P_\infty(t)$. Furthermore the curvilinear polygons satisfy the following 2 conditions.

1. The polygon $P_\infty(t)$ is conformally regular meaning that there is a conformal map taking $P_\infty(t)$ to the regular $latexn$-gon in the plane that maps vertices to vertices.
2. For any two neighboring tiles $t_1$ and $t_2$ meeting at an edge $e$, there is an anticonformal reflection between $P_\infty(t_1)$ and $P_\infty(t_2)$ across the curvilinear edge corresponding to $e$.

The tiling made up of all of the $P_\infty(t)$‘s is called a conformal tiling. In fact, any subdivision of the plane into curvilinear polygons that satisfies conditions 1 and 2 above is called a conformal tiling. It seems a bit remarkable to me that such things exist at all (other than boring examples like square grids) and particularly beautiful that finite subdivision rules can be used to construct them.

### Finite quasi-conformal tilings

The conformal tilings described in the last section are mathematically interesting but we would like to be able to see what they look like, which is challenging given that they have infinitely many tiles (some of which, like the chair tiling, have no underlying symmetries to exploit) and on top of that require two different limiting processes to compute.

We’re now going to look at process that gives us just such a drawing. But first let’s get a new tiling, that isn’t our old friend the chair. This is a particularly stunning one called the twisted pentagonal tiling. Unlike the chair tiling, this tiling does not have a corresponding geometric tiling. Thus, I’m going to hand-draw the initial subdivision rule. There’s one prototile, a combinatorial pentagon. We introduce one vertex on its interior and split each of its edges into 3. Finally, we subdivide its interior into five pentagons. Here’s a hand sketch of the rule:

This is purely combinatorial, because there is no way to subdivide a regular pentagon into regular pentagons. Here is the koebepy code for it:

from koebe.algorithms.tiling import *

pent_rules = TilingRules()
pent = pent_rules.createPrototile("pent", tuple("ABCDE"))

(("B","C"), ("c", "d")),
(("C","D"), ("e", "f")),
(("D","E"), ("g", "h")),
(("E","A"), ("i", "j"))))

Now, we would like a drawing of this tiling, but instead of using Tutte embeddings, we are going to compute a circle packing. Currently all of our tiles are five-sided, but circle packings require triangulated complexes. To get a triangulated complex we star-triangulate each pentagonal face by introducing a new interior vertex and subdivide the face into triangles by attaching edges from each of the original vertices of the tile to the new vertex. We then compute a circle packing. The left of the figure below shows the result.

The code for generating the left of figure 14 is below. Changing the showCircles and showTriangulation flags to False produces the center of figure 14. The right was traced by hand in an image editing program. There’s always more to implement. Check out the code, and then let’s talk about the right of figure 14.

pent_tiling = pent_rules.generateTiling("pent", depth = 4)
pent_packing, _ = generateCirclePackingLayout(pent_tiling)
CirclePackedTilingViewer(
pent_tiling,
pent_packing,
showCircles = True,
showTriangulation = True
).show()

In the right of figure 14 I have highlighted the boundaries of supertiles at levels 3, 2, and 1. Think of this as the inverse of the subdivision procedure. I’m aggregating (to use a term from [BS97, BS17]) the subtiles back into their parent super tile to move to a parent level. Notice that we still see a pentagon, but with fractal-like edges stretching between the vertices (red) of each pentagon. There’s a lot of fascinating geometry here, but you’ll have to read [BS97, BS17] for more details. For the twisted pentagonal tiling, in the limit, we get fractal polygons. For some sets of rules, however, this aggregation method does not converge on a fractal. It converges on the shape of the tile in the conformal tiling generated by the rules. The most surprising result, however, comes when we look again at geometric tilings.

### …and from conformal back to geometric.

Let’s go back to our old chair tiling again, but this time we’re going to forget its geometry (like we did when we used a Tutte embedding) and use a star-triangulation and a circle packing to obtain a new geometry of the tiling. Take a look at the next figure.

On the left of figure 15 we see the circle packing layout of the level 4 chair tiling. In the middle, I’ve aggregated the level 4 tiles back into their parent tiles from level 3. Already they are beginning to look a bit chair like, except for notches in the at the back of the “seat” of the chair and a notch where the back of the chair meets the floor. The right of the figure shows the aggregate supertiles at level 2. Just 2 levels up from the smallest tiles we are really starting to see chairs emerge and the notches have proportionally gotten smaller. We could imagine computing the level 5 tiling and looking back at the level 2 super tiles (3 levels up this time). We’d again see chairs and again the notches would get smaller.

This raises the question: will the aggregate tiles approach the original geometric tiles? If so this is a rather incredible result. Remember that we threw out the geometry completely and computed a purely combinatorial tiling. We got a new geometry back from circle packing which it would seem is completely arbitrary and unrelated to the original, and yet, it appears that some how the combinatorics of the geometric tiling really encoded the geometry of the tiling as well.

It seems mystical, but this is indeed the case. The following incredible theorem is a corollary of the main result of [KS19]. (Their main result deals with infinite tilings, and the version I’m detailing here deals only with finite tilings.) One fact I’ve glossed over a bit is that circle packings of combinatorial tilings approximate conformal tilings (see [KS19]) and converge to them as the number of subdivisons approaches infinity.

Theorem (Corollary to the Kenyon-Stephenson Theorem [KS19]). Suppose we have a geometric tiling produced by a finite subdivision rule. Let $t_k$ denote a tile produced at level $k$ in the conformal tiling that is not incident the boundary. Let $t_k^{\langle n \rangle}$ denote the set of tiles at level $n > k$ whose aggregate at level $k$ is $t_k$. Then the shape of $t_k^{\langle n \rangle}$ approaches the shape of original geometric prototile corresponding to $t_k$ as $n\rightarrow\infty$.

In other words, in the limit, those octagons really do turn back into chairs.

## Looking forward

I originally intended this post to explain how to use koebepy to produce tilings. I had planned to write a short introduction to tilings as a lead in and if you’ve gotten this far, you’ve seen how short my introduction was. I’m going to leave a technical tutorial on how to actually use the tiling features of koebepy to a future post. There is code below in the Appendix section for several of the figures. For now, please let me know what you think in the comments.

[BS97] Bowers, P. and Stephenson, K., 1997. A “regular” pentagonal tiling of the plane. Conformal Geometry and Dynamics of the American Mathematical Society, 1(5), pp.58-86.
[BS17] Bowers, P.L. and Stephenson, K., 2017. Conformal tilings I: foundations, theory, and practice. Conform. Geom. Dyn., 21, pp.1-63.
[CFP01] Cannon, J., Floyd, W. and Parry, W., 2001. Finite subdivision rules. Conformal Geometry and Dynamics of the American Mathematical Society, 5(8), pp.153-196.
[CFP06] Cannon, J., Floyd, W. and Parry, W., 2006. Expansion complexes for finite subdivision rules. I. Conformal Geometry and Dynamics of the American Mathematical Society, 10(4), pp.63-99.
[KS19] Kenyon, R. and Stephenson, K., 2019. Shape convergence for aggregate tiles in conformal tilings. Proceedings of the American Mathematical Society, 147(10), pp.4275-4287.
[S05] Stephenson, K. (2005). Introduction to Circle Packing: The Theory of Discrete Analytic Functions. Cambridge: Cambridge University Press.

## Appendix

### Code for figure 9 and 12

The first code block produces figure 9. To additionally produce figure 12, append the second code block.

from koebe.geometries.euclidean2 import PointE2, SegmentE2
from koebe.graphics.euclidean2viewer import UnitScaleE2Sketch, PoincareDiskViewer
from koebe.algorithms.incrementalConvexHull import randomConvexHullE3
from koebe.algorithms.tutteEmbeddings import tutteEmbeddingE2

poly = randomConvexHullE3(6) # Generates a random 6 vertex polyhedron
poly.outerFace = poly.faces[0] # Converts one face to the outerface to make it a disk

tutteGraph = tutteEmbeddingE2(poly) # Compute a Tutte embedding

# Show the Tutte embedding
viewer = UnitScaleE2Sketch()
for e in tutteGraph.edges]
)
viewer.show()

# Compute a maximal packing of the hyperbolic plane
from koebe.algorithms.hypPacker import *

packing, _ = maximalPacking(
tutteGraph,
num_passes=1000
)

# Show the circle packing
viewer = PoincareDiskViewer(600, 600)
for e in packing.edges]
)
viewer.show()

To produce figure 12 you first run the code above followed by the code below.

from koebe.geometries.hyperbolic2 import PointH2, SegmentH2, LineH2
# Show the circle packing
viewer = PoincareDiskViewer(600, 600)

def sc(z):
# I haven't implemented SegmentH2/LineH2's between
# points at infinity, but the PointH2 class is able to store
# points at infinity. This function is just scaling points really
# close to infinity a bit so they are finite, but appear infinite
# for drawing purposes.
# This is now on my TODO
if z.coord.modulusSquared > 0.999999999:
return PointH2(0.9999*z.coord)
else:
return z

lineStyle = makeStyle(stroke="#f4d35e", strokeWeight=1.0)
rayStyle = makeStyle(stroke="#f95738", strokeWeight=1.0)
segmentStyle = makeStyle(stroke="#0d3b66", strokeWeight=1.0)
pointStyle = makeStyle(stroke="#000", strokeWeight=2.0)

boundaryVerts = set(packing.outerFace.vertices())
for e in packing.edges:
u, v = e.endPoints()
if u in boundaryVerts and v in boundaryVerts:
elif u in boundaryVerts or v in boundaryVerts:
else:

viewer.addAll([(v.data.center, pointStyle) for v in packing.verts])

viewer.show()

### Code for figure 10 left

from koebe.geometries.hyperbolic2 import *
from koebe.graphics.euclidean2viewer import PoincareDiskViewer, makeStyle

# Create a new Poincare disk viewer
viewer = PoincareDiskViewer(400, 400)

# Create 5 points A, B, C, D, E
A = PointH2.fromComplex(complex(0.5, 0.5))
B = PointH2.fromComplex(complex(0.2, 0.75))
C = PointH2.fromComplex(complex(0.25, -0.15))
D = PointH2.fromComplex(complex(-0.3, -0.4))
E = PointH2.fromComplex(complex(-0.4, 0.25))

# Create some different styles to draw the lines with
blueLine = makeStyle(stroke="#0d3b66", strokeWeight=2.0)
yellowLine = makeStyle(stroke="#f4d35e", strokeWeight=2.0)
redLine = makeStyle(stroke="#f95738", strokeWeight=2.0)
pointStyle = makeStyle(stroke="#000", strokeWeight=3.0)

# Add lines AB, AC, DE and point A to the viewer
[(LineH2(A, B), blueLine),
(LineH2(A, C), yellowLine),
(LineH2(D, E), redLine),
(A, pointStyle)
]
)

# Show the viewer
viewer.show()

### Code for figure 10 right

from koebe.geometries.hyperbolic2 import *
from koebe.graphics.euclidean2viewer import PoincareDiskViewer, makeStyle
import math

# Create a poincare disk viewer
viewer = PoincareDiskViewer(400, 400)

# Create 5 points of a regular pentagon centered
# at the origin
A,B,C,D,E = [PointH2.fromComplex(
complex(math.cos(2*math.pi*i/5)*0.65,
math.sin(2*math.pi*i/5)*0.65))
for i in range(5)]

# Create some styles for drawing
lineStyle = makeStyle(stroke="#0d3b66", strokeWeight=1.0)
segmentStyle = makeStyle(stroke="#f95738", strokeWeight=3.0)
pointStyle = makeStyle(stroke="#000", strokeWeight=3.0)

# Add the pentagon's supporting lines, segments, and points
# to the viewer.
(LineH2(A, B), lineStyle),
(LineH2(B, C), lineStyle),
(LineH2(C, D), lineStyle),
(LineH2(D, E), lineStyle),
(LineH2(E, A), lineStyle),
(SegmentH2(A, B), segmentStyle),
(SegmentH2(B, C), segmentStyle),
(SegmentH2(C, D), segmentStyle),
(SegmentH2(D, E), segmentStyle),
(SegmentH2(E, A), segmentStyle),
(A, pointStyle),
(B, pointStyle),
(C, pointStyle),
(D, pointStyle),
(E, pointStyle)
])

# Show the viewer
viewer.show()

## Code for figure 11

from koebe.geometries.hyperbolic2 import *
from koebe.graphics.euclidean2viewer import PoincareDiskViewer, makeStyle
import math

# Converts a length x hyperbolic units along the x-axis to
# the euclidean distance of the point to the origin.
def hypXAxisToEuc(x):

# Create a poincare disk viewer
viewer = PoincareDiskViewer(600, 600)

# Create the circle centers and circles
As = [PointH2(complex(hypXAxisToEuc(0.5*i), 0)) for i in range(10)]
Cs = [CircleH2.withCenterAndHRadius(A, 0.25) for A in As]

A = PointH2(complex(0, 0.95))

B = PointH2(complex(-0.999999995, 0))

# Create some styles for drawing
circleStyle1 = makeStyle(stroke="#0d3b66", strokeWeight=1.0)
circleStyle2 = makeStyle(stroke="#f95738", strokeWeight=2.0)
circleStyle3 = makeStyle(stroke="#f4d35e", strokeWeight=2.0)
pointStyle = makeStyle(stroke="#0d3b66", strokeWeight=0.5)

# Add the pentagon's supporting lines, segments, and points
# to the viewer.


text:
Tight binding model for iron pnictides - Condensed Matter > Superconductivity

Abstract: We propose a five-band tight-binding model for the Fe-As layers of ironpnictides with the hopping amplitudes calculated within the Slater-Kosterframework. The band structure found in DFT, including the orbital content ofthe bands, is well reproduced using only four fitting parameters to determineall the hopping amplitudes. The model allows to study the changes in theelectronic structure caused by a modification of the angle $\alpha$ formed bythe Fe-As bonds and the Fe-plane and recovers the phenomenology previouslydiscussed in the literature. We also find that changes in $\alpha$ modify theshape and orbital content of the Fermi surface sheets.

Author: M.J. Calderon ICMM-Csic, B. Valenzuela ICMM-Csic, UAM, E. Bascones ICMM-Csic

Source: https://arxiv.org/


text:
+0

# Quadrilateral

0
39
1

In quadrilateral ABCD, we have AB = 3, BC = 6, CD = $$9$$, and DA = $$12$$.
If the length of diagonal AC is an integer, what are all the possible values for AC? Explain your answer in complete sentences.

May 13, 2022

### 1+0 Answers

#1
+9457
0

Triangle inequality implies $$\begin{cases} 3 + 6 > AC\\ 3 + AC > 6\\ 6 + AC > 3\\ 9 + AC > 12\\ 9 + 12 > AC\\ 12 + AC > 9 \end{cases}$$. If you list the integers satisfying all 6 inequalities, the possible values would be 4, 5, 6, 7, 8.

May 14, 2022


text:
Back to Course

0% Complete
0/0 Steps

• ## Do you like this content?

Lesson 9, Topic 2
In Progress

# Excitation & Ionization Energies

Lesson Progress
0% Complete

The energy absorbed or acquired by an electron to move to higher energy level is called excitation energy. Ionization energy is the energy absorbed by an electron to move it out completely from an atom.

An electron at ground state requires -13.6ev to free it from attraction of the nucleus.

Ionization energy of electron at first energy level is -3.39ev

Colour and Light Frequency

When an electron falls from a higher energy level to a lower energy level, it gives out excess energy in form of radiation. Therefore,

Frequency of radiation, f = $$\frac{\Delta E}{h}$$

Wavelength of height radiated in relation to quantum energy is

∆E = Ei – Ef = hf (where i and f indicate initial and final energy levels)

Ei – Ef = $$\frac{hc}{\lambda}$$

Wavelength and frequency are related to colours. Red light has a larger wavelength and low frequency while a violet colour has a shorter wavelength and higher frequency.

Example

The ground state energy for a hydrogen atom is 6.4×10-19J. If an electron drops from 22.8×10-19J energy to the ground state, calculate the frequency of the emitted radiation (h = 6.6×10-34Js)

Solution

E1 – E0 = hf

f = $$\frac{E_1 \; – \; E_0}{h}$$

f = $$\frac{2.28 \times 10^{-19} \; – \; 6.4 \times 10^{-19}}{6.6\times 10^{-34}}$$

f = -9.6×10-14Hz

error:


text:
# Number of $9-$digit numbers, all digits are different and nonzero and having no consecutive digits in consecutive positions

I am trying to solve a problem: We are asked to find the number of $9-$digit numbers by using the digits from $1$ to $9$ only once. There is also one more restriction. Consecutive digits should not be positioned side by side.

For example, $814953627$ is convenient while $8\mathbf{21}574936$ is not.

It seems a hard problem to me. $1$ and $9$ have one consecutive digit while others have two. This makes the problem harder a bit. So I tried to establish a recurrence relation. For $2\leq n\leq 9$, if the number of such numbers is $A_n$, we can use $A_{n-1}$. For each such $(n-1)-$digit numbers, we can find $n-2$ such $n-$digit numbers. Let me give an example, if $n=5$, and we have such a $4-$digit number, $3142$ for instance, we have three position to place digit $5$. Therefore $$A_n = (n-2)A_{n-1} + \cdots$$ Of course this is not the only way to have such an $n-$digit number. We also place the digit $n$ between two consecutive digits. Again if we take $n=5$, and if we have an inconvenient $4-$digit number $4231$, we can place the digit $5$ between $2$ and $3$, and we obtain a convenient $5-$digit number $42531$. However, in this case, we must have only two digits positioned side by side and one of them must not be $n-1$. So, if we say $B_n$ the number of $n-$digit numbers whose digits vary between $1$ and $n$ and it has two and only two consecutive digits in consecutive positions such that consectuive digits are different than $n$, then we have $$A_n = (n-2)A_{n-1} + B_{n-1}.$$ However, we need to have one more recurrence ralation in order to find $B_{n-1}$. I could not find yet. What should I do? Trying to solve by using a completely different method or going over $B_n$? Your helps make me happy for both cases.

The first step of any problem in enumerative combinatorics is to compute the first few cases, then look the sequence up on OEIS. If we do that here, we find A002464:

Hertzsprung's problem: ways to arrange n non-attacking kings on an n X n board, with 1 in each row and column. Also number of permutations of length n without rising or falling successions.

There is no particularly nice formula for $A_n$, which dashes our hopes of finding a particularly nice solution.

Your approach of finding $A_n$ in terms of $A_{n-1}$ and $B_{n-1}$ seems like it might possibly lead to the recurrence $$A_n = (n+1)A_{n-1} - (n-2)A_{n-2} - (n-5)A_{n-3} + (n-3) A_{n-4}$$ after a lot more work. But the original source for this recurrence finds it algebraically, so it's not clear if a combinatorial interpretation is even known.

Taking an inclusion-exclusion type approach to this problem is slightly more straightforward. For this, we want to compute the number of $n$-digit numbers that at least contain some $r$ pairs of adjacent consecutive digits, in $c$ "clumps". For example, in $843256917$, there are $r=3$ adjacent pairs total: $(4,3)$, $(3,2)$, and $(5,6)$, in two clumps: $432$ and $56$.

We can:

• permute the $c$ clumps and $n-r-c$ elements outside the clumps ($n-r$ objects total) in $(n-r)!$ ways,
• orient the clumps in $2^c$ ways,
• choose the sizes of the $c$ clumps (each with size at least $2$, total size $r+c$), in $\binom{r-1}{c-1}$ ways, and
• choose the sizes of the $n-c+1$ gaps between the largest element of one clump and smallest element of the next, plus the start and end (each gap at least $0$, total size of gaps $n-r-c$) in $\binom{n-r}{c}$ ways.

This gives us the formula $$A_n = n! + \sum_{r=1}^{n-1} (-1)^r (n-r)! \sum_{c=1}^r 2^c \binom{r-1}{c-1} \binom{n-r}{c}.$$

(See the Art of Problem Solving thread for more discussion of this formula.)

Finally, we can approximate $A_n$ fairly closely by an asymptotic formula: there are $n-1$ pairs of consecutive elements, which can be adjacent in a random permutation with probability $\frac{2}{n-1}$. Assuming independence (falsely), there is a a $(1 - \frac{2}{n-1})^{n-1} \approx e^{-2}$ chance that no pair of consecutive elements is adjacent, which implies that $A_n \approx e^{-2} n!$.

• Thanks for this nice solution and explanation. – faith Mar 17 '17 at 19:11


text:
When forces F1, F2, F3 are acting on a particle of mass m such that F2 and F3 are mutually perpendicular, then the particle remains stationary. If the force F1 is now removed then the acceleration of the particle is

(1) ${F}_{1}/m$

(2) ${F}_{2}{F}_{3}/m{F}_{1}$

(3) $\left({F}_{2}-{F}_{3}\right)/m$

(4) ${F}_{2}/m$

Concept Videos :-

#7-Solved-Examples-1
#8-Solved-Examples-2
#9-Solved-Examples-3
#10-Solved-Examples-4
#11-Solved-Examples-5
#12-Solved-Examples-6

Concept Questions :-

Application of laws
Explanation is a part of a Paid Course. To view Explanation Please buy the course.

Difficulty Level:


text:
In applied mathematics, the Ostrogradsky instability is a feature of some solutions of theories having equations of motion with more than two time derivatives (higher-derivative theories). It is suggested by a theorem of Mikhail Ostrogradsky in classical mechanics according to which a non-degenerate Lagrangian dependent on time derivatives higher than the first corresponds to a Hamiltonian unbounded from below. As usual, the Hamiltonian is associated with the Lagrangian via a Legendre transform. The Ostrogradsky instability has been proposed as an explanation as to why no differential equations of higher order than two appear to describe physical phenomena.[1] However, Ostrogradsky's theorem does not imply that all solutions of higher-derivative theories are unstable as many counterexamples are known.[2][3][4][5][6][7][8]

## Outline of proof [9]

The main points of the proof can be made clearer by considering a one-dimensional system with a Lagrangian ${\displaystyle L(q,{\dot {q}},{\ddot {q}})}$. The Euler–Lagrange equation is

${\displaystyle {\frac {\partial L}{\partial q}}-{\frac {d}{dt}}{\frac {\partial L}{\partial {\dot {q}}}}+{\frac {d^{2}}{dt^{2}}}{\frac {\partial L}{\partial {\ddot {q}}}}=0.}$

Non-degeneracy of ${\displaystyle L}$ means that the canonical coordinates can be expressed in terms of the derivatives of ${\displaystyle {q}}$ and vice versa. Thus, ${\displaystyle \partial L/\partial {\ddot {q}}}$ is a function of ${\displaystyle {\ddot {q}}}$ (if it was not, the Jacobian ${\displaystyle \det[\partial ^{2}L/(\partial {{\ddot {q}}_{i}}\,\partial {\ddot {q}}_{j})]}$ would vanish, which would mean that ${\displaystyle L}$ is degenerate), meaning that we can write ${\displaystyle q^{(4)}=F(q,{\dot {q}},{\ddot {q}},q^{(3)})}$ or, inverting, ${\displaystyle q=G(t,q_{0},{\dot {q}}_{0},{\ddot {q}}_{0},q_{0}^{(3)})}$. Since the evolution of ${\displaystyle q}$ depends upon four initial parameters, this means that there are four canonical coordinates. We can write those as

${\displaystyle Q_{1}:=q}$
${\displaystyle Q_{2}:={\dot {q}}}$

and by using the definition of the conjugate momentum,

${\displaystyle P_{1}:={\frac {\partial L}{\partial {\dot {q}}}}-{\frac {d}{dt}}{\frac {\partial L}{\partial {\ddot {q}}}}}$
${\displaystyle P_{2}:={\frac {\partial L}{\partial {\ddot {q}}}}}$

The above results can be obtained as follows. First, we rewrite the Lagrangian into "ordinary" form by introducing a Lagrangian multiplier as a new dynamic variable ${\displaystyle \lambda }$

${\displaystyle L(q,{\dot {q}},{\ddot {q}})\to {\tilde {L}}=L(Q_{1},{\dot {Q_{1}}},{\dot {Q_{2}}})-\lambda (Q_{2}-{\dot {Q_{1}}})}$,

from which, the Euler-Lagrangian equations for ${\displaystyle Q_{1},Q_{2},\lambda }$ read

${\displaystyle Q_{1}:{\frac {d}{dt}}{\frac {\partial L}{\partial {\dot {Q_{1}}}}}+{\dot {\lambda }}-{\frac {\partial L}{\partial Q_{1}}}=0}$,
${\displaystyle Q_{2}:{\frac {d}{dt}}{\frac {\partial L}{\partial {\dot {Q_{2}}}}}+{\lambda }=0}$,
${\displaystyle \lambda :Q_{2}-{\dot {Q_{1}}}=0}$,

Now, the canonical momentum ${\displaystyle P_{1},P_{2}}$ with respect to ${\displaystyle {\tilde {L}}}$ are readily shown to be

${\displaystyle P_{1}={\frac {\partial {\tilde {L}}}{\partial {\dot {Q_{1}}}}}={\frac {\partial L}{\partial {\dot {Q_{1}}}}}+\lambda ={\frac {\partial L}{\partial {\dot {Q_{1}}}}}-{\frac {d}{dt}}{\frac {\partial L}{\partial {\dot {Q_{2}}}}}}$
${\displaystyle P_{2}={\frac {\partial {\tilde {L}}}{\partial {\dot {Q_{2}}}}}={\frac {\partial {L}}{\partial {\dot {Q_{2}}}}}}$

while

${\displaystyle P_{\lambda }=0}$

These are precisely the definitions given above by Ostrogradski. One may proceed further to evaluate the Hamiltonian

${\displaystyle {\tilde {H}}=P_{1}{\dot {Q_{1}}}+P_{2}{\dot {Q_{2}}}+p_{\lambda }{\dot {\lambda }}-{\tilde {L}}=P_{1}Q_{2}+P_{2}{\dot {Q_{2}}}-{L}}$,

where one makes use of the above Euler-Lagrangian equations for the second equality. We note that due to non-degeneracy, we can write ${\displaystyle {\ddot {q}}={\dot {Q_{2}}}}$ as ${\displaystyle a(Q_{1},Q_{2},P_{2})}$. Here, only three arguments are needed since the Lagrangian itself only has three free parameters. Therefore, the last expression only depends on ${\displaystyle P_{1},P_{2},Q_{1},Q_{2}}$, it effectively serves as the Hamiltonian of the original theory, namely,

${\displaystyle H=P_{1}Q_{2}+P_{2}a(Q_{1},Q_{2},P_{2})-L(Q_{1},Q_{2},P_{2})}$.

We now notice that the Hamiltonian is linear in ${\displaystyle P_{1}}$. This is a source of Ostrogradsky instability, and it stems from the fact that the Lagrangian depends on fewer coordinates than there are canonical coordinates (which correspond to the initial parameters needed to specify the problem). The extension to higher dimensional systems is analogous, and the extension to higher derivatives simply means that the phase space is of even higher dimension than the configuration space.

## Notes

1. ^ Motohashi, Hayato; Suyama, Teruaki (2015). "Third-order equations of motion and the Ostrogradsky instability". Physical Review D. 91 (8): 085009. arXiv:1411.3721. doi:10.1103/PhysRevD.91.085009. S2CID 118565011.
2. ^ Pais, A.; Uhlenbeck, G. E. (1950). "On Field theories with nonlocalized action". Physical Review. 79 (145): 145–165. doi:10.1103/PhysRev.79.145. S2CID 123644136.
3. ^ Pagani, E.; Tecchiolli, G.; Zerbini, S. (1987). "On the Problem of Stability for Higher Order Derivatives: Lagrangian Systems". Lett. Math. Phys. 14 (311): 311–319. doi:10.1007/BF00402140. S2CID 120866609.
4. ^ Smilga, A. V. (2005). "Benign versus malicious ghosts in higher-derivative theories". Nucl. Phys. B. 706 (598): 598–614. arXiv:hep-th/0407231. doi:10.1016/j.nuclphysb.2004.10.037. S2CID 2058604.
5. ^ Pavsic, M. (2013). "Stable Self-Interacting Pais-Uhlenbeck Oscillator". Mod. Phys. Lett. A. 28 (1350165). arXiv:1302.5257. doi:10.1142/S0217732313501654.
6. ^ Kaparulin, D. S.; Lyakhovich, S. L.; Sharapov, A. A. (2014). "Classical and quantum stability of higher-derivative dynamics". Eur. Phys. J. C. 74 (3072). arXiv:1407.8481. doi:10.1140/epjc/s10052-014-3072-3. S2CID 54059979.
7. ^ Pavsic, M. (2016). "Pais-Uhlenbeck oscillator and negative energies". Int. J. Geom. Methods Mod. Phys. 13 (1630015). arXiv:1607.06589. doi:10.1142/S0219887816300154.
8. ^ Smilga, A. V. (2017). "Classical and quantum dynamics of higher-derivative systems". Int. J. Mod. Phys. A. 32 (1730025). arXiv:1710.11538. doi:10.1142/S0217751X17300253. S2CID 119435244.
9. ^ Woodard, R.P. (2007). "Avoiding Dark Energy with 1/R Modifications of Gravity". The Invisible Universe: Dark Matter and Dark Energy (PDF). Lecture Notes in Physics. Vol. 720. pp. 403–433. arXiv:astro-ph/0601672. doi:10.1007/978-3-540-71013-4_14. ISBN 978-3-540-71012-7. S2CID 16631993.


text:
## Prealgebra (7th Edition)

$\frac{5y}{16}$
We can simplify the fraction $\frac{10y}{32}$ by factoring out 2 from each of the terms. $\frac{10y}{32}$ =$\frac{10y\div2}{32\div2}$ =$\frac{5y}{16}$