From meyer@imap.theory.csail.mit.edu Wed Nov 16 13:12:07 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAGIC75o032029 for <6042-probs@theory.csail.mit.edu>; Wed, 16 Nov 2005 13:12:07 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAGIC5YB016120; Wed, 16 Nov 2005 13:12:05 -0500 (EST) Received: from [18.96.6.248] (SIMMONS-FIVE-O-THREE.MIT.EDU [18.96.6.248]) (authenticated bits=0) (User authenticated as hkhall@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAGIBmTx029706 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=NOT); Wed, 16 Nov 2005 13:11:49 -0500 (EST) Mime-Version: 1.0 (Apple Message framework v623) Content-Type: text/plain; charset=ISO-2022-JP; format=flowed Message-Id: <488a6fb141c55248b795e2c28e8cceb1@mit.edu> Content-Transfer-Encoding: 7bit From: Harrison King Hall Subject: [David] Week 11 Comments Date: Wed, 16 Nov 2005 13:11:48 -0500 To: 6042-probs@theory.csail.mit.edu X-Mailer: Apple Mail (2.623) X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO Content-Length: 553 X-IMAPbase: 1126748715 968 NonJunk $Label4 $Label1 $Label2 $Label3 $Label5 Junk $MDNSent $Forwarded NotJunk X-UID: 894 X-Keywords: NonJunk This is really a cool way to do counting problems, and really intuitive since you only have to worry about how to select each class of element for n elements independent of all the others. My only issue is that I don't always see the generating function . Like in the "Impossible" counting problem, I didn't see that the number of oranges was O(x) = 1 + x + x ^2 + x^3 + x^4 = (1 $B!](B x^5)/(1 $B!](B x) and I don't really know how you got there. That is probably something that comes with time however. This is really slick. -Harrison From meyer@imap.theory.csail.mit.edu Wed Nov 16 14:07:07 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAGJ775o006315 for <6042-probs@theory.csail.MIT.EDU>; Wed, 16 Nov 2005 14:07:07 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAGJ75YB017370 for <6042-probs@theory.csail.MIT.EDU>; Wed, 16 Nov 2005 14:07:06 -0500 (EST) Received: from m66-080-1.mit.edu (M66-080-1.MIT.EDU [18.63.1.1]) (authenticated bits=56) (User authenticated as lye@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAGJ72hh023705 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for <6042-probs@theory.csail.MIT.EDU>; Wed, 16 Nov 2005 14:07:03 -0500 (EST) Received: (from lye@localhost) by m66-080-1.mit.edu (8.12.9) id jAGJ72JD022931; Wed, 16 Nov 2005 14:07:02 -0500 Subject: [Sayan] Week 11 comments From: Linda Ye To: 6042-probs@theory.csail.MIT.EDU Content-Type: text/plain Content-Transfer-Encoding: 7bit Date: Wed, 16 Nov 2005 14:07:02 -0500 Message-Id: <1132168022.22906.2.camel@m66-080-1.mit.edu> Mime-Version: 1.0 X-Mailer: Evolution 2.0.4 X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO Content-Length: 175 X-UID: 895 X-Keywords: NonJunk Section 3.2 Finding a Closed Form for fib gen func I don't really understand why we split the denominators. Why does solving for the alphas give us the nth Fibonacci number? From meyer@imap.theory.csail.mit.edu Wed Nov 16 16:46:57 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAGLkv5o024930 for <6042-probs@theory.csail.mit.edu>; Wed, 16 Nov 2005 16:46:57 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAGLktYB023018 for <6042-probs@theory.csail.mit.edu>; Wed, 16 Nov 2005 16:46:56 -0500 (EST) Received: from [18.238.6.75] (EASTCAMPUS-EIGHT-FORTY-TWO.MIT.EDU [18.238.6.75]) (authenticated bits=0) (User authenticated as juang@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAGLkq7J013219 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for <6042-probs@theory.csail.mit.edu>; Wed, 16 Nov 2005 16:46:52 -0500 (EST) Message-ID: <437BA8B1.2090306@mit.edu> Date: Wed, 16 Nov 2005 16:46:25 -0500 From: Jason Juang User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.7.5) Gecko/20041201 Thunderbird/1.0RC1 Mnenhy/0.6.0.104 X-Accept-Language: en-us, en MIME-Version: 1.0 To: 6042-probs@theory.csail.mit.edu Subject: [David] Week 11 Comments Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 8bit X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO Content-Length: 394 X-UID: 896 X-Keywords: NonJunk On page 1, the lecture notes state "A generating function is a “formal” power series in the sense that we usually regard x as a placeholder rather than a number. Only in rare cases will we actually evaluate a generating function by letting x take a real number value, so we generally ignore the issue of convergence." In what cases might we actually evaluate a generating function? Jason. From meyer@imap.theory.csail.mit.edu Wed Nov 16 18:30:20 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAGNUK5o019715 for <6042-probs@theory.csail.mit.edu>; Wed, 16 Nov 2005 18:30:20 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAGNUJYB016924 for <6042-probs@theory.csail.mit.edu>; Wed, 16 Nov 2005 18:30:19 -0500 (EST) Received: from christope8f0c6 (MACGREGOR-ONE-TWENTY-FOUR.MIT.EDU [18.239.5.124]) (authenticated bits=0) (User authenticated as yangc@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAGNUADm015510 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NOT) for <6042-probs@theory.csail.mit.edu>; Wed, 16 Nov 2005 18:30:11 -0500 (EST) Message-Id: <200511162330.jAGNUADm015510@outgoing.mit.edu> From: "Chris Yang" To: <6042-probs@theory.csail.mit.edu> Subject: [David] Week 11 Comments Date: Wed, 16 Nov 2005 18:32:07 -0500 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_NextPart_000_0066_01C5EADC.0CE44B80" X-Mailer: Microsoft Office Outlook, Build 11.0.5510 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2180 Thread-Index: AcXrBfUkhsykDmfkSFKhOYrW+a1kZg== X-Spam-Score: 0.179 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO Content-Length: 2228 X-UID: 897 X-Keywords: NonJunk This is a multi-part message in MIME format. ------=_NextPart_000_0066_01C5EADC.0CE44B80 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit I don't really understand how the Convolution rule works. Will we be covering it in class on Friday? Also, the apples/oranges thing at the end is pretty cool. Thanks, Chris Yang ------=_NextPart_000_0066_01C5EADC.0CE44B80 Content-Type: text/html; charset="US-ASCII" Content-Transfer-Encoding: quoted-printable

I don’t really understand how the Convolution = rule works.  Will we be covering it in class on Friday?  Also, the = apples/oranges thing at the end is pretty cool.

 

Thanks,

Chris Yang

