# [question about partitions]

Frank Ruskey fruskey at csr.csc.uvic.ca
Fri Feb 15 00:37:02 CET 2002

```To exhaustively generate the necklaces you can use the algorithm in
the paper "An Efficient Algorithm for Generating Necklaces with
Fixed Density", SIAM J. Computing, 29 (1999) 671-684, by Joe
Sawada and myself.  Given n and k as input it will generate
all T(n,k) binary necklaces of length n with k 1's in time
proportional to T(n,k), which is best possible in an amortized
sense.  Also, if you only want the necklaces for
smallish values of n then my "Combinatorial Object Server" page
at http://www.theory.csc.uvic.ca/~cos/gen/neck.html
will generate them for you.

Regards,

Frank R.

"Christian G.Bower" wrote:
>
> ID Number: A047996
> Sequence:  1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,2,2,1,1,1,1,3,4,3,1,1,1,1,
>            3,5,5,3,1,1,1,1,4,7,10,7,4,1,1,1,1,4,10,14,14,10,4,1,1,1,1,
>            5,12,22,26,22,12,5,1,1,1,1,5,15,30,42,42,30,15,5,1,1,1,1,6,
>            19,43,66,80,66,43,19,6,1,1,1,1,6,22
> Name:      Triangle of circular binomial coefficients T(n,k), 0<=k<=n.
> Comments:  T(n,k)=number of necklaces with k black beads, n-k white beads.
> References D. E. Knuth, Computer science and its relation to mathematics,
> Amer.
>               Math. Monthly, 81 (1974), 323-343.
>            H. S. Wilf, personal communication, Nov., 1990.
> Links:     Index entries for sequences related to necklaces
> Formula:   T(n,k)=(1/n) * Sum_{d | (n,k)} phi(d)*binomial(n/d,k/d).
> Example:   1; 1,1; 1,1,1; 1,1,1,1; 1,1,2,1,1; 1,1,2,2,1,1; 1,1,3,4,3,1,1; ...
> See also:  Row sums: A000031. Columns 0-12: A000012, A000012, A004526,
>               A007997(n-3), A008610, A008646, A032191-A032197.
>            Cf. A051168, A052307, A052311-A052313.
> Keywords:  nonn,tabl,easy,nice
> Offset:    0
> Author(s): njas
>
> T(n,k) corresponds to n=n, p=k, except that in the partition case,
> T(n,0)=0 while in the necklace case T(n,0)=1.
>
> This table includes odd values of n and k which the correspondent
> excluded.
>
> Christian
>
> "N. J. A. Sloane" <njas at research.att.com> wrote:
> > Anyone want to help this correspondent?  -  njas
> >
> >
> >
> > >>From mahmoud.bekheit at eee.strath.ac.uk  Thu Feb 14 10:12:33 2002
> > >>Delivered-To: njas at research.att.com
> > >>From: "Mahmoud Bekheit" <mahmoud.bekheit at eee.strath.ac.uk>
> > >>To: <njas at research.att.com>
> > >>Subject: Help: Partitions of a number into summand parts & Non-equivalent
> under rotation
> ...
> > >>Dear Prof. Sloane
> > >>
> > >>I'm interested in generating all partitions of an integer number n into
> > >>parts p, each partition should be permutated to five all possible prtts
> > >>permutations. This permutation should satisfy the "non-equivalent under
> > >>rotation", like Necklaces.
> ...
> > >>sample results are:
> > >>
> > >>p          2        4        6        8        10
> > >>===================================
> > >>n
> > >>2          1
> > >>4          2        1
> > >>6          3        3        1
> > >>8          4        10      4        1
> > >>10        5        22      22      5        1
> > >>12        6        43      80      43      6      1
> > >>14        7        73      217    217    73    7     1
> > >>16        8        116    504    810    504  116        1
> > >>
> > >>My question to you
> > >>Is there any definition of this sequence(non equivalent under rotation
> for
> > >>set of p parts)
> > >>
> > >>Thanks
> > >>Mahmoud Bekheit
> > >>University of Strathclyde
> > >>Department of Electronic and Electrical Engineering
> > >>Royal College Building
> > >>204 George Street
> > >>Glasgow G1 1XW
> > >>Scotland, U.K
> > >>
> > >>Tel: 0141 548 2544
> > >>Int.: +44 141 548 2544
> > >>Fax: 0141 552 2487
> > >>E-mail: mahmoud.bekheit at eee.strath.ac.uk
> > >>

--
----------------------
Frank Ruskey                     e-mail: fruskey at csr.uvic.ca
Dept. of Computer Science        fax:    250-721-7292
University of Victoria           office: 250-721-7232
Victoria, B.C. V8W 3P6 CANADA    WWW: http://csr.csc.uvic.ca/~fruskey

```

More information about the SeqFan mailing list