How to prove this combinatorial formula?

98 Views Asked by At

Notation: For a finite set $S$, we denote by $|S|$ its cardinal, i.e. the number of its elements.

Let $(A,B)$ be a couple of two finite sets such that $|B|\geq 2$. The following equality has been conjectured (using Python code, see below): $$\sum_{n\geq 1}\frac{(-1)^n}{n!}\sum_{(C_1,\ldots,C_n)}(|C_1|-1)!\ldots (|C_n|-1)!=0$$ where the second sum of runs over all $n$-tuples $(C_1,\ldots,C_n)$ of non-empty sets that are pairwise disjoints, such that $\cup_{i=1}^n C_i=A\cup B$, and each $C_i$ contains at least one element of $B$.

Nota Bene: The expression below is equivalent to the last one and it is used to code the algorithm for the conjecture:

$$\sum_{n=1}^{|B|}\frac{(-1)^n}{n!}\sum_{b_1=1}^{|B|-(n-1)}\sum_{b_2=1}^{|B|-(n-2)-b_1} \ldots \sum_{b_{n-1}=1}^{|B|-1-b_1-\ldots-b_{n-2}}\binom{|B|}{b_1,\ldots,b_n}\sum_{a_1=0}^{|A|}\sum_{a_2=0}^{|A|-a_1} \ldots \sum_{a_{n-1}=0}^{|A|-a_1-\ldots-a_{n-2}}\binom{|A|}{a_1,\ldots,a_n}(a_1+b_1-1)!\ldots (a_n+b_n-1)!$$ where $b_n=|B|-b_1-\ldots-b_{n-1}$ and $a_n=|A|-a_1-\ldots-a_{n-1}$.

**Code in Python:**

def multi_binomial(C, c):
res=factorial(C)
for c_i in c:
    res/=factorial(c_i)
return res

def sum_rec(B,A,b,a,n):
res=0
if n==0:
    for k in range(1,B+1):
        res+=(-1)**k/(factorial(k))*sum_rec(B,A,b,a,k)
else:
    if len(b)<(n-1) and len(a)==0:
        for i in range(1,B-sum(b)-(n-len(b))+2):
            res+=sum_rec(B,A,b+[i],a,n)
    if len(b)==(n-1):
        b=b+[B-sum(b)]
        for i in range(A+1):
            res+=sum_rec(B,A,b,a+[i],n)
    if len(a)>0 and len(a)<(n-1):
        for i in range(A-sum(a)+1):
            res+=sum_rec(B,A,b,a+[i],n)
    if len(a)==(n-1):
        a=a+[A-sum(a)]
        res=multi_binomial(B,b)*multi_binomial(A, a)
        for i in range(n):
            res*=factorial(a[i]+b[i]-1)
return(res)


def sol(B,A):
return (sum_rec(B,A,[],[],0))

for B in range(2,10):
for A in range(0,10):
    print("sol(",B,",",A,")=",sol(B,A),)