text:
# ACT Math Practice Test 6

Difficulty Level – 3: Medium / Difficult

Directions: Solve each problem and then click on the correct answer. You are permitted to use a calculator on this test.

Congratulations - you have completed . You scored %%SCORE%% out of %%TOTAL%%. Your performance has been rated as %%RATING%%
 Question 1

 A −2 B −1 C 0 D 1 E 2
Question 1 Explanation:
The correct answer is (C). This initially looks very complicated; however, recall that i is equal to the square root of −1, so i2 is equal to −1. Evaluating the numerator of the expression on the left gives us 0 and because we are dividing the first expression by the second and 0 divided by anything is 0, the entire expression evaluates to 0.
 Question 2
What is the sum of the x and y coordinates of the midpoint between the points (−2, 9) and (10, −4)?

 A 3.5 B 5 C 6.5 D 7.5 E 8
Question 2 Explanation:
The correct answer is (C). Recall midpoint formula is the average of the x values and the average of the y values in (x,y) coordinate form.

First find the x coordinate midpoint:
(10 + (−2)) ÷ 2
= 4

Then find the y coordinate midpoint:
(9 + (−4)) ÷ 2
=2.5

Add them together to get the sum:
4 + 2.5 = 6.5
 Question 3
A group of 6 students are going to have a vote to determine who should be President, Vice President, Secretary, and Treasurer with only 1 person per job. How many different groups can be formed from the 6 students?

 A 30 B 45 C 90 D 180 E 360
Question 3 Explanation:
The correct answer is (E). In approaching this problem, consider the number of options the students have for each role. As a role is taken up, there is 1 less student to fill the next role. For President there are 6 options, for Vice President 5 options, for Secretary 4 options, and for Treasurer 3 options. Multiply each of these to find 360 different groups:
6 * 5 * 4 * 3 = 360
 Question 4

In the figure above, A, C, D, and E are collinear; B, C, and F are collinear; and the angles at B, D, and F are right angles, as marked. Which of the following statements is NOT justifiable from the given information?

 A AB is parallel to EF. B BC is congruent to CF. C EF is perpendicular to BF. D Angle BCA is congruent to angle DCF. E Triangle BAC is similar to triangle DCF.
Question 4 Explanation:
The correct answer is (B). Solve this by process of elimination.

A: True: AB and EF are both perpendicular to line BCF.
C: True: Angle F is a right angle, so the two lines are perpendicular.
D: True: Angle BCA and angle DCF are vertical angles, so they must be equal.
E: True: Angle ABC = angle CDF (they are both right angles).

Angle BCA = angle DCF (see statement D). Therefore, angle BAC must equal angle DFC (since the other two angles are equal, and the three angles total to 180). Since the two triangles have three corresponding angles, they are similar. B can be false.

Although we know that triangles ABC and CDF are similar, we do not know that they are congruent. So these sides may be unequal.
 Question 5
If (3.1358)(10x) = 0.0000031358 what is the value of x?

 A −7 B −6 C −5 D 6 E 7
Question 5 Explanation:
The correct answer is (B). The easiest way to solve this problem is to count how many places the decimal moves from the number on the left to the number on the right. Our decimal moves 6 places to the left, so x = −6.
 Question 6
A triangle is composed of angles represented as:

3x + 10, −2x + 40, and x + 40

What is the value of x?

 A 45 B 50 C 55 D 60 E 65
Question 6 Explanation:
The correct answer is (A). Recall that the angles of a triangle sum to 180 degrees:
3x + 10 + −2x + 40 + x + 40 = 180
2x + 90 = 180
2x = 90
x = 45
 Question 7
Choose an expression that is equivalent to the following:

 A B C D E
Question 7 Explanation:
The correct answer is (E). Begin by distributing the 3y through the parentheses to get −2x + 6xy − 12y as the numerator. Factor out a −2 to get −2(x − 3xy+ 6y), also factor out a −2 from the denominator to get −2(−2x + y), eliminate the −2 to get numerator of x − 3xy + 6y and denominator of y − 2x.
 Question 8

The curve y = 0.01x2 - 3x + 150 for 0 ≤ x ≤ 100 and the line segment from F(0,100) to G(100,0) are shown in the standard (x, y) coordinate plane provided. To the nearest integer, what is the y-coordinate for the point on the curve with x-coordinate 50?

 A 0 B 25 C 50 D 75 E 100
Question 8 Explanation:
The correct answer is (B). Plug the given x value into the given equation:
y = 0.01(502) − 3(50) + 150
y = .01(2500) − 150 + 150
y = 25 − 150 + 150
y = 25
 Question 9
If the number 89.8756 is rounded to the nearest hundredth, what will be the sum of the tenths and hundredths place of the resulting number?

 A 10 B 12 C 14 D 16 E 18
Question 9 Explanation:
The correct answer is (D). Begin by rounding the number to the nearest hundredth: 89.88. Now add the tenths place, 8, and the hundredths, 8, to get 16.
 Question 10
On the Cartesian plane, what is the distance between the points (0,0) and (5,−5)?

 A 5 B $\sqrt{50}$ C $\sqrt{60}$ D $\sqrt{75}$ E 10
Question 10 Explanation:
The correct answer is (B). One way to do this problem is to use the distance formula right away. Another way to do it is to graph the points and see that this is a right triangle with side lengths 5 and 5 so our hypotenuse (or the distance between the points) is $5\sqrt{2}$ which is equal to the square root of 50.
Once you are finished, click the button below. Any items you have not completed will be marked incorrect.
There are 10 questions to complete.
 ← List →


text:
# Lim X → 7 4 − √ 9 + X 1 − √ 8 − X - Mathematics

$\lim_{x \to 7} \frac{4 - \sqrt{9 + x}}{1 - \sqrt{8 - x}}$

#### Solution

$\lim_{x \to 7} \left[ \frac{4 - \sqrt{9 + x}}{1 - \sqrt{8 - x}} \right]$ It is of the form $\frac{0}{0}$

Rationalising the numerator and the denominator:

$\lim_{x \to 7} \left[ \frac{\left( 4 - \sqrt{9 + x} \right)}{1} \times \frac{\left( 4 + \sqrt{9 + x} \right)}{\left( 4 + \sqrt{9 + x} \right)} \times \frac{1}{\left( 1 - \sqrt{8 - x} \right)} \times \frac{\left( 1 + \sqrt{8 - x} \right)}{\left( 1 + \sqrt{8 - x} \right)} \right]$

=  $\lim_{x \to 7} \left[ \frac{16 - \left( 9 + x \right)}{\left( 4 + \sqrt{9 + x} \right)} \times \frac{\left( 1 + \sqrt{8 - x} \right)}{1 - \left( 8 - x \right)} \right]$

=  $\lim_{x \to 7} \left[ \frac{- 1\left( - 7 + x \right)\left( 1 + \sqrt{8 - x} \right)}{\left( 4 + \sqrt{9 + x} \right)\left( - 7 + x \right)} \right]$

=  $\lim_{x \to 7} \left[ \frac{- \left( 1 + \sqrt{8 - x} \right)}{4 + \sqrt{9 + x}} \right]$

= $- \left( \frac{1 + \sqrt{8 - 7}}{4 + \sqrt{9 + 7}} \right)$

=  $\frac{- 2}{4 + 4}$

=  $\frac{- 1}{4}$

Is there an error in this question or solution?

#### APPEARS IN

RD Sharma Class 11 Mathematics Textbook
Chapter 29 Limits
Exercise 29.4 | Q 15 | Page 28

format: plain


text:
# A replacement for NextPermutation in Combinatorica [duplicate]

Does anyone know of a replacement for NextPermutation in Combinatorica? The problem with loading Combinatorica is that it interferes with new functionality which I also want to use. I need to generate all the permutations of a list in lexicographic order one by one. Thanks for your help.

• If you want all permutations in canonical order just use Permutations For perm = Permutations[{a, b, c, d, e, f, g}]; then OrderedQ[perm] evaluates to True Oct 6, 2019 at 15:11
• @BobHanlon The problem with this approach is that you get all the permutations at once in memory, which I want to avoid ... I want to access them one by one, else there are too many ... there are close to 40 M permutations with lists that have 11 members, too many to have in memory, but it is possible with some time to look at each one of them and seek the property I want ... does this make sense?
– EGME
Oct 6, 2019 at 15:17
• Can you explain more about what do you need to do? (Not all people here might be familiar with the Combinatorica package). Oct 6, 2019 at 15:33
• @TumbiSapichu Right: I would like to access each and all of the permutations of a list, one at a time. A function like Permutations that returns all the permutations is of no use, given the large number of permutations that I need to inspect. The logical way make sure you access each and every permutation is to do so in some order, say, the lexicographic order. Does this make sense? So the function NextPermutation applied to the list {1,2,3} would return {1,3,2} ... essentially I want a function that implements this ... it used to exist, in the Combinatorica package ... contd.
– EGME
Oct 6, 2019 at 15:38
• @TumbiSapichu The problem with loading Combinatorica is that it overlaps with functionality that has replaced some of what is in there ...
– EGME
Oct 6, 2019 at 15:38

See page 57 of the book Computational Discrete Mathematics by Pemmaraju and Skiena.

NextPermutation[l_List] := Sort[l] /; (l === Reverse[Sort[l]])

NextPermutation[l_List] :=
Module[{n = Length[l], i, j, t, nl = l},
i = n - 1;
While[Order[nl[[i]], nl[[i + 1]]] == -1, i--];
j = n;
While[Order[nl[[j]], nl[[i]]] == 1, j--];
{nl[[i]], nl[[j]]} = {nl[[j]], nl[[i]]};
Join[Take[nl, i], Reverse[Drop[nl, i]]]
]

For example:

NextPermutation[{8, 7, 6, 5, 4, 3, 2, 1}]

{1, 2, 3, 4, 5, 6, 7, 8}

NextPermutation[{7, 12, 4, 1, 3, 10, 5, 6, 8, 11, 2, 9}]

{7, 12, 4, 1, 3, 10, 5, 6, 8, 11, 9, 2}

• Thank you, this is quite useful, not having the book - even if ideally, I want a “plug and play” replacement which is as fast as possible - thanks once again!
– EGME
Oct 7, 2019 at 7:38
• I should accept one of the two answers if nothing else comes, the problem is choosing one of the two!
– EGME
Oct 7, 2019 at 7:39
• Just as an extra remark: if you change the instances such as Order[x, y] == 1 (which doesn't compile) with OrderedQ[{x, y}] (which does), you can plonk the whole thing into Compile and get a much faster version for integers. Oct 7, 2019 at 11:21

The best way for me to do what you are asking for is to, if I remember correctly from the last time I did something like this.

1. Open up Combinatorica.m in a fresh notebook. It contains what looks like Mathematica code and Mathematica is happy to do this. The last time I looked the Combinatorica.m file is still there buried down inside the installed Mathematica files. Try searching your entire file system for the name if you can't find it.

2. Scroll down and find the well written self contained definition of NextPermutation

3. Scrape that definition into your clipboard

4. Close the notebook without changing Combinatorica.m

6. Paste the definition into your notebook, along with credits, where it came from and how to find it and do this again if you need to

and you are ready to go with your own personal copy of NextPermutation in your notebook without any of the other definitions from combinatorica.m

• Thank you, this is also quite useful ... I haven’t tried it, but I think I will try it ... it solves a more general problem, and it is almost like plug and play, although this is not as optimized as might be ... as in the answer above, I would accept one of the two answers, were it not difficult to choose one, and waiting also for something else that might come around
– EGME
Oct 7, 2019 at 7:41
• Note that FindFile["Combinatorica"] gives a hint where to look for the file. Oct 7, 2019 at 13:22
• @EGME I don't assume that readers have a copy of "Computational Discrete Mathematics" on their shelves, although I've recommended that in the past. It seems more and more when I recommend looking in a book that the response is "Oh GAWD! Not a dead tree! Can't you just tell me where I can scrape the code." I'm not kidding, I've gotten that response from people.
– Bill
Oct 8, 2019 at 15:28
• @Bill Right ... I use libraries, or look for electronic copies of books ... many books now exist in electronic form ... maybe this one does, and I just didn’t look well enough. ... this one really seems like a book that ought to be in a shelf as you say, classics are worth getting even if in print, I think.
– EGME
Oct 8, 2019 at 15:51

If you have a numeric list, we can get a substantial speedup by using Compile.

nextPerm = Compile[{{operm, _Integer, 1}},
Module[{i, j, perm},
perm = operm;
j = Length[perm];
i = j-1;
While[i > 0 && perm[[i]] > perm[[i+1]], i--];
If[i == 0, Return[Reverse[perm]]];
While[perm[[j]] < perm[[i]], j--];
perm[[{i, j}]] = perm[[{j, i}]];
Join[perm[[1 ;; i]], perm[[-1 ;; i+1 ;; -1]]]
],
CompilationTarget -> "C",
RuntimeOptions -> "Speed"
];

Cycling through all permutations:

Nest[nextPerm, Range[11], 11!] // AbsoluteTiming

{29.7751, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}}

