Divisibility and Binomial Coefficients

Mon May 5 23:03:31 CEST 2008

I tried looking at this with Legendre's theorem, and got
nowhere with it.

Here's one idea: if we fix a and b, the expression
C(n,a+b) / (C(n,a) + C(n,b))
is a rational function in n.  From this, one can prove that certain
combinations of a and b are not possible.  1,2 is one such.

I suspect from this that any given a and b will have solutions for
only finitely many n.  Perhaps at most one.  I don't see how to
get a start at proving this, however.

I also suspect that there are solutions with differences of more
than 2 between a and b.  Perhaps someone could do an
intensive search for differences of 3.

Franklin T. Adams-Watters

-----Original Message-----
From: Stefan Steinerberger <stefan.steinerberger at gmail.com>

First, thanks for all your interest and thoughts.
The computed numbers lead me to conjecture that
both problems

C(n,a)+C(n,a+1) | C(n,2a+1)
C(n,a)+C(n,a+2) | C(n,2a+2)

have infinitely many solutions and that Drew's observation
about the fact that the two variables never differ by more than
2 is correct. Sadly, no idea for a proof (I don't suppose one
could prove the "differ by 2" statement by using Legendre's
theorem to count the multiplicity of prime factors of both terms?)

In any case, thanks for all your interest/time/computing power,
Stefan

> I appreciate your inform about transforms. That is new to me.

An opportunity to promote the PARI transforms!
I can't pass that up.

By the way, if you don't have PARI, you can check out the page at:
http://pari.math.u-bordeaux.fr/

Using the PARI coding for the transforms on the page

http://www.research.att.com/~njas/sequences/transforms_pari.txt

We can do your calculations.

> Example 1) Number of unlabeled graphs on n nodes with m connected
components.

First I calculate A000088

(This is a bit complicated, sorry.)

? /* Return next partition (as vector of 2-element vectors) */
{ nextpart(P) = local(excess=1, m);
}