------=_NextPart_000_0066_01C5EADC.0CE44B80-- From hsoumare@MIT.EDU Wed Nov 16 21:52:36 2005 Return-Path: Received: from south-station-annex.mit.edu (SOUTH-STATION-ANNEX.MIT.EDU [18.72.1.2]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAH2qa5o025699 for <6042-probs@theory.lcs.mit.edu>; Wed, 16 Nov 2005 21:52:36 -0500 Received: from central-city-carrier-station.mit.edu (CENTRAL-CITY-CARRIER-STATION.MIT.EDU [18.7.7.72]) by south-station-annex.mit.edu (8.12.4/8.9.2) with ESMTP id jAH2qZCE005738 for <6042-probs@theory.lcs.mit.edu>; Wed, 16 Nov 2005 21:52:35 -0500 (EST) Received: from outgoing-legacy.mit.edu (OUTGOING-LEGACY.MIT.EDU [18.7.22.104]) by central-city-carrier-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAH2qZM3014716 for <6042-probs@theory.lcs.mit.edu>; Wed, 16 Nov 2005 21:52:35 -0500 (EST) Received: from [18.241.6.25] (NEW-TWO-EIGHTY.MIT.EDU [18.241.6.25]) ) by outgoing-legacy.mit.edu (8.12.4/8.12.4) with ESMTP id jAH2qSMu013640 for <6042-probs@theory.lcs.mit.edu>; Wed, 16 Nov 2005 21:52:28 -0500 (EST) Mime-Version: 1.0 (Apple Message framework v746.2) Content-Transfer-Encoding: 7bit Message-Id: <69C53F7D-7FEA-40EA-B7AD-27850D67CB59@mit.edu> Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed To: 6042-probs@theory.lcs.mit.edu From: Hamidou Soumare Subject: {Sayan} Weekly Email Comment Date: Wed, 16 Nov 2005 22:01:49 -0500 X-Mailer: Apple Mail (2.746.2) X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 898 Content-Length: 142 X-Keywords: NonJunk Hi I would like you to go over how the closed form of the nth coefficient of the fibonacci series was obtained on page 9. Thanks. Hamidou From xiaoranz@MIT.EDU Thu Nov 17 00:23:58 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAH5Nw5o009165 for <6042-probs@theory.lcs.MIT.EDU>; Thu, 17 Nov 2005 00:23:58 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAH5NvYB027223 for <6042-probs@theory.lcs.MIT.EDU>; Thu, 17 Nov 2005 00:23:57 -0500 (EST) Received: from w92-130-webmail-6.mit.edu (W92-130-WEBMAIL-6.MIT.EDU [18.7.22.137]) ) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAH5Nu7V020678 for <6042-probs@theory.lcs.MIT.EDU>; Thu, 17 Nov 2005 00:23:56 -0500 (EST) Received: (from nobody@localhost) by w92-130-webmail-6.mit.edu (8.12.4) id jAH5NucA018057; Thu, 17 Nov 2005 00:23:56 -0500 Received: from MCCORMICK-SEVEN-SIXTY.MIT.EDU (MCCORMICK-SEVEN-SIXTY.MIT.EDU [18.240.7.249]) (User authenticated as xiaoranz@ATHENA.MIT.EDU) by webmail.mit.edu (Horde MIME library) with HTTP for ; Thu, 17 Nov 2005 00:23:56 -0500 Message-ID: <20051117002356.q2ggn1b0cdoo8sw4@webmail.mit.edu> Date: Thu, 17 Nov 2005 00:23:56 -0500 From: "Xiaoran (Sharon) Zhang" To: 6042-probs@theory.lcs.MIT.EDU Subject: [Hanson] Weekly Comments MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) H3 (4.0.3) X-Spam-Score: -2.599 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 899 Content-Length: 503 X-Keywords: NonJunk I thought the generating functions are interesting in that they can help solve counting problems in a whole new way. The "Impossible" counting problem solution is truly awesome. ************************************************** Xiaoran (Sharon) Zhang Class of 2008 Department of Biology & Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology 320 Memorial Drive, Cambridge, MA 02139 E-mail: xiaoranz@mit.edu ************************************************** From mdmurray@MIT.EDU Thu Nov 17 03:08:57 2005 Return-Path: Received: from south-station-annex.mit.edu (SOUTH-STATION-ANNEX.MIT.EDU [18.72.1.2]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAH88v5o004712 for <6042-probs@theory.csail.mit.edu>; Thu, 17 Nov 2005 03:08:57 -0500 Received: from central-city-carrier-station.mit.edu (CENTRAL-CITY-CARRIER-STATION.MIT.EDU [18.7.7.72]) by south-station-annex.mit.edu (8.12.4/8.9.2) with ESMTP id jAH88tCE021568; Thu, 17 Nov 2005 03:08:56 -0500 (EST) Received: from outgoing-legacy.mit.edu (OUTGOING-LEGACY.MIT.EDU [18.7.22.104]) by central-city-carrier-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAH88tM3024254; Thu, 17 Nov 2005 03:08:55 -0500 (EST) Received: from [18.234.0.116] (MDMURRAY.MIT.EDU [18.234.0.116]) ) by outgoing-legacy.mit.edu (8.12.4/8.12.4) with ESMTP id jAH88mMu026115; Thu, 17 Nov 2005 03:08:48 -0500 (EST) Mime-Version: 1.0 (Apple Message framework v746.2) Content-Transfer-Encoding: 7bit Message-Id: <0D51FC0A-5E73-4CA7-846E-9E0334875C73@mit.edu> Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed To: 6042-probs@theory.csail.mit.edu, 6042-probs@theory.lcs.mit.edu From: Michael Murray Subject: [Hanson] Generating Functions Notes Date: Thu, 17 Nov 2005 03:07:43 -0500 X-Mailer: Apple Mail (2.746.2) X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 900 Content-Length: 494 X-Keywords: NonJunk Having never seen generating functions before I think the notes and lecture where a great introduction and everything so far is pretty clear. I like the use of whiteboard in lecture today, I thought it was much easier to follow than the slides and the lecture was at a much nicer pace than usual. I am however a little unclear in the explanation of the product rule. I don't really understand the table and I don't know why c_n = a_0*b_n + a_1*b_n-1 + a_2*b_n-2... Thanks, Michael From mdmurray@MIT.EDU Thu Nov 17 03:08:57 2005 Return-Path: Received: from south-station-annex.mit.edu (SOUTH-STATION-ANNEX.MIT.EDU [18.72.1.2]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAH88v5o004714 for <6042-probs@theory.lcs.mit.edu>; Thu, 17 Nov 2005 03:08:57 -0500 Received: from central-city-carrier-station.mit.edu (CENTRAL-CITY-CARRIER-STATION.MIT.EDU [18.7.7.72]) by south-station-annex.mit.edu (8.12.4/8.9.2) with ESMTP id jAH88tCE021568; Thu, 17 Nov 2005 03:08:56 -0500 (EST) Received: from outgoing-legacy.mit.edu (OUTGOING-LEGACY.MIT.EDU [18.7.22.104]) by central-city-carrier-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAH88tM3024254; Thu, 17 Nov 2005 03:08:55 -0500 (EST) Received: from [18.234.0.116] (MDMURRAY.MIT.EDU [18.234.0.116]) ) by outgoing-legacy.mit.edu (8.12.4/8.12.4) with ESMTP id jAH88mMu026115; Thu, 17 Nov 2005 03:08:48 -0500 (EST) Mime-Version: 1.0 (Apple Message framework v746.2) Content-Transfer-Encoding: 7bit Message-Id: <0D51FC0A-5E73-4CA7-846E-9E0334875C73@mit.edu> Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed To: 6042-probs@theory.csail.mit.edu, 6042-probs@theory.lcs.mit.edu From: Michael Murray Subject: [Hanson] Generating Functions Notes Date: Thu, 17 Nov 2005 03:07:43 -0500 X-Mailer: Apple Mail (2.746.2) X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 901 Content-Length: 494 X-Status: D X-Keywords: NonJunk Having never seen generating functions before I think the notes and lecture where a great introduction and everything so far is pretty clear. I like the use of whiteboard in lecture today, I thought it was much easier to follow than the slides and the lecture was at a much nicer pace than usual. I am however a little unclear in the explanation of the product rule. I don't really understand the table and I don't know why c_n = a_0*b_n + a_1*b_n-1 + a_2*b_n-2... Thanks, Michael From shreyes19@gmail.com Thu Nov 17 13:37:13 2005 Return-Path: Received: from nproxy.gmail.com (nproxy.gmail.com [64.233.182.194]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAHIbC5o029031 for <6042-probs@theory.lcs.mit.edu>; Thu, 17 Nov 2005 13:37:12 -0500 Received: by nproxy.gmail.com with SMTP id l36so489563nfa for <6042-probs@theory.lcs.mit.edu>; Thu, 17 Nov 2005 10:37:12 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:sender:to:subject:mime-version:content-type; b=lsgHD6RMcULSavVlis8wZ0uUjyKX8f6OdLpANjlqbpqZ0kzkq/w6E9u34t2dTwGpex3ic30GCgfF7RBHTBIu4z6mgn1PJUIqav30h88EjUB9O79O+lkkb9NTSt00Z2oIWbfDeFxiZu+q+98NyBXw/QpqOHD2dzOKZkp2SVxDEFQ= Received: by 10.48.229.10 with SMTP id b10mr440397nfh; Thu, 17 Nov 2005 10:37:12 -0800 (PST) Received: by 10.48.161.8 with HTTP; Thu, 17 Nov 2005 10:37:12 -0800 (PST) Message-ID: <3c33fe380511171037i4f862502kda5ec4d351eb5f3e@mail.gmail.com> Date: Thu, 17 Nov 2005 13:37:12 -0500 From: Shreyes Seshasai Sender: shreyes19@gmail.com To: 6042-probs@theory.lcs.mit.edu Subject: [Sayan] Week 11 Reading Comments MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_50059_899955.1132252632166" Status: RO X-UID: 902 Content-Length: 1877 X-Keywords: NonJunk ------=_Part_50059_899955.1132252632166 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Hi, That last "impossible" counting problem was cool. Funny though how the numbers seemed to cancel perfectly... It's still cool to know that the procedure works like that, even if the answer doesn't turn out as nice ever= y time. Since most of the first half of the notes has been done in lecture already, I'm guessing the rest will be done tomorrow. The question I have regarding the second section is in reference to the Convolution Rule (page 10). Is there an easy way to compute the generating function if the two sets A and = B are not disjoint? It's hard for me to even think of a common scenario when this is the case, but I'd be interested to see if there's an easy way someone has though of to do it. Thanks, Shreyes ------=_Part_50059_899955.1132252632166 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Hi,

That last "impossible" counting problem was cool.  Funny tho= ugh how the numbers seemed to cancel perfectly... It's still cool to know that the procedure works like that, even if the answer doesn't turn out as nice every time.
Since most of the first half of the notes has been done in lecture already, I'm guessing the rest will be done tomorrow.  The question I have regarding the second section is in reference to the Convolution Rule (page 10).  Is there an easy way to compute the generating function if the two sets A and B are not disjoint?  It's hard for me to even think of a common scenario when this is the case, but I'd be interested to see if there's an easy way someone has though of to do it.

Thanks,
Shreyes
------=_Part_50059_899955.1132252632166-- From hmzhou@blackbird.csail.mit.edu Thu Nov 17 16:18:19 2005 Return-Path: Received: from blackbird.csail.mit.edu (blackbird.csail.mit.edu [128.30.51.72]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAHLIJ5o004898; Thu, 17 Nov 2005 16:18:19 -0500 Received: from blackbird.csail.mit.edu (localhost.localdomain [127.0.0.1]) by blackbird.csail.mit.edu (8.13.4/8.13.4) with ESMTP id jAHLII8n016097; Thu, 17 Nov 2005 16:18:18 -0500 Received: from localhost (hmzhou@localhost) by blackbird.csail.mit.edu (8.13.4/8.13.4/Submit) with ESMTP id jAHLIIt6016094; Thu, 17 Nov 2005 16:18:18 -0500 Date: Thu, 17 Nov 2005 16:18:18 -0500 (EST) From: Hanson Zhou To: Michael Murray cc: 6042-probs@theory.csail.mit.edu Subject: Re: [Hanson] Generating Functions Notes In-Reply-To: <0D51FC0A-5E73-4CA7-846E-9E0334875C73@mit.edu> Message-ID: References: <0D51FC0A-5E73-4CA7-846E-9E0334875C73@mit.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-UID: 903 Content-Length: 1092 X-Keywords: The table is merely a multiplication table to show you the result of multiplying a term from each sum. From it you should be able to see which terms contribute to the coefficient of x^n in the final product. Specifically, each pair that multiplies to give x^n contributes to the coefficient of x^n in the final answer. The pairs that contribute are therefore: (0,n), (1, n-1), (2, n-2)... and hence the coefficient on x^n in the final product is: c_n = a_0*b_n + a_1*b_n-1 + a_2*b_n-2... See me if you are still confused. -Hanson On Thu, 17 Nov 2005, Michael Murray wrote: > Having never seen generating functions before I think the notes and > lecture where a great introduction and everything so far is pretty > clear. I like the use of whiteboard in lecture today, I thought it > was much easier to follow than the slides and the lecture was at a > much nicer pace than usual. > > I am however a little unclear in the explanation of the product rule. > I don't really understand the table and I don't know why > > c_n = a_0*b_n + a_1*b_n-1 + a_2*b_n-2... > > Thanks, > Michael > From ozcan@MIT.EDU Thu Nov 17 16:41:13 2005 Return-Path: Received: from grand-central-station.mit.edu (GRAND-CENTRAL-STATION.MIT.EDU [18.7.21.82]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAHLfD5o018719 for <6042-probs@theory.lcs.mit.edu>; Thu, 17 Nov 2005 16:41:13 -0500 Received: from outgoing-legacy.mit.edu (OUTGOING-LEGACY.MIT.EDU [18.7.22.104]) by grand-central-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAHLfCv0013056 for <6042-probs@theory.lcs.mit.edu>; Thu, 17 Nov 2005 16:41:12 -0500 (EST) Received: from ebrum.mit.edu (OZCAN.MIT.EDU [18.241.3.106]) ) by outgoing-legacy.mit.edu (8.12.4/8.12.4) with ESMTP id jAHLf4ol001023 for <6042-probs@theory.lcs.mit.edu>; Thu, 17 Nov 2005 16:41:05 -0500 (EST) Message-Id: <5.2.1.1.2.20051117163659.02394d48@po12.mit.edu> X-Sender: ozcan@hesiod (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.2.1 Date: Thu, 17 Nov 2005 16:41:02 -0500 To: 6042-probs@theory.lcs.mit.edu From: Yasin Ozcan Subject: [Hanson]reading comments Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 904 Content-Length: 208 X-Keywords: Section 3.2 as a whole, i.e. the construction of a closed form for the Fibonacci numbers: It is quite impressive to be able to code this much information into only one simple function, I am really amazed. From fluff@MIT.EDU Thu Nov 17 17:24:19 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAHMOJ5o010091 for <6042-probs@theory.lcs.mit.edu>; Thu, 17 Nov 2005 17:24:19 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAHMOHYW029150 for <6042-probs@theory.lcs.mit.edu>; Thu, 17 Nov 2005 17:24:18 -0500 (EST) Received: from [18.244.6.19] (SENIOR-TWO-SEVENTY-FOUR.MIT.EDU [18.244.6.19]) (authenticated bits=0) (User authenticated as fluff@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAHMOBk3018759 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=NOT) for <6042-probs@theory.lcs.mit.edu>; Thu, 17 Nov 2005 17:24:12 -0500 (EST) Mime-Version: 1.0 (Apple Message framework v734) Content-Transfer-Encoding: 7bit Message-Id: Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed To: 6042-probs@theory.lcs.mit.edu From: Crystal Chao Subject: [Jelani] week 11 reading Date: Thu, 17 Nov 2005 17:22:08 -0500 X-Mailer: Apple Mail (2.734) X-Spam-Score: 2.706 X-Spam-Level: ** (2.706) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 905 Content-Length: 346 X-Keywords: NonJunk "Amazing!" It's still not entirely intuitive to me why the Convolution Rule works, but overall the reading was interesting, flowed well, and made sense. I liked how the reading was shorter and all on one topic, instead of like previous readings that were on a million different things all glommed onto some 25-page monstrosity. ~Crystal From mracich@MIT.EDU Thu Nov 17 18:25:56 2005 Return-Path: Received: from grand-central-station.mit.edu (GRAND-CENTRAL-STATION.MIT.EDU [18.7.21.82]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAHNPu5o029959 for <6042-probs@theory.lcs.mit.edu>; Thu, 17 Nov 2005 18:25:56 -0500 Received: from outgoing-legacy.mit.edu (OUTGOING-LEGACY.MIT.EDU [18.7.22.104]) by grand-central-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAHNPuv0017621 for <6042-probs@theory.lcs.mit.edu>; Thu, 17 Nov 2005 18:25:56 -0500 (EST) Received: from MACGREGOR-FOUR-O-ONE.MIT.EDU (MACGREGOR-FOUR-O-ONE.MIT.EDU [18.239.6.146]) ) by outgoing-legacy.mit.edu (8.12.4/8.12.4) with ESMTP id jAHNPlMu018802 for <6042-probs@theory.lcs.mit.edu>; Thu, 17 Nov 2005 18:25:48 -0500 (EST) Subject: [Sayan] Comments for Course Notes, Week 11 (Generating Functions) From: Moira Racich To: 6042-probs@theory.lcs.mit.edu Content-Type: text/plain Date: Thu, 17 Nov 2005 18:25:47 -0500 Message-Id: <1132269947.8084.22.camel@localhost.localdomain> Mime-Version: 1.0 X-Mailer: Evolution 2.4.1 Content-Transfer-Encoding: 7bit X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 906 Content-Length: 276 X-Keywords: I found section 3.2, "Finding a Closed Form", (starting on page 8) confusing, both in the notes and when it was covered in lecture. I would appreciate it if this was explained further. I think I would also find a brief partial fractions review very helpful. Moira Racich From ereid@MIT.EDU Thu Nov 17 18:36:30 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAHNaU5o031118 for <6042-probs@theory.lcs.mit.edu>; Thu, 17 Nov 2005 18:36:30 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAHNaTYW022105 for <6042-probs@theory.lcs.mit.edu>; Thu, 17 Nov 2005 18:36:29 -0500 (EST) Received: from [18.242.6.198] (NEXT-FOUR-FIFTY-THREE.MIT.EDU [18.242.6.198]) (authenticated bits=0) (User authenticated as ereid@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAHNaMYF006340 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=NOT) for <6042-probs@theory.lcs.mit.edu>; Thu, 17 Nov 2005 18:36:22 -0500 (EST) Mime-Version: 1.0 (Apple Message framework v734) Content-Transfer-Encoding: 7bit Message-Id: <94C740B9-2FE5-4D4D-BC5D-6FD20BC9D421@MIT.EDU> Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed To: 6042-probs@theory.lcs.mit.edu From: Elizabeth Reid Subject: [Hanson] Reading Comments Date: Thu, 17 Nov 2005 18:36:10 -0500 X-Mailer: Apple Mail (2.734) X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 907 Content-Length: 148 X-Keywords: NonJunk The reading makes sense, but I feel like I wouldn't be able to do it myself. Is there anywhere I can go that would help me practice this stuff? From dangut@MIT.EDU Thu Nov 17 19:13:52 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAI0Dq5o018276 for <6042-probs@theory.csail.MIT.EDU>; Thu, 17 Nov 2005 19:13:52 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAI0DpYW016474 for <6042-probs@theory.csail.MIT.EDU>; Thu, 17 Nov 2005 19:13:51 -0500 (EST) Received: from w92-130-webmail-5.mit.edu (W92-130-WEBMAIL-5.MIT.EDU [18.7.22.136]) ) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAI0Dn9K013316 for <6042-probs@theory.csail.MIT.EDU>; Thu, 17 Nov 2005 19:13:49 -0500 (EST) Received: (from nobody@localhost) by w92-130-webmail-5.mit.edu (8.12.4) id jAI0DnGM007198; Thu, 17 Nov 2005 19:13:49 -0500 Received: from MACGREGOR-FOUR-EIGHTY-THREE.MIT.EDU (MACGREGOR-FOUR-EIGHTY-THREE.MIT.EDU [18.239.6.228]) (User authenticated as dangut@ATHENA.MIT.EDU) by webmail.mit.edu (Horde MIME library) with HTTP for ; Thu, 17 Nov 2005 19:13:49 -0500 Message-ID: <20051117191349.qo4qd0bqx2os404s@webmail.mit.edu> Date: Thu, 17 Nov 2005 19:13:49 -0500 From: Daniel A Gutierrez To: 6042-probs@theory.csail.MIT.EDU Subject: [Hansen] TP11 Reading Response MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) H3 (4.0.3) X-Spam-Score: -2.599 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 908 Content-Length: 160 X-Keywords: NonJunk These all make logical sense, but I was wondering if by chance you have a list or know where to find one so that I can review geometric summing? Thanks, Daniel From petek@MIT.EDU Thu Nov 17 20:53:08 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAI1r85o010400 for <6042-probs@theory.lcs.mit.edu>; Thu, 17 Nov 2005 20:53:08 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAI1r7YW012863 for <6042-probs@theory.lcs.mit.edu>; Thu, 17 Nov 2005 20:53:07 -0500 (EST) Received: from [18.194.1.37] (SN-THIRTY-SEVEN.MIT.EDU [18.194.1.37]) (authenticated bits=0) (User authenticated as petek@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAI1r5s5028547 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for <6042-probs@theory.lcs.mit.edu>; Thu, 17 Nov 2005 20:53:05 -0500 (EST) Message-ID: <437D340D.1000309@mit.edu> Date: Thu, 17 Nov 2005 20:53:17 -0500 From: Pete Kruskall User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: 6042-probs@theory.lcs.mit.edu Subject: [Jelani] This Week's Notes Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 909 Content-Length: 377 X-Keywords: NonJunk I'm still shaky on why a generating function is called what it is... Also need some more practice on counting with these things. It is kinda cool that you can solve some complex probs that way.... -P -- Pete Kruskall 28 The Fenway Boston, MA 02215 ::::::::::::::::::::::::::::: 617.536.9925 :::Sigma Nu::::: 508.843.5861 ::::Cell Phone:: ::::http://tege.mit.edu:::::: From tylerw@MIT.EDU Thu Nov 17 21:10:04 2005 Return-Path: Received: from grand-central-station.mit.edu (GRAND-CENTRAL-STATION.MIT.EDU [18.7.21.82]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAI2A35o022126 for <6042-probs@theory.csail.mit.edu>; Thu, 17 Nov 2005 21:10:03 -0500 Received: from outgoing-legacy.mit.edu (OUTGOING-LEGACY.MIT.EDU [18.7.22.104]) by grand-central-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAI2A3v0023101 for <6042-probs@theory.csail.mit.edu>; Thu, 17 Nov 2005 21:10:03 -0500 (EST) Received: from [18.246.1.160] (TYLERW.MIT.EDU [18.246.1.160]) ) by outgoing-legacy.mit.edu (8.12.4/8.12.4) with ESMTP id jAI2A0ok013801 for <6042-probs@theory.csail.mit.edu>; Thu, 17 Nov 2005 21:10:01 -0500 (EST) Mime-Version: 1.0 (Apple Message framework v746.2) Content-Transfer-Encoding: 7bit Message-Id: <3431AB96-1519-4D5A-9413-03E2898B828C@mit.edu> Content-Type: text/plain; charset=US-ASCII; format=flowed To: 6042-probs@theory.csail.mit.edu From: Tyler Williams Subject: [TA-name] Week 11 Comments Date: Thu, 17 Nov 2005 21:09:48 -0500 X-Mailer: Apple Mail (2.746.2) X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 910 Content-Length: 60 X-Keywords: NonJunk I thought the impossible counting problem was interesting. From bilodeau@MIT.EDU Thu Nov 17 21:32:57 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAI2Wv5o024360 for <6042-probs@theory.lcs.mit.edu>; Thu, 17 Nov 2005 21:32:57 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAI2WuYW005191 for <6042-probs@theory.lcs.mit.edu>; Thu, 17 Nov 2005 21:32:56 -0500 (EST) Received: from pbilodeau (MACGREGOR-TWO-TWENTY-ONE.MIT.EDU [18.239.5.221]) (authenticated bits=0) (User authenticated as bilodeau@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAI2Wmbc004247 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NOT) for <6042-probs@theory.lcs.mit.edu>; Thu, 17 Nov 2005 21:32:48 -0500 (EST) Message-Id: <200511180232.jAI2Wmbc004247@outgoing.mit.edu> From: "Peter Bilodeau" To: <6042-probs@theory.lcs.mit.edu> Subject: [jelani] reading comments Date: Thu, 17 Nov 2005 21:32:38 -0500 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_NextPart_000_0000_01C5EBBE.6F45DBD0" X-Mailer: Microsoft Office Outlook, Build 11.0.5510 Thread-Index: AcXr6FeVrw3dzlYHRUCTZ2eGwvMXmQ== X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2180 X-Spam-Score: 2.779 X-Spam-Level: ** (2.779) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 911 Content-Length: 2064 X-Keywords: NonJunk This is a multi-part message in MIME format. ------=_NextPart_000_0000_01C5EBBE.6F45DBD0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit In this week's reading, part of what was hard to understand was the way the formula for the infinite sum was used to describe the series that generates the coefficients. Trying to think about what is being substituted for x and what operations happen on each term is a little difficult for me to grasp. ------=_NextPart_000_0000_01C5EBBE.6F45DBD0 Content-Type: text/html; charset="us-ascii" Content-Transfer-Encoding: quoted-printable

In this week’s reading, part of what was hard = to understand was the way the formula for the infinite sum was used to = describe the series that generates the coefficients.  Trying to think about = what is being substituted for x and what operations happen on each term is a = little difficult for me to grasp.

------=_NextPart_000_0000_01C5EBBE.6F45DBD0-- From jehan@MIT.EDU Thu Nov 17 21:33:32 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAI2XV5o024721 for <6042-probs@theory.csail.mit.edu>; Thu, 17 Nov 2005 21:33:32 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAI2XUYW005459 for <6042-probs@theory.csail.mit.edu>; Thu, 17 Nov 2005 21:33:30 -0500 (EST) Received: from mopspeak.mit.edu (EASTCAMPUS-SIX-SIXTY-SEVEN.MIT.EDU [18.238.5.156]) (authenticated bits=0) (User authenticated as jehan@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAI2XSLZ004350 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=NOT) for <6042-probs@theory.csail.mit.edu>; Thu, 17 Nov 2005 21:33:29 -0500 (EST) Message-Id: <5.2.1.1.2.20051117212717.00bc1968@po14.mit.edu> X-Sender: jehan@hesiod X-Mailer: QUALCOMM Windows Eudora Version 5.2.1 Date: Thu, 17 Nov 2005 21:31:46 -0500 To: 6042-probs@theory.csail.mit.edu From: Jehan deFonseka Subject: [Sayan] Week 11 Comments Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 912 Content-Length: 63 X-Keywords: NonJunk I don't understand relating generating functions to counting. From dnreshef@MIT.EDU Thu Nov 17 21:36:34 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAI2aY5o028373 for <6042-probs@theory.lcs.MIT.EDU>; Thu, 17 Nov 2005 21:36:34 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAI2aWYW007236 for <6042-probs@theory.lcs.MIT.EDU>; Thu, 17 Nov 2005 21:36:32 -0500 (EST) Received: from w92-130-webmail-2.mit.edu (W92-130-WEBMAIL-2.MIT.EDU [18.7.22.132]) ) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAI2aQ0m004741 for <6042-probs@theory.lcs.MIT.EDU>; Thu, 17 Nov 2005 21:36:26 -0500 (EST) Received: (from nobody@localhost) by w92-130-webmail-2.mit.edu (8.12.4) id jAI2aQT1002449; Thu, 17 Nov 2005 21:36:26 -0500 Received: from MACGREGOR-EIGHTY-SIX.MIT.EDU (MACGREGOR-EIGHTY-SIX.MIT.EDU [18.239.5.86]) (User authenticated as dnreshef@ATHENA.MIT.EDU) by webmail.mit.edu (Horde MIME library) with HTTP for ; Thu, 17 Nov 2005 21:36:26 -0500 Message-ID: <20051117213626.gdig760cb4oc0ck8@webmail.mit.edu> Date: Thu, 17 Nov 2005 21:36:26 -0500 From: David N Reshef To: 6042-probs@theory.lcs.MIT.EDU Subject: [Hanson] Reading 11 Comments MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) H3 (4.0.3) X-Spam-Score: -2.599 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 913 Content-Length: 310 X-Keywords: NonJunk Of all of the course material we have covered thus far, this has been the most interesting, and I would like to get into it a lot more in class. I had a little bit of trouble with the section on counting with generating functions on page 9. Can we go over how to build generating functions that count? -Dave From hectorb@MIT.EDU Thu Nov 17 22:07:12 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAI37C5o031052 for <6042-probs@theory.lcs.mit.edu>; Thu, 17 Nov 2005 22:07:12 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAI379YW024840; Thu, 17 Nov 2005 22:07:09 -0500 (EST) Received: from [18.246.7.127] (BEXLEY-SIX-THIRTY-EIGHT.MIT.EDU [18.246.7.127]) (authenticated bits=0) (User authenticated as hectorb@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAI376Be009319 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT); Thu, 17 Nov 2005 22:07:06 -0500 (EST) Message-ID: <437D4555.2070302@mit.edu> Date: Thu, 17 Nov 2005 22:07:01 -0500 From: Hector Beltran User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: 6042-probs@theory.lcs.mit.edu Subject: [Hanson] Week 11 Reading Comment Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 2.706 X-Spam-Level: ** (2.706) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 914 Content-Length: 222 X-Keywords: NonJunk This week's reading was very straight forward; there wasn't anything I had a hard time understanding. I found the last section the most interesting, being able to generate functions for nasty counting problems. -Hector From icharny@MIT.EDU Thu Nov 17 22:08:33 2005 Return-Path: Received: from south-station-annex.mit.edu (SOUTH-STATION-ANNEX.MIT.EDU [18.72.1.2]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAI38X5o031285 for <6042-probs@theory.csail.mit.edu>; Thu, 17 Nov 2005 22:08:33 -0500 Received: from central-city-carrier-station.mit.edu (CENTRAL-CITY-CARRIER-STATION.MIT.EDU [18.7.7.72]) by south-station-annex.mit.edu (8.12.4/8.9.2) with ESMTP id jAI38W5b021833 for <6042-probs@theory.csail.mit.edu>; Thu, 17 Nov 2005 22:08:32 -0500 (EST) Received: from outgoing-legacy.mit.edu (OUTGOING-LEGACY.MIT.EDU [18.7.22.104]) by central-city-carrier-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAI38WAe009343 for <6042-probs@theory.csail.mit.edu>; Thu, 17 Nov 2005 22:08:32 -0500 (EST) Received: from [127.0.0.1] (EASTCAMPUS-NINE-EIGHTY-THREE.MIT.EDU [18.238.6.216]) ) by outgoing-legacy.mit.edu (8.12.4/8.12.4) with ESMTP id jAI38JMw028294 for <6042-probs@theory.csail.mit.edu>; Thu, 17 Nov 2005 22:08:30 -0500 (EST) Message-ID: <437D45A4.3090007@mit.edu> Date: Thu, 17 Nov 2005 22:08:20 -0500 From: Isaac Charny User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: 6042-probs@theory.csail.mit.edu Subject: [Sayan] Week 11 Comments Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 915 Content-Length: 98 X-Keywords: NonJunk I don't understand counting with functions (section 4, page 9). Please clarify this in lecture. From vixen@MIT.EDU Thu Nov 17 22:38:02 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAI3c25o010006 for <6042-probs@theory.lcs.mit.edu>; Thu, 17 Nov 2005 22:38:02 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAI3c1YW012690 for <6042-probs@theory.lcs.mit.edu>; Thu, 17 Nov 2005 22:38:01 -0500 (EST) Received: from [18.243.2.26] (WALLFLOWER.MIT.EDU [18.243.2.26]) (authenticated bits=0) (User authenticated as vixen@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAI3bvxW013920 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=NOT) for <6042-probs@theory.lcs.mit.edu>; Thu, 17 Nov 2005 22:37:59 -0500 (EST) Mime-Version: 1.0 X-Sender: vixen@hesiod Message-Id: Date: Thu, 17 Nov 2005 22:35:56 -0500 To: 6042-probs@theory.lcs.mit.edu From: Amanda Seybold Subject: LN11 Content-Type: text/plain; charset="us-ascii" ; format="flowed" X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 916 Content-Length: 69 X-Keywords: I found the part about counting with generating functions confusing. From dowgun@MIT.EDU Thu Nov 17 22:58:36 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAI3wa5o014963 for <6042-probs@theory.lcs.MIT.EDU>; Thu, 17 Nov 2005 22:58:36 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAI3wZYW025233 for <6042-probs@theory.lcs.MIT.EDU>; Thu, 17 Nov 2005 22:58:35 -0500 (EST) Received: from w92-130-webmail-4.mit.edu (W92-130-WEBMAIL-4.MIT.EDU [18.7.22.135]) ) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAI3wSJq017238 for <6042-probs@theory.lcs.MIT.EDU>; Thu, 17 Nov 2005 22:58:29 -0500 (EST) Received: (from nobody@localhost) by w92-130-webmail-4.mit.edu (8.12.4) id jAI3wSFn010054; Thu, 17 Nov 2005 22:58:28 -0500 Received: from PLP-ONE-FORTY-THREE.MIT.EDU (PLP-ONE-FORTY-THREE.MIT.EDU [18.218.1.143]) (User authenticated as dowgun@ATHENA.MIT.EDU) by webmail.mit.edu (Horde MIME library) with HTTP for ; Thu, 17 Nov 2005 22:58:28 -0500 Message-ID: <20051117225828.bsxr9oqa0j0gw44g@webmail.mit.edu> Date: Thu, 17 Nov 2005 22:58:28 -0500 From: Neil M Dowgun To: 6042-probs@theory.lcs.MIT.EDU Subject: [Hanson] reading question MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) H3 (4.0.3) X-Spam-Score: -2.599 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 917 Content-Length: 553 X-Status: A X-Keywords: NonJunk So I realized that the example where we found the coefficiants for the Fibonacci sequence doesn't really provide a clean fomulaic way to find coefficiants given a closed form. I guess there's just always going to be some dirty math to do. Anyway, I was wondering if using the Taylor expansion to find the coefficiants was always a viable option. I mean, I realize that it would be a real pain to take the derivative of an expression say, thirty times, but it just seems like a more surefire way to get the answer if it really is foolproof. Thanks, Neil From brevzin@MIT.EDU Thu Nov 17 23:30:43 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAI4Uh5o021455 for <6042-probs@theory.csail.mit.edu>; Thu, 17 Nov 2005 23:30:43 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAI4UgYW013921 for <6042-probs@theory.csail.mit.edu>; Thu, 17 Nov 2005 23:30:42 -0500 (EST) Received: from BARRY.mit.edu (PLP-TWELVE.MIT.EDU [18.218.1.12]) (authenticated bits=0) (User authenticated as brevzin@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAI4UZwH022543 (version=TLSv1/SSLv3 cipher=DES-CBC3-SHA bits=168 verify=NOT) for <6042-probs@theory.csail.mit.edu>; Thu, 17 Nov 2005 23:30:36 -0500 (EST) Message-Id: <6.1.2.0.1.20051117232905.019f2b98@po14.mit.edu> X-Sender: brevzin@hesiod X-Mailer: QUALCOMM Windows Eudora Version 6.1.2.0 Date: Thu, 17 Nov 2005 23:30:35 -0500 To: 6042-probs@theory.csail.mit.edu From: Barry Revzin Subject: [Hanson] Reading Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 918 Content-Length: 421 X-Keywords: For the convolution rule, I think it's really confusing that it's called the convolution rule. It really has nothing to do with the idea of a convolution from analysis, does it ? I'm really used to the convolution of f and g (f*g) being the integral of f(y)g(x-y)dy. Why IS it called that then ? Why not like... disjoint union rule ? Or Countable Additivity, which would be consistent with measure theory... Barry From tonyng@MIT.EDU Thu Nov 17 23:56:45 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAI4uj5o023106 for <6042-probs@theory.lcs.mit.edu>; Thu, 17 Nov 2005 23:56:45 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAI4uhYW028803 for <6042-probs@theory.lcs.mit.edu>; Thu, 17 Nov 2005 23:56:44 -0500 (EST) Received: from TNG.mit.edu (BURTON-TWO-TWENTY-SIX.MIT.EDU [18.247.5.226]) (authenticated bits=0) (User authenticated as tonyng@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAI4udHe026272 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=NOT) for <6042-probs@theory.lcs.mit.edu>; Thu, 17 Nov 2005 23:56:41 -0500 (EST) Message-Id: <5.2.1.1.2.20051117235257.02142d78@po9.mit.edu> X-Sender: tonyng@hesiod X-Mailer: QUALCOMM Windows Eudora Version 5.2.1 Date: Thu, 17 Nov 2005 23:56:41 -0500 To: 6042-probs@theory.lcs.mit.edu From: Tony Ng Subject: [Jelani] Reading Comments: Week 11 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 919 Content-Length: 350 X-Status: A X-Keywords: NonJunk I found the fruit counting problem ("An 'Impossible' Counting Problem, pg12) to be very interesting. I didn't understand the need for generating functions during the last lecture and it seemed excessively complicated to do, however, now I understand why it is necessary because it may be the only way we know how to solve some problems. - Tony From ctsims@MIT.EDU Fri Nov 18 00:03:39 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAI53d5o024488 for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 00:03:39 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAI53cYW002523 for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 00:03:38 -0500 (EST) Received: from HowardRoark.mit.edu (EASTCAMPUS-EIGHT-THIRTY-EIGHT.MIT.EDU [18.238.6.71]) (authenticated bits=0) (User authenticated as ctsims@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAI53aDr027191 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=NOT) for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 00:03:36 -0500 (EST) Message-Id: <5.2.1.1.2.20051117223854.02036418@po12.mit.edu> X-Sender: ctsims@po12.mit.edu X-Mailer: QUALCOMM Windows Eudora Version 5.2.1 Date: Fri, 18 Nov 2005 00:01:19 -0500 To: 6042-probs@theory.lcs.mit.edu From: Clayton Sims Subject: [6.042] Reading Comments Lecture Notes 8 - Clayton Sims Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 920 Content-Length: 420 X-Status: D X-Keywords: Junk I felt like the material on page 7 was the most challenging. Generalizing the method of turning a sequence of coefficients into different Function Generators that are easily converted into a representation of the function is something that I feel I would benefit from practicing. Additionally, a quick review (5 mins.) of partial fractions in class would be nice, although not entirely necessary. -Clayton Sims From jacques@MIT.EDU Fri Nov 18 00:17:13 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAI5HD5o032741 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 18 Nov 2005 00:17:13 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAI5HCYW010134 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 18 Nov 2005 00:17:12 -0500 (EST) Received: from w92-130-webmail-4.mit.edu (W92-130-WEBMAIL-4.MIT.EDU [18.7.22.135]) ) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAI5H6Qr029343 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 18 Nov 2005 00:17:06 -0500 (EST) Received: (from nobody@localhost) by w92-130-webmail-4.mit.edu (8.12.4) id jAI5H6xb017829; Fri, 18 Nov 2005 00:17:06 -0500 Received: from EASTCAMPUS-ONE-O-THREE-HUNDRED-FORTY-EIGHT.MIT.EDU (EASTCAMPUS-ONE-O-THREE-HUNDRED-FORTY-EIGHT.MIT.EDU [18.238.7.81]) (User authenticated as jacques@ATHENA.MIT.EDU) by webmail.mit.edu (Horde MIME library) with HTTP for ; Fri, 18 Nov 2005 00:17:06 -0500 Message-ID: <20051118001706.zbxgn5qon6lw8ckg@webmail.mit.edu> Date: Fri, 18 Nov 2005 00:17:06 -0500 From: jacques To: 6042-probs@theory.lcs.MIT.EDU Subject: [David] Week 11 reading comments MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) H3 (4.0.3) X-Spam-Score: -2.599 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 921 Content-Length: 311 X-Keywords: NonJunk Page 11-12. I never thought the Taylor Series, which I'd seen and used many times to approximate functions, could be related combinatorics (aka. most surprising passage). I actually thought generating functions were a difficult concept until I read this example, since it was a series I was so familiar with. From sergiob@MIT.EDU Fri Nov 18 00:25:26 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAI5PQ5o001795 for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 00:25:26 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAI5PPYW014380 for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 00:25:25 -0500 (EST) Received: from mit-kf7uwcnbdr4.mit.edu (SENIOR-THREE-FIFTY-EIGHT.MIT.EDU [18.244.6.103]) (authenticated bits=0) (User authenticated as sergiob@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAI5PMuu000375 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=NOT) for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 00:25:22 -0500 (EST) Message-Id: <5.2.1.1.2.20051117222122.00c5c020@po14.mit.edu> X-Sender: sergiob@po14.mit.edu X-Mailer: QUALCOMM Windows Eudora Version 5.2.1 Date: Thu, 17 Nov 2005 22:25:17 -0700 To: 6042-probs@theory.csail.mit.edu From: Sergio Bacallado Subject: [David] Week 11 Comments Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 922 Content-Length: 362 X-Keywords: NonJunk I thought it was amazing how useful generating functions can be to solve counting problems. I would like to know if there is always an easy way to find a closed form for the nth term of a sequence, if you know the value of the generating function. That is, other than differentiating the function to get the Taylor expansion term. Sergio Bacallado Group A From jjmonzon@MIT.EDU Fri Nov 18 00:38:56 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAI5cu5o006909 for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 00:38:56 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAI5ctYW021231 for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 00:38:55 -0500 (EST) Received: from JOSHDESKTOP.mit.edu (BURTON-TWO-TWELVE.MIT.EDU [18.247.5.212]) (authenticated bits=0) (User authenticated as jjmonzon@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAI5cqof001946 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 00:38:54 -0500 (EST) Message-Id: <6.2.3.4.2.20051118003612.01e0a888@po9.mit.edu> X-Mailer: QUALCOMM Windows Eudora Version 6.2.3.4 Date: Fri, 18 Nov 2005 00:38:58 -0500 To: 6042-probs@theory.csail.mit.edu From: "Joshua Jen C. Monzon" Subject: David - Reading Comments Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 923 Content-Length: 391 X-Keywords: NonJunk I'm a little confused on the convolution rule. Perhaps this would be explained a little more in class. Also, I didn't really understand how they obtained the answer in the last problem of the tutorial. Hope tomorrow's lecture clears this up. Josh Joshua Jen C. Monzon Massachusetts Institute of Technology Electrical Engineering with Computer Science jjmonzon@mit.edu 617-803-7497 From aston@MIT.EDU Fri Nov 18 00:51:55 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAI5pt5o010259 for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 00:51:55 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAI5psYW027870 for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 00:51:54 -0500 (EST) Received: from astonlaptop (NEW-SEVENTY-TWO.MIT.EDU [18.241.5.72]) (authenticated bits=0) (User authenticated as aston@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAI5pl9e003405 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NOT) for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 00:51:48 -0500 (EST) Message-Id: <200511180551.jAI5pl9e003405@outgoing.mit.edu> Reply-To: From: "Aston Motes" To: <6042-probs@theory.csail.mit.edu> Subject: [Hanson] Week 11 Comments Date: Fri, 18 Nov 2005 00:51:47 -0500 Organization: MIT MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_NextPart_000_0000_01C5EBDA.417239D0" X-Mailer: Microsoft Office Outlook, Build 11.0.6353 Thread-Index: AcXsBClqDP/jYmp1QGqsP8mEQisXug== X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2180 X-Spam-Score: 2.778 X-Spam-Level: ** (2.778) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 924 Content-Length: 1335 X-Keywords: This is a multi-part message in MIME format. ------=_NextPart_000_0000_01C5EBDA.417239D0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit I was really impressed by the fruit problem (pages 12 and 13), but I don't feel like the explanation for why the convolution is the right answer to problems like these (page 10) was a very convincing one. - Aston ------=_NextPart_000_0000_01C5EBDA.417239D0 Content-Type: text/html; charset="us-ascii" Content-Transfer-Encoding: quoted-printable
I was = really=20 impressed by the fruit problem (pages 12 and 13), but I don't feel like = the=20 explanation for why the convolution is the right answer to problems like = these=20 (page 10) was a very convincing one.
 
    -=20 Aston