Compare to Combinatorica:

<<Combinatorica
Nest[NextPermutation, Range[11], 11!] // AbsoluteTiming

{637.568, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}}

• Thank you ... this is indeed quite useful ... very significant speed up ...
– EGME
Oct 7, 2019 at 14:42

If you ever need a definition from an old function like this, you can try this trick to see if you can access the definition of the function directly:

<<Combinatorica
GeneralUtilitiesPrintDefinitions[NextPermutation]

• The source code of Combinatorica is available. It's better to read the source file, in case there are any comments. Oct 7, 2019 at 11:21

I have made use of commands from Combinatorica as well as more recent built-in commands, in the same code, and where their names have clashed, I have tried to differentiate between them by referring to them as, for example,

CombinatoricaSymmetricGroup

for the Combinatorica one, and

SystemSymmetricGroup

for the more recent one, rather than just SymmetricGroup. This seems to have worked for me.

• I'd be curious to know what it is that you need from Combinatorica that you cannot get elsewhere. Oct 7, 2019 at 11:22
• SetPartitions and RankSetPartition were two examples, I seem to remember, and I think that for some reason I preferred the Combinatorica version of SymmetricGroup, if indeed it's any different from the new one. Oct 7, 2019 at 11:37
• @Szabolcs I found a nasty graph related bug which calls for a replacement. However, I do not wish to post about bugs here, so I could send you a very short notebook with the example if you can be reached? By the way, why was this question closed ... I did not see parallel prior questions with these good answers, although it really doesn’t matter ... it has served its purpose, but that is not the reason given for its closure ... Apologies for asking, and thank you at the same time, I thought you might know, and also, be interested in the first issue ...
– EGME
Nov 29, 2019 at 16:43


text:
# Uun bmeo vyigirls come0n letshaves€xcomefast

Uun bmeo vyi
girls
come0n
lets
have
s€x
come
fast

### What is the width? (8 points) (NO LINKS)

What is the width? (8 points) (NO LINKS)...

### What was the impact of the internment?(interment camps)

What was the impact of the internment? (interment camps)...

### Kenneth a competitor in cup stscking claims that his average stacking time is 8.2 seconds. during a practice session kenneth

Kenneth a competitor in cup stscking claims that his average stacking time is 8.2 seconds. during a practice session kenneth has a sample stacking time mean of 7.8 seconds based on trials. at the 4% sugnificant level does the data provide sufficient evidence to conclude...

### Which of the following best describes death in 'because i could not stop for death' a. a courteous friend

Which of the following best describes death in "because i could not stop for death" a. a courteous friend b. field of grain c. brooding master d. gossamer gown...

### What do holes in igneous rocks indicate about the cooling process of the magma?AThe magma cooled too quickly for gas to escape.BThe molten rock cooled

What do holes in igneous rocks indicate about the cooling process of the magma? A The magma cooled too quickly for gas to escape. B The molten rock cooled slowly. C The magma cooled in layers. D The rock cooled with fossils in each of the holes or spaces....

### Suppose that a worker in country a can make either 10 ipods or 5 tablets each year. country a? has 100

Suppose that a worker in country a can make either 10 ipods or 5 tablets each year. country a? has 100 workers. suppose a worker in country b can make elther 2 ipods or 10 tablets each year. country b has 200 workers. a bundle of goods that country b could potentially make would be: multiple choic...

### Every saturday morning jack read for 30in play baskeball for 60 min and ride his bike if jack

Every saturday morning jack read for 30in play baskeball for 60 min and ride his bike if jack...

### Economists occasionally speak of 'helicopter money' as a shorthand approach to explaining increases in the money supply. Suppose the chair of the Federal

Economists occasionally speak of "helicopter money" as a shorthand approach to explaining increases in the money supply. Suppose the chair of the Federal Reserve flies over the country in a helicopter, dropping 10,000,000 newly printed $100 bills (a total of$1 billion). By how much will the money s...

### How does the text structure in passage one contribute to the plot of the story

How does the text structure in passage one contribute to the plot of the story...
Determine which lines if any can be proved parallel given the angle relationship. Give the converse to justify your answer. Plz help and show your work :) $Determine which lines if any can be proved parallel given the angle relationship. Give the converse$...


text:
# Probablity - A question about Poisson distribution and Stirlings Formula leading up to the central limit theorem

The goal of this problem is to prove that $P(S_n = k)\sqrt{2\pi n} \rightarrow e^{-\frac{x^2}{2}}$ by using Stirling's formula.

Here is what is given:

1) $S_n = \sum_1^n X_i$, where $\{X_i\}$ are independent, with Poisson distribution, mean 1.

2) Stirling's formula is that $\dfrac{n!}{n^n e^{-n} \sqrt{2 \pi n}} \rightarrow 1$.

3) $\frac{k-n}{\sqrt n} \rightarrow x$

Here is what I don't understand:

1) What does it mean for $\frac{k-n}{\sqrt n} \rightarrow x$? As what approaches $\infty$? I thought that $k$ and $n$ were integers? How are they related? Are they really integer-valued functions? Or is $k$ a function of $n$, somehow? None of this is clear from the context.

Here is what I have, though I'm assuming all limits are in terms of $n$:

1) $-\frac{(n-k)^2}{2n} \rightarrow \frac{-x^2}{2}$.

2) Since $\sqrt{n} \rightarrow \infty$, we know that $(n-k)^2 \rightarrow \infty$.

3) There is a lemma which I can use to show that $(1 + (\frac{-1}{2n}))^{(n-k)^2} \rightarrow e^\frac{-x^2}{2}$. (The lemma states that if $c_ja_j \rightarrow \lambda$ where $c_j \rightarrow \infty$ and $a_j \rightarrow 0$ then $(1+a_j)^{c_j} \rightarrow e^\lambda$).

4) Putting all this together yields that $$P(S_n = k)\sqrt{2\pi n} = \frac{e^{-n}n^k \sqrt{2\pi n} }{k!} = \frac{e^{-n} n^n \sqrt{2 \pi n}}{n!} \cdot \frac{n! n^k}{k! n^n}$$.

5) So what I would love to do is show that $\frac{n! n^k}{k! n^n} \rightarrow e^\frac{-x^2}{2}$, or equivalently, by using 3), that $|\frac{n! n^k}{k! n^n} - (\frac{2n-1}{2n})^{(n-k)^2}| \rightarrow 0$.

Any tips or insights or clarifications will be greatly appreciated.

Thanks

-
Treat $k$ as fixed. $n$=1,2,3,4,... is a sequence of integers approaching infinity. $k$ does not depend on $n$, but $P(S_n=k)$ clearly does depend on $n$. –  Silverfish Nov 6 '13 at 2:24
If what you say is true, then why does $(k-n)/\sqrt n$ not approach $-\infty$ –  user28877 Nov 6 '13 at 3:02
Bingo, that's exactly what it does! Think of it like the z score for your Sn. Let's take k as 10. When n is small, eg 3, it's unlikely Sn will be so high (add three Poisons with mean 1 and see). K is well above the expected value of $S_3$ and so has a positive z score. But when n is 50 it's very unlikely $S_{50}$ will be anywhere near as low as 10. K is now well below the mean and has a very negative z score. As n gets bigger the z score will get ever more negative.... –  Silverfish Nov 6 '13 at 3:32
Btw you can see it is like a z score when you realise $S_n$ is Poisson with parameter n so the mean and variance are both n and the standard deviation is the square root of that. –  Silverfish Nov 6 '13 at 3:46
Yes I see what you mean, though I still think that $(k-n)/\sqrt n$ cannot converge to $x \in \mathbb{R}$ unless $k$ is a function of $n$. Is this some kind of shorthand? –  user28877 Nov 6 '13 at 4:31


text:
# TR.5 Set Command Specification

This command allows you to set various general specifications for the analysis/design run.

## General Format

SET { NL i1 | {DISPLACEMENT i2 | PDELTA TOLERANCE i9} | SDAMP i3 | WARP i4 | ITERLIM i5 | PRINT i7 | NOPRINT DIRECT | SHEAR | ECHO { ON | OFF } | GUI i6 | { Z | Y } UP | DEFLECTION CUTOFF  f1 | FLOOR LOAD TOLERANCE f2 | EIGEN METHOD { LANCZOS | RITZ} }

Where:

## Description

The following SET commands contain values with associated units and should appear after a UNIT command and before the first JOINT command.

Table 1. Commonly used SET commands which take units
Command Parameter Description
SET NL i1 The SET NL command is used in a multiple analysis run if you want to add more primary load cases after one analysis has been performed. Specifically, for those examples which use the CHANGE command (see TR.38 Change Specification), if you want to add more primary load cases, the NL value should be set to the maximum number (or slightly more) with the SET NL command. The program will then be able to set aside additional memory space for information to be added later. This command should be provided before any joint, member or load specifications.

The value for i1 is the maximum number of primary load cases (NL). This value should not be much greater than the maximum number of primary load cases actually used in the model.

Note: If plates are present, the SET NL value includes the total number of primary and load combinations in the model.

SET DISPLACEMENT

i2 For PDELTA ANALYSIS with CONVERGE option there are two convergence methodologies to choose from (refer to TR.37.2 P-Delta Analysis Options for additional information)
1. The SET DISPLACEMENT i2 command is used to specify the convergence tolerance. If the Euclidean norm RMS displacement of two consecutive iterations changes less than the value entered, then that load case is converged. This command should be placed before the JOINT COORDINATE specification. The default tolerance value, i2 , is equal to the maximum span of structure divided by 120. The convergence tolerance for the Euclidean norm is difficult to know, so using this option is not recommended.
2. The SET PDELTA TOL i9 command selects this second method. Default tolerance value, i9 , is 0.01 inch. If the maximum change in each displacement dof from two consecutive iterations is less than ftol, then that load case is converged. This command should be placed before the JOINT COORDINATE specification and after a UNIT command.
Note: Both i2 and i9 are the P-Delta Convergence criteria input. There are two methods available, enter SET DISPLACEMENT i2 or SET PDELTA TOL i9 . Enter only one.
• i2 = If the change in the Euclidean norm of the displacement vector from one PDELTA iteration to the next is less than this convergence tolerance value; then the iteration has converged for the case being analyzed.
• i9 = If the maximum absolute change in displacement of each dof from one PDELTA iteration to the next is less than this convergence tolerance value; then the iteration has converged for the case being analyzed.

PDELTA TOLERANCE

i9
SET DEFLECTION CUTOFF f1 Used to arrest huge displacements in minor axis due to small delta effects.

f1 = If the absolute value of the maximum section displacement is less than f1 after two iterations; then it is converged. Rapidly diverging minor axis displacement will not occur until after two iterations. f1 is in current length units.

Used to specify the tolerance for out of plane nodes in a floor load. The program expects all nodes to lie in the same plain. If there is any minor variation in coordinates of the nodes, the program will excluded floor panels connected to those nodes. Hence, a tolerance value is used to so that all nodes with in the range (min. Y and min Y + tolerance).

