Catenary and 组合数学 (Fall 2017)/Problem Set 1: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
imported>Thrasymedes
m (move wikilink to first instance of "chain")
 
imported>Etone
 
Line 1: Line 1:
[[File:Catenary-pm.svg|right|thumb|350x350px|Plots of <math>y = a \cosh \left(\frac{x}{a}\right)</math> with <math>a = 0.5, 1, 2</math>. The variable <math>x</math> is on the horizontal axis and  <math>y</math> is on the vertical axis.]]
== Problem 1 ==
[[File:Kette_Kettenkurve_Catenary_2008_PD.JPG|right|thumb|290x290px|A chain hanging like this forms the shape of a catenary approximately]]
#有<math>k</math>种不同的明信片，每种明信片有无限多张，寄给<math>n</math>个人，每人一张，有多少种方法？
A '''catenary''' is a type of [[curve]]. An ideal [[chain]] hanging between two supports and acted on by a uniform [[Gravity|gravitational force]] makes the shape of a catenary.<ref name="wolfram">{{cite web|url=http://mathworld.wolfram.com/Catenary.html|title=Catenary|publisher=Wolfram Research|accessdate=2016-10-30}}</ref> (An ideal chain is one that can bend perfectly, cannot be stretched and has the same [[density]] throughout.<ref name="csu">{{cite web|url=http://curvebank.calstatela.edu/catenary/catenary.htm|title=The Catenary -  The "Chain" Curve|publisher=California State University|accessdate=2016-10-30}}</ref>) The supports can be at different heights and the shape will still be a catenary.<ref>{{cite web|url=http://people.math.aau.dk/~br/catenary.pdf|title=Catenary|first=Bo|last=Rosbjerg|publisher=Aalborg University|accessdate=2016-10-30}}</ref> A catenary looks a bit like a [[parabola]], but they are different.<ref>{{cite web|url=http://mathforum.org/library/drmath/view/65729.html|title=Catenary and Parabola Comparison|publisher=Drexel University|accessdate=2016-11-05}}</ref>
#有<math>k</math>种不同的明信片，每种明信片有无限多张，寄给<math>n</math>个人，每人一张，每个人必须收到不同种类的明信片，有多少种方法？
#有<math>k</math>种不同的明信片，每种明信片有无限多张，寄给<math>n</math>个人，每人收到<math>r</math>张不同的明信片（但不同的人可以收到相同的明信片），有多少种方法？
#只有一种明信片，共有<math>m</math>张，寄给<math>n</math>个人，全部寄完，每个人可以收多张明信片或者不收明信片，有多少种方法？
#有<math>k</math>种不同的明信片，其中第<math>i</math>种明信片有<math>m_i</math>张，寄给<math>n</math>个人，全部寄完，每个人可以收多张明信片或者不收明信片，有多少种方法？


The [[equation]] for a catenary in [[Cartesian coordinate system|Cartesian coordinates]] is<ref name="csu" /><ref name="math24">{{cite web|url=http://www.math24.net/equation-of-catenary.html|title=Equation of Catenary|publisher=Math24.net|accessdate=2016-10-30}}</ref>
== Problem 2 ==
: <math>y = a \cosh \left(\frac{x}{a}\right)</math>
Find the number of ways to select <math>2n</math> balls from <math>n</math> identical blue balls, <math>n</math> identical red balls and <math>n</math> identical green balls.
where <math>a</math> is a [[parameter]] that determines the shape of the catenary<ref name="math24" /> and {{math|cosh}} is the [[Hyperbolic function|hyperbolic cosine]] function, which is defined as<ref name="stroud" />
* Give a combinatorial proof for the problem.
: <math> \cosh x = \frac {e^x + e^{-x}} {2}</math>.
* Give an algebraic proof for the problem.
Hence, we can also write the catenary equation as
: <math> y = \frac{a\left(e^\frac{x}{a} + e^{-\frac{x}{a}}\right)}{2}</math>.


The word "catenary" comes from the [[Latin]] word ''catena'', which means "chain".<ref name="stroud">{{cite book|first1=K. A.|last1=Stroud|first2=Dexter J.|last2=Booth|title=Engineering Mathematics|edition=7th|publisher=Palgrave Macmillan|date=2013|isbn=978-1-137-03120-4|page=438}}</ref> A catenary is also called called an alysoid and a chainette.<ref name="wolfram" />
== Problem 3 ==
*一个长度为<math>n</math>的“山峦”是如下由<math>n</math>个"/"和<math>n</math>个"\"组成的，从坐标<math>(0,0)</math>到<math>(0,2n)</math>的折线，但任何时候都不允许低于<math>x</math>轴。例如下图：


== References ==
    /\
{{reflist}}
  /  \/\/\    /\/\
  /        \/\/    \/\/\
  ----------------------
:长度为<math>n</math>的“山峦”有多少？


[[Category:Geometry]]
*一个长度为<math>n</math>的“地貌”是由<math>n</math>个"/"和<math>n</math>个"\"组成的，从坐标<math>(0,0)</math>到<math>(0,2n)</math>的折线，允许低于<math>x</math>轴。长度为<math>n</math>的“地貌”有多少？
{{math-stub}}
 
== Problem 4==
李雷和韩梅梅竞选学生会主席，韩梅梅获得选票 <math>p</math> 张，李雷获得选票 <math>q</math> 张，<math>p>q</math>。我们将总共的 <math>p+q</math> 张选票一张一张的点数，有多少种选票的排序方式使得在整个点票过程中，韩梅梅的票数一直高于李雷的票数？等价地，假设选票均匀分布的随机排列，以多大概率在整个点票过程中，韩梅梅的票数一直高于李雷的票数。
 
==Problem 5==
A <math>2\times n</math> rectangle is to be paved with <math>1\times 2</math> identical blocks and <math>2\times 2</math> identical blocks. Let <math>f(n)</math> denote the number of ways that can be done. Find a recurrence relation for <math>f(n)</math>, solve the recurrence relation.
 
== Problem 6 ==
Let <math>a_n</math> be a sequence of numbers satisfying the recurrence relation:
:<math>p a_n+q a_{n-1}+r a_{n-2}=0</math>
with initial condition <math>a_0=s</math> and <math>a_1=t</math>, where <math>p,q,r,s,t</math> are constants such that <math>{p}+q+r=0</math>, <math>p\neq 0</math> and <math>s\neq t</math>. Solve the recurrence relation.

Revision as of 13:10, 17 September 2017

Problem 1

  1. 有[math]\displaystyle{ k }[/math]种不同的明信片，每种明信片有无限多张，寄给[math]\displaystyle{ n }[/math]个人，每人一张，有多少种方法？
  2. 有[math]\displaystyle{ k }[/math]种不同的明信片，每种明信片有无限多张，寄给[math]\displaystyle{ n }[/math]个人，每人一张，每个人必须收到不同种类的明信片，有多少种方法？
  3. 有[math]\displaystyle{ k }[/math]种不同的明信片，每种明信片有无限多张，寄给[math]\displaystyle{ n }[/math]个人，每人收到[math]\displaystyle{ r }[/math]张不同的明信片（但不同的人可以收到相同的明信片），有多少种方法？
  4. 只有一种明信片，共有[math]\displaystyle{ m }[/math]张，寄给[math]\displaystyle{ n }[/math]个人，全部寄完，每个人可以收多张明信片或者不收明信片，有多少种方法？
  5. 有[math]\displaystyle{ k }[/math]种不同的明信片，其中第[math]\displaystyle{ i }[/math]种明信片有[math]\displaystyle{ m_i }[/math]张，寄给[math]\displaystyle{ n }[/math]个人，全部寄完，每个人可以收多张明信片或者不收明信片，有多少种方法？

Problem 2

Find the number of ways to select [math]\displaystyle{ 2n }[/math] balls from [math]\displaystyle{ n }[/math] identical blue balls, [math]\displaystyle{ n }[/math] identical red balls and [math]\displaystyle{ n }[/math] identical green balls.

  • Give a combinatorial proof for the problem.
  • Give an algebraic proof for the problem.

Problem 3

  • 一个长度为[math]\displaystyle{ n }[/math]的“山峦”是如下由[math]\displaystyle{ n }[/math]个"/"和[math]\displaystyle{ n }[/math]个"\"组成的，从坐标[math]\displaystyle{ (0,0) }[/math]到[math]\displaystyle{ (0,2n) }[/math]的折线，但任何时候都不允许低于[math]\displaystyle{ x }[/math]轴。例如下图：
   /\
  /  \/\/\    /\/\
 /        \/\/    \/\/\
 ----------------------
长度为[math]\displaystyle{ n }[/math]的“山峦”有多少？
  • 一个长度为[math]\displaystyle{ n }[/math]的“地貌”是由[math]\displaystyle{ n }[/math]个"/"和[math]\displaystyle{ n }[/math]个"\"组成的，从坐标[math]\displaystyle{ (0,0) }[/math]到[math]\displaystyle{ (0,2n) }[/math]的折线，允许低于[math]\displaystyle{ x }[/math]轴。长度为[math]\displaystyle{ n }[/math]的“地貌”有多少？

Problem 4

李雷和韩梅梅竞选学生会主席，韩梅梅获得选票 [math]\displaystyle{ p }[/math] 张，李雷获得选票 [math]\displaystyle{ q }[/math] 张，[math]\displaystyle{ p\gt q }[/math]。我们将总共的 [math]\displaystyle{ p+q }[/math] 张选票一张一张的点数，有多少种选票的排序方式使得在整个点票过程中，韩梅梅的票数一直高于李雷的票数？等价地，假设选票均匀分布的随机排列，以多大概率在整个点票过程中，韩梅梅的票数一直高于李雷的票数。

Problem 5

A [math]\displaystyle{ 2\times n }[/math] rectangle is to be paved with [math]\displaystyle{ 1\times 2 }[/math] identical blocks and [math]\displaystyle{ 2\times 2 }[/math] identical blocks. Let [math]\displaystyle{ f(n) }[/math] denote the number of ways that can be done. Find a recurrence relation for [math]\displaystyle{ f(n) }[/math], solve the recurrence relation.

Problem 6

Let [math]\displaystyle{ a_n }[/math] be a sequence of numbers satisfying the recurrence relation:

[math]\displaystyle{ p a_n+q a_{n-1}+r a_{n-2}=0 }[/math]

with initial condition [math]\displaystyle{ a_0=s }[/math] and [math]\displaystyle{ a_1=t }[/math], where [math]\displaystyle{ p,q,r,s,t }[/math] are constants such that [math]\displaystyle{ {p}+q+r=0 }[/math], [math]\displaystyle{ p\neq 0 }[/math] and [math]\displaystyle{ s\neq t }[/math]. Solve the recurrence relation.

Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=Catenary&oldid=7924"