Problems with A121312

[Max A.]

Joshua,

You seem to be right.

btw, I've got the following (somewhat new) formula for the number of
such pairs (in PARI/GP notation):

{ a(n) = sum(i=0,n, binomial(n,i) * f(n,i) ) }

where function f(n,k) is ala Vandermonde's convolution:

{ f(n,k) = local(d); d=gcd(n,k); sum(j=0,d,
binomial(k,j*k/d)*binomial(n-k,j*(n-k)/d) ) }

It is clear that f(n,k) = f(n,n-k), thus giving a symmetric triangle
of coefficient (for n=1..14):

2 2
4 2 4
8 2 2 8
16 2 6 2 16
32 2 2 2 2 32
64 2 14 20 14 2 64
128 2 2 2 2 2 2 128
256 2 42 2 70 2 42 2 256
512 2 2 92 2 2 92 2 2 512
1024 2 142 2 122 252 122 2 142 2 1024
2048 2 2 2 2 2 2 2 2 2 2 2048
4096 2 506 506 646 2 924 2 646 506 506 2 4096
8192 2 2 2 2 2 2 2 2 2 2 2 2 8192
16384 2 1850 2 1514 2 1402 3432 1402 2 1514 2 1850 2 16384

This triangle seems to be missing in the OEIS.

Other properties of the function f(n,k):

f(n,0) = f(n,n) = 2^n

f(n,k) = 2 as soon as gcd(n,k)=1

f(2k,k) = binomial(2k,k)

Max

On 10/2/06, Joshua Zucker <joshua.zucker at gmail.com> wrote:
> Conjecture: maybe it means independent in the sense of probability for
> equally likely events?
> Then two sets A and B that are subsets of a set of n elements are
> independent if and only if |A| * |B| = |A intersect B| * n, or more
> probabilistically speaking, |A|/n * |B|/n = |A intersect B| / n.
>
> So the empty set is always independent with everything, and the full
> set is always independent with everything ...
>
> Let's see what I get for three elements.
> Empty set with everything: 15 pairs.
> Full set with everything: 13 pairs (don't count the empty set!)
> And that makes 28, and I think that's everything.
>
> For four elements:
> Empty set with everything: 31 pairs
> Full set with everything: 29 pairs.
> Well, that's 60 so far.
> Then we have the cases where |A| * |B| = 4, |A intersect B| = 1,
> and those would already have been counted if |A| is 4, so it's |A| = 2
> and |B| = 2 and |A intersect B| = 1.  6 ways to choose A, and then 4
> ways to choose B (one of the two elements of A, and one of the two
> elements of non-A), so that's 24 more, making 84.
>
> So I think I got it!
> --Joshua Zucker
>
>
> On 10/2/06, franktaw at netscape.net <franktaw at netscape.net> wrote:
> > Two problems with this sequence
> > (http://www.research.att.com/~njas/sequences/A121312):
> >
> > The minor one is that the author has misspelled "independent" as
> > "independant" twice, adding an extra "s" at the end the second time.
> >
> > More seriously, I don't know what he means by "independent subset".
> > Mathworld shows this as a synonym for "disjoint subset", but that is
> > clearly not what is meant here.  I don't know what definition of
> > independent would have ({x}, {x}) and ({x}, {y}) not be independent,
> > but ({}, {}), ({}, {x,y}), and ({x,y}, {x,y}) would be independent.
> >
> > The formulas and program don't leave me any wiser; they show how the
> > sequence was computed, but not what it means.
> >
> > Franklin T. Adams-Watters
>



X-From_: owner-nmbrthry at LISTSERV.NODAK.EDU Thu Oct  5 14:38:31 2006