Note: Inclined floor panels are defined separately using the floor group option.

Refer to TR.32.4.3 Floor Load Specification for details on specifying a plane for floor loads.

f2 = tolerance value used

The following SET commands have dimensionless input

Table 2. Other commonly used SET commands
Command Parameter Description
SET SDAMP i3 The SET SDAMP command will allow the damping of springs to be considered in computing the composite modal damping for each mode in a dynamic solution. This command is not used unless CDAMP ratios are also entered for the members and elements in the CONSTANTS command. Composite damping is generally only used if there are many modes in the dynamic solution and there are a wide range of damping ratios in the springs, members, or elements.

i3 = the damping ratio to be used for all springs in computing the modal composite damping in dynamics.

SET WARP i4 The SET WARP command will allow the I section member end warping restraint to be considered in calculating the torsional stiffness rigidity. Full or partial or no warping restraint are allowed.
SET ITERLIM i5

The SET ITERLIM command is for raising the maximum iteration limit above the default of 10 in tension/compression iterations. Since this iterative procedure will not necessarily converge, this option of more iterations may not help and should be used with caution. The minimum iteration limit that may be entered is 3. The maximum number if 150. Any value higher than this will be replaced with 150.

After any tension/compression analysis, the output file (file extension .ANL) should be scanned for warnings of non-convergence. Do not use results from non-converged cases.

i5 = Maximum number of tension/compression iterations.

SET PRINT i7 The following values can be used to suppress the described warnings or include the described additional results in the output:
• 1 = Omit zero stiffness message, Rotational zero stiffness message due to solids, and "Node not connected. OK if control/dependent" message.
• 2 = Omit Member in list does not exist message.
• 3 = Omit joint not connected message.
• 5 = Turn off floor load message.
• 8 = Omit self weight warnings.
• 10 = Turns on some iteration messages in direct analysis.
• 17 = Write rotational masses to mass text file; otherwise only translational masses written. Print scaled modal results for RSA and some force data by floor for RSA.

i7 = Used to suppress some warning messages or to include additional output.

SET NOPRINT DIRECT (n/a) Used to turn off the tau-b details in the output file when running a Direct Analysis (refer to TR.37.5 Direct Analysis).
SET SHEAR (n/a) The SET SHEAR command is for omitting the additional pure shear distortion stiffness terms in forming beam member stiffnesses. With this command you can exactly match simple textbook beam theory results.
SET ECHO (n/a) The SET ECHO ON command will activate and the SET ECHO OFF command will deactivate the echoing of input file commands in the output file. In the absence of the SET ECHO command, input file commands will be echoed back to the output file.
SET GUI i6 After the calculations are completed, and before the Analysis window is closed, the program creates several files for the purpose of displaying results in the post processing mode. In large models, this can be a time consuming process. If the user's goal is to look at results in the output file only (file extension .ANL) and does not intend to go into the post-processing mode, he/she could instruct the program to skip the process of creating those files. The SET GUI 1 may be specified immediately before the FINISH command, or somewhere near the beginning of the file after STAAD SPACE.

i6 = 1, Bypass forming data and files needed for post-processing.

SET { Z | Y } UP (n/a)

By default, the Y-axis is the vertical axis. However, the SET Z UP command may be used to model situations where Z-axis represents the vertical axis (direction of gravity load) of the structure. This situation may arise if the input geometry is created through some CAD software. This command will affect the default BETA angle specification. However, BETA can be set to a certain value for all members parallel to a particular global axis by using the MEMBER X (or Y or Z) type of listing. For additional information, see the CONSTANTs specification (see TR.26 Specifying and Assigning Material Constants).

Note: Both options follow the "right hand rule."

### Global axis orientation options in STAAD.Pro

The SET Z UP Command directly influences the values of the following input:
1. JOINT COORDINATE
2. Input for the PERFORM ROTATION Command
3. BETA ANGLE
Note: The following features of STAAD cannot be used with the SET Z UP command:
• Automatic Generation of Spring Supports for Mat Foundations
SET STAR i Instructs the program which solver to use. Refer to TR.0 STAAD Commands and Input Instructions for additional information.
Note: When SET STAR 3 is used and if the following limits are exceeded, then the solver will automatically switch to out-of-core:
1. Number of nodes >30,000
2. Number of nodes times the number of active primary load cases > 1,600,000
SET EIGEN METHOD { LANCZOS | RITZ } (n/a)

LANCZOS — Instructs the solver to use Arnoldi/Lanczos method for extraction of eigen vectors.

RITZ — Use load dependent Ritz vectors method for extraction of eigen vectors.

The use of either the Arnoldi/Lanczos method or the Ritz method require a STAAD.Pro Advanced license. If neither method is specified, the default method of Subspace-iteration is used.

Note: SET EIGEN METHOD RITZ is not supported by pushover analysis or steady state analysis. In the case of a pushover analysis, this is because the lateral load distribution is based on the eigen vector. If the command is present, a warning message is given in the output.

## Less frequently used SET commands

The following table contains a list of less frequently used SET commands

Command Default Description
SET INTERPOLATION { LIN | LOG }   LIN or LOG for spectra
SET NOSECT   No section results will be calculated
SET PLATE FLATNESS TOLERANCE f

Used to so specify a tolerance for the plate warping check. By default, plate warping is reported when there is a 30 degree angle (or larger) between the normal to two triangles which are formed by splitting a quad element. This splitting can be done two ways so there are four triangles. If any have more than the tolerance angle (in degrees) between them, then an error is reported.

The value f is given in degrees.

SET INPLANE ROTATION   In-plane rotation (MX) in plates will be ignored.
SET ENDFACTOR f   1.0 or -1.0 for combining spectrum cases
SET PROFILE s2   A command to define the path of the folder that contains the collection of databases of section property data in SQLite (.DB3) files. Note also that the GUI will use this as the location of the section profile databases.
SET NOWARNING   Switches off some warning messages.
SET USE DLL   Used plugin .dll for design (ACI code only)
SET RIGID DIAPHRAGM i 150

The number of diaphragms used. This command is used to reserve memory for the maximum number of diaphragms that may be defined in the model.

See section TR.28.2 Floor Diaphragm for more information on defining and using floor diaphragms in an analysis.
SET INCLINED REACTION   To obtain reactions at inclined supports in the inclined axis system.
SET GROUP DUPLICATES   Followed by an integer value which is used to specify the number of groups to which one model entity (node, member, plate, or solid object) may belong. Must be in the range of four to 100, inclusive. The default value is 10 groups.
SET CG TXT   Used to print section forces for generated load combinations to an external text file. See TR.35 Load Combination Specification for additional details. This command should be used only for review of data and not in normal circumstances as the resulting text file can be very large.
SET RS TXT   Used to print section forces for each of the modes for response spectrum load cases to an external text file. See TR.35 Load Combination Specification for additional details. This command should be used only for review of data and not in normal circumstances as the resulting text file can be very large.
SET NF TXT   Used to print section forces for each member corresponding to the critical load combination generation case to an external text file. See TR.35 Load Combination Specification for additional details. This command should be used only for review of data and not in normal circumstances as the resulting text file can be very large.
SET THCOPYS i

i = 4 (default)

i = number of TYPES that a given node-dof may be a part of in time history loading.

SET WARNING { ON | OFF }   Used to suppress warnings in the output (.anl) file when set to OFF (ON is default).
SET NOTE { ON | OFF }   Used to suppress notes in the output (.anl) file when set to OFF (ON is default).
SET DIVISION i   Set the number of divisions used in meshing for surfaces (default is 10)
SET MULTI { 1 | 2 }   If multi-linear analysis fails to converge, try entering SET MULTI 2 and re-running.
SET PARTICIPATION FACTOR   Compute participation factors as a numeric value in addition to the percentage of total mass usually displayed.
SET BUCKLING MODES i   Number of buckling modes computed with advanced solver. Default is i= 4.
SET BYPASS { DIS | FOR | EJS | EJF }

Bypass generating certain outputs for the graphical user interface.

• DIS = section displacements
• FOR = section force
• EJS = plate nodal stress
• EJF = plate nodal force


text:
Fundamental Limits on Correlated Catalytic State Transformations

Quantum state transformation is a fundamental problem in quantum resource theories. Resource theories offer a general framework to quantify the usefulness of quantum states and their inconvertibility under free operations. A resource theory is defined by a subset of quantum states called free states and a set of free operations with the property that map free states into free states. In this picture, the free states do not contain any resource and the free operations cannot create a resource state when acting on a free state. A prominent example is entanglement theory where entanglement is the resource, the free states are the separable states and the free operations are the local operations and classical communications (LOCC). Given a fixed state $\rho$, we call $\mathcal{FO}(\rho)$ the set of all $\rho'$ that can be reached from $\rho$ using free operations.

A natural question is whether a catalyst could enhance quantum state transformation. A catalyst is an ancillary system that assists the transformation but it is left unchanged at the end of the process. The term catalyst is borrowed from chemistry. Here, a catalyst is a substance that enables or increases the rate of a chemical reaction without itself changing during the process. We call $\mathcal{CO}(\rho)$ the set of all states $\rho'$ for which there exists a catalyst and a free operation which maps $\rho$ into $\rho'$ leaving the catalyst unchanged. More recently, a further relaxation has been studied where correlations between the catalyst and the target state after the transformation are allowed and can be used as a resource to enhance catalytic transformations. Similarly, we call $\mathcal{CCO}(\rho)$ the set of all states $\rho'$ for which a catalytic transformation with residual correlations from $\rho$ exists. In this case, at the end of the process, there are non-zero residual correlations between the catalyst and the output state $\rho'$. We show below an example of these sets for the classical resource theory of athermality.

In our work we study correlated catalytic transformations. Our main contribution is to find a trade-off between the residual correlation between the system and the catalyst at the end of the process and the resource of the catalyst that we need to prepare to perform the transformation. We find that for a large class of transformations, a small residual correlation between catalyst and target state implies that the catalyst needs to be highly resourceful. In fact, the resources required diverge in the limit of vanishing residual correlation. In the figure above, we show in red the set of output states that need a catalyst whose resources diverge as the correlations vanish.

Our work was presented at AQIS21, BIID’9, and QIP22 and it was published in Physical Review Letters.

This entry was posted in Uncategorized. Bookmark the permalink.


text:
# What is the most direct proof of the Riemann hypothesis for Dirichlet L-functions over function fields?

Let $$\mathbb{F}$$ be a finite field of order $$q$$, let $$m$$ be an irreducible polynomial in the ring $$\mathbb{F}[T]$$, and let $$\chi$$ be a Dirichlet character modulo $$m$$. Define the function field Dirichlet $$L$$-function $$L(s,\chi) := \sum'_f \frac{\chi(f)}{|f|^s}$$ where the sum is over monic polynomials in $$\mathbb{F}[T]$$, and $$|f| = q^{\mathrm{deg}(f)}$$ is the usual valuation. The Riemann hypothesis for this $$L$$-function asserts that the non-trivial zeroes of this $$L$$-function all lie on the line $$\mathrm{Re}(s) = \frac{1}{2}$$. An equivalent form of this result is that the error term in the prime number theorem for arithmetic progressions is of square root type in the function field setting.

The only way I know how to prove this is to show that such a Dirichlet $$L$$-function can be multiplied with other Dirichlet $$L$$-functions or zeta functions to create (up to some local factors) a Dedekind zeta function over some finite extension of $$\mathbb{F}[T]$$, which is essentially the local zeta function of some curve over $$\mathbb{F}$$, and at this point one can use any of the usual proofs of RH for such curves (Weil, Bombieri-Stepanov, etc.). But to get the finite extension I either need to appeal to some general theorem in class field theory (existence of ray class fields, which I understand to be a difficult result) or to explicitly construct the extension using Carlitz modules or something equivalent to such modules (the latter is discussed for instance in the answer to this other MathOverflow post).

