Search: id:A133925
Results 1-1 of 1 results found.

%I A133925
%S A133925 0,1,1,1,2,0,3,1,2,3,1,5,1,5,4,3,8,2,10,5,8,12,5,18,7,18,17,13,30,12,36,
%T A133925 24,31,47,25,66,36,67,71,56,113,61,133,107,123,184,117,246,168,256,291,
%U A133925 240,430,285,502,459,496,721,525,932,744,998,1180,1021,1653,1269,1930
%N A133925 Number of compositions of n into parts of size 2 and 3 with no three 
               consecutive 2s and no two consecutive 3s.
%C A133925 We give a combinatorial proof of the claimed recursion. We use the phrase 
               "good compositions" to mean "compositions of the desired sort, i.e. 
               into parts of size 2 or 3 with no three consecutive 2s or two consecutive 
               3s." Take n >= 7. Then good compositions of n and (n - 1) beginning 
               with 3 are in bijection with good compositions of (n - 3) and (n 
               - 4) beginning with 2 -- remove the leading 3. Good compositions 
               of n beginning with 23 are in bijection with good compositions of 
               (n - 5) beginning with 2 -- remove the leading 23. Good compositions 
               of n and (n - 1) beginning with 223 are in bijection with good compositions 
               of (n - 4) and (n - 5) beginning with 3 -- remove the leading 22. 
               And good compositions of (n - 1) beginning with 23 are in bijection 
               with good compositions of (n - 3) beginning with 3 -- remove the 
               leading 2. Taken together, this gives that good compositions of n 
               and (n - 1) are in bijection with good compositions of (n - 3), (n 
               - 4) and (n - 5), so a(n) = -a(n - 1) + a(n - 3) + a(n - 4) + a(n 
               - 5). A000931(n + 3) gives the number of compositions of n into parts 
               of size 2 and 3 without any additional restrictions.
%F A133925 a(n) = -a(n - 1) + a(n - 3) + a(n - 4) + a(n - 5).
%F A133925 G.f.: (x^2+2*x+2) / (1+x-x^4-x^3-x^5). [From Alois P. Heinz (heinz(AT)hs-heilbronn.de), 
               Oct 07 2008]
%e A133925 a(5) = 2 because we have 5 = 2 + 3 = 3 + 2. a(6) = 0 because the only 
               ways to write 6 as a sum of 2s and 3s are 6 = 2 + 2 + 2 = 3 + 3.
%p A133925 a:= n-> (Matrix([[1$3, 0, 2]]). Matrix(5, (i,j)-> if i+1=j then 1 elif 
               j=1 then [ -1, 0, 1$3][i] else 0 fi)^n)[1,5]: seq (a(n), n=1..67); 
               [From Alois P. Heinz (heinz(AT)hs-heilbronn.de), Oct 07 2008]
%Y A133925 Sequence in context: A054656 A080096 A068915 this_sequence A071492 A096067 
               A098861
%Y A133925 Adjacent sequences: A133922 A133923 A133924 this_sequence A133926 A133927 
               A133928
%K A133925 easy,nonn
%O A133925 1,5
%A A133925 Joel Lewis (jblewis(AT)post.harvard.edu), Jan 07 2008

Search completed in 0.001 seconds