[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