My question is whether there is a more direct way to establish RH for Dirichlet L-functions over function fields without having to locate a suitable field extension (or whether there is some "soft" way to abstractly demonstrate the existence of such an extension without a huge amount of effort). For instance, is it possible to interpret the Dirichlet $$L$$-function directly as the zeta function of some $$\ell$$-adic sheaf? Or can the elementary methods of Stepanov type be adapted directly to the Dirichlet $$L$$-function (or perhaps the product of all $$L$$-functions of the given modulus $$m$$?

• But the curve you need is $y^n = m(x)$ if your character has order $n$, so you don't need any fancy theory to write down the curve. You can then write Stepanov's proof directly in terms of polynomials in $x$. See Stark's paper on hyperelliptic curves for $n=2$. – Felipe Voloch May 14 '19 at 23:44
• Felipe: for the $n=2$ case I can see the connection using quadratic reciprocity, but for higher $n$ what is the reciprocity relationship that links a Dirichlet character of modulus $m$ and order $n$ to the curve $y^n = m(x)$? I am a little surprised the answer is so simple given that the literature seems to tout the field extensions coming from Carlitz modules as the "correct" analogue of cyclotomic field extensions. (But perhaps this is more to handle the case when $n$ and $q$ share a common factor, which doesn't arise here?) – Terry Tao May 15 '19 at 1:19
• There is a general statement (Weil reciprocity) that works but the $n$-th power reciprocity for rational function fields (see e.g. Hasse, Number Theory, Ch 5, at the very end) is easy to prove and is enough to give the result. You are correct in your comment about the Carlitz module not being necessary in the prime to $q$ case. – Felipe Voloch May 15 '19 at 2:42
• Yes, to apply the results directly, we need $n|(q-1)$ and we can get around that by passing to an extension of some degree $d$. That changes the roots $\alpha$ of the $L$-functions to $\alpha^d$ (in the variable $q^{-s}$). – Felipe Voloch May 15 '19 at 17:52
• Regardless of the details in my answer, did you have a plan for how getting a $\ell$-adic sheaf interpretation would give a more direct proof? Don't you then have to define $\ell$-adic cohomology, set up the basic formalism, and give Deligne's proof of the Riemann hypothesis? Even with the simplifications for the special case of curves, that can't be less than a book. – Will Sawin May 16 '19 at 2:58

Switching from comment to answer because the comment thread is getting too long.

Let $$\# \mathbb{F}=q, t=q^{-s}$$ and consider $$L(t,\chi)$$. Then (by taking the logarithmic derivative of the Euler product)

$$L(t,\chi) = \exp (\sum_{n=1}^{\infty} S_n t^n/n )$$

where $$S_n = \sum_{\deg P | n} \chi(P)\deg P$$

and $$P$$ runs through irreducible polynomials of $$\mathbb{F}[T]$$.

Then for any integer $$d>0$$,

$$\prod_{\zeta^d =1} L(\zeta t,\chi) = \exp (\sum_{n=1}^{\infty} S_{dn} t^{dn}/n )$$

Now, if $$Q$$ is an irreducible polynomial of degree $$n$$ over the field of $$q^d$$ elements, then $$Q$$ has $$m$$ (some $$m|d$$) conjugates $$Q_i$$ over $$\mathbb{F}$$ and the product of these conjugates is an irreducible polynomial $$P$$ in $$\mathbb{F}[T]$$ so (edit: fixed error pointed out in comments)

$$\sum_i \chi(Q_i)\deg Q_i = (\sum \chi(Q_i))\deg Q = \chi(P)m\deg(Q) = \chi(P)\deg(P).$$

Using this, one checks that the equivalent of $$S_n$$ over the field extension equals $$S_{nd}$$ and this gives $$\exp (\sum_{n=1}^{\infty} S_{dn} t^n/n )$$ is the $$L$$-function in the extension field, say $$L_d(t,\chi)$$. Another way of stating this is $$\prod_{\zeta^d =1} L(\zeta t,\chi)= L_d(t^d,\chi)$$.The relation with the zeros follows. (This is e.g. in Weil, Basic Number Theory, Appendix 5, lemma 4 in much more generality and fancier language).

• You should mention that the character you call $\chi$ of $\mathbb F_{q^d} [T]$ is the original character $\chi$ composed with the norm map. – Will Sawin May 16 '19 at 3:00
• @WillSawin yes. – Felipe Voloch May 16 '19 at 3:03
• Sorry for being dense, but could you explain why one has $\sum \chi(Q_i)$ equal to $\chi(P)$? Even with Will's clarification, I don't see this. – Terry Tao May 16 '19 at 3:17
• @TerryTao I would write $S_n$ as $\sum_{ P \in \mathbb F_q[T], \deg P = n} \chi(P) \Lambda(P)$ where $\Lambda(P)$ is $0$ if $P$ is not a prime power and the degree of that prime power otherwise. Then we need to check $\sum_{ P \in \mathbb F_q[T], \deg P = dn} = \sum_{ Q \in \mathbb F_{q^d} [T], \deg Q = n} \chi(\operatorname{Norm}(Q)) \Lambda(Q))$. For $Q$ a prime power in $\mathbb F_{q^d}[T]$, the norm of $Q$ is a prime power in $\mathbb F_q[T]$, and the prime of $\mathbb F_q^d[T]$ will lie over the prime of $\mathbb F_q[T]$. – Will Sawin May 16 '19 at 3:28
• @TerryTao So breaking the sum into powers of primes lying over a given prime, we need to know that the total degree of the prime polynomials living over a given prime polynomial is the degree of that polynomial. This follows because their product is the base polynomial. – Will Sawin May 16 '19 at 3:31

Is it possible to interpret the Dirichlet $$L$$-function directly as the zeta function of some $$\ell$$-adic sheaf?

Yes and no. Yes in that it's possible to express the Dirichlet $$L$$-function directly as the zeta function of some $$\ell$$-adic sheaf. No in that doing so is essentially the same as constructing the relevant Galois extension, and so you're forced to again rely on an explicit construction or an abstract existence result. Indeed the relevant $$\ell$$-adic sheaf has rank one, so you get a homomorphism $$\pi_1^{et}( \operatorname{Spec} \mathbb F [T , m^{-1} ] ) \to \overline{\mathbb Q}_\ell^\times$$ but $$\pi_1^{et}( \operatorname{Spec} \mathbb F [T , m^{-1} ] )$$ is just a quotient of $$\operatorname{Gal} (\mathbb F (T))$$ so you can derive the abelian Galois extension from the $$\ell$$-adic sheaf.

whether there is some "soft" way to abstractly demonstrate the existence of such an extension without a huge amount of effort.

I don't think the explicit existence proof of the field extension is really that bad. I might regret saying this, but I don't think it's that much worse than the proof of power reciprocity.

An (I think) essentially self-contained proof using mainly elementary algebraic number theory is below:

Lemma:

Fix $$m$$ a polynomial of degree $$d$$ over $$\mathbb F_q$$.

Let $$k$$ be an algebraically closed field containing $$\mathbb F_q$$ and let $$c_0,\dots, c_{d-1}$$ be elements of $$k$$. If $$\operatorname{Res} ( c_0 + \dots + c_{d-1} X^{d-1} , m(X) ) \neq 0$$, then the solutions $$a_0,\dots, a_{d-1} \in k$$ with $$(a_0^q + \dots + a_{d-1}^{q} X^{d-1} ) = ( c_0 + \dots + c_{d-1} X^{d-1} ) ( a_0 + \dots + a_{d-1} X^{d-1} ) \mod m(X)$$ and $$\operatorname{Res} ( a_0 + \dots + a_{d-1} X^{d-1} , m(X) ) \neq 0$$ form exactly one orbit under the action of $$(\mathbb F_q[X]/m(X))^\times$$.

Proof: Multiplying by an element of $$(\mathbb F_q[X]/m(X))^\times$$ gives another solution, so the solutions form a union of orbits. The ratio between any two solutions is an element of $$(k[X]/m(x))^\times$$ with each coordinate equal to its own $$q$$th power, hence an element of $$(\mathbb F_q[X]/m(X))^\times$$, so there is at most one orbit. To check that there is at least one orbit, first note that if $$a_0,\dots, a_{d-1}$$ are independent transcendentals, then $$c_0,\dots, c_{d-1}$$ would be independent transcendentals (or otherwise there would be infinitely many solutions), so there exist solutions when $$c_0,\dots, c_{d-1}$$ are independent transcendentals. Given any tuple $$c_0,\dots, c_{d-1}$$ in $$k$$, take $$c'_0,\dots, c'_{d-1}$$ independent transcendentals in $$k' = k(c_0',\dots, c_{d-1}'$$, and then the coefficients of $$( c_0 + \dots + c_{d-1} X^{d-1})( c_0' + \dots + c_{d-1}' X^{d-1})\mod m$$ are themselves independent transcendentals, so dividing the solutions for these two, there are solutions in $$k'$$, and then because $$k$$ is algebraically closed, solutions in $$k$$. QED

Now adjoin to $$\mathbb F_q(T)$$ a root in $$\overline{\mathbb F_q(T)}$$ of the system of equations $$a_0,\dots, a_{d-1} \in k$$ with $$(a_0^q + \dots + a_{d-1}^{q} X^{d-1} ) = ( X-T ) ( a_0 + \dots + a_{d-1} X^{d-1} ) \mod m(X)$$ and $$\operatorname{Res} ( a_0 + \dots + a_{d-1} X^{d-1} , m(X) ) \neq 0$$

Because the set of roots forms an orbit under $$(\mathbb F_q[X]/m(X) )^\times$$, the Galois group is a subgroup of $$(\mathbb F_q[X]/m(X) )^\times$$. We want to check that the Frobenius element associated to a prime $$\pi(T)$$ not dividing $$m(T)$$ inside this Galois group is equal to the reduction of $$m(X)$$ mod $$(X)$$. It follows immediately from the definition of the zeta function of a global field that the zeta function of the function field generated by this root is a product of Dirichlet $$L$$-functions for characters of $$(\mathbb F_q[X]/m(X) )^\times$$.

The Frobenius element in the Galois group is the same as the Frobenius element in the local field $$K_\pi$$ for $$K = \mathbb F_q(T)$$. By Hensel's lemma, each solution in the algebraic closure of the residue field $$\overline{k}_\pi$$ lifts to a solution in an unramified extension of $$K_\pi$$ and thus to an element of the algebraic closure $$\overline{K}_\pi$$. Because $$\overline{k}_\pi$$ and $$\overline{K}_\pi$$ have the same number of solutions, all solutions in $$\overline{K}_\pi$$ arise this way, so the action of Frobenius on solutions over the local field $$\overline{K}_\pi$$ is equal to its action on solutions over the residue field $$k_\pi = \mathbb F_q[T]/\pi(T)$$.

But the Frobenius in $$\overline{ \mathbb F_q[T]/\pi(T)}$$ sends $$a_i$$ to $$a_i^{q^{\deg \pi}}$$, so it acts on $$(a_0 + \dots + a_{d-1} X^d)$$ by multiplication by $$(X-T) (X-T^q) \dots (X - T^{ q^{ \deg \pi -1 } } ) .$$ Because $$T \in \mathbb F_q[T]/\pi(T)$$ is a root of $$\pi(T)$$, $$T^q,T^{q^2}, \dots$$ must be the remaining roots, and so Frobenius acts by multiplication by $$\pi(X)$$, as desired.

• Stepanov's method produces a function in $\mathbb{F}(x,y), y^n = m(x)$ but this function is invariant under the automorphism $y \mapsto \zeta y$ so it comes out as a polynomial in $x$, and you can set up the construction this way to begin with. Same for Artin-Schreier $y^p-y=f(x)$ and the automorphism $y \mapsto y+1$. The original papers treat only these cases in this way. I am definitely not talking about later extensions such as Bombieri's. – Felipe Voloch May 16 '19 at 2:58
• @FelipeVoloch Ah, I didn't know that as I am too sophisticated to understand proofs that don't have Riemann-Roch in them. If the relationship between the classical case and general case is just working with invariant functions in the classical case, then surely there is a version of the classical argument that can be made for general Dirichlet characters using the explicit equations for this field extension avoiding some of the abstract steps. But I could be wrong about this as well. – Will Sawin May 16 '19 at 3:21
• Thanks for this. While I am not yet proficient enough in the etale formalism to fully follow this more modern interpretation of the Carlitz construction, it at least does seem less ad hoc this way. – Terry Tao May 16 '19 at 3:44
• @TerryTao One doesn't really need the etale formalism - it should all be doable in the language of algebraic number theory, which I have attempted to do above. – Will Sawin May 16 '19 at 14:06
• @TerryTao Your comment that this is the more modern interpretation made me wonder by how much. It seems that this idea is Lang 1956 (doi.org/10.2307%2F2372673 "In the case the group $G$ is commutative than one can use it to derive the class field theory over a variety $V$ having a rational map to $G$") while the Carlitz module approach is Carlitz 1935. So about 20 years more modern. But the Carlitz module approach seems much better known, possibly because Lang didn't fully write it up in that paper ("The abelian class field theory is carried out in detail elsewhere") – Will Sawin May 16 '19 at 14:09


text:
# Pascal's triangle

In Pascal's triangle, each number is the sum of the two numbers directly above it.

In mathematics, Pascal's triangle is a triangular array of the binomial coefficients. In much of the Western world, it is named after the French mathematician Blaise Pascal, although other mathematicians studied it centuries before him in India,[1] Persia (Iran)[2], China, Germany, and Italy.[3]

The rows of Pascal's triangle are conventionally enumerated starting with row n = 0 at the top (the 0th row). The entries in each row are numbered from the left beginning with k = 0 and are usually staggered relative to the numbers in the adjacent rows. The triangle may be constructed in the following manner: In row 0 (the topmost row), there is a unique nonzero entry 1. Each entry of each subsequent row is constructed by adding the number above and to the left with the number above and to the right, treating blank entries as 0. For example, the initial number in the first (or any other) row is 1 (the sum of 0 and 1), whereas the numbers 1 and 3 in the third row are added to produce the number 4 in the fourth row.

## Formula

A diagram that shows Pascal's triangle with rows 0 through 7.

The entry in the nth row and kth column of Pascal's triangle is denoted ${\displaystyle {\tbinom {n}{k}}}$. For example, the unique nonzero entry in the topmost row is ${\displaystyle {\tbinom {0}{0}}=1}$. With this notation, the construction of the previous paragraph may be written as follows:

${\displaystyle {n \choose k}={n-1 \choose k-1}+{n-1 \choose k}}$,

for any non-negative integer n and any integer k between 0 and n, inclusive.[4] This recurrence for the binomial coefficients is known as Pascal's rule.

Pascal's triangle has higher dimensional generalizations. The three-dimensional version is called Pascal's pyramid or Pascal's tetrahedron, while the general versions are called Pascal's simplices.

## History

Yang Hui's triangle, as depicted by the Chinese using rod numerals, appears in a mathematical work by Zhu Shijie, dated 1303. The title reads "The Old Method Chart of the Seven Multiplying Squares" (Chinese: 古法七乘方圖; the fourth character 椉 in the image title is archaic).
Blaise Pascal's version of the triangle

The pattern of numbers that forms Pascal's triangle was known well before Pascal's time. Pascal innovated many previously unattested uses of the triangle's numbers, uses he described comprehensively in what is perhaps the earliest known mathematical treatise to be specially devoted to the triangle, his Traité du triangle arithmétique (1653). Centuries before, discussion of the numbers had arisen in the context of Indian studies of combinatorics and of binomial numbers and Greeks' study of figurate numbers.[5]

From later commentary, it appears that the binomial coefficients and the additive formula for generating them, ${\displaystyle {\tbinom {n}{r}}={\tbinom {n-1}{r}}+{\tbinom {n-1}{r-1}}}$, were known to Pingala in or before the 2nd century BC.[6][7] While Pingala's work only survives in fragments, the commentator Varāhamihira, around 505, gave a clear description of the additive formula,[7] and a more detailed explanation of the same rule was given by Halayudha, around 975. Halayudha also explained obscure references to Meru-prastaara, the Staircase of Mount Meru, giving the first surviving description of the arrangement of these numbers into a triangle.[7][8] In approximately 850, the Jain mathematician Mahāvīra gave a different formula for the binomial coefficients, using multiplication, equivalent to the modern formula ${\displaystyle {\tbinom {n}{r}}={\tfrac {n!}{r!(n-r)!}}}$.[7] In 1068, four columns of the first sixteen rows were given by the mathematician Bhattotpala, who was the first recorded mathematician to equate the additive and multiplicative formulas for these numbers.[7]

At around the same time, the Persian mathematician Al-Karaji (953–1029) wrote a now lost book which contained the first description of Pascal's triangle.[9][10] It was later repeated by the Persian poet-astronomer-mathematician Omar Khayyám (1048–1131); thus the triangle is also referred to as the Khayyam triangle in Iran.[11] Several theorems related to the triangle were known, including the binomial theorem. Khayyam used a method of finding nth roots based on the binomial expansion, and therefore on the binomial coefficients.[12]

Pascal's triangle was known in China in the early 11th century through the work of the Chinese mathematician Jia Xian (1010–1070). In the 13th century, Yang Hui (1238–1298) presented the triangle and hence it is still called Yang Hui's triangle (杨辉三角; 楊輝三角) in China.[13]

In the west, the binomial coefficients were calculated by Gersonides in the early 14th century, using the multiplicative formula for them.[7] Petrus Apianus (1495–1552) published the full triangle on the frontispiece of his book on business calculations in 1527. This is the first record of the triangle in Europe.[14] Michael Stifel published a portion of the triangle (from the second to the middle column in each row) in 1544, describing it as a table of figurate numbers.[7] In Italy, Pascal's triangle is referred to as Tartaglia's triangle, named for the Italian algebraist Niccolò Fontana Tartaglia (1500–1577), who published six rows of the triangle in 1556.[7] Gerolamo Cardano, also, published the triangle as well as the additive and multiplicative rules for constructing it in 1570.[7]

Pascal's Traité du triangle arithmétique (Treatise on Arithmetical Triangle) was published posthumously in 1665. In this, Pascal collected several results then known about the triangle, and employed them to solve problems in probability theory. The triangle was later named after Pascal by Pierre Raymond de Montmort (1708) who called it "Table de M. Pascal pour les combinaisons" (French: Table of Mr. Pascal for combinations) and Abraham de Moivre (1730) who called it "Triangulum Arithmeticum PASCALIANUM" (Latin: Pascal's Arithmetic Triangle), which became the modern Western name.[15]

