Problem z wyznaczeniem kombinacji

[orzechw]

Witam, problem jest przedstawiony następująco:

Mam \(\displaystyle{ n}\) zbiorów kolejno \(\displaystyle{ a_{1} , a_{2} , ..., a_{n}}\) elementowych. Na ile sposób mogę wybrać 3 elementy tak, aby każdy element był z innego zbioru?

Na przykład:
\(\displaystyle{ n = 4\\
a_{1} = 3, a_{2} = 2, a_{3} = 2, a_{4} = 1}\)
zbiór 1: \(\displaystyle{ \{a, b, c\}}\)
zbiór 2: \(\displaystyle{ \{d, e\}}\)
zbiór 3: \(\displaystyle{ \{f, g\}}\)
zbiór 4: \(\displaystyle{ \{h\}}\)

Z tego co udało mi się zauważyć wynika, że wynikiem jest suma iloczynów wszystkich możliwych 3-elementowych kombinacji liczebności zbiorów, tj. dla danych w przykładzie:
\(\displaystyle{ ( a_{1} \cdot a_{2} \cdot a_{3} )+( a_{1} \cdot a_{2} \cdot a_{4} )+( a_{1} \cdot a_{3} \cdot a_{4} )+( a_{2} \cdot a_{3} \cdot a_{4} ) = 12+6+6+4 = 28}\)

Jednak zastanawiam się czy da się uniknąć generowania wszystkich możliwych kombinacji spośród liczebności zbiorów, bo dla np. \(\displaystyle{ n = 10}\) byłoby ich już \(\displaystyle{ {10\choose 3}}\) czyli \(\displaystyle{ 120}\).

Zastanawiałem się nad kilkoma sposobami, pierwszy zakładał obliczenie wszystkich możliwych kombinacji, tj. dla przykładu:
\(\displaystyle{ a_{1} + a_{2} + a_{3} + a_{4} = 8}\) czyli \(\displaystyle{ {8\choose 3}}\)
i odejmowanie od wyniku wszystkich błędnych kombinacji, ale niestety nie udało mi się do niczego sensowanego dojść..

Proszę o pomoc.

[vpprof]

Ja mogę tylko stwierdzić, że szukane przez ciebie liczby spełniają zależność rekurencyjną:
\(\displaystyle{ c_{1,k}=1 \\
c_{n,1}= \sum_{i=1}^{n}a_i \\
c_{n+1,k}=c_{n,k}+a_{n+1} \cdot c_{n,k-1}}\)
gdzie \(\displaystyle{ c_{n,k}}\) to liczba kombinacji przy wyborze \(\displaystyle{ k}\) elementów (u ciebie \(\displaystyle{ k=3}\)) spośród \(\displaystyle{ n}\) zbiorów mających \(\displaystyle{ a_1,a_2,…a_n}\) elementów.

Można tę rekurencję rozwiązać za pomocą funkcji tworzących (z dwiema zmiennymi), można też odgadnąć wynik (bo na oko ma to wiele wspólnego z trójkątem Pascala), ale to chyba ponad moje siły. A szczerze mówiąc, chętnie zobaczyłbym jaka jest funkcja tworząca takiego ciągu i jak odczytać z niej postać jawną.

[mrugacz95]

Należy dodać jeszcze jedno założenie gdy \(\displaystyle{ n<k}\) to \(\displaystyle{ c _{n,k}=0}\)

[vpprof]

W pierwszym warunku mojej rekurencji jest błąd, powinno być \(\displaystyle{ a_1}\) zamiast \(\displaystyle{ 1}\) — jeśli już, ale można ją w ogóle lepiej skonstruować. Poniżej ta sama rekurencja „na czysto”:
\(\displaystyle{ \forall n,k \in \mathbb{N}_+ \\
\begin{cases} c_{1,k+1}=0 \\
c_{n,1} = \sum_{i=1}^{n} a_i \\
c_{n,k} = c_{n-1,k}+a_nc_{n-1,k-1}\end{cases}}\)

orzechw aka mrugacz95, spróbuję z tego wyprowadzić wzór jawny dla ciebie, ale to nie dzisiaj. Tymczasem to powyższe sprawdziłem w Excelu, bardzo ładnie działa.