Bracelets {Necklaces}

Bracelets

Description

The function generates all the representatives of all the bracelets of length n over an alphabet of m consecutive non-negative integers.

Usage

Bracelets(n=1, m=1, fn=1)

Arguments

n

positive integer: the length of the representatives

m

positive integer: the number of consecutive non-negative integers in the alphabet

fn

integer: the first value of the alphabet, the default is 1

Details

The function generates the list of all representatives of all bracelets having a fixed length n on the same alphabet, by default {1,2,...,m}. The main block function is the fBracelets function of the Necklaces package, which is called repeatedly. The input parameters of the fBracelets function are generated by using the mKT function of the kStatistics package. Indeed, given a multi-index v, that is a vector of non-negative integers, and a positive integer n, the mKT function returns all the lists (v1,...,vn) of non-negative integer vectors, having the same length of the multi-index v and such that v=v1+...+vn. Here, the mKT function is used with the input vector having length 1 as well as the output vectors v1,...,vn, corresponding to the partitions of an integer with a fixed number of parts. As example, the mKT function with input (3,3) generates the following result:

[( 1 )( 1 )( 1 )]

[( 0 )( 1 )( 2 )]

[( 1 )( 0 )( 2 )]

[( 1 )( 2 )( 0 )]

[( 0 )( 2 )( 1 )]

[( 2 )( 0 )( 1 )]

[( 2 )( 1 )( 0 )]

[( 0 )( 3 )( 0 )]

[( 3 )( 0 )( 0 )]

[( 0 )( 0 )( 3 )]

Each vector is a possible configuration and then passed to the fBracelets function to recover the corresponding bracelet. For example

• the configuration [( 1 )( 1 )( 1 )] denotes the vector (1,2,3); calling fBracelets(c(1,1,1)), the representative [1 2 3] is generated;
  

• the configuration [( 0 )( 1 )( 2 )] denotes the vector (2,3,3); calling fBracelets(c(0,1,2)), the representative [2 3 3] is generated;
  

• the configuration [( 1 )( 0 )( 2 )] denotes the vector (1,3,3); calling fBracelets(c(1,0,2)), the representative [1 3 3] is generated;

and so on. As last step, the union of all the outputs gives the expected result:

[ 1 1 1 ], [ 1 1 2 ], [ 1 1 3 ], [ 1 2 2 ], [ 1 2 3 ], [ 1 3 3 ], [ 2 2 2 ], [ 2 2 3 ], [ 2 3 3 ], [ 3 3 3 ]

that are all the representatives of bracelets of length 3 on the alphabet {1,2,3}.

Note: Comparing this example with the one given in the description of the fNecklaces function, [1 3 2] is missed since it is in the class of the bracelet [1 2 3] = {(1 2 3),(1 3 2),(2 1 3),(2 3 1),(3 1 2),(3 2 1)} obtained running cBracelets(c(1,2,3)).

Value

list

the list containing all the representatives of all the bracelets of length n over an alphabet of m consecutive non-negative integers.

Note

The function calls the fBracelets function in the Necklaces package and the mKT function in the kStatistics package.

Author(s)

Elvira Di Nardo [e-mail],
Giuseppe Guarino [e-mail]

References

Di Nardo, E., and Guarino., G. (2022) kStatistics: Unbiased Estimates of Joint Cumulant Products from the Multivariate Faa Di Bruno's Formula. The R journal - In press. (https://arxiv.org/abs/2206.15348)

Di Nardo, E., and Guarino., G. (2022) Necklaces and bracelets in R - (https://arxiv.org/abs/2208.06855)

Flajolet, P., and Sedgewick, R. (2009) Analytic combinatorics. Cambridge University press.

See Also

fBracelets, LyndonW, sBruijn

Examples

# Generate the list of all the representatives of all the bracelets 
# of length 4 over the alphabet {1,2}. 
Bracelets(4,2)  

# Generate the list of  all the representatives of all the bracelets 
# of length 5 over the alphabet {1,2,3}. 
Bracelets(5,3)  

# Generate the list of  all the representatives of all the bracelets 
# of length 5 over the alphabet {0,1,2}. 
Bracelets(5,3,0)