## Binomial expansions

Visualisation of binomial expansion up to the 4th power

Pascal's triangle determines the coefficients which arise in binomial expansions. For an example, consider the expansion

(x + y)2 = x2 + 2xy + y2 = 1x2y0 + 2x1y1 + 1x0y2.

Notice the coefficients are the numbers in row two of Pascal's triangle: 1, 2, 1. In general, when a binomial like x + y is raised to a positive integer power we have:

(x + y)n = a0xn + a1xn−1y + a2xn−2y2 + ... + an−1xyn−1 + anyn,

where the coefficients ai in this expansion are precisely the numbers on row n of Pascal's triangle. In other words,

${\displaystyle a_{i}={n \choose i}.}$

This is the binomial theorem.

Notice that the entire right diagonal of Pascal's triangle corresponds to the coefficient of yn in these binomial expansions, while the next diagonal corresponds to the coefficient of xyn−1 and so on.

To see how the binomial theorem relates to the simple construction of Pascal's triangle, consider the problem of calculating the coefficients of the expansion of (x + 1)n+1 in terms of the corresponding coefficients of (x + 1)n (setting y = 1 for simplicity). Suppose then that

${\displaystyle (x+1)^{n}=\sum _{i=0}^{n}a_{i}x^{i}.}$

Now

${\displaystyle (x+1)^{n+1}=(x+1)(x+1)^{n}=x(x+1)^{n}+(x+1)^{n}=\sum _{i=0}^{n}a_{i}x^{i+1}+\sum _{i=0}^{n}a_{i}x^{i}.}$
Six rows Pascal's triangle as binomial coefficients

The two summations can be reorganized as follows:

{\displaystyle {\begin{aligned}&\sum _{i=0}^{n}a_{i}x^{i+1}+\sum _{i=0}^{n}a_{i}x^{i}\\&{}=\sum _{i=1}^{n+1}a_{i-1}x^{i}+\sum _{i=0}^{n}a_{i}x^{i}\\&{}=\sum _{i=1}^{n}a_{i-1}x^{i}+\sum _{i=1}^{n}a_{i}x^{i}+a_{0}x^{0}+a_{n}x^{n+1}\\&{}=\sum _{i=1}^{n}(a_{i-1}+a_{i})x^{i}+a_{0}x^{0}+a_{n}x^{n+1}\\&{}=\sum _{i=1}^{n}(a_{i-1}+a_{i})x^{i}+x^{0}+x^{n+1}\end{aligned}}}

(because of how raising a polynomial to a power works, a0an = 1).

We now have an expression for the polynomial (x + 1)n+1 in terms of the coefficients of (x + 1)n (these are the ais), which is what we need if we want to express a line in terms of the line above it. Recall that all the terms in a diagonal going from the upper-left to the lower-right correspond to the same power of x, and that the a-terms are the coefficients of the polynomial (x + 1)n, and we are determining the coefficients of (x + 1)n+1. Now, for any given i not 0 or n + 1, the coefficient of the xi term in the polynomial (x + 1)n+1 is equal to ai−1(the figure above and to the left of the figure to be determined, since it is on the same diagonal) + ai (the figure to the immediate right of the first figure). This is indeed the simple rule for constructing Pascal's triangle row-by-row.

It is not difficult to turn this argument into a proof (by mathematical induction) of the binomial theorem. Since (a + b)n = bn(a/b +  1)n, the coefficients are identical in the expansion of the general case.

An interesting consequence of the binomial theorem is obtained by setting both variables x and y equal to one. In this case, we know that (1 + 1)n = 2n, and so

${\displaystyle {n \choose 0}+{n \choose 1}+\cdots +{n \choose n-1}+{n \choose n}=2^{n}.}$

In other words, the sum of the entries in the nth row of Pascal's triangle is the nth power of 2.

## Combinations

A second useful application of Pascal's triangle is in the calculation of combinations. For example, the number of combinations of n things taken k at a time (called n choose k) can be found by the equation

${\displaystyle \mathbf {C} (n,k)=\mathbf {C} _{k}^{n}={_{n}C_{k}}={n \choose k}={\frac {n!}{k!(n-k)!}}.}$

But this is also the formula for a cell of Pascal's triangle. Rather than performing the calculation, one can simply look up the appropriate entry in the triangle. Provided we have the first row and the first entry in a row numbered 0, the answer will be located at entry k in row n. For example, suppose a basketball team has 10 players and wants to know how many ways there are of selecting 8. The answer is entry 8 in row 10, which is 45; that is, 10 choose 8 is 45.

## Relation to binomial distribution and convolutions

When divided by 2n, the nth row of Pascal's triangle becomes the binomial distribution in the symmetric case where p = 1/2. By the central limit theorem, this distribution approaches the normal distribution as n increases. This can also be seen by applying Stirling's formula to the factorials involved in the formula for combinations.

This is related to the operation of discrete convolution in two ways. First, polynomial multiplication exactly corresponds to discrete convolution, so that repeatedly convolving the sequence {..., 0, 0, 1, 1, 0, 0, ...} with itself corresponds to taking powers of 1 + x, and hence to generating the rows of the triangle. Second, repeatedly convolving the distribution function for a random variable with itself corresponds to calculating the distribution function for a sum of n independent copies of that variable; this is exactly the situation to which the central limit theorem applies, and hence leads to the normal distribution in the limit.

## Patterns and properties

Pascal's triangle has many properties and contains many patterns of numbers.

Each frame represents a row in Pascal's triangle. Each column of pixels is a number in binary with the least significant bit at the bottom. Light pixels represent ones and the dark pixels are zeroes.

