A000931 (Padovan sequence) W. Lang, Jun 21 2010 I was led to consider the Padovan sequence by a paper sent to me by A. Farina (June 11 2010): "Expressing stochastic filters via number sequences", A. Capponi, A. Farina, C. Pilotto, Signal Processing 90 (2010) 2124-2132. p(n)=A000931(n+3), n>=1, is the number of partitions of the numbers {1,2,3,...,n} into lists of length two or three containing neighboring numbers. The 'or' is inclusive. For n=0 one takes p(0)=1. Call the number of these lists s2 and s3, respectively, where s2 and s3 are nonnegative integers. More precisely: s3 from {0,1,...,floor(n/3)} and s2 from {0,1,...,floor((n-s2*3)/2)}. The number of solutions of n= 3*s3 + 2*s2 is A103221(n), n>=0, the number of partitions of n consisting of parts 2 or 3 only. Note that A103221(0)=1 from the trivial solution. E.g., A103221(8)=2 from the two solutions s3=2, s2=1 and s3=0 and s2=4, corresponding to the partitons (3,3,2) and (2,2,2,2) of 8. Examples for the p(n) combinatorics: p(1)=0 because there is no solution, p(2)=1 from s3=0, s2=1 and the list [1,2], p(3)=1 from s3=1, s2=0 and the list [1,2,3], p(4)=1 from s3=0, s2=2 and the lists [1,2][2,4], p(5)=2 from s3=1, s2=1 and the lists [1,2,3][4,5] and [1,2][3,4,5] p(6)=2 from s3=2, s2=0 and the lists [1,2,3][4,5,6] and from s3=0, s2=3 and the lists [1,2][3,4][5,6] p(7)=3 from s3=1, s2=2 and the lists [1,2,3][4,5][6,7], [1,2][3,4,5][6,7], [1,2][3,4][5,6,7] p(8)=4 from s3=2, s2=1 and the lists [1,2,3][4,5,6][7,8], [1,2][3,4,5][6,7,8], [1,2,3][4,5][6,7,8] and from s3=0, s2=4 and the lists [1,2][3,4][5,6][7,8] p(9)=5 from s3=3, s2=0 and the list [1,2,3][4,5,6][7,8,9] and from s3=1, s2=3 and the lists [1,2,3][4,5][6,7][8,9], [1,2],[3,4,5][6,7][8,9], [1,2],[3,4][5,6,7][8,9], [1,2],[3,4][5,6][7,8,9], p(10)=7 from s3=2, s2=2 and the lists [1,2,3][4,5,6][7,8][9,10], [1,2,3][4,5][6,7,8][9,10], [1,2,3][4,5][6,7][8,9,10], [1,2][3,4,5][6,7,8][9,10], [1,2][3,4,5][6,7][8,9,10], [1,2][3,4][5,6,7][8,9,10], and from s3=0, s2=5 and the list [1,2][3,4][5,6][7,8][8,10] . etc. Note: this is a special case of the so called (general) Morse-code polynomials. In this case only s3 3-lines (of length 2) or s2 2-lines (of length 1) connecting 3 or 2 neighbouring points, respectively, in a row of n points are admitted. Because the recurrence for p(n) has no p(n-1) term, there are no dots (1-lines of length 0). The classical Morse case with only dots and 2-lines of length1 (dashes) shows up for Fibonacci type recurrences. E.g., the four codes for n=8 are -- -- - , - -- --, -- - --, and - - - - . The numbers 1,..,8 border the lines. Because of this combinatorial interpretation the sequence p(n) = 0*p(n-1) + 1*p(n-2) +1*p(n-3) with inputs p(-2)=0, p(-1)=0, and p(0)=1 is the fundamental sequence. As mentioned above p(n) = A000931(n+3) = [1, 0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16,...]. The o.g.f. P(x) = sum(p(n)*x^n,n=0..infty) = 1/(1-x^2-x^3), also showing that this is the fundamental sequence. ##################################################################################################################################### a(a,b;n) Padovan sequences: The sequence a(n) = a(n-2) + a(n-3) with input a(-2)=a, a(-1)=b, and a(0)=1 (hence a(1)= a+b, a(2)= b+1) is a(n) = a(a,b;n) = p(n) + (a+b)*p(n-1) + b*p(n-2). Therefore, A000931(n) = a(1,-1 ;n) = p(n) - p(n-2) = p(n-3) = [1, 0, 0, 1, 0, 1, 1, 1, 2, 2, 3, 4,...], n>=0. Similarly, A000931(n+5) = a(1,0;n) = p(n) + p(n-1) = p(n+2) = [1, 1, 1, 2, 2, 3, 4, 5, 7, 9, ...], n>=0, also A007307(n+1) = a(2,0;n) = p(n) + 2*p(n-1) = p(n+2) + p(n-1) = [1, 2, 1, 3, 3, 4, 6, 7, 10, 13,...], n>=0, also A000931(n+7) = a(1,1;n) = p(n) +2*p(n-1) + p(n-2) = p(n+4) = [1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21,...], n>=0, also A141038(n+1) = a(-1,2;n) = p(n) + p(n-1) +2*p(n-2) = p(n+3) +p(n-2) = [1, 1, 3, 2, 4, 5, 6, 9, 11, 15, 20, ...], n>=0. also A084338(n+1) = a(0,2;n) = p(n) + 2*(p(n-1)+p(n-2)) = p(n) +2*p(n+1) = p(n+3) + p(n+1) = [1, 2, 3, 3, 5, 6, 8, 11, 14, 19, 25, 33, 44,...], n>=0. etc. General input case: a(a,b,c;n) Padovan sequences: a(n) = a(n-2) + a(n-3) with input a(-2)=a, a(-1)=b, and a(0)=c (hence a(1)= a+b, a(2)= b+c) is a(n) = a(a,b,c;n) = c*p(n) + (a+b)*p(n-1) + b*p(n-2), with p(n):=a(0,0,1;n). The o.g.f. is P(a,b,c;x) = (c + (a+b)*x + b*x^2)/(1-x^2-x^3). Therefore the Perrin sequence A001608(n) = a(1,-1,3;n) = 3*p(n) - p(n-2) = 2*p(n) + p(n-3) = [3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, 51, 68, 90, 119, 158, 209, 277,...], n>=0, with o.g.f. P(1,-1,3;x) =(3-x^2)/(1-x^2-x^3) . ####################################################################################################################################### Generalized (A,B)-Padovan sequences with general input: a(A,B;a,b,c;n) (June 24, 2010) a(n) =A*a(n-2) + B*a(n-3) with input a(-2)=a, a(-1)=b, and a(0)=c (hence a(1)= A*b+B*a, a(2)=A*c+B*b) is a(n) = a(A,B;a,b,c;n) = c*p(A,B;n) + (A*b+B*a)*p(A,B;n-1) + B*b*p(A,B;n-2). with p(A,B;n):=a(A,B;0,0,1;n) . The o.g.f. is P(A,B;a,b,c;x) = (c + (A*b+B*a)*x + B*b*x^2)/(1-A*x^2-B*x^3), especially 1/(1-A^x^2-B*x^3) for p(A,B;n). ############################################################# Instances: (2,1)-Padovan: P(2,1;a,b,c;x) = (c + (2*b + a)*x + b*x^2)/((1-x-x^2)*(1+x)). (a,b,c)=(0,0,1): A008346(n) = Fibonacci(n) +(-1)^n . (a,b,c)=(0,1,0): A008346(n+1), n>=0. (a,b,c)=(1,0,0): A008346(n-1), n>=0, with Fibonacci(-1) =1. (a,b,c)=(1,0,1): A000045(n+1)= Fibonacci(n+1). (a,b,c)=(0,1,1): A000045(n+2)Fibonacci(n+2). (a,b,c)=(1,1,0): [0, 3, 1, 6, 5, 13, 16, 31, 45, 78, 121, 201, 320, 523, ...]. (a,b,c)=(1,1,1): A066983(n+3), n>=0. (a,b,c)=(1,-1,1): A033999(n)= (-1)^n. etc. (1,2)-Padovan: (a,b,c)=(0,0,1): A052947(n); (a,b,c)=(0,1,0): A052947(n+1); (a,b,c)=(1,0,0): 2*A052947(n-1) . (a,b,c)=(1,0,1): A052947(n+2); (a,b,c)=(0,1,1): A159284(n+2); n>=0. (a,b,c)=(1,1,0): [0,3,2,3,8,7,14,23,28,51,74,107,176,255,390,607,900,1387,2114,3187,4888,...] (a,b,c)=(1,1,1):A159284(n+3) . (a,b,c)=(1,-1,1):A078026(n+2). etc. #################################################################################### Factorization of the type (1 - A*x^2 - B*x^3) = (1 - al*x - (A-al^2)*x^2)*(1 + al*x) (June 28 2010). Input al (alpha) and A with B = (A-al^2)*al. Special case i) A = 3*(al/2)^2 and B = -2*(al/2)^3 with ((1 - (1/2)*al*x)^2)*(1 + al*x)) = 1 - (3/4)*(al*x)^2 + (1/4)*(al*x)^3 with partial fraction decomposition for the o.g.f. Pfrac(3*(al/2)^2, -2*(al/2)^3,x) := (3/(1 - al*x/2)^2 + 2/(1-al*x/2) + 4/(1 + al*x))/9 leading to p((3/4)*(al)^2, -(1/4)*al^3;n) = ((3*n+5 + (-2)^(n+2))*(al/2)^n)/9 . E.g., al=2: p(3,-2;n) = A077898(n). Special case ii) A = 3*al^2 and B = 2*al^3 with (1 - 2*al*x)*(1 + al*x) = 1 - 3*(al*x)^2 - 2*(al*x)^3 with the partial fraction decomposition for the o.g.f Pfrac(3*al^2, 2*al^3,x ) := (4/(1-2*al*x)+ 2/(1+al*x) + 3/(1+al*x)^2)/9 leading to p(3*al^2, 2*al^3;n) = ((3*n+5 + 2^(n+2))*al^n)/9 . E.g., al=1: p(3,2;n) = A053088(n), n>=0. Other cases iii) al and A (not related like in case i) or case ii)) as input with B =(A-al^2)*al. (1 - A*x^2 - B*x^3) = (1 - al*x - (A-al^2)*x^2)*(1 + al*x) with the partial fraction decomposition for the o.g.f. Pfrac(A, (A - al^2)*al;x) := (((A-2*al^2) - al*(A-al^2)*x)/(1-al*x-(A-al^2)*x^2) - (-al)^(n+2))/(A-3*al^2) leading to p(A,(A - al^2)*al;n) = ((A-2*al^2)*U(al,A-al^2;n) - al*(A-al^2)*U(al,A-al^2;n-1) - (-al)^(n+2))/(A-3*al^2) , with U(al,be;n) generated by the o.g.f. U(al,be;x):=1/(1- al*x - be*x^2) ((al,be)-Fibonacci/Chebyshev). E.g., al=1, A=2; B=1; (1 - 2*x^2 - x^3) = (1 - x - x^2 )*(1 + x); Pfrac(2,1;x)= x/(1-x-x^2)+1/(1+x) ; p(2,1;n) = F(n) + (-1)^n = A008346(n), with the Fibonacci numbers U(1,1;n-1) =F(n)= A000045(n). ######################################################################## For the explicit (Binet-de Moivre type) formula for (A,B)-Padovan sequences see below. ####################################################################### (A,B)-Padovan combinatorics (June 28 2010) For the case (A,B)=(1,1) (Padovan A000931(n+3)) see the beginning of this link. The (generalized) Morse code uses only 3-lines of length 2, namely --, connecting three neighboring points, and 2-lines of length 1, namely - (dash), connecting two neighboring points. There are s3 3-lines and s2 2-lines, with s3 and s2 non-negative integers. If n= 3*s3 + 2*s2 has no solution a(A,B;n)=0. Hence s2 = (n - 3*s2)/2. Each of the s3 3-lines receives a weight A, and each of the s2 2-lines (dashes) a weight B. a(A,B;n) is the number of possible Morse codes of this special weighted type, namely a(A,B;n) = 0 if n= 3*s3 + 2*s2 , else sum((1/s3!)*((n- 2*s3 -1*s2)!/s2!)*(A^s2)*(B^s3), s3=0..floor(n/3)), with s2=s2(n,s3):= (n - 3*s3)/2. E.g., (A,B)=(2,1) a(2,1;n)= A008346(n) (Fibonacci(n) + (-1)^n), n=5: One solution of 5= 3*s3+2*s2: s3=1, s2=1 with the two codes -- - and - --, weighted each with 2^1*1^1=2, i.e., a(2,1;5 ) = 2+2 = 4. ####################################################################################################################################### The explicit formula for p(n) (analogon to the Binet- de Moivre formula for Fibonacci type sequences). See also the formula for A000931(n)= p(n-3) given by Keith Schneider. Here the formula is made explicit. p(n) = ( r^(n+2) + c*z^n + cb*zb^n )/(3*r^2-1), n>=0, with the complex number c:= ((2*r^2-1) + (r/s)*I)/2 and its complex conjugate cb = ((2*r^2-1) - (r/s)*I)/2, and the complex solution z to x^3-x-1=0. i.e., z= e*u + eb*v, with the complex number e:=(-1 + sqrt(3)*I)/2 and its complex conjugate eb= -(1 + sqrt(3)*I)/2 (the two solutions to x^2 + x + 1=0) as well as the two solutions to x^2 - x +1/3^3 =0, namely u^3:= (1 + sqrt(69)/9)/2 and v^3:= (1 - sqrt(69)/9)/2. r:=u + v and s:=sqrt(3)*(u -v). Some numbers which appear in this formula are approximately given by (10 digits, maple13): u: 0.9869912063, v: 0.3377267510, The so called plastic number r: 1.324717957, s: 1.124559024, r/s: 1.177988820, 3*r^2-1: 4.264632998. The complex coefficient c: -.6623589787 + .5622795122*I , c/(3*r^2-1): -.1553144148+.1318471044*I. ########################################################################################### For the (A,B)-Padovan sequences p(A,B;n), defined above, the analog explicit formulae for the case D(A,B):= (B^2)/4 - (A/3)^3 >0 is: p(A,B;n) = ( r(A,B)^(n+2) + c(A,B)*z(A,B)^n + cb(A,B)*zb(A,B)^n )/(3*r(A,B)^2-A), n>=0, with the complex number c(A,B):= (2*(3*r(A,B)^2 - A) - A)/6 + (A*r(A,B)/(2*s(A,B)))*I and its complex conjugate cb(A,B) = ((2*(3*r(A,B)^2 - A) - A)/6 - (A*r(A,B)/(2*s(A,B)))*I and the complex solution z to x^3 - A*x - B = 0. i.e., z(A,B)= e*u(A,B) + eb*v(A,B), with the complex number e:=(-1 + sqrt(3)*I)/2 and its complex conjugate eb= -(1 + sqrt(3)*I)/2 (the two solutions to x^2 + x + 1=0) as well as the two solutions to x^2 - B*x + (A/3)^3 = 0, namely u(A,B)^3:= b/2 + sqrt(D(A,B)) and v(A,B)^3:= b/2 - sqrt(D(A,B)), with D(A,B) from above. zb(A,B) is the complex conjugate of z(A,B) and r(A,B):=u(A,B) + v(A,B) and s(A,B):=sqrt(3)*(u(A,B) - v(A,B)). ############################################################################################## ############################## e.o.f. ########################################################################################################