Functions(指数型生成函数)

Functions(指数型生成函数) 7.6 Exponential Generating Functions 複習：Generating Functions Let h, h, …, h, … 01n be an infinite sequence of numbers. Its generating function is 2n g(x) = h + hx + hx +…+ hx + …. 012n generating functions, . – (generating functions) Example. (P224) 令h為由蘋果、香蕉、橘子、梨中, 取出n個的方法數; 規定：蘋果n 要偶數個, 香蕉的個數是a multiple of 5, 橘子at most 4, 梨 0 or 1. 求 h. n2 4 5 10 2 3 4令g(x) = (1 + x+ x+ …)(1 + x+ x+ …)(1 + x + x+ x+ x)(1 + x). n 則 h = g(x) 的展開式中 x的係數. n 新人上場：Exponential Generating Functions Let h, h, …, h, … 01n be an infinite sequence of numbers. Its exponential generating function is 2nxxx()e (),，，，？，，？gxhhhh012n. 1!2!!n exponential generating functions, . – (exponential generating functions) Example. (P243) 令h為由1, 2, 3所形成的n-digit numbers的方法數; 規定：1要偶數個, n 2的個數at least three, 3的個數at most four. 求 h. n 24345234xxxxxxxxxe()gx(),(1，，，？)(，，，？)(1，，，，)令 . 2!4!3!4!5!1!2!3!4! nx(e) 則 g(x)h = 的展開式中 的係數. nn! 17 Example. (P244) Determine the number of ways to color the squares of a 1-by-n chessboard, using the colors, red, white, and blue, if an even number of squares are to be colored red. 用「紅」「白」「藍」三色來塗1-by-n棋盤, 規定：要有偶數個格子塗「紅」, .問有多少方法. 令h為方法數. n 2422xxxxxx()eg(x),(1，，，？)(1，，，？)(1，，，？)令 . 2!4!1!2!1!2! 11(e)x,xxx3xxg(x),(e，e)ee,(e，e)則 22 n,,,nn,,,,1xx1xnn,,,,3(31),，,，,,, . ,,,,2n!n!2n!,0,0nnn,0,,,, n1xn(e) ,(3，1)? g(x)h = 的展開式中 的係數 . ? nn!2 Example. (P244) Determine the number h of n-digit numbers with each digit odd where the n digits 1 and 3 occur an even number of times. 用「1, 3, 5, 7, 9」來形成n-digit numbers, 規定：1 and 3要有偶數個, . 問有多少方法. 令h為方法數. n 242xxxxe()23g(x),(1，，，？)(1，，，？)令 . 2!4!1!2! 2 11,,(e)x,x3x5x3xxg(x),(e，e)e,？,(e，2e，e),,則 【中間自己寫】 24,, nnnnnn,,,,,,,,1xxx5231x，，，nn,,,,523,，，，,,,,,,,,, . 4n!n!n!4n!nnn0,0,00,,n,,,, nnn5，2，3，1x(e) ,? g(x)h = 的展開式中 的係數 . ? n4n! 12.6/6【碩士班林鼎鈞負責】Chapter 7: 習38, 39, 40, 41. 18 set -- 元素不可重複. multiset -- 元素可重複. , permutations of a set -- 3.2的內容 , combinations of a set -- 3.3的內容 , permutations of a multiset {n．a, n．a, …, n．a} 1122kk -- 3.4「只講兩情形」： 情形1. 每種東西的repetition number 都是 ?. 情形2. 每種東西的repetition number 都是finite, 但全部東西都要拿出來排列. 這也是大家以前學過的 “重覆排列”, n!. n!n!...n!12k -- 7.5 exponential generating functions 講其他更general的情形. 描述問題 – 叫我(exponential generating functions)第一名！ Example. (P243) 令h為由1, 2, 3所形成的n-digit numbers的方法數; n 規定：1要偶數個, 2的個數at least three, 3的個數at most four. 求 h. n 24345234xxxxxxxxxe()令 gx(),(1，，，？)(，，，？)(1，，，，). 2!4!3!4!5!1!2!3!4! nx(e) 則 g(x)h = 的展開式中 的係數. nn! , combinations of a multiset {n．a, n．a, …, n．a} 1122kk -- 3.5「只講一情形」：每種東西的repetition number 都是 ?. -- 6.2「只講一情形」：只講每種東西的取出的個數都是在某個range之內. 用來解. Example. (P169) Determine the number of 10-combinations of T = {4,a,3,b,4,c,5,d}. Example. Determine the number of integral solutions（整數解） of the equation x，x，x，x,183,x,90,x,5 which satisfy 1,x,5, . ,2,x,4,12344312 -- 7.4 generating functions 講其他講其他更general的情形. 描述問題 – 叫我(generating functions)第一名！ Example. (P224) 令h為由蘋果、香蕉、橘子、梨中, 取出n個的方法數; 規定：n 蘋果要偶數個, 香蕉的個數是a multiple of 5, 橘子at most 4, 梨 0 or 1. 求 h. n2 4 5 10 2 3 4令g(x) = (1 + x+ x+ …)(1 + x+ x+ …)(1 + x + x+ x+ x)(1 + x). n 則 h = g(x) 的展開式中 x的係數. n 19 Example. (P245) Determine the number h of ways to color the squares of a 1-by-n n chessboard, using the colors, red, white, and blue, where the number of red squares is even and there is at least one blue square. 用「紅」「白」「藍」三色來塗1-by-n棋盤, 規定：要有偶數個格子塗「紅」、至少一個格子塗「藍」, .問有多少方法. 令h為方法數. n 2422xxxxxx()eg(x),(1，，，？)(1，，，？)(，，？)令 . 2!4!1!2!1!2! 11(e)x,xxx3x2xxg(x),(e，e)e(e,1)則 ,(e,e，e,1) 22 ,nnn1321x,，,,，,. 22n!,n0 nx(e) g(x)h = 的展開式中 的係數. nn! nn3,2，1? h = 0 if n = 0 and h = if n = 1, 2, … ? nn2 , n = 4 . nx紅個數 白個數 藍個數 塗法數 exponential generating function中的係數 n! 4!0 0 4 【你】 0!0!4! 0134xxx4!x4!0 1 3 ,,, 0!1!3!0!1!3!4!0!1!3! 4!0 2 2 【你】 0!2!2! 4!0 3 1 【你】 0!3!1! 4!2 0 2 【你】 2!0!2! 2114xxx4!x4!2 1 1 ,,, 2!1!1!2!1!1!4!2!1!1! , (P241) Theorem 7.7.1 【自己看】 20