### Rows

• The sum of the elements of a single row is twice the sum of the row preceding it. For example, row 0 (the topmost row) has a value of 1, row 1 has a value of 2, row 2 has a value of 4, and so forth. This is because every item in a row produces two items in the next row: one left and one right. The sum of the elements of row n is equal to 2n.
• Taking the product of the elements in each row, the sequence of products (sequence A001142 in the OEIS) is related to the base of the natural logarithm, e.[16][17] Specifically, define the sequence sn as follows:
${\displaystyle s_{n}=\prod _{k=0}^{n}{\binom {n}{k}}=\prod _{k=0}^{n}{\frac {n!}{k!(n-k)!}}~,~n\geq 0.}$
Then, the ratio of successive row products is
${\displaystyle {\frac {s_{n+1}}{s_{n}}}={\frac {(n+1)!^{(n+2)}\prod _{k=0}^{n+1}{k!^{-2}}}{n!^{(n+1)}\prod _{k=0}^{n}{k!^{-2}}}}={\frac {(n+1)^{n}}{n!}}}$
and the ratio of these ratios is
${\displaystyle {\frac {(s_{n+1})(s_{n-1})}{(s_{n})^{2}}}=\left({\frac {n+1}{n}}\right)^{n},~n\geq 1.}$
The right-hand side of the above equation takes the form of the limit definition of e
${\displaystyle {\textit {e}}=\lim _{n\to \infty }\left(1+{\frac {1}{n}}\right)^{n}.}$
• Pi can be found in Pascal's triangle through the Nilakantha infinite series.[18]
${\displaystyle \pi =3+\sum _{n=1}^{\infty }(-1)^{n+1}{\frac {\binom {2n+1}{1}}{{\binom {2n+1}{2}}{\binom {2n+2}{2}}}}}$
• The value of a row, if each entry is considered a decimal place (and numbers larger than 9 carried over accordingly), is a power of 11 ( 11n, for row n). Thus, in row 2, ⟨1, 2, 1⟩ becomes 112, while ⟨1, 5, 10, 10, 5, 1⟩ in row five becomes (after carrying) 161,051, which is 115. This property is explained by setting x = 10 in the binomial expansion of (x + 1)n, and adjusting values to the decimal system. But x can be chosen to allow rows to represent values in any base.
• In base 3: 1 2 13 = 42 (16)
• ⟨1, 3, 3, 1⟩ → 2 1 0 13 = 43 (64)
• In base 9: 1 2 19 = 102 (100)
•               1 3 3 19 = 103 (1000)
• ⟨1, 5, 10, 10, 5, 1⟩ → 1 6 2 1 5 19 = 105 (100000)
In particular (see previous property), for x = 1 place value remains constant (1place=1). Thus entries can simply be added in interpreting the value of a row.
• Some of the numbers in Pascal's triangle correlate to numbers in Lozanić's triangle.
• The sum of the squares of the elements of row n equals the middle element of row 2n. For example, 12 + 42 + 62 + 42 + 12 = 70. In general form:
${\displaystyle \sum _{k=0}^{n}{n \choose k}^{2}={2n \choose n}.}$
• On any row n, where n is even, the middle term minus the term two spots to the left equals a Catalan number, specifically the (n/2 + 1)th Catalan number. For example: on row 4, 6 − 1 = 5, which is the 3rd Catalan number, and 4/2 + 1 = 3.
• In a row p where p is a prime number, all the terms in that row except the 1s are multiples of p. This can be proven easily, since if ${\displaystyle p\in \mathbb {P} }$, then p has no factors save for 1 and itself. Every entry in the triangle is an integer, so therefore by definition ${\displaystyle (p-k)!}$ and ${\displaystyle k!}$ are factors of ${\displaystyle p!\,}$. However, there is no possible way p itself can show up in the denominator, so therefore p (or some multiple of it) must be left in the numerator, making the entire entry a multiple of p.
• Parity: To count odd terms in row n, convert n to binary. Let x be the number of 1s in the binary representation. Then the number of odd terms will be 2x. These numbers are the values in Gould's sequence.[19]
• Every entry in row 2n-1, n ≥ 0, is odd.[20]
• Polarity: When the elements of a row of Pascal's triangle are added and subtracted together sequentially, every row with a middle number, meaning rows that have an odd number of integers, gives 0 as the result. As examples, row 4 is 1 4 6 4 1, so the formula would be 6 – (4+4) + (1+1) = 0; and row 6 is 1 6 15 20 15 6 1, so the formula would be 20 – (15+15) + (6+6) – (1+1) = 0. So every even row of the Pascal triangle equals 0 when you take the middle number, then subtract the integers directly next to the center, then add the next integers, then subtract, so on and so forth until you reach the end of the row.

### Diagonals

Derivation of simplex numbers from a left-justified Pascal's triangle

The diagonals of Pascal's triangle contain the figurate numbers of simplices:

{\displaystyle {\begin{aligned}P_{0}(n)&=P_{d}(0)=1,\\P_{d}(n)&=P_{d}(n-1)+P_{d-1}(n)\\&=\sum _{i=0}^{n}P_{d-1}(i)=\sum _{i=0}^{d}P_{i}(n-1).\end{aligned}}}

The symmetry of the triangle implies that the nth d-dimensional number is equal to the dth n-dimensional number.

An alternative formula that does not involve recursion is as follows:

${\displaystyle P_{d}(n)={\frac {1}{d!}}\prod _{k=0}^{d-1}(n+k)={n^{(d)} \over d!}={\binom {n+d-1}{d}}}$
where n(d) is the rising factorial.

The geometric meaning of a function Pd is: Pd(1) = 1 for all d. Construct a d-dimensional triangle (a 3-dimensional triangle is a tetrahedron) by placing additional dots below an initial dot, corresponding to Pd(1) = 1. Place these dots in a manner analogous to the placement of numbers in Pascal's triangle. To find Pd(x), have a total of x dots composing the target shape. Pd(x) then equals the total number of dots in the shape. A 0-dimensional triangle is a point and a 1-dimensional triangle is simply a line, and therefore P0(x) = 1 and P1(x) = x, which is the sequence of natural numbers. The number of dots in each layer corresponds to Pd − 1(x).

### Calculating a row or diagonal by itself

There are simple algorithms to compute all the elements in a row or diagonal without computing other elements or factorials.

To compute row ${\displaystyle n}$ with the elements ${\displaystyle {\tbinom {n}{0}}}$, ${\displaystyle {\tbinom {n}{1}}}$, ..., ${\displaystyle {\tbinom {n}{n}}}$, begin with ${\displaystyle {\tbinom {n}{0}}=1}$. For each subsequent element, the value is determined by multiplying the previous value by a fraction with slowly changing numerator and denominator:

${\displaystyle {n \choose k}={n \choose k-1}\times {\frac {n+1-k}{k}}.}$

For example, to calculate row 5, the fractions are  ${\displaystyle {\tfrac {5}{1}}}$${\displaystyle {\tfrac {4}{2}}}$${\displaystyle {\tfrac {3}{3}}}$${\displaystyle {\tfrac {2}{4}}}$ and ${\displaystyle {\tfrac {1}{5}}}$, and hence the elements are  ${\displaystyle {\tbinom {5}{0}}=1}$,   ${\displaystyle {\tbinom {5}{1}}=1\times {\tfrac {5}{1}}=5}$,   ${\displaystyle {\tbinom {5}{2}}=5\times {\tfrac {4}{2}}=10}$, etc. (The remaining elements are most easily obtained by symmetry.)

To compute the diagonal containing the elements ${\displaystyle {\tbinom {n}{0}}}$, ${\displaystyle {\tbinom {n+1}{1}}}$, ${\displaystyle {\tbinom {n+2}{2}}}$, ..., we again begin with ${\displaystyle {\tbinom {n}{0}}=1}$ and obtain subsequent elements by multiplication by certain fractions:

${\displaystyle {n+k \choose k}={n+k-1 \choose k-1}\times {\frac {n+k}{k}}.}$

For example, to calculate the diagonal beginning at ${\displaystyle {\tbinom {5}{0}}}$, the fractions are  ${\displaystyle {\tfrac {6}{1}}}$${\displaystyle {\tfrac {7}{2}}}$${\displaystyle {\tfrac {8}{3}}}$, ..., and the elements are ${\displaystyle {\tbinom {5}{0}}=1}$,   ${\displaystyle {\tbinom {6}{1}}=1\times {\tfrac {6}{1}}=6}$,   ${\displaystyle {\tbinom {7}{2}}=6\times {\tfrac {7}{2}}=21}$, etc. By symmetry, these elements are equal to ${\displaystyle {\tbinom {5}{5}}}$, ${\displaystyle {\tbinom {6}{5}}}$, ${\displaystyle {\tbinom {7}{5}}}$, etc.

### Overall patterns and properties

A level-4 approximation to a Sierpinski triangle obtained by shading the first 32 rows of a Pascal triangle white if the binomial coefficient is even and black if it is odd.
• The pattern obtained by coloring only the odd numbers in Pascal's triangle closely resembles the fractal called the Sierpinski triangle. This resemblance becomes more and more accurate as more rows are considered; in the limit, as the number of rows approaches infinity, the resulting pattern is the Sierpinski triangle, assuming a fixed perimeter.[21] More generally, numbers could be colored differently according to whether or not they are multiples of 3, 4, etc.; this results in other similar patterns.
Pascal's triangle overlaid on a grid gives the number of distinct paths to each square, assuming only rightward and downward movements are considered.
• In a triangular portion of a grid (as in the images below), the number of shortest grid paths from a given node to the top node of the triangle is the corresponding entry in Pascal's triangle. On a Plinko game board shaped like a triangle, this distribution should give the probabilities of winning the various prizes.
• If the rows of Pascal's triangle are left-justified, the diagonal bands (colour-coded below) sum to the Fibonacci numbers.
 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1

### Construction as matrix exponential

Binomial matrix as matrix exponential. All the dots represent 0.

Due to its simple construction by factorials, a very basic representation of Pascal's triangle in terms of the matrix exponential can be given: Pascal's triangle is the exponential of the matrix which has the sequence 1, 2, 3, 4, … on its subdiagonal and zero everywhere else.

### Connections to geometry of polytopes

Pascal's triangle can be used as a lookup table for the number of elements (such as edges and corners) within a polytope (such as a triangle, a tetrahedron, a square and a cube).

#### Number of elements of simplices

Let's begin by considering the 3rd line of Pascal's triangle, with values 1, 3, 3, 1. A 2-dimensional triangle has one 2-dimensional element (itself), three 1-dimensional elements (lines, or edges), and three 0-dimensional elements (vertices, or corners). The meaning of the final number (1) is more difficult to explain (but see below). Continuing with our example, a tetrahedron has one 3-dimensional element (itself), four 2-dimensional elements (faces), six 1-dimensional elements (edges), and four 0-dimensional elements (vertices). Adding the final 1 again, these values correspond to the 4th row of the triangle (1, 4, 6, 4, 1). Line 1 corresponds to a point, and Line 2 corresponds to a line segment (dyad). This pattern continues to arbitrarily high-dimensioned hyper-tetrahedrons (known as simplices).

To understand why this pattern exists, one must first understand that the process of building an n-simplex from an (n − 1)-simplex consists of simply adding a new vertex to the latter, positioned such that this new vertex lies outside of the space of the original simplex, and connecting it to all original vertices. As an example, consider the case of building a tetrahedron from a triangle, the latter of whose elements are enumerated by row 3 of Pascal's triangle: 1 face, 3 edges, and 3 vertices (the meaning of the final 1 will be explained shortly). To build a tetrahedron from a triangle, we position a new vertex above the plane of the triangle and connect this vertex to all three vertices of the original triangle.