------=_NextPart_000_0000_01C5EBDA.417239D0-- From cwong08@MIT.EDU Fri Nov 18 01:34:01 2005 Return-Path: Received: from south-station-annex.mit.edu (SOUTH-STATION-ANNEX.MIT.EDU [18.72.1.2]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAI6Y15o015454 for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 01:34:01 -0500 Received: from central-city-carrier-station.mit.edu (CENTRAL-CITY-CARRIER-STATION.MIT.EDU [18.7.7.72]) by south-station-annex.mit.edu (8.12.4/8.9.2) with ESMTP id jAI6Y05b001251 for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 01:34:00 -0500 (EST) Received: from outgoing-legacy.mit.edu (OUTGOING-LEGACY.MIT.EDU [18.7.22.104]) by central-city-carrier-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAI6Y0Ae015586 for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 01:34:00 -0500 (EST) Received: from [127.0.0.1] (CWONG08.MIT.EDU [18.216.0.136]) ) by outgoing-legacy.mit.edu (8.12.4/8.12.4) with ESMTP id jAI6XmMv007563 for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 01:33:53 -0500 (EST) Message-ID: <437D75C7.9000305@mit.edu> Date: Fri, 18 Nov 2005 01:33:43 -0500 From: Chris Wong User-Agent: Mozilla Thunderbird 1.0 (Windows/20041206) X-Accept-Language: en-us, en MIME-Version: 1.0 To: 6042-probs@theory.csail.mit.edu Subject: [Sayan] Week 11 Comments Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 925 Content-Length: 101 X-Keywords: NonJunk The part about convolution (pg 10) is confusing to me. I don't really get what it's trying to say. From scot@MIT.EDU Fri Nov 18 01:57:35 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAI6vZ5o025168 for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 01:57:35 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAI6vYYW029724 for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 01:57:34 -0500 (EST) Received: from [18.227.1.135] (ZBT-ONE-THIRTY-FIVE.MIT.EDU [18.227.1.135]) (authenticated bits=0) (User authenticated as scot@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAI6vPTM009350 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 01:57:27 -0500 (EST) Message-ID: <437D7B55.4000408@mit.edu> Date: Fri, 18 Nov 2005 01:57:25 -0500 From: Scot Frank User-Agent: Thunderbird 1.4 (Windows/20050908) MIME-Version: 1.0 To: 6042-probs@theory.lcs.mit.edu Subject: Comments Jelani Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 926 Content-Length: 267 X-Status: A X-Keywords: Hi, The biggest question I had from this week of notes was the reason that, while Prof. Meyer was on the board, he choose to round up on the sum, after erasing the second term. I was confused, and could not understand the conflicting explanations. Thanks, Scot From cbossard@MIT.EDU Fri Nov 18 03:03:47 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAI83l5o020660 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 18 Nov 2005 03:03:47 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAI83kYW029169 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 18 Nov 2005 03:03:46 -0500 (EST) Received: from w92-130-webmail-5.mit.edu (W92-130-WEBMAIL-5.MIT.EDU [18.7.22.136]) ) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAI83eUa013584 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 18 Nov 2005 03:03:40 -0500 (EST) Received: (from nobody@localhost) by w92-130-webmail-5.mit.edu (8.12.4) id jAI83ed1018729; Fri, 18 Nov 2005 03:03:40 -0500 Received: from 1116host44.starwoodbroadband.com (1116host44.starwoodbroadband.com [12.146.116.44]) (User authenticated as cbossard@ATHENA.MIT.EDU) by webmail.mit.edu (Horde MIME library) with HTTP for ; Fri, 18 Nov 2005 03:03:40 -0500 Message-ID: <20051118030340.i5w8dncex73kocgg@webmail.mit.edu> Date: Fri, 18 Nov 2005 03:03:40 -0500 From: cbossard@MIT.EDU To: 6042-probs@theory.lcs.MIT.EDU Subject: [David] Week 11 reading comments MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) H3 (4.0.3) X-Spam-Score: -1.638 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 927 Content-Length: 737 X-Keywords: NonJunk I find this to be an interesting topic although I have trouble reproducing and creating these functions on my own they generally make sense to me when I see them explained. In section 2.5 on products I am not seeing/understanding how the terms of the diagonal were collected so I don't see why it's not aobo + a1b1 instead of aobn etc. Again with although the convolution rule makes some sense to me in section 4.2 I dont see how they are getting the numbers from the formula that was created. I can see that each is (1+x) and they should be multiplied. Intuively I understand that there's 1 way to choose 0 elements, 2 ways to choose 1, etc but I do not see how this information can be attained from the 1+2x+x^2 equation. Cynthia From kjhollen@MIT.EDU Fri Nov 18 03:05:48 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAI85m5o020780 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 18 Nov 2005 03:05:48 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAI85lYW000154 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 18 Nov 2005 03:05:47 -0500 (EST) Received: from w92-130-webmail-2.mit.edu (W92-130-WEBMAIL-2.MIT.EDU [18.7.22.132]) ) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAI85f4Q013703 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 18 Nov 2005 03:05:41 -0500 (EST) Received: (from nobody@localhost) by w92-130-webmail-2.mit.edu (8.12.4) id jAI85fgN031472; Fri, 18 Nov 2005 03:05:41 -0500 Received: from c-65-96-174-14.hsd1.ma.comcast.net (c-65-96-174-14.hsd1.ma.comcast.net [65.96.174.14]) (User authenticated as kjhollen@ATHENA.MIT.EDU) by webmail.mit.edu (Horde MIME library) with HTTP for ; Fri, 18 Nov 2005 03:05:41 -0500 Message-ID: <20051118030541.5q6lwdoe1k0ockw8@webmail.mit.edu> Date: Fri, 18 Nov 2005 03:05:41 -0500 From: Kate Hollenbach To: 6042-probs@theory.lcs.MIT.EDU Subject: [Hanson] counting example MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) H3 (4.0.3) X-Spam-Score: -1.11 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 928 Content-Length: 113 X-Keywords: NonJunk the counting example for generating functions (p 12-13) is too cool!! hope we do some problems like it in class. From mpapi@MIT.EDU Fri Nov 18 03:31:57 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAI8Vv5o022344 for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 03:31:57 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAI8VtYW011622 for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 03:31:55 -0500 (EST) Received: from mpapi.MIT.EDU (MPAPI.MIT.EDU [18.239.4.219]) (authenticated bits=0) (User authenticated as mpapi@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAI8Vjge015001 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NOT) for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 03:31:45 -0500 (EST) Subject: [Jelani] week 11 comments From: Matt Papi To: 6042-probs@theory.lcs.mit.edu Content-Type: text/plain Date: Fri, 18 Nov 2005 03:33:27 -0500 Message-Id: <1132302808.31951.85.camel@localhost.localdomain> Mime-Version: 1.0 X-Mailer: Evolution 2.4.1 Content-Transfer-Encoding: 7bit X-Spam-Score: 3.076 X-Spam-Level: *** (3.076) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 929 Content-Length: 300 X-Keywords: NonJunk Section 3.2, page 8. I could use a review or appendix or something regarding partial fractions. The examples are good, but once in a while there are functions where the numerators of the split terms are polynomials - anything more complex than the given examples I don't remember how to do. - Matt From veracarr@MIT.EDU Fri Nov 18 03:59:05 2005 Return-Path: Received: from grand-central-station.mit.edu (GRAND-CENTRAL-STATION.MIT.EDU [18.7.21.82]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAI8x55o028025 for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 03:59:05 -0500 Received: from outgoing-legacy.mit.edu (OUTGOING-LEGACY.MIT.EDU [18.7.22.104]) by grand-central-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAI8x4v0004487 for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 03:59:04 -0500 (EST) Received: from [192.168.2.34] (c-67-176-37-51.hsd1.co.comcast.net [67.176.37.51]) ) by outgoing-legacy.mit.edu (8.12.4/8.12.4) with ESMTP id jAI8wuok000032 for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 03:58:57 -0500 (EST) Message-ID: <437DB426.1010801@mit.edu> Date: Fri, 18 Nov 2005 03:59:50 -0700 From: Vera Carr User-Agent: Mozilla Thunderbird 1.0.2 (Windows/20050317) X-Accept-Language: en-us, en MIME-Version: 1.0 To: 6042-probs@theory.lcs.mit.edu Subject: [Hanson] Generating Functions Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 3.817 X-Spam-Level: *** (3.817) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 930 Content-Length: 222 X-Keywords: NonJunk Genearting Functions pg 1 When trying to find the sequence for a generating function when you have written the function in closed form what's the best way to find the sequence? Do a taylor expansion on the closed form? From bakster@MIT.EDU Fri Nov 18 04:02:09 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAI9295o028402 for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 04:02:09 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAI928YW024820 for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 04:02:08 -0500 (EST) Received: from [18.246.6.125] (BEXLEY-THREE-EIGHTY.MIT.EDU [18.246.6.125]) (authenticated bits=0) (User authenticated as bakster@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAI926rG016482 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 04:02:06 -0500 (EST) Message-ID: <437D988C.8020808@mit.edu> Date: Fri, 18 Nov 2005 04:02:04 -0500 From: Alexander Bakst User-Agent: Mozilla Thunderbird 1.0.2 (Windows/20050317) X-Accept-Language: en-us, en MIME-Version: 1.0 To: 6042-probs@theory.lcs.mit.edu Subject: [David] Lecture Notes 11 Comments Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 931 Content-Length: 146 X-Keywords: NonJunk What kind of situations would require us to use values for x? In the readings it said that they are unusual or rare, I believe. Alexander Bakst From lmccart@MIT.EDU Fri Nov 18 04:19:49 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAI9Jn5o030028 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 18 Nov 2005 04:19:49 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAI9JmYW002337 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 18 Nov 2005 04:19:48 -0500 (EST) Received: from w92-130-webmail-2.mit.edu (W92-130-WEBMAIL-2.MIT.EDU [18.7.22.132]) ) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAI9Jfsp017236 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 18 Nov 2005 04:19:41 -0500 (EST) Received: (from nobody@localhost) by w92-130-webmail-2.mit.edu (8.12.4) id jAI9JfYh002961; Fri, 18 Nov 2005 04:19:41 -0500 Received: from AP-EIGHTY-FIVE.MIT.EDU (AP-EIGHTY-FIVE.MIT.EDU [18.153.1.85]) (User authenticated as lmccart@ATHENA.MIT.EDU) by webmail.mit.edu (Horde MIME library) with HTTP for ; Fri, 18 Nov 2005 04:19:41 -0500 Message-ID: <20051118041941.dpepyf0a3wf4k048@webmail.mit.edu> Date: Fri, 18 Nov 2005 04:19:41 -0500 From: Lauren McCarthy To: 6042-probs@theory.lcs.MIT.EDU Subject: [David] week 11 MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) H3 (4.0.3) X-Spam-Score: -2.599 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 932 Content-Length: 118 X-Keywords: NonJunk I did not find anything particularly confusing in this reading, but it was a pretty good reading nonetheless -Lauren From mukkala@MIT.EDU Fri Nov 18 04:23:04 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAI9N45o009796 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 18 Nov 2005 04:23:04 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAI9N2YW003746 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 18 Nov 2005 04:23:02 -0500 (EST) Received: from w92-130-webmail-2.mit.edu (W92-130-WEBMAIL-2.MIT.EDU [18.7.22.132]) ) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAI9Mue9017375 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 18 Nov 2005 04:22:56 -0500 (EST) Received: (from nobody@localhost) by w92-130-webmail-2.mit.edu (8.12.4) id jAI9MuI8003153; Fri, 18 Nov 2005 04:22:56 -0500 Received: from AP-EIGHTY-FIVE.MIT.EDU (AP-EIGHTY-FIVE.MIT.EDU [18.153.1.85]) (User authenticated as mukkala@ATHENA.MIT.EDU) by webmail.mit.edu (Horde MIME library) with HTTP for ; Fri, 18 Nov 2005 04:22:55 -0500 Message-ID: <20051118042255.gnsdycackpmsk80c@webmail.mit.edu> Date: Fri, 18 Nov 2005 04:22:55 -0500 From: Praveen Pamidimukkala To: 6042-probs@theory.lcs.MIT.EDU Subject: [Sayan] Week 11 Reading Comments MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) H3 (4.0.3) X-Spam-Score: -2.599 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 933 Content-Length: 229 X-Keywords: I'm not sure that I completely understand the last part of the reading. The application of generating functions to the fruit problem is kind of confusing. I hope to go over it in class on friday. Thanks, Praveen Pamidimukkala From kevin08@MIT.EDU Fri Nov 18 05:07:50 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAIA7o5o007134 for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 05:07:50 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAIA7mYW022208 for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 05:07:49 -0500 (EST) Received: from kevlar.mit.edu (NEXT-FIVE-EIGHTY-SIX.MIT.EDU [18.242.7.75]) (authenticated bits=0) (User authenticated as kevin08@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAIA7ekQ019043 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 05:07:41 -0500 (EST) Message-Id: <6.2.3.4.2.20051118050105.029324e0@po10.mit.edu> X-Mailer: QUALCOMM Windows Eudora Version 6.2.3.4 Date: Fri, 18 Nov 2005 05:07:35 -0500 To: 6042-probs@theory.lcs.mit.edu From: Kevin Wang Subject: [Hanson] Notes 11 Comments Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 934 Content-Length: 237 X-Status: A X-Keywords: NonJunk Hi, I thought this reading was fairly straightforward and understood all of it. With that being said though, if Prof. Meyers could go over proving the bookkeeper rule (Section 4.3) in class, that would be instructive. Thanks, Kevin From antonk@MIT.EDU Fri Nov 18 05:56:20 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAIAuK5o026391 for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 05:56:20 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAIAuJYW011817 for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 05:56:19 -0500 (EST) Received: from silencer (SILUET.MIT.EDU [18.234.0.112]) (authenticated bits=0) (User authenticated as antonk@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAIAuCNl020825 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NOT) for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 05:56:13 -0500 (EST) From: "Anton Katz" To: <6042-probs@theory.lcs.mit.edu> Subject: [david] needs more explanation Date: Fri, 18 Nov 2005 05:56:11 -0500 Organization: Massachusetts Institute of Technology Message-ID: <000501c5ec2e$b06336b0$0100a8c0@silencer> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_NextPart_000_0006_01C5EC04.C78D2EB0" X-Mailer: Microsoft Office Outlook 11 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2180 Thread-Index: AcXsLq5xzcUwNM7wQvaa4UevSlklXQ== X-Spam-Score: 0.758 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 935 Content-Length: 2554 X-Keywords: NonJunk This is a multi-part message in MIME format. ------=_NextPart_000_0006_01C5EC04.C78D2EB0 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit HI, I had problems with coming up with the generating functions. Is there anything else that can be used apart from the sums? Anton. ------=_NextPart_000_0006_01C5EC04.C78D2EB0 Content-Type: text/html; charset="US-ASCII" Content-Transfer-Encoding: quoted-printable

HI,

I had problems with coming up with the generating = functions.

Is there anything else that can be used apart from = the sums?

 

Anton.

 

------=_NextPart_000_0006_01C5EC04.C78D2EB0-- From arup@MIT.EDU Fri Nov 18 06:09:14 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAIB9E5o027665 for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 06:09:14 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAIB9DYW016940 for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 06:09:13 -0500 (EST) Received: from [18.247.7.36] (BURTON-FIVE-FORTY-SEVEN.MIT.EDU [18.247.7.36]) (authenticated bits=0) (User authenticated as arup@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAIB901h021311 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 06:09:08 -0500 (EST) Message-ID: <437DB623.2090907@mit.edu> Date: Fri, 18 Nov 2005 06:08:19 -0500 From: Arup Sarma User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: 6042-probs@theory.csail.mit.edu Subject: [Jelani] Week 11 Comments Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 936 Content-Length: 126 X-Keywords: NonJunk Section 4.2: I think this should be covered in lecture since I wasn't sure about the choosing with repetition stuff. |Arup| From lkini@MIT.EDU Fri Nov 18 08:36:40 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAIDad5o028758 for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 08:36:39 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAIDacYW000180 for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 08:36:38 -0500 (EST) Received: from [18.239.6.100] (MACGREGOR-THREE-FIFTY-FIVE.MIT.EDU [18.239.6.100]) (authenticated bits=0) (User authenticated as lkini@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAIDaUTh006684 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 08:36:31 -0500 (EST) Message-ID: <437DD8D5.3040909@mit.edu> Date: Fri, 18 Nov 2005 08:36:21 -0500 From: Lohith Kini User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: 6042-probs@theory.lcs.mit.edu Subject: [Hanson] Week 11 reading Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 937 Content-Length: 260 X-Keywords: NonJunk Hi Hanson, The most surprising thing I read in the lecture notes was how to use generating functions to count. This is immensely helpful for counting the larger, difficult counting questions such as that in the last few pages of the lecture notes. Lohith From kromer@MIT.EDU Fri Nov 18 09:17:06 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAIEH65o026891 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 18 Nov 2005 09:17:06 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAIEH4YW029178 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 18 Nov 2005 09:17:05 -0500 (EST) Received: from w92-130-webmail-5.mit.edu (W92-130-WEBMAIL-5.MIT.EDU [18.7.22.136]) ) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAIEGwb1017214 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 18 Nov 2005 09:16:58 -0500 (EST) Received: (from nobody@localhost) by w92-130-webmail-5.mit.edu (8.12.4) id jAIEGwXs010211; Fri, 18 Nov 2005 09:16:58 -0500 Received: from BURTON-TWO-THIRTY-FIVE.MIT.EDU (BURTON-TWO-THIRTY-FIVE.MIT.EDU [18.247.5.235]) (User authenticated as kromer@ATHENA.MIT.EDU) by webmail.mit.edu (Horde MIME library) with HTTP for ; Fri, 18 Nov 2005 09:16:58 -0500 Message-ID: <20051118091658.flzzeo34lb4ks0oo@webmail.mit.edu> Date: Fri, 18 Nov 2005 09:16:58 -0500 From: Katherine A Romer To: 6042-probs@theory.lcs.MIT.EDU Subject: [David] Email comments for reading MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) H3 (4.0.3) X-Spam-Score: -2.599 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 938 Content-Length: 337 X-Keywords: p. 10 "Informally, the only restrictions are that (1) the order in which items are selected is disregarded and (2) restrictions on the selection of items from sets A and B also apply in selecting items from A union B". Is there any way to use generating functions to count when the order in which items are selected matters? Katherine From ajshafer@MIT.EDU Fri Nov 18 09:21:56 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAIELu5o031432 for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 09:21:56 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAIELtYW003685 for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 09:21:55 -0500 (EST) Received: from ajshafer (AJSHAFER.MIT.EDU [18.247.4.109]) (authenticated bits=0) (User authenticated as ajshafer@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAIELmk0018837 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NOT) for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 09:21:49 -0500 (EST) Message-ID: <000201c5ec4b$6bc71a40$6d04f712@ajshafer> From: "Andrew Shafer" To: <6042-probs@theory.csail.mit.edu> Subject: [Sayan] Week 11 Comments Date: Fri, 18 Nov 2005 09:21:51 -0500 MIME-Version: 1.0 Content-Type: text/plain; format=flowed; charset="iso-8859-1"; reply-type=original Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2900.2670 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2670 X-Spam-Score: -1.215 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 939 Content-Length: 373 X-Keywords: NonJunk Generating functions still seem really hard. What does G(x) represent when we plug in a value for x? Is it only useful here for trying to derive the f(n) function? -Andrew ---------------------------- Illegitmitatum Non Carborundum Est Andrew Shafer, MIT Blog http://shaferandrew.blogspot.com Si hoc legere scis numium eruditionis habes. ---------------------------- From jstritar@MIT.EDU Fri Nov 18 09:34:01 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAIEY15o001142 for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 09:34:01 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAIEXxYW015388 for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 09:34:00 -0500 (EST) Received: from [18.245.6.234] (BAKER-FOUR-EIGHTY-NINE.MIT.EDU [18.245.6.234]) (authenticated bits=0) (User authenticated as jstritar@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAIEXpTD024084 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 09:33:53 -0500 (EST) Message-ID: <437DE64B.3070202@mit.edu> Date: Fri, 18 Nov 2005 09:33:47 -0500 From: Jon Stritar User-Agent: Thunderbird 1.5 (Windows/20051025) MIME-Version: 1.0 To: 6042-probs@theory.csail.mit.edu Subject: [Sayan] Reading comments Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 940 Content-Length: 317 X-Keywords: NonJunk 3.1 Finding a Generating Function I thought this section was pretty interesting because I remember using a method involving matrices to obtain generating functions. I don't remember the exact procedure, but I am wondering if the two are related or simply different techniques for the same solution. Jon Stritar From meyer@imap.theory.csail.mit.edu Fri Nov 18 09:37:49 2005 Message-ID: <437DE73F.3060504@csail.mit.edu> Date: Fri, 18 Nov 2005 09:37:51 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Kevin Wang Subject: Re: [Hanson] Notes 11 Comments References: <6.2.3.4.2.20051118050105.029324e0@po10.mit.edu> In-Reply-To: <6.2.3.4.2.20051118050105.029324e0@po10.mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Length: 464 Status: RO X-UID: 941 X-Keywords: take another look at week 10 Monday, class problem 3, which we thought spelled out the Bookkeeper rule pretty thoroughly. Did you get a chance to do that problem in class? regards, A. Kevin Wang wrote: > Hi, > > I thought this reading was fairly straightforward and understood all > of it. With that being said though, if Prof. Meyers could go over > proving the bookkeeper rule (Section 4.3) in class, that would be > instructive. > > Thanks, > Kevin > From letrec@MIT.EDU Fri Nov 18 10:04:53 2005 Return-Path: Received: from south-station-annex.mit.edu (SOUTH-STATION-ANNEX.MIT.EDU [18.72.1.2]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAIF4r5o031371 for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 10:04:53 -0500 Received: from central-city-carrier-station.mit.edu (CENTRAL-CITY-CARRIER-STATION.MIT.EDU [18.7.7.72]) by south-station-annex.mit.edu (8.12.4/8.9.2) with ESMTP id jAIF4p5b015630 for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 10:04:52 -0500 (EST) Received: from outgoing-legacy.mit.edu (OUTGOING-LEGACY.MIT.EDU [18.7.22.104]) by central-city-carrier-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAIF4pAe001116 for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 10:04:51 -0500 (EST) Received: from [18.237.0.82] (TDCIP82.MIT.EDU [18.237.0.82]) ) by outgoing-legacy.mit.edu (8.12.4/8.12.4) with ESMTP id jAIF4nok018042 for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 10:04:49 -0500 (EST) Message-ID: <437DED8E.8020103@mit.edu> Date: Fri, 18 Nov 2005 10:04:46 -0500 From: Alton Torregano User-Agent: Debian Thunderbird 1.0.7 (X11/20051017) X-Accept-Language: en-us, en MIME-Version: 1.0 To: 6042-probs@theory.lcs.mit.edu Subject: [Hanson] Week 11 Comments Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 942 Content-Length: 524 X-Status: A X-Keywords: NonJunk This reading packet is one of the best written and most comprehensive. I have been introduced to the concept of generating functions before in Combinatorics, and the subject was never explained as succinctly and straightforward. In particular, the section on derivatives and Taylor's theorem are useful in gaining a slightly more in-depth and abstract understanding of the inner workings of the Generating Functions at this level of survey. Are we to cover exponential generating functions at all in this course? ~ Alton From kktyan@MIT.EDU Fri Nov 18 10:06:44 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAIF6i5o031508 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 18 Nov 2005 10:06:44 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAIF6gYW016035 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 18 Nov 2005 10:06:42 -0500 (EST) Received: from w92-130-webmail-5.mit.edu (W92-130-WEBMAIL-5.MIT.EDU [18.7.22.136]) ) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAIF6elX008391 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 18 Nov 2005 10:06:40 -0500 (EST) Received: (from nobody@localhost) by w92-130-webmail-5.mit.edu (8.12.4) id jAIF6eLr016249; Fri, 18 Nov 2005 10:06:40 -0500 Received: from BURTON-THREE-THIRTY-SIX.MIT.EDU (BURTON-THREE-THIRTY-SIX.MIT.EDU [18.247.6.81]) (User authenticated as kktyan@ATHENA.MIT.EDU) by webmail.mit.edu (Horde MIME library) with HTTP for ; Fri, 18 Nov 2005 10:06:40 -0500 Message-ID: <20051118100640.u6rpkk0lpe2scogs@webmail.mit.edu> Date: Fri, 18 Nov 2005 10:06:40 -0500 From: Karena Tyan To: 6042-probs@theory.lcs.MIT.EDU Subject: [Hanson] Reading Comments 11 MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) H3 (4.0.3) X-Spam-Score: -2.599 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 943 Content-Length: 519 X-Keywords: I mostly understood everything in this reading, so I'd just like to note that the method to discover the Fibonacci sequence's generating function was quite fun and exciting. Overall, I'd like to submit the suggestion (for the reading, as Professor Meyer explained it better in class) how exactly to find the complex roots (alpha_1 and alpha_2, per se) and giving a review on partial fractions for those of us who don't quite remember how to do them. - Karena -- 410 Memorial Drive Cambridge, MA 02139 (585)957-5923 From meyer@imap.theory.csail.mit.edu Fri Nov 18 10:19:12 2005 Message-ID: <437DF0F2.4060100@csail.mit.edu> Date: Fri, 18 Nov 2005 10:19:14 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Scot Frank Subject: Re: Comments Jelani References: <437D7B55.4000408@mit.edu> In-Reply-To: <437D7B55.4000408@mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Length: 800 Status: RO X-UID: 944 X-Keywords: $Forwarded Actually Prof. Meyer was a little confused too :-) and when he thinks about it, he thinks /rounding/ (either way) is wrong. The right thing to do is choose the /nearest/ integer: The Fib formula looks like Term1 - Term2 where the absolute value of Term2 < 1/2. But since Term1 - Term2 is an integer (a Fib. number), it follows that the integer nearest to Term1 must be the final answer. So we can ignore Term2 and just pick the closest integer to Term1. Make sense now? Regards, A. Scot Frank wrote: > Hi, > > The biggest question I had from this week of notes was the reason > that, while Prof. Meyer was on the board, he choose to round up on the > sum, after erasing the second term. I was confused, and could not > understand the conflicting explanations. > > Thanks, > > Scot From meyer@imap.theory.csail.mit.edu Fri Nov 18 10:29:11 2005 Message-ID: <437DF349.2050701@csail.mit.edu> Date: Fri, 18 Nov 2005 10:29:13 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Tony Ng Subject: Re: [Jelani] Reading Comments: Week 11 References: <5.2.1.1.2.20051117235257.02142d78@po9.mit.edu> In-Reply-To: <5.2.1.1.2.20051117235257.02142d78@po9.mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Length: 734 Status: RO X-UID: 945 X-Keywords: Even before the "amazing" fruit problem :-) , we used generating functions to find a formula, first for Fib nums, and then for another recursively specified sequence in the class prob. Didn't that illustrate the usefulness of gen funcs? .. or did you already know of some alternative way to find closed formulas for such sequences? regards, A. Tony Ng wrote: > I found the fruit counting problem ("An 'Impossible' Counting Problem, > pg12) to be very interesting. I didn't understand the need for > generating functions during the last lecture and it seemed excessively > complicated to do, however, now I understand why it is necessary > because it may be the only way we know how to solve some problems. > > - Tony > From meyer@imap.theory.csail.mit.edu Fri Nov 18 10:32:44 2005 Message-ID: <437DF41E.8050108@csail.mit.edu> Date: Fri, 18 Nov 2005 10:32:46 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Neil M Dowgun Subject: Re: [Hanson] reading question References: <20051117225828.bsxr9oqa0j0gw44g@webmail.mit.edu> In-Reply-To: <20051117225828.bsxr9oqa0j0gw44g@webmail.mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Length: 778 Status: RO X-UID: 946 X-Keywords: Neil M Dowgun wrote: >So I realized that the example where we found the coefficiants for the Fibonacci >sequence doesn't really provide a clean fomulaic way to find coefficiants given >a closed form. > Actually, it does. What makes you think not? >I guess there's just always going to be some dirty math to do. >Anyway, I was wondering if using the Taylor expansion to find the coefficiants >was always a viable option. I mean, I realize that it would be a real pain to >take the derivative of an expression say, thirty times, but it just seems like >a more surefire way to get the answer if it really is foolproof. > > both Taylor expansion and the partial fraction method are useful, though there are problems where neither one works. >Thanks, Neil > > regards, A. From meyer@imap.theory.csail.mit.edu Fri Nov 18 10:35:44 2005 Message-ID: <437DF4D3.2000009@csail.mit.edu> Date: Fri, 18 Nov 2005 10:35:47 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Alton Torregano Subject: Re: [Hanson] Week 11 Comments References: <437DED8E.8020103@mit.edu> In-Reply-To: <437DED8E.8020103@mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Length: 711 Status: RO X-UID: 947 X-Keywords: glad you liked the Notes. No, we won't cover exponential gen funcs: ordinary ones are enough for a broad intro course like 6.042. regards, A. Alton Torregano wrote: >This reading packet is one of the best written and most comprehensive. I >have been introduced to the concept of generating functions before in >Combinatorics, and the subject was never explained as succinctly and >straightforward. > >In particular, the section on derivatives and Taylor's theorem are >useful in gaining a slightly more in-depth and abstract understanding of >the inner workings of the Generating Functions at this level of survey. >Are we to cover exponential generating functions at all in this course? > >~ Alton > > From meyer@imap.theory.csail.mit.edu Fri Nov 18 00:03:39 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAI53d5o024488 for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 00:03:39 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAI53cYW002523 for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 00:03:38 -0500 (EST) Received: from HowardRoark.mit.edu (EASTCAMPUS-EIGHT-THIRTY-EIGHT.MIT.EDU [18.238.6.71]) (authenticated bits=0) (User authenticated as ctsims@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAI53aDr027191 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=NOT) for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 00:03:36 -0500 (EST) Message-Id: <5.2.1.1.2.20051117223854.02036418@po12.mit.edu> X-Sender: ctsims@po12.mit.edu X-Mailer: QUALCOMM Windows Eudora Version 5.2.1 Date: Fri, 18 Nov 2005 00:01:19 -0500 To: 6042-probs@theory.lcs.mit.edu From: Clayton Sims Subject: [6.042] Reading Comments Lecture Notes 8 - Clayton Sims Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO Content-Length: 420 X-UID: 948 X-Keywords: NonJunk I felt like the material on page 7 was the most challenging. Generalizing the method of turning a sequence of coefficients into different Function Generators that are easily converted into a representation of the function is something that I feel I would benefit from practicing. Additionally, a quick review (5 mins.) of partial fractions in class would be nice, although not entirely necessary. -Clayton Sims From nedzel@MIT.EDU Fri Nov 18 10:42:49 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAIFgn5o026043 for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 10:42:49 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAIFglYW021674 for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 10:42:47 -0500 (EST) Received: from ThinkPadT43 (SIMMONS-ONE-NINETY-NINE.MIT.EDU [18.96.5.199]) (authenticated bits=0) (User authenticated as nedzel@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAIFgdSL024551 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NOT) for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 10:42:40 -0500 (EST) Message-Id: <200511181542.jAIFgdSL024551@outgoing.mit.edu> From: "David A. Nedzel" To: <6042-probs@theory.csail.mit.edu> Subject: [Sayan] Week 11 Comments Date: Fri, 18 Nov 2005 10:42:33 -0500 MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Mailer: Microsoft Office Outlook, Build 11.0.6353 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2180 Thread-Index: AcW4zeo7ykLa/WaNRiGOpegAnm9CXA== X-Spam-Score: 2.037 X-Spam-Level: ** (2.037) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 949 Content-Length: 80 X-Keywords: NonJunk I didn't understand the notes on using generating functions to count. - David From vbrobbey@MIT.EDU Fri Nov 18 10:49:00 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAIFn05o030882 for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 10:49:00 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAIFmxYW028662 for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 10:48:59 -0500 (EST) Received: from napoleon (NAPOLEON-BONAPARTE.MIT.EDU [18.18.3.59]) (authenticated bits=0) (User authenticated as vbrobbey@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAIFmu52027362 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NOT) for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 10:48:57 -0500 (EST) Message-ID: <000c01c5ec57$95bd05b0$3b031212@napoleon> From: "Valery Kwasi Brobbey" To: <6042-probs@theory.lcs.mit.edu> Subject: [Hanson]Week 11 comments Date: Fri, 18 Nov 2005 10:48:54 -0500 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_NextPart_000_0009_01C5EC2D.ABC42890" X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2900.2670 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2670 X-Spam-Score: -0.718 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 950 Content-Length: 1856 X-Keywords: This is a multi-part message in MIME format. ------=_NextPart_000_0009_01C5EC2D.ABC42890 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Generating functions look very much like Taylor series expansion. I = actually used some of my knowledge of Taylor series to do some of the TP = problems. The lecture should probably have discussed the relationship = between the two. It's interesting how you can use generating functions = to count.=20 I like the lecture on Wednesday. I found that more interactive than = lectures with slides. However, I think the lecture was quite long. It = would have helped if we have the problem solving session right in the = middle. ------=_NextPart_000_0009_01C5EC2D.ABC42890 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable
Generating functions look very much = like Taylor=20 series expansion. I actually used some of my knowledge of Taylor series = to do=20 some of the TP problems. The lecture should probably have discussed the=20 relationship between the two. It's interesting how you can use = generating=20 functions to count.
I like the lecture on Wednesday. I = found that more=20 interactive than lectures with slides. However, I think the lecture was = quite=20 long. It would have helped if we have the problem solving session right = in the=20 middle.
 
------=_NextPart_000_0009_01C5EC2D.ABC42890-- From hmzhou@blackbird.csail.mit.edu Fri Nov 18 11:58:28 2005 Return-Path: Received: from blackbird.csail.mit.edu (blackbird.csail.mit.edu [128.30.51.72]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAIGwR5o030797; Fri, 18 Nov 2005 11:58:27 -0500 Received: from blackbird.csail.mit.edu (localhost.localdomain [127.0.0.1]) by blackbird.csail.mit.edu (8.13.4/8.13.4) with ESMTP id jAIGwRbf028621; Fri, 18 Nov 2005 11:58:27 -0500 Received: from localhost (hmzhou@localhost) by blackbird.csail.mit.edu (8.13.4/8.13.4/Submit) with ESMTP id jAIGwR7K028618; Fri, 18 Nov 2005 11:58:27 -0500 Date: Fri, 18 Nov 2005 11:58:27 -0500 (EST) From: Hanson Zhou To: Elizabeth Reid cc: 6042-probs@theory.lcs.mit.edu Subject: Re: [Hanson] Reading Comments In-Reply-To: <94C740B9-2FE5-4D4D-BC5D-6FD20BC9D421@MIT.EDU> Message-ID: References: <94C740B9-2FE5-4D4D-BC5D-6FD20BC9D421@MIT.EDU> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-UID: 951 Content-Length: 352 X-Keywords: Most good texts on discrete mathematics should have sections on generating functions and exercises. Look around or ask Prof. Meyer for pointers. -Hanson On Thu, 17 Nov 2005, Elizabeth Reid wrote: > The reading makes sense, but I feel like I wouldn't be able to do it > myself. Is there anywhere I can go that would help me practice this > stuff? > From hmzhou@blackbird.csail.mit.edu Fri Nov 18 12:01:20 2005 Return-Path: Received: from blackbird.csail.mit.edu (blackbird.csail.mit.edu [128.30.51.72]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAIH1K5o031635; Fri, 18 Nov 2005 12:01:20 -0500 Received: from blackbird.csail.mit.edu (localhost.localdomain [127.0.0.1]) by blackbird.csail.mit.edu (8.13.4/8.13.4) with ESMTP id jAIH1KPq028665; Fri, 18 Nov 2005 12:01:20 -0500 Received: from localhost (hmzhou@localhost) by blackbird.csail.mit.edu (8.13.4/8.13.4/Submit) with ESMTP id jAIH1Ko0028662; Fri, 18 Nov 2005 12:01:20 -0500 Date: Fri, 18 Nov 2005 12:01:20 -0500 (EST) From: Hanson Zhou To: Daniel A Gutierrez cc: 6042-probs@theory.csail.MIT.EDU Subject: Re: [Hansen] TP11 Reading Response In-Reply-To: <20051117191349.qo4qd0bqx2os404s@webmail.mit.edu> Message-ID: References: <20051117191349.qo4qd0bqx2os404s@webmail.mit.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-UID: 952 Content-Length: 398 X-Keywords: Well there is a formula for the geometric sum: 1+x+x^+...+x^n = (x^(n+1)-1)/(x-1). You can review from the course lecture notes or from just about any discrete math text. -Hanson On Thu, 17 Nov 2005, Daniel A Gutierrez wrote: > These all make logical sense, but I was wondering if by chance you have > a list or know where to find one so that I can review geometric summing? > Thanks, Daniel > From hmzhou@blackbird.csail.mit.edu Fri Nov 18 12:07:53 2005 Return-Path: Received: from blackbird.csail.mit.edu (blackbird.csail.mit.edu [128.30.51.72]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAIH7r5o032336; Fri, 18 Nov 2005 12:07:53 -0500 Received: from blackbird.csail.mit.edu (localhost.localdomain [127.0.0.1]) by blackbird.csail.mit.edu (8.13.4/8.13.4) with ESMTP id jAIH7qbQ028727; Fri, 18 Nov 2005 12:07:52 -0500 Received: from localhost (hmzhou@localhost) by blackbird.csail.mit.edu (8.13.4/8.13.4/Submit) with ESMTP id jAIH7qUt028724; Fri, 18 Nov 2005 12:07:52 -0500 Date: Fri, 18 Nov 2005 12:07:52 -0500 (EST) From: Hanson Zhou To: Barry Revzin cc: 6042-probs@theory.csail.mit.edu Subject: Re: [Hanson] Reading In-Reply-To: <6.1.2.0.1.20051117232905.019f2b98@po14.mit.edu> Message-ID: References: <6.1.2.0.1.20051117232905.019f2b98@po14.mit.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-UID: 953 Content-Length: 721 X-Keywords: Well...and I'm purely speculating here: Integral f(y)g(n-y)dy, with f(y) = a_y x^y, and g(n-y) = b_(n-y) x^(n-y), would seem to be the continuous analogue of the discrete convolution we talk about here. Ask Prof. Meyer to make sure. -Hanson On Thu, 17 Nov 2005, Barry Revzin wrote: > For the convolution rule, I think it's really confusing that it's called > the convolution rule. It really has nothing to do with the idea of a > convolution from analysis, does it ? I'm really used to the convolution of > f and g (f*g) being the integral of f(y)g(x-y)dy. Why IS it called that > then ? Why not like... disjoint union rule ? Or Countable Additivity, which > would be consistent with measure theory... > > Barry > > From lana@MIT.EDU Fri Nov 18 12:23:57 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAIHNv5o009032 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 18 Nov 2005 12:23:57 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAIHNt0C011117 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 18 Nov 2005 12:23:56 -0500 (EST) Received: from w92-130-webmail-1.mit.edu (W92-130-WEBMAIL-1.MIT.EDU [18.7.22.131]) ) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAIHNsaC008964 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 18 Nov 2005 12:23:54 -0500 (EST) Received: (from nobody@localhost) by w92-130-webmail-1.mit.edu (8.12.4) id jAIHNs3o002445; Fri, 18 Nov 2005 12:23:54 -0500 Received: from NEXT-FOUR-TWENTY-THREE.MIT.EDU (NEXT-FOUR-TWENTY-THREE.MIT.EDU [18.242.6.168]) (User authenticated as lana@ATHENA.MIT.EDU) by webmail.mit.edu (Horde MIME library) with HTTP for ; Fri, 18 Nov 2005 12:23:54 -0500 Message-ID: <20051118122354.ujookdbnpiskw0s4@webmail.mit.edu> Date: Fri, 18 Nov 2005 12:23:54 -0500 From: Svetlana Goldenberg To: 6042-probs@theory.lcs.MIT.EDU Subject: [Sayan] TP11 MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) H3 (4.0.3) X-Spam-Score: -2.599 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 954 Content-Length: 177 X-Keywords: NonJunk I was wondering if it is possible to have a function that can not be expressed through a generating function or if 2 generating functions can result in the same expression Lana From ksindi@MIT.EDU Fri Nov 18 13:47:01 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAIIl05o028638 for <6042-probs@theory.csail.MIT.EDU>; Fri, 18 Nov 2005 13:47:01 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAIIkx0C024536 for <6042-probs@theory.csail.MIT.EDU>; Fri, 18 Nov 2005 13:46:59 -0500 (EST) Received: from w92-130-webmail-2.mit.edu (W92-130-WEBMAIL-2.MIT.EDU [18.7.22.132]) ) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAIIkr0X008754 for <6042-probs@theory.csail.MIT.EDU>; Fri, 18 Nov 2005 13:46:53 -0500 (EST) Received: (from nobody@localhost) by w92-130-webmail-2.mit.edu (8.12.4) id jAIIkrIv030446; Fri, 18 Nov 2005 13:46:53 -0500 Received: from c-24-218-110-155.hsd1.ma.comcast.net (c-24-218-110-155.hsd1.ma.comcast.net [24.218.110.155]) (User authenticated as ksindi@ATHENA.MIT.EDU) by webmail.mit.edu (Horde MIME library) with HTTP for ; Fri, 18 Nov 2005 13:46:53 -0500 Message-ID: <20051118134653.j9kik70v0asks8cc@webmail.mit.edu> Date: Fri, 18 Nov 2005 13:46:53 -0500 From: Kamil Y Sindi To: 6042-probs@theory.csail.MIT.EDU Subject: [David] Week 11 Comments MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) H3 (4.0.3) X-Spam-Score: -2.599 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 955 Content-Length: 153 X-Keywords: I found it conceptiually confusing of how one treats generating functions only formally without worry of convergence. However Im getting the hang of it. From dshin@MIT.EDU Fri Nov 18 17:16:28 2005 Return-Path: Received: from south-station-annex.mit.edu (SOUTH-STATION-ANNEX.MIT.EDU [18.72.1.2]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAIMGS5o010910 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 18 Nov 2005 17:16:28 -0500 Received: from central-city-carrier-station.mit.edu (CENTRAL-CITY-CARRIER-STATION.MIT.EDU [18.7.7.72]) by south-station-annex.mit.edu (8.12.4/8.9.2) with ESMTP id jAIMGRVi009673 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 18 Nov 2005 17:16:27 -0500 (EST) Received: from outgoing-legacy.mit.edu (OUTGOING-LEGACY.MIT.EDU [18.7.22.104]) by central-city-carrier-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAIMGQBa022368; Fri, 18 Nov 2005 17:16:26 -0500 (EST) Received: from [192.168.1.4] (c-65-96-190-64.hsd1.ma.comcast.net [65.96.190.64]) ) by outgoing-legacy.mit.edu (8.12.4/8.12.4) with ESMTP id jAIMGOok021449; Fri, 18 Nov 2005 17:16:24 -0500 (EST) Message-ID: <437E5286.3050200@mit.edu> Date: Fri, 18 Nov 2005 17:15:34 -0500 From: David Shin User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Katherine A Romer CC: 6042-probs@theory.lcs.MIT.EDU Subject: Re: [David] Email comments for reading References: <20051118091658.flzzeo34lb4ks0oo@webmail.mit.edu> In-Reply-To: <20051118091658.flzzeo34lb4ks0oo@webmail.mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 956 Content-Length: 860 X-Keywords: Interesting question! I spent a bit of time thinking about whether generating functions could be used in this type of situation, and I'm leaning towards an answer of "no". The reason is that multiplication is commutative: x^a*x^b = x^{ab}. It doesn't seem possible to encode order-dependent information with this order-independent operation (multiplication). Maybe there exists some crazy method using non-commutative algebraic structures, but I am highly doubtful. DS Katherine A Romer wrote: >p. 10 "Informally, the only restrictions are that (1) the order in which items >are selected is disregarded and (2) restrictions on the selection of items from >sets A and B also apply in selecting items from A union B". > >Is there any way to use generating functions to count when the order in which >items are selected matters? > >Katherine > > From dshin@MIT.EDU Fri Nov 18 17:40:52 2005 Return-Path: Received: from grand-central-station.mit.edu (GRAND-CENTRAL-STATION.MIT.EDU [18.7.21.82]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAIMeq5o015999 for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 17:40:52 -0500 Received: from outgoing-legacy.mit.edu (OUTGOING-LEGACY.MIT.EDU [18.7.22.104]) by grand-central-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAIMeoOp023578; Fri, 18 Nov 2005 17:40:50 -0500 (EST) Received: from [192.168.1.4] (c-65-96-190-64.hsd1.ma.comcast.net [65.96.190.64]) ) by outgoing-legacy.mit.edu (8.12.4/8.12.4) with ESMTP id jAIMelMu004586; Fri, 18 Nov 2005 17:40:47 -0500 (EST) Message-ID: <437E583D.9010003@mit.edu> Date: Fri, 18 Nov 2005 17:39:57 -0500 From: David Shin User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Alexander Bakst CC: 6042-probs@theory.lcs.mit.edu, 6042 staff <6042-staff@theory.csail.mit.edu> Subject: Re: [David] Lecture Notes 11 Comments References: <437D988C.8020808@mit.edu> In-Reply-To: <437D988C.8020808@mit.edu> Content-Type: multipart/alternative; boundary="------------020405060808050509060906" X-Spam-Score: 1.218 X-Spam-Level: * (1.218) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 957 Content-Length: 4414 X-Keywords: This is a multi-part message in MIME format. --------------020405060808050509060906 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Alexander Bakst wrote: > What kind of situations would require us to use values for x? In the > readings it said that they are unusual or rare, I believe. There are a few really ingenious applications of generating functions that involve using values for x. Typically, the plugging-in-for-x step is to reach some sort of contradiction: you have two generating functions that are supposed to be equal, but they don't agree at a particular value of x. Unfortunately, most examples are fairly complex (pun somewhat intended). I tried to think of a simple example, but this is the best I could come up with: ----- *Problem*: Suppose we have a collection of infinite arithmetic sequences (like {1,4,7,10,...} or {10,12,14,16,...}) where each sequence has difference term larger than 1. Suppose that every natural number occurs EXACTLY once among the sequences. Prove that two of the sequences have the same difference term. *Solution*: Suppose not. Let the sequences be S_i = {a_i + n*b_i} for i=1,2,... Then, since all the difference terms are distinct, the values of b_i are all distinct. Assume without loss of generality that b_1 is the smallest of the b_i. Sequence S_i can be represented by a sequence of 0's and 1's, which can be represented by the generating function x^{a_i}/(1-x^{b_i}). The natural numbers can be represented by a sequence of all 1's, which can be represented by the generating function 1/(1-x). Since each natural number occurs exactly once among the sequences, we have that 1/(1-x) = SUM_i (x^{a_i}/(1-x^{b_i})) Let x be close to a (b_1)-th root of unity. I won't give a rigorous proof, but it's true that the right hand side blows up while the left hand side doesn't. A contradiction. ----- Hopefully you find that somewhat cool. DS --------------020405060808050509060906 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Alexander Bakst wrote:
What kind of situations would require us to use values for x? In the readings it said that they are unusual or rare, I believe.
There are a few really ingenious applications of generating functions that involve using values for x.  Typically, the plugging-in-for-x step is to reach some sort of contradiction:  you have two generating functions that are supposed to be equal, but they don't agree at a particular value of x. 

Unfortunately, most examples are fairly complex (pun somewhat intended).  I tried to think of a simple example, but this is the best I could come up with:

-----

Problem:  Suppose we have a collection of infinite arithmetic sequences (like {1,4,7,10,...} or {10,12,14,16,...}) where each sequence has difference term larger than 1.  Suppose that every natural number occurs EXACTLY once among the sequences.  Prove that two of the sequences have the same difference term. 

Solution:  Suppose not.  Let the sequences be S_i = {a_i + n*b_i} for i=1,2,...  Then, since all the difference terms are distinct, the values of b_i are all distinct.  Assume without loss of generality that b_1 is the smallest of the b_i. 

Sequence S_i can be represented by a sequence of 0's and 1's, which can be represented by the generating function x^{a_i}/(1-x^{b_i}).  The natural numbers can be represented by a sequence of all 1's, which can be represented by the generating function 1/(1-x).  Since each natural number occurs exactly once among the sequences, we have that

1/(1-x) = SUM_i (x^{a_i}/(1-x^{b_i}))

Let x be close to a (b_1)-th root of unity.  I won't give a rigorous proof, but it's true that the right hand side blows up while the left hand side doesn't.  A contradiction. 

-----

Hopefully you find that somewhat cool. 

DS --------------020405060808050509060906-- From dshin@MIT.EDU Fri Nov 18 17:43:52 2005 Return-Path: Received: from south-station-annex.mit.edu (SOUTH-STATION-ANNEX.MIT.EDU [18.72.1.2]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAIMhq5o020866 for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 17:43:52 -0500 Received: from central-city-carrier-station.mit.edu (CENTRAL-CITY-CARRIER-STATION.MIT.EDU [18.7.7.72]) by south-station-annex.mit.edu (8.12.4/8.9.2) with ESMTP id jAIMhpVi022551 for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 17:43:51 -0500 (EST) Received: from outgoing-legacy.mit.edu (OUTGOING-LEGACY.MIT.EDU [18.7.22.104]) by central-city-carrier-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAIMhoBa023540; Fri, 18 Nov 2005 17:43:51 -0500 (EST) Received: from [192.168.1.4] (c-65-96-190-64.hsd1.ma.comcast.net [65.96.190.64]) ) by outgoing-legacy.mit.edu (8.12.4/8.12.4) with ESMTP id jAIMhmok022831; Fri, 18 Nov 2005 17:43:48 -0500 (EST) Message-ID: <437E58F2.5060402@mit.edu> Date: Fri, 18 Nov 2005 17:42:58 -0500 From: David Shin User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Harrison King Hall CC: 6042-probs@theory.csail.mit.edu Subject: Re: [David] Week 11 Comments References: <488a6fb141c55248b795e2c28e8cceb1@mit.edu> In-Reply-To: <488a6fb141c55248b795e2c28e8cceb1@mit.edu> Content-Type: text/plain; charset=ISO-2022-JP Content-Transfer-Encoding: 7bit X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 958 Content-Length: 668 X-Keywords: Glad you're liking this stuff. Do you see why the oranges thing works now? DS Harrison King Hall wrote: > This is really a cool way to do counting problems, and really > intuitive since you only have to worry about how to select each class > of element for n elements independent of all the others. My only issue > is that I don't always see the generating function . Like in the > "Impossible" counting problem, I didn't see that the number of oranges > was O(x) = 1 + x + x ^2 + x^3 + x^4 = (1 $B!](B x^5)/(1 $B!](B x) and I don't > really know how you got there. That is probably something that comes > with time however. This is really slick. > -Harrison > From dshin@MIT.EDU Fri Nov 18 17:47:59 2005 Return-Path: Received: from south-station-annex.mit.edu (SOUTH-STATION-ANNEX.MIT.EDU [18.72.1.2]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAIMlx5o024327 for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 17:47:59 -0500 Received: from central-city-carrier-station.mit.edu (CENTRAL-CITY-CARRIER-STATION.MIT.EDU [18.7.7.72]) by south-station-annex.mit.edu (8.12.4/8.9.2) with ESMTP id jAIMlwVi029077 for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 17:47:58 -0500 (EST) Received: from outgoing-legacy.mit.edu (OUTGOING-LEGACY.MIT.EDU [18.7.22.104]) by central-city-carrier-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAIMlwBa023675; Fri, 18 Nov 2005 17:47:58 -0500 (EST) Received: from [192.168.1.4] (c-65-96-190-64.hsd1.ma.comcast.net [65.96.190.64]) ) by outgoing-legacy.mit.edu (8.12.4/8.12.4) with ESMTP id jAIMlook023000; Fri, 18 Nov 2005 17:47:50 -0500 (EST) Message-ID: <437E59E4.6050200@mit.edu> Date: Fri, 18 Nov 2005 17:47:00 -0500 From: David Shin User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Jason Juang CC: 6042-probs@theory.csail.mit.edu Subject: Re: [David] Week 11 Comments References: <437BA8B1.2090306@mit.edu> In-Reply-To: <437BA8B1.2090306@mit.edu> Content-Type: multipart/alternative; boundary="------------080504060501080501020402" X-Spam-Score: 2.569 X-Spam-Level: ** (2.569) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 959 Content-Length: 5064 X-Keywords: This is a multi-part message in MIME format. --------------080504060501080501020402 Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 7bit Jason Juang wrote: > In what cases might we actually evaluate a generating function? There are a few really ingenious applications of generating functions that involve using values for x. Typically, the plugging-in-for-x step is to reach some sort of contradiction: you have two generating functions that are supposed to be equal, but they don't agree at a particular value of x. Unfortunately, most examples are fairly complex (pun somewhat intended). I tried to think of a simple example, but this is the best I could come up with: ----- *Problem*: Suppose we have a collection of infinite arithmetic sequences (like {1,4,7,10,...} or {10,12,14,16,...}) where each sequence has difference term larger than 1. Suppose that every natural number occurs EXACTLY once among the sequences. Prove that two of the sequences have the same difference term. *Solution*: Suppose not. Let the sequences be S_i = {a_i + n*b_i} for i=1,2,... Then, since all the difference terms are distinct, the values of b_i are all distinct. Assume without loss of generality that b_1 is the smallest of the b_i. Sequence S_i can be represented by a sequence of 0's and 1's, which can be represented by the generating function x^{a_i}/(1-x^{b_i}). The natural numbers can be represented by a sequence of all 1's, which can be represented by the generating function 1/(1-x). Since each natural number occurs exactly once among the sequences, we have that 1/(1-x) = SUM_i (x^{a_i}/(1-x^{b_i})) Let x be close to a (b_1)-th complex root of unity. I won't give a rigorous proof, but it's true that the right hand side blows up while the left hand side doesn't. (It relies on the fact that b_1 is distinct from all the other b_i...) A contradiction. ----- Hopefully you find that somewhat cool. If you want a really cool challenge, try your hand at this: Problem: Suppose you have a tiling of an 8x8 chessboard with 21 trinominos (3x1 rectangles) and one monomino (1x1 rectangle). Find all possible positions for the monomino. Believe it or not, it can be done with (finite) generating functions! It involves cubic roots of unity... DS --------------080504060501080501020402 Content-Type: text/html; charset=windows-1252 Content-Transfer-Encoding: 8bit Jason Juang wrote:
In what cases might we actually evaluate a generating function?
There are a few really ingenious applications of generating functions that involve using values for x.  Typically, the plugging-in-for-x step is to reach some sort of contradiction:  you have two generating functions that are supposed to be equal, but they don't agree at a particular value of x. 

Unfortunately, most examples are fairly complex (pun somewhat intended).  I tried to think of a simple example, but this is the best I could come up with:

-----

Problem:  Suppose we have a collection of infinite arithmetic sequences (like {1,4,7,10,...} or {10,12,14,16,...}) where each sequence has difference term larger than 1.  Suppose that every natural number occurs EXACTLY once among the sequences.  Prove that two of the sequences have the same difference term. 

Solution:  Suppose not.  Let the sequences be S_i = {a_i + n*b_i} for i=1,2,...  Then, since all the difference terms are distinct, the values of b_i are all distinct.  Assume without loss of generality that b_1 is the smallest of the b_i. 

Sequence S_i can be represented by a sequence of 0's and 1's, which can be represented by the generating function x^{a_i}/(1-x^{b_i}).  The natural numbers can be represented by a sequence of all 1's, which can be represented by the generating function 1/(1-x).  Since each natural number occurs exactly once among the sequences, we have that

1/(1-x) = SUM_i (x^{a_i}/(1-x^{b_i}))

Let x be close to a (b_1)-th complex root of unity.  I won't give a rigorous proof, but it's true that the right hand side blows up while the left hand side doesn't.  (It relies on the fact that b_1 is distinct from all the other b_i...)  A contradiction. 

-----

Hopefully you find that somewhat cool. 

If you want a really cool challenge, try your hand at this:

Problem:  Suppose you have a tiling of an 8x8 chessboard with 21 trinominos (3x1 rectangles) and one monomino (1x1 rectangle).  Find all possible positions for the monomino.

Believe it or not, it can be done with (finite) generating functions!  It involves cubic roots of unity...

DS --------------080504060501080501020402-- From dshin@MIT.EDU Fri Nov 18 17:48:17 2005 Return-Path: Received: from south-station-annex.mit.edu (SOUTH-STATION-ANNEX.MIT.EDU [18.72.1.2]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAIMmH5o024338 for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 17:48:17 -0500 Received: from central-city-carrier-station.mit.edu (CENTRAL-CITY-CARRIER-STATION.MIT.EDU [18.7.7.72]) by south-station-annex.mit.edu (8.12.4/8.9.2) with ESMTP id jAIMmGVi029580 for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 17:48:16 -0500 (EST) Received: from outgoing-legacy.mit.edu (OUTGOING-LEGACY.MIT.EDU [18.7.22.104]) by central-city-carrier-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAIMmFBa023684; Fri, 18 Nov 2005 17:48:15 -0500 (EST) Received: from [192.168.1.4] (c-65-96-190-64.hsd1.ma.comcast.net [65.96.190.64]) ) by outgoing-legacy.mit.edu (8.12.4/8.12.4) with ESMTP id jAIMm8ok023012; Fri, 18 Nov 2005 17:48:08 -0500 (EST) Message-ID: <437E59F6.8050503@mit.edu> Date: Fri, 18 Nov 2005 17:47:18 -0500 From: David Shin User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Chris Yang CC: 6042-probs@theory.csail.mit.edu Subject: Re: [David] Week 11 Comments References: <200511162330.jAGNUADm015510@outgoing.mit.edu> In-Reply-To: <200511162330.jAGNUADm015510@outgoing.mit.edu> Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 8bit X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 960 Content-Length: 253 X-Keywords: Did class help with convolution? DS Chris Yang wrote: > I don’t really understand how the Convolution rule works. Will we be > covering it in class on Friday? Also, the apples/oranges thing at the > end is pretty cool. > > Thanks, > > Chris Yang > From dshin@MIT.EDU Fri Nov 18 17:49:55 2005 Return-Path: Received: from grand-central-station.mit.edu (GRAND-CENTRAL-STATION.MIT.EDU [18.7.21.82]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAIMnt5o024445 for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 17:49:55 -0500 Received: from outgoing-legacy.mit.edu (OUTGOING-LEGACY.MIT.EDU [18.7.22.104]) by grand-central-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAIMnrOp023843; Fri, 18 Nov 2005 17:49:53 -0500 (EST) Received: from [192.168.1.4] (c-65-96-190-64.hsd1.ma.comcast.net [65.96.190.64]) ) by outgoing-legacy.mit.edu (8.12.4/8.12.4) with ESMTP id jAIMnook023098; Fri, 18 Nov 2005 17:49:50 -0500 (EST) Message-ID: <437E5A5C.7010005@mit.edu> Date: Fri, 18 Nov 2005 17:49:00 -0500 From: David Shin User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Sergio Bacallado CC: 6042-probs@theory.csail.mit.edu Subject: Re: [David] Week 11 Comments References: <5.2.1.1.2.20051117222122.00c5c020@po14.mit.edu> In-Reply-To: <5.2.1.1.2.20051117222122.00c5c020@po14.mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 961 Content-Length: 539 X-Keywords: Taylor expansion is sure to work. If your function is a quotient of polynomials, then partial fractions often can do the trick. DS Sergio Bacallado wrote: > I thought it was amazing how useful generating functions can be to > solve counting problems. I would like to know if there is always an > easy way to find a closed form for the nth term of a sequence, if you > know the value of the generating function. That is, other than > differentiating the function to get the Taylor expansion term. > > Sergio Bacallado > Group A > From dshin@MIT.EDU Fri Nov 18 17:53:34 2005 Return-Path: Received: from grand-central-station.mit.edu (GRAND-CENTRAL-STATION.MIT.EDU [18.7.21.82]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAIMrY5o024623 for <6042-probs@theory.lcs.mit.edu>; Fri, 18 Nov 2005 17:53:34 -0500 Received: from outgoing-legacy.mit.edu (OUTGOING-LEGACY.MIT.EDU [18.7.22.104]) by grand-central-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAIMrWOp024036; Fri, 18 Nov 2005 17:53:32 -0500 (EST) Received: from [192.168.1.4] (c-65-96-190-64.hsd1.ma.comcast.net [65.96.190.64]) ) by outgoing-legacy.mit.edu (8.12.4/8.12.4) with ESMTP id jAIMrTMu005130; Fri, 18 Nov 2005 17:53:29 -0500 (EST) Message-ID: <437E5B37.6070903@mit.edu> Date: Fri, 18 Nov 2005 17:52:39 -0500 From: David Shin User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: cbossard@MIT.EDU CC: 6042-probs@theory.lcs.mit.edu Subject: Re: [David] Week 11 reading comments References: <20051118030340.i5w8dncex73kocgg@webmail.mit.edu> In-Reply-To: <20051118030340.i5w8dncex73kocgg@webmail.mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 962 Content-Length: 969 X-Keywords: It would have been great if you had come to lecture today - we covered much of these topics in class. I would recommend coming to office hours if you are still having difficulty. DS cbossard@MIT.EDU wrote: >I find this to be an interesting topic although I have trouble >reproducing and creating these functions on my own they generally >make sense to me when I see them explained. In section 2.5 on >products I am not seeing/understanding how the terms of the diagonal >were collected so I don't see why it's not aobo + a1b1 instead of >aobn etc. Again with although the convolution rule makes some sense >to me in section 4.2 I dont see how they are getting the numbers from >the formula that was created. I can see that each is (1+x) and they >should be multiplied. Intuively I understand that there's 1 way to >choose 0 elements, 2 ways to choose 1, etc but I do not see how this >information can be attained from the 1+2x+x^2 equation. > >Cynthia > > From dshin@MIT.EDU Fri Nov 18 17:54:01 2005 Return-Path: Received: from south-station-annex.mit.edu (SOUTH-STATION-ANNEX.MIT.EDU [18.72.1.2]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAIMs15o024680 for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 17:54:01 -0500 Received: from central-city-carrier-station.mit.edu (CENTRAL-CITY-CARRIER-STATION.MIT.EDU [18.7.7.72]) by south-station-annex.mit.edu (8.12.4/8.9.2) with ESMTP id jAIMrxVi008807 for <6042-probs@theory.csail.mit.edu>; Fri, 18 Nov 2005 17:54:00 -0500 (EST) Received: from outgoing-legacy.mit.edu (OUTGOING-LEGACY.MIT.EDU [18.7.22.104]) by central-city-carrier-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAIMrxBa023952; Fri, 18 Nov 2005 17:53:59 -0500 (EST) Received: from [192.168.1.4] (c-65-96-190-64.hsd1.ma.comcast.net [65.96.190.64]) ) by outgoing-legacy.mit.edu (8.12.4/8.12.4) with ESMTP id jAIMrqok023380; Fri, 18 Nov 2005 17:53:52 -0500 (EST) Message-ID: <437E5B4E.6040406@mit.edu> Date: Fri, 18 Nov 2005 17:53:02 -0500 From: David Shin User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: "Joshua Jen C. Monzon" CC: 6042-probs@theory.csail.mit.edu Subject: Re: David - Reading Comments References: <6.2.3.4.2.20051118003612.01e0a888@po9.mit.edu> In-Reply-To: <6.2.3.4.2.20051118003612.01e0a888@po9.mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 963 Content-Length: 464 X-Keywords: did class help? DS Joshua Jen C. Monzon wrote: > I'm a little confused on the convolution rule. Perhaps this would be > explained a little more in class. Also, I didn't really understand how > they obtained the answer in the last problem of the tutorial. Hope > tomorrow's lecture clears this up. > > Josh > > > > Joshua Jen C. Monzon > Massachusetts Institute of Technology > Electrical Engineering with Computer Science > jjmonzon@mit.edu 617-803-7497 > From meyer@imap.theory.csail.mit.edu Fri Nov 18 17:40:53 2005 Return-Path: Received: from grand-central-station.mit.edu (GRAND-CENTRAL-STATION.MIT.EDU [18.7.21.82]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAIMeq5o015997 for <6042-staff@theory.csail.mit.edu>; Fri, 18 Nov 2005 17:40:52 -0500 Received: from outgoing-legacy.mit.edu (OUTGOING-LEGACY.MIT.EDU [18.7.22.104]) by grand-central-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAIMeoOp023578; Fri, 18 Nov 2005 17:40:50 -0500 (EST) Received: from [192.168.1.4] (c-65-96-190-64.hsd1.ma.comcast.net [65.96.190.64]) ) by outgoing-legacy.mit.edu (8.12.4/8.12.4) with ESMTP id jAIMelMu004586; Fri, 18 Nov 2005 17:40:47 -0500 (EST) Message-ID: <437E583D.9010003@mit.edu> Date: Fri, 18 Nov 2005 17:39:57 -0500 From: David Shin User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Alexander Bakst CC: 6042-probs@theory.lcs.mit.edu, 6042 staff <6042-staff@theory.csail.mit.edu> Subject: Re: [David] Lecture Notes 11 Comments References: <437D988C.8020808@mit.edu> In-Reply-To: <437D988C.8020808@mit.edu> Content-Type: multipart/alternative; boundary="------------020405060808050509060906" X-Spam-Score: 1.218 X-Scanned-By: MIMEDefang 2.42 X-Spam-Checker-Version: SpamAssassin 2.63 (2004-01-11) on theory.csail.mit.edu X-Spam-Level: X-Spam-Status: No, hits=-4.8 required=3.7 tests=AWL,BAYES_00,HTML_MESSAGE autolearn=ham version=2.63 Status: RO Content-Length: 4414 X-UID: 964 X-Keywords: This is a multi-part message in MIME format. --------------020405060808050509060906 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Alexander Bakst wrote: > What kind of situations would require us to use values for x? In the > readings it said that they are unusual or rare, I believe. There are a few really ingenious applications of generating functions that involve using values for x. Typically, the plugging-in-for-x step is to reach some sort of contradiction: you have two generating functions that are supposed to be equal, but they don't agree at a particular value of x. Unfortunately, most examples are fairly complex (pun somewhat intended). I tried to think of a simple example, but this is the best I could come up with: ----- *Problem*: Suppose we have a collection of infinite arithmetic sequences (like {1,4,7,10,...} or {10,12,14,16,...}) where each sequence has difference term larger than 1. Suppose that every natural number occurs EXACTLY once among the sequences. Prove that two of the sequences have the same difference term. *Solution*: Suppose not. Let the sequences be S_i = {a_i + n*b_i} for i=1,2,... Then, since all the difference terms are distinct, the values of b_i are all distinct. Assume without loss of generality that b_1 is the smallest of the b_i. Sequence S_i can be represented by a sequence of 0's and 1's, which can be represented by the generating function x^{a_i}/(1-x^{b_i}). The natural numbers can be represented by a sequence of all 1's, which can be represented by the generating function 1/(1-x). Since each natural number occurs exactly once among the sequences, we have that 1/(1-x) = SUM_i (x^{a_i}/(1-x^{b_i})) Let x be close to a (b_1)-th root of unity. I won't give a rigorous proof, but it's true that the right hand side blows up while the left hand side doesn't. A contradiction. ----- Hopefully you find that somewhat cool. DS --------------020405060808050509060906 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Alexander Bakst wrote:
What kind of situations would require us to use values for x? In the readings it said that they are unusual or rare, I believe.
There are a few really ingenious applications of generating functions that involve using values for x.  Typically, the plugging-in-for-x step is to reach some sort of contradiction:  you have two generating functions that are supposed to be equal, but they don't agree at a particular value of x. 

Unfortunately, most examples are fairly complex (pun somewhat intended).  I tried to think of a simple example, but this is the best I could come up with:

-----

Problem:  Suppose we have a collection of infinite arithmetic sequences (like {1,4,7,10,...} or {10,12,14,16,...}) where each sequence has difference term larger than 1.  Suppose that every natural number occurs EXACTLY once among the sequences.  Prove that two of the sequences have the same difference term. 

Solution:  Suppose not.  Let the sequences be S_i = {a_i + n*b_i} for i=1,2,...  Then, since all the difference terms are distinct, the values of b_i are all distinct.  Assume without loss of generality that b_1 is the smallest of the b_i. 

Sequence S_i can be represented by a sequence of 0's and 1's, which can be represented by the generating function x^{a_i}/(1-x^{b_i}).  The natural numbers can be represented by a sequence of all 1's, which can be represented by the generating function 1/(1-x).  Since each natural number occurs exactly once among the sequences, we have that

1/(1-x) = SUM_i (x^{a_i}/(1-x^{b_i}))

Let x be close to a (b_1)-th root of unity.  I won't give a rigorous proof, but it's true that the right hand side blows up while the left hand side doesn't.  A contradiction. 

-----

Hopefully you find that somewhat cool. 

DS --------------020405060808050509060906-- From minilek@gmail.com Sat Nov 19 17:20:33 2005 Return-Path: Received: from zproxy.gmail.com (zproxy.gmail.com [64.233.162.206]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAJMKX5o003467 for <6042-probs@theory.lcs.mit.edu>; Sat, 19 Nov 2005 17:20:33 -0500 Received: by zproxy.gmail.com with SMTP id l8so476019nzf for <6042-probs@theory.lcs.mit.edu>; Sat, 19 Nov 2005 14:20:33 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:sender:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=qPN9JR04KWTogW9W8UMysXNVovZD+C9cg68Z0DLTg4QZJr6iaK1XZAD0NfapH0b6iC50ic5wO1QcaY2gT/ntIc6ORumXg17ZJmSsTai/d116IYLmsfqKnD85uF8s1Fr+AyAb3rvf0tYM4S1ndOl3g5KuBuSTsdUajH+pqwqjBYQ= Received: by 10.64.199.9 with SMTP id w9mr1173433qbf; Sat, 19 Nov 2005 14:20:33 -0800 (PST) Received: by 10.64.150.8 with HTTP; Sat, 19 Nov 2005 14:20:33 -0800 (PST) Message-ID: Date: Sat, 19 Nov 2005 17:20:33 -0500 From: Jelani Nelson Sender: minilek@gmail.com To: David Shin Subject: Re: [David] Lecture Notes 11 Comments Cc: Alexander Bakst , 6042-probs@theory.lcs.mit.edu, 6042 staff <6042-staff@theory.csail.mit.edu> In-Reply-To: <437E583D.9010003@mit.edu> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline References: <437D988C.8020808@mit.edu> <437E583D.9010003@mit.edu> Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by theory.csail.mit.edu id jAJMKX5o003467 Status: RO X-UID: 965 Content-Length: 219 X-Keywords: >> The natural numbers can be represented by a sequence of all 1's, which can be >> represented by the generating function 1/(1-x) Aren't the natural numbers represented by x times the derivative of 1/(1-x)? -Jelani From dshin@MIT.EDU Sat Nov 19 17:23:43 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAJMNh5o007207 for <6042-probs@theory.lcs.MIT.EDU>; Sat, 19 Nov 2005 17:23:43 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAJMNf8R029318; Sat, 19 Nov 2005 17:23:41 -0500 (EST) Received: from w92-130-webmail-4.mit.edu (W92-130-WEBMAIL-4.MIT.EDU [18.7.22.135]) ) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAJMNegd007256; Sat, 19 Nov 2005 17:23:40 -0500 (EST) Received: (from nobody@localhost) by w92-130-webmail-4.mit.edu (8.12.4) id jAJMNeDX025206; Sat, 19 Nov 2005 17:23:40 -0500 Received: from W20-575-87.MIT.EDU (W20-575-87.MIT.EDU [18.187.1.248]) (User authenticated as dshin830@ATHENA.MIT.EDU) by webmail.mit.edu (Horde MIME library) with HTTP for ; Sat, 19 Nov 2005 17:23:40 -0500 Message-ID: <20051119172340.nyecjozz2coo8800@webmail.mit.edu> Date: Sat, 19 Nov 2005 17:23:40 -0500 From: David Shin To: Jelani Nelson Cc: Alexander Bakst , 6042-probs@theory.lcs.MIT.EDU, 6042 staff <6042-staff@theory.csail.MIT.EDU> Subject: Re: [David] Lecture Notes 11 Comments References: <437D988C.8020808@mit.edu> <437E583D.9010003@mit.edu> In-Reply-To: MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format="flowed" Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) H3 (4.0.3) X-Spam-Score: -2.599 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 966 Content-Length: 531 X-Keywords: With this application, I'm using using coefficients of 1 and 0 to represent a subset of the natural numbers. For example, the subset {0,2,3} corresponds to the sequence <1,0,1,1,0,0,0...> and thus to the function 1+x^2+x^3. Sorry if it wasn't clear. DS Quoting Jelani Nelson : >>> The natural numbers can be represented by a sequence of all 1's, > which can be >>> represented by the generating function 1/(1-x) > > Aren't the natural numbers represented by x times the derivative of 1/(1-x)? > > -Jelani > From meyer@imap.theory.csail.mit.edu Sat Nov 19 17:23:43 2005 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAJMNh5o007205 for <6042-staff@theory.csail.MIT.EDU>; Sat, 19 Nov 2005 17:23:43 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id jAJMNf8R029318; Sat, 19 Nov 2005 17:23:41 -0500 (EST) Received: from w92-130-webmail-4.mit.edu (W92-130-WEBMAIL-4.MIT.EDU [18.7.22.135]) ) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id jAJMNegd007256; Sat, 19 Nov 2005 17:23:40 -0500 (EST) Received: (from nobody@localhost) by w92-130-webmail-4.mit.edu (8.12.4) id jAJMNeDX025206; Sat, 19 Nov 2005 17:23:40 -0500 Received: from W20-575-87.MIT.EDU (W20-575-87.MIT.EDU [18.187.1.248]) (User authenticated as dshin830@ATHENA.MIT.EDU) by webmail.mit.edu (Horde MIME library) with HTTP for ; Sat, 19 Nov 2005 17:23:40 -0500 Message-ID: <20051119172340.nyecjozz2coo8800@webmail.mit.edu> Date: Sat, 19 Nov 2005 17:23:40 -0500 From: David Shin To: Jelani Nelson Cc: Alexander Bakst , 6042-probs@theory.lcs.MIT.EDU, 6042 staff <6042-staff@theory.csail.MIT.EDU> Subject: Re: [David] Lecture Notes 11 Comments References: <437D988C.8020808@mit.edu> <437E583D.9010003@mit.edu> In-Reply-To: MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format="flowed" Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) H3 (4.0.3) X-Spam-Score: -2.599 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO Content-Length: 531 X-UID: 967 X-Keywords: With this application, I'm using using coefficients of 1 and 0 to represent a subset of the natural numbers. For example, the subset {0,2,3} corresponds to the sequence <1,0,1,1,0,0,0...> and thus to the function 1+x^2+x^3. Sorry if it wasn't clear. DS Quoting Jelani Nelson : >>> The natural numbers can be represented by a sequence of all 1's, > which can be >>> represented by the generating function 1/(1-x) > > Aren't the natural numbers represented by x times the derivative of 1/(1-x)? > > -Jelani > From meyer@imap.theory.csail.mit.edu Sat Nov 19 17:20:34 2005 Return-Path: Received: from wproxy.gmail.com (wproxy.gmail.com [64.233.184.206]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id jAJMKX5o003472 for <6042-staff@theory.csail.mit.edu>; Sat, 19 Nov 2005 17:20:33 -0500 Received: by wproxy.gmail.com with SMTP id i12so589364wra for <6042-staff@theory.csail.mit.edu>; Sat, 19 Nov 2005 14:20:33 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:sender:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=qPN9JR04KWTogW9W8UMysXNVovZD+C9cg68Z0DLTg4QZJr6iaK1XZAD0NfapH0b6iC50ic5wO1QcaY2gT/ntIc6ORumXg17ZJmSsTai/d116IYLmsfqKnD85uF8s1Fr+AyAb3rvf0tYM4S1ndOl3g5KuBuSTsdUajH+pqwqjBYQ= Received: by 10.64.199.9 with SMTP id w9mr1173433qbf; Sat, 19 Nov 2005 14:20:33 -0800 (PST) Received: by 10.64.150.8 with HTTP; Sat, 19 Nov 2005 14:20:33 -0800 (PST) Message-ID: Date: Sat, 19 Nov 2005 17:20:33 -0500 From: Jelani Nelson Sender: minilek@gmail.com To: David Shin Subject: Re: [David] Lecture Notes 11 Comments Cc: Alexander Bakst , 6042-probs@theory.lcs.mit.edu, 6042 staff <6042-staff@theory.csail.mit.edu> In-Reply-To: <437E583D.9010003@mit.edu> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline References: <437D988C.8020808@mit.edu> <437E583D.9010003@mit.edu> Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by theory.csail.mit.edu id jAJMKX5o003472 Status: RO Content-Length: 219 X-UID: 968 X-Keywords: >> The natural numbers can be represented by a sequence of all 1's, which can be >> represented by the generating function 1/(1-x) Aren't the natural numbers represented by x times the derivative of 1/(1-x)? -Jelani