/* Partition divisor */
{ partval(P) = prod(i=1,#P,P[i][1]^P[i][2]*P[i][2]!);
}

/* Graphs (symmetric reflexive relations) */
{ rec_fix_graph(P,z=2) = local(gc,r=1,e);
}

{ rec_graph(n,k=2) = local(s,P=n);
}

? ? ? ? ? ? ? ? ? ? ? ? A000088=concat(1,vector(10,n,rec_graph(n)))
%1 = [1, 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, 12005168]

*****
Now using the transforms, I calculate A001349 and the triagle
*****

? \r transforms_pari.txt
? A001349=trv_i_euler(A000088)
%2 = [0, 1, 1, 2, 6, 21, 112, 853, 11117, 261080, 11716571]
? m1=matrix(11,11)
%3 = 
[0 0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0 0]

? for(i=1,#A001349,m1[i,2]=A001349[i])
? m1
%5 = 
[0 0 0 0 0 0 0 0 0 0 0]

[0 1 0 0 0 0 0 0 0 0 0]

[0 1 0 0 0 0 0 0 0 0 0]

[0 2 0 0 0 0 0 0 0 0 0]

[0 6 0 0 0 0 0 0 0 0 0]

[0 21 0 0 0 0 0 0 0 0 0]

[0 112 0 0 0 0 0 0 0 0 0]

[0 853 0 0 0 0 0 0 0 0 0]

[0 11117 0 0 0 0 0 0 0 0 0]

[0 261080 0 0 0 0 0 0 0 0 0]

[0 11716571 0 0 0 0 0 0 0 0 0]

? trm_euler(m1)
%6 = 
[1 0 0 0 0 0 0 0 0 0 0]

[0 1 0 0 0 0 0 0 0 0 0]

[0 1 1 0 0 0 0 0 0 0 0]

[0 2 1 1 0 0 0 0 0 0 0]

[0 6 3 1 1 0 0 0 0 0 0]

[0 21 8 3 1 1 0 0 0 0 0]

[0 112 30 9 3 1 1 0 0 0 0]

[0 853 145 32 9 3 1 1 0 0 0]

[0 11117 1028 154 33 9 3 1 1 0 0]

[0 261080 12320 1065 156 33 9 3 1 1 0]

[0 11716571 274806 12513 1074 157 33 9 3 1 1]

> Example 2) Number of graphs on n labeled nodes with m connected components

? A006125=vector(11,n,2^binomial(n-1,2))
%7 = [1, 1, 2, 8, 64, 1024, 32768, 2097152, 268435456, 68719476736,
35184372088832]
? A001187=trv_log(A006125)
%9 = [0, 1, 1, 4, 38, 728, 26704, 1866256, 251548592, 66296291072,
34496488594816]
? for(i=1,#A001187,m1[i,2]=A001187[i])
? m1
%10 = 
[0 0 0 0 0 0 0 0 0 0 0]

[0 1 0 0 0 0 0 0 0 0 0]

[0 1 0 0 0 0 0 0 0 0 0]

[0 4 0 0 0 0 0 0 0 0 0]

[0 38 0 0 0 0 0 0 0 0 0]

[0 728 0 0 0 0 0 0 0 0 0]

[0 26704 0 0 0 0 0 0 0 0 0]

[0 1866256 0 0 0 0 0 0 0 0 0]

[0 251548592 0 0 0 0 0 0 0 0 0]

[0 66296291072 0 0 0 0 0 0 0 0 0]

[0 34496488594816 0 0 0 0 0 0 0 0 0]

? trm_exp_h(m1)
%11 = 
[1 0 0 0 0 0 0 0 0 0 0]

[0 1 0 0 0 0 0 0 0 0 0]

[0 1 1 0 0 0 0 0 0 0 0]

[0 4 3 1 0 0 0 0 0 0 0]

[0 38 19 6 1 0 0 0 0 0 0]

[0 728 230 55 10 1 0 0 0 0 0]

[0 26704 5098 825 125 15 1 0 0 0 0]

[0 1866256 207536 20818 2275 245 21 1 0 0 0]

[0 251548592 15891372 925036 64673 5320 434 28 1 0 0]

[0 66296291072 2343580752 76321756 3102204 169113 11088 714 36 1 0]

[0 34496488594816 675458276144 12143833740 272277040 8692845 391881 21210 1110
45 1]

*****
And we have your 2nd triangle
*****

> Once I went to the task of extend the sequence A001429 with formula
> a(n) = A068051(n) - A027852(n) - A000081(n). I worked well with
> A027852 but I cannot understand the DIK transform,

DIK transform is implemented in the PARI script as trv_polygon.

A068051 can be calculated as follows:

? A000081=[0,1]
%14 = [0, 1]
? for(i=2,10,A000081=concat(0,trv_euler(A000081)))
? A000081
%15 = [0, 1, 1, 2, 4, 9, 20, 48, 115, 286, 719]
? A027852=trv_euler_2(A000081)
%16 = [0, 0, 1, 1, 3, 6, 16, 37, 96, 239, 622]
? A068051=trv_polygon(A000081)
%17 = [1, 1, 2, 4, 9, 20, 49, 118, 300, 765, 1998]
? A001429=A068051-A027852-A000081
%18 = [1, 0, 0, 1, 2, 5, 13, 33, 89, 240, 657]
? A001429[1]=0
%19 = 0
? A001429
%20 = [0, 0, 0, 1, 2, 5, 13, 33, 89, 240, 657]

*****
As far as comments on partition formulas, they are good for hand checking
tedious very quickly with 719 partitions of 10. So it's nice to have
efficient formulas and let the computer do the work.

The Euler and exponential transforms and their inverses are also available
in the Maple and Mathematica programs. I don't think the matrix forms are
though. The DIK/polygon transform has not been implemented in those.

Christian

%N A117871 Decimal expansion of reciprocals of cumulative product of all divisors of 1..n.

Huh?  Decimal expansion of reciprocals ... is meaningless

%F A117871 Decimal expansion of SUM[i=1..infinity] 1/A092143(i) = SUM[i=1..infinity] 1 / product_{k=1..i} floor(i,k)!.

Huh?  floor(i,k)! is meaningless

I will edit both entries

Neil