The number of a given dimensional element in the tetrahedron is now the sum of two numbers: first the number of that element found in the original triangle, plus the number of new elements, each of which is built upon elements of one fewer dimension from the original triangle. Thus, in the tetrahedron, the number of cells (polyhedral elements) is 0 (the original triangle possesses none) + 1 (built upon the single face of the original triangle) = 1; the number of faces is 1 (the original triangle itself) + 3 (the new faces, each built upon an edge of the original triangle) = 4; the number of edges is 3 (from the original triangle) + 3 (the new edges, each built upon a vertex of the original triangle) = 6; the number of new vertices is 3 (from the original triangle) + 1 (the new vertex that was added to create the tetrahedron from the triangle) = 4. This process of summing the number of elements of a given dimension to those of one fewer dimension to arrive at the number of the former found in the next higher simplex is equivalent to the process of summing two adjacent numbers in a row of Pascal's triangle to yield the number below. Thus, the meaning of the final number (1) in a row of Pascal's triangle becomes understood as representing the new vertex that is to be added to the simplex represented by that row to yield the next higher simplex represented by the next row. This new vertex is joined to every element in the original simplex to yield a new element of one higher dimension in the new simplex, and this is the origin of the pattern found to be identical to that seen in Pascal's triangle. The "extra" 1 in a row can be thought of as the -1 simplex, the unique center of the simplex, which ever gives rise to a new vertex and a new dimension, yielding a new simplex with a new center.

#### Number of elements of hypercubes

A similar pattern is observed relating to squares, as opposed to triangles. To find the pattern, one must construct an analog to Pascal's triangle, whose entries are the coefficients of (x + 2)Row Number, instead of (x + 1)Row Number. There are a couple ways to do this. The simpler is to begin with Row 0 = 1 and Row 1 = 1, 2. Proceed to construct the analog triangles according to the following rule:

${\displaystyle {n \choose k}=2\times {n-1 \choose k-1}+{n-1 \choose k}.}$

That is, choose a pair of numbers according to the rules of Pascal's triangle, but double the one on the left before adding. This results in:

                             1
1       2
1       4       4
1       6       12      8
1       8       24      32      16
1       10      40      80      80       32
1       12      60      160     240     192       64
1       14      84      280     560     672      448       128

The other way of manufacturing this triangle is to start with Pascal's triangle and multiply each entry by 2k, where k is the position in the row of the given number. For example, the 2nd value in row 4 of Pascal's triangle is 6 (the slope of 1s corresponds to the zeroth entry in each row). To get the value that resides in the corresponding position in the analog triangle, multiply 6 by 2Position Number = 6 × 22 = 6 × 4 = 24. Now that the analog triangle has been constructed, the number of elements of any dimension that compose an arbitrarily dimensioned cube (called a hypercube) can be read from the table in a way analogous to Pascal's triangle. For example, the number of 2-dimensional elements in a 2-dimensional cube (a square) is one, the number of 1-dimensional elements (sides, or lines) is 4, and the number of 0-dimensional elements (points, or vertices) is 4. This matches the 2nd row of the table (1, 4, 4). A cube has 1 cube, 6 faces, 12 edges, and 8 vertices, which corresponds to the next line of the analog triangle (1, 6, 12, 8). This pattern continues indefinitely.

To understand why this pattern exists, first recognize that the construction of an n-cube from an (n − 1)-cube is done by simply duplicating the original figure and displacing it some distance (for a regular n-cube, the edge length) orthogonal to the space of the original figure, then connecting each vertex of the new figure to its corresponding vertex of the original. This initial duplication process is the reason why, to enumerate the dimensional elements of an n-cube, one must double the first of a pair of numbers in a row of this analog of Pascal's triangle before summing to yield the number below. The initial doubling thus yields the number of "original" elements to be found in the next higher n-cube and, as before, new elements are built upon those of one fewer dimension (edges upon vertices, faces upon edges, etc.). Again, the last number of a row represents the number of new vertices to be added to generate the next higher n-cube.

In this triangle, the sum of the elements of row m is equal to 3m. Again, to use the elements of row 4 as an example: ${\displaystyle 1+8+24+32+16=81}$, which is equal to ${\displaystyle 3^{4}=81}$.

#### Counting vertices in a cube by distance

Each row of Pascal's triangle gives the number of vertices at each distance from a fixed vertex in an n-dimensional cube. For example, in three dimensions, the third row (1 3 3 1) corresponds to the usual three-dimensional cube: fixing a vertex V, there is one vertex at distance 0 from V (that is, V itself), three vertices at distance 1, three vertices at distance 2 and one vertex at distance 3 (the vertex opposite V). The second row corresponds to a square, while larger-numbered rows correspond to hypercubes in each dimension.

### Fourier transform of sin(x)n+1/x

As stated previously, the coefficients of (x + 1)n are the nth row of the triangle. Now the coefficients of (x − 1)n are the same, except that the sign alternates from +1 to −1 and back again. After suitable normalization, the same pattern of numbers occurs in the Fourier transform of sin(x)n+1/x. More precisely: if n is even, take the real part of the transform, and if n is odd, take the imaginary part. Then the result is a step function, whose values (suitably normalized) are given by the nth row of the triangle with alternating signs.[22] For example, the values of the step function that results from:

${\displaystyle \,{\mathfrak {Re}}\left({\text{Fourier}}\left[{\frac {\sin(x)^{5}}{x}}\right]\right)}$

compose the 4th row of the triangle, with alternating signs. This is a generalization of the following basic result (often used in electrical engineering):

${\displaystyle \,{\mathfrak {Re}}\left({\text{Fourier}}\left[{\frac {\sin(x)^{1}}{x}}\right]\right)}$

is the boxcar function.[23] The corresponding row of the triangle is row 0, which consists of just the number 1.

If n is congruent to 2 or to 3 mod 4, then the signs start with −1. In fact, the sequence of the (normalized) first terms corresponds to the powers of i, which cycle around the intersection of the axes with the unit circle in the complex plane:

${\displaystyle \,+i,-1,-i,+1,+i,\ldots \,}$

### Elementary cellular automaton

The pattern produced by an elementary cellular automaton using rule 60 is exactly Pascal's triangle of binomial coefficients reduced modulo 2 (black cells correspond to odd binomial coefficients).[24] Rule 102 also produces this pattern when trailing zeros are omitted. Rule 90 produces the same pattern but with an empty cell separating each entry in the rows.

## Extensions

Pascal's triangle can be extended to negative row numbers.

First write the triangle in the following form:

 m = 0 m = 1 m = 2 m = 3 m = 4 m = 5 ... n = 0 1 0 0 0 0 0 ... n = 1 1 1 0 0 0 0 ... n = 2 1 2 1 0 0 0 ... n = 3 1 3 3 1 0 0 ... n = 4 1 4 6 4 1 0 ...

Next, extend the column of 1s upwards:

 m = 0 m = 1 m = 2 m = 3 m = 4 m = 5 ... n = −4 1 ... n = −3 1 ... n = −2 1 ... n = −1 1 ... n = 0 1 0 0 0 0 0 ... n = 1 1 1 0 0 0 0 ... n = 2 1 2 1 0 0 0 ... n = 3 1 3 3 1 0 0 ... n = 4 1 4 6 4 1 0 ...

Now the rule:

${\displaystyle {n \choose m}={n-1 \choose m-1}+{n-1 \choose m}}$

can be rearranged to:

${\displaystyle {n-1 \choose m}={n \choose m}-{n-1 \choose m-1}}$

which allows calculation of the other entries for negative rows:

 m = 0 m = 1 m = 2 m = 3 m = 4 m = 5 ... n = −4 1 −4 10 −20 35 −56 ... n = −3 1 −3 6 −10 15 −21 ... n = −2 1 −2 3 −4 5 −6 ... n = −1 1 −1 1 −1 1 −1 ... n = 0 1 0 0 0 0 0 ... n = 1 1 1 0 0 0 0 ... n = 2 1 2 1 0 0 0 ... n = 3 1 3 3 1 0 0 ... n = 4 1 4 6 4 1 0 ...

This extension preserves the property that the values in the mth column viewed as a function of n are fit by an order m polynomial, namely

${\displaystyle {n \choose m}={\frac {1}{m!}}\prod _{k=0}^{m-1}(n-k)={\frac {1}{m!}}\prod _{k=1}^{m}(n-k+1)}$.

This extension also preserves the property that the values in the nth row correspond to the coefficients of (1 + x)n:

${\displaystyle (1+x)^{n}=\sum _{k=0}^{\infty }{n \choose k}x^{k}\quad |x|<1}$

For example:

${\displaystyle (1+x)^{-2}=1-2x+3x^{2}-4x^{3}+\cdots \quad |x|<1}$

