Make your own free website on Tripod.com


1. Some combinatorics

Every aditive expression of a natural number n as an ordered sequence of natural numbers is called a decomposition [18] of n. All the decompositions of n we denote by n'. The number of decompositions of n is d'(n) = 2n-1. We also distinguish a subclass of decompositions, denoted by n'', where every decomposition is identified with its obverse. The number of n''-decompositions is 

d''(n) = 2n-2+2[n/2]-1.

If n is decomposed in k numbers, the number of such k-decompositions of n is 
 

d'(n,k)=  æ 
è 
n-1 
k-1
ö 
ø 
 

Every decomposition of n by numbers 2 or 1 is called a bicomposition of n. The number of bicompositions of n, denoted by ~n, is ~b(n) = fn, where fn is Fibonacci sequence, determined by the recursion formula 
  

f0 = 1,  f1 = 1,  fn-2+ fn-1 = fn.
 
 

For the subclass of bicompositions n, where every bicomposition is identified with its obverse, their number b(n) is given by the recursion formula 
  

b(0) = 1,  b(1) = 1,  b(2n-2) + b(2n-1) = b(2n),
 

  

b(2n) + b(2n-1) - fn-1 = b(2n+1).
 
 

Every ~n- or n-bicomposition with the number 2 occuring l-k times and 1 occuring k times is called ~(l,k)- or (l,k)-bicomposition, and l is called the lenght of bicomposition. There are 

æ 
è
l 
k
ö 
ø
+ s(l,k)

2
 

(l,k)-bicompositions, and among them s(l,k) are symmetrical, where s(l,k)= 

0 for l=0 (mod 2) and k=1 (mod 2);
(k/2)!/((k/2)!((l-k)/2)!) for l=0 (mod 2) and k=0 (mod 2);
((l-1)/2)!/((k/2)!((l-k-1)/2)!) for l=1 (mod 2) and k=0 (mod 2);
((l-1)/2)!/((k-1/2)!((l-k)/2)!) for l=1 (mod 2) and k=1 (mod 2).

Also, we will consider the subclasses of n'- and n''-decompositions, ~ n- and n-bicompositions, beginning with any number except 1, denoted respectively by n *, n **, ~n * , n *. Their numbers are:
d * (n) = 2n-2d **(n) = 2n-4+2[n/2]-2
~ d * (n) = fn-2,  d *(n) = b(n-4).  

 

NEXT