When viewed as a series, the rows of negative n diverge. However, they are still Abel summable, which summation gives the standard values of 2n. (In fact, the n = -1 row results in Grandi's series which "sums" to 1/2, and the n = -2 row results in another well-known series which has an Abel sum of 1/4.)

Another option for extending Pascal's triangle to negative rows comes from extending the other line of 1s:

 m = −4 m = −3 m = −2 m = −1 m = 0 m = 1 m = 2 m = 3 m = 4 m = 5 ... n = −4 1 0 0 0 0 0 0 0 0 0 ... n = −3 1 0 0 0 0 0 0 0 0 ... n = −2 1 0 0 0 0 0 0 0 ... n = −1 1 0 0 0 0 0 0 ... n = 0 0 0 0 0 1 0 0 0 0 0 ... n = 1 0 0 0 0 1 1 0 0 0 0 ... n = 2 0 0 0 0 1 2 1 0 0 0 ... n = 3 0 0 0 0 1 3 3 1 0 0 ... n = 4 0 0 0 0 1 4 6 4 1 0 ...

Applying the same rule as before leads to

 m = −4 m = −3 m = −2 m = −1 m = 0 m = 1 m = 2 m = 3 m = 4 m = 5 ... n = −4 1 0 0 0 0 0 0 0 0 0 ... n = −3 −3 1 0 0 0 0 0 0 0 0 ... n = −2 3 −2 1 0 0 0 0 0 0 0 ... n = −1 −1 1 −1 1 0 0 0 0 0 0 .. n = 0 0 0 0 0 1 0 0 0 0 0 ... n = 1 0 0 0 0 1 1 0 0 0 0 ... n = 2 0 0 0 0 1 2 1 0 0 0 ... n = 3 0 0 0 0 1 3 3 1 0 0 ... n = 4 0 0 0 0 1 4 6 4 1 0 ...

Note that this extension also has the properties that just as

${\displaystyle \exp {\begin{pmatrix}.&.&.&.&.\\1&.&.&.&.\\.&2&.&.&.\\.&.&3&.&.\\.&.&.&4&.\end{pmatrix}}={\begin{pmatrix}1&.&.&.&.\\1&1&.&.&.\\1&2&1&.&.\\1&3&3&1&.\\1&4&6&4&1\end{pmatrix}},}$

we have

${\displaystyle \exp {\begin{pmatrix}.&.&.&.&.&.&.&.&.&.\\-4&.&.&.&.&.&.&.&.&.\\.&-3&.&.&.&.&.&.&.&.\\.&.&-2&.&.&.&.&.&.&.\\.&.&.&-1&.&.&.&.&.&.\\.&.&.&.&0&.&.&.&.&.\\.&.&.&.&.&1&.&.&.&.\\.&.&.&.&.&.&2&.&.&.\\.&.&.&.&.&.&.&3&.&.\\.&.&.&.&.&.&.&.&4&.\end{pmatrix}}={\begin{pmatrix}1&.&.&.&.&.&.&.&.&.\\-4&1&.&.&.&.&.&.&.&.\\6&-3&1&.&.&.&.&.&.&.\\-4&3&-2&1&.&.&.&.&.&.\\1&-1&1&-1&1&.&.&.&.&.\\.&.&.&.&.&1&.&.&.&.\\.&.&.&.&.&1&1&.&.&.\\.&.&.&.&.&1&2&1&.&.\\.&.&.&.&.&1&3&3&1&.\\.&.&.&.&.&1&4&6&4&1\end{pmatrix}}}$

Also, just as summing along the lower-left to upper-right diagonals of the Pascal matrix yields the Fibonacci numbers, this second type of extension still sums to the Fibonacci numbers for negative index.

Either of these extensions can be reached if we define

${\displaystyle {n \choose k}={\frac {n!}{(n-k)!k!}}\equiv {\frac {\Gamma (n+1)}{\Gamma (n-k+1)\Gamma (k+1)}}}$

and take certain limits of the gamma function, ${\displaystyle \Gamma (z)}$.

## References

1. ^ Maurice Winternitz, History of Indian Literature, Vol. III
2. ^ J. L. Coolidge, The Story of the Binomial Theorem, Amer. Math. Monthly, Vol. 56, No. 3 (Mar., 1949), pp. 147–157
3. ^ Peter Fox (1998). Cambridge University Library: the great collections. Cambridge University Press. p. 13. ISBN 978-0-521-62647-7.
4. ^ The binomial coefficient ${\displaystyle \scriptstyle {n \choose k}}$ is conventionally set to zero if k is either less than zero or greater than n.
5. ^ Pascal's triangle | World of Mathematics Summary
6. ^ A. W. F. Edwards. Pascal's arithmetical triangle: the story of a mathematical idea. JHU Press, 2002. Pages 30–31.
7. Edwards, A. W. F. (2013), "The arithmetical triangle", in Wilson, Robin; Watkins, John J., Combinatorics: Ancient and Modern, Oxford University Press, pp. 166–180.
8. ^ Alexander Zawaira; Gavin Hitchcock (2008). A Primer for Mathematics Competitions. Oxford University Press. p. 237. ISBN 978-0-19-156170-2.
9. ^ "Al-Karajī | Persian mathematician and engineer", Encyclopedia Britannica, retrieved 2018-07-19, Al-Karajī, also known as al-Karkhī, in full, Abū Bakr ibn Muḥammad ibn al-Ḥusayn al-Karajī, (born c. 980, most likely Karaj, Persia, rather than Karkh, near Baghdad, Iraq—died c. 1030), mathematician and engineer who held an official position in Baghdad (c. 1010–1015), perhaps culminating in the position of vizier, during which time he wrote his three main works, al-Fakhrī fīʾl-jabr wa’l-muqābala (“Glorious on algebra”), al-Badī‘ fī’l-hisāb (“Wonderful on calculation”), and al-Kāfī fī’l-hisāb (“Sufficient on calculation”). A now lost work of his contained the first description of what later became known as Pascal’s triangle
10. ^
11. ^ Kennedy, E. (1966). Omar Khayyam. The Mathematics Teacher 1958. National Council of Teachers of Mathematics. p. 140-142.
12. ^ Coolidge, J. L. (1949), "The story of the binomial theorem", The American Mathematical Monthly, 56: 147–157, JSTOR 10.2307/2305028, MR 0028222.
13. ^ Weisstein, Eric W. (2003). CRC concise encyclopedia of mathematics, p. 2169. ISBN 978-1-58488-347-0.
14. ^ Smith, Karl J. (2010), Nature of Mathematics, Cengage Learning, p. 10, ISBN 9780538737586.
15. ^ Fowler, David (January 1996). "The Binomial Coefficient Function". The American Mathematical Monthly. 103 (1): 1–17. doi:10.2307/2975209. JSTOR 2975209. See in particular p. 11.
16. ^ Brothers, H. J. (2012), "Finding e in Pascal's triangle", Mathematics Magazine, 85: 51, doi:10.4169/math.mag.85.1.51.
17. ^ Brothers, H. J. (2012), "Pascal's triangle: The hidden stor-e", The Mathematical Gazette, 96: 145–148.
18. ^ Foster, T. (2014), "Nilakantha's Footprints in Pascal's Triangle", Mathematics Teacher, 108: 247, doi:10.5951/mathteacher.108.4.0246
19. ^ Fine, N. J. (1947), "Binomial coefficients modulo a prime", American Mathematical Monthly, 54: 589–592, doi:10.2307/2304500, MR 0023257. See in particular Theorem 2, which gives a generalization of this fact for all prime moduli.
20. ^ Hinz, Andreas M. (1992), "Pascal's triangle and the Tower of Hanoi", The American Mathematical Monthly, 99 (6): 538–544, doi:10.2307/2324061, MR 1166003. Hinz attributes this observation to an 1891 book by Édouard Lucas, Théorie des nombres (p. 420).
21. ^ Wolfram, S. (1984). "Computation Theory of Cellular Automata". Comm. Math. Phys. 96: 15–57. Bibcode:1984CMaPh..96...15W. doi:10.1007/BF01217347.
22. ^ For a similar example, see e.g. Hore, P. J. (1983), "Solvent suppression in Fourier transform nuclear magnetic resonance", Journal of Magnetic Resonance, 55 (2): 283–300, Bibcode:1983JMagR..55..283H, doi:10.1016/0022-2364(83)90240-8.
23. ^ Karl, John H. (2012), An Introduction to Digital Signal Processing, Elsevier, p. 110, ISBN 9780323139595.
24. ^ Wolfram, S. (2002). A New Kind of Science. Champaign IL: Wolfram Media. pp. 870, 931–2.


text:
Problem on exponential of entire function

I am stuck at a problem which says :

" Let $f$ and $g$ are entire functions such that $e^f, e^g$ and $1$ are linearly dependant over $\mathbb{C}$. Show that $f$, $g$ and 1 are also linearly dependant."

So basically we have constants $C_1$, $C_2$, $C_3$ in $\mathbb{C}$, not all zero, such that $C_1 e^f + C_2 e^g + C_3=0$ . It becomes easy if one of the $C_i$ 's is zero. But I am stuck in the case where all of them are non-zero.

I can understand that it suffices to show that $|Af + Bg|$ is bounded on $\mathbb{C}$ for some complex constants $A, B$, not both of them zero. I tried using the inequality $|e^z|\leq e^{|z|}$, but it is not working.

-
Why "as soon as possible"? Sounds like it is a "hand-in/homework" problem. –  AD. Jan 25 '13 at 8:23
If none of $C_i$ is zero, both $f$ and $g$ are constant by Little Picard's theorem. –  achille hui Jan 25 '13 at 10:12
I obviously over thinking for a while before I realize this... –  Bombyx mori Jan 25 '13 at 10:36
@AD. I wrote that because it is bothering me for quite a few days, and now I have started to feel that may be my approach is wrong. –  user44349 Jan 25 '13 at 18:14

Suppose we have $c_{1} e^{f}+c_{2} e^{g}+ c_{3}=0$ and $c_1\ne0$ then we have $$e^g= \frac{c_3-c_1 e^f}{c_1}$$ and also we have $$c_{1}f' e^{f}+c_{2}g'e^{g}=0$$ which implies $$\frac{f'}{g'}=\frac{-c_2 e^{g}}{c_1 e^f}$$ Thus we have $$\frac{f'}{g'}=\frac{-c_2(c_3-c_1 e^f)}{c_1^2 e^f}=\frac{b}{e^f}-c$$ for some constants $b$ and $c$. This implies that $\frac{f'}{g'}$ is bounded, Thus, using Liouville's theorem we get that $\frac{f'}{g'}$ is constant that is $$f'=kg'$$ Now by integrating both sides we get that $$f=kg+l$$ which implies that $\{f,g,1\}$ are linearly dependent.

-
Thanks a lot ! But how did you infer that $f'/g'$ is bounded ? For example, it can be that $f(z) =-z$ for all $z$. –  user44349 Feb 7 '13 at 22:50
@CB_Student I assumed $f$ is not bounded which implies that $e^f$ is not bounded, Thus, $\left|\frac{f'}{g'}\right|\le\frac{|b|}{\left|e^f\right|}+\left|c\right|$ but we know that $\left|e^f \right|\longrightarrow\infty$ as $z\longrightarrow \infty$ so we can have a big enough circle such that $\frac{1}{|e^f|}$ is bounded outside it and it bounded insided it by analyticity (continuouity ) of $\frac{1}{e^f}$ thus $\frac{f'}{g'}$ is bounded. –  i.a.m Feb 7 '13 at 23:26
@CB_Student is there something wrong with the answer?! –  i.a.m Feb 13 '13 at 22:00
No, absolutely not ! Thanks a lot for taking time to write it all down ! :) –  user44349 Feb 14 '13 at 0:34
@CB_Student you are welcome –  i.a.m Feb 14 '13 at 1:02

Assume all the constants are not zero, then we may assume without loss of generality that $e^f=e^g+1$, then you use the Picard theorem, because the range of $e^f$ doesn't contain 0 and 1(because $e^g$ can't be 0). So you get the conclusion that f and g must be constants.

-
Thanks! I get it, but actually little Picard's theorem is not covered in the class till now. So I was trying to do it without using it. Is that possible ? –  user44349 Jan 25 '13 at 18:06
I've been thinking about that for a while. But I haven't got another solution yet. –  lee Jan 30 '13 at 2:41
I think there is a necessary and sufficient condition for a function to be exponential of another entire function. –  lee Jan 31 '13 at 5:21


text:
# Using modulus in one time pad?

I would like to know what is the real purpose of using a modulus in the equivalent of a Vernam cipher:

Data $d$, large number $M$.
Assume the key length is $\lambda$ bits. Then $M$ could be $2^\lambda$. $k$ is picked from $\{0,1\}^\lambda$ using a pseudo random function (PRF)

Encryption: $C = k + d \pmod{M}$
Decryption: $d = C - k \pmod{M}$

What's the purpose of using $M$?

• 1) What would you use instead? It's correct and it's convenient. What more do you want? 2) Nowadays we typically use xor (addition modulo 2) which is fast in software and encryption/decryption are the same function. 3) why do you claim M is a large number? It's often 2 or 256 and very rarely larger than 64 bits or so. – CodesInChaos Sep 22 '14 at 13:02

It depends on what you think of as an alternative.

If you think of the scheme where you do not use $M$ as a modulus, but the keys a picked as: $$k \leftarrow \{1, \ldots, M-1\}$$ Encryption: $$C = d + k$$ Decryption: $$d = C - k$$ Then the scheme is insecure. One way to see this is to note that we have $C \geq d$. So the ciphertext communicates the information that $d \leq C$.

You could also think of a scheme where there is no $M$ at all: $$k \leftarrow \mathbb{Z}$$ Encryption: $$C = d + k$$ Decryption: $$d = C - k$$ This would be secure, however, it would be impossible to implement because there is no way to sample $\mathbb{Z}$ (the integers) uniformly at random (think about it, how would you do that?).

So you see $M$ is really quite essential to the scheme.

• So, for security reason, we must use the modulus ??? – zof Sep 22 '14 at 14:28
• You could say that, yes. – Guut Boy Sep 22 '14 at 14:35
• @zof In addition to this answer, maybe this page about “modulo encryption” can help you grasp it completely. (That “modulo encryption” also represents a nice string to throw at search engines btw.) – e-sushi Sep 22 '14 at 14:59
• Yes, but in terms of security, what is the role of M !? – zof Sep 22 '14 at 15:36
• @zof: it is there in order to make the +/- an operation over a finite group; OTP needs to be performed over a finite group (or, at least, a finite latin square) in order to be secure. – poncho Sep 22 '14 at 15:39


text:
Both the Linux-laptop I name ‘Klystron’, and the server of this Web-site, this server being named ‘Phoenix’, received a major update this evening. On ‘Phoenix’, a total of 78 packages needed to be updated, including a Kernel-Update, and a Graphics-Driver Update. This collective update effectively converted both computers from Debian 8.7 to Debian 8.8 systems. And both updates appear to have succeeded, at first glance without breaking anything.

However, this was an update that required a reboot for ‘Phoenix’, even though this is my Web-server, and so my site was also down briefly, from approximately 20h40 until 20h50.

I am happy to say however, that ‘Phoenix’ had been running for 58 days straight, without requiring any reboot whatsoever until tonight.

Oh, but I must disappoint some of my readers with the fact that performing these updates also required I restart my ‘memcached‘ service, which means that pages or postings the readers like to visit most often will be a bit slower to fetch, until this server-side caching is replenished.

Dirk

This site uses Akismet to reduce spam. Learn how your comment data is processed.