/*

	Multinomialkoeffizienten
	------------------------
	
	Leonhard Fellermayr, Matr.Nr. 22128130XXXX
	
	Programmausgabe:
	
	Ergebnis 8 über {2,3,3}:		5.600000e+02
	Ergebnis 50 über {20,20,10}:		1.415998e+21
	Ergebnis 100 über {25,11,37,27}:	1.005733e+54
	Ergebnis 500 über {200,150,20,80,50}:	5.113276e+294


*/

#include <stdio.h>
#include <stdlib.h>

/* ***** Berechnen der Fakultaet ***** */

long double fak (int x) {
  if (x == 1) return 1;
  else return (x * fak (x - 1));
} // fak ()

/* ***** Berechnen von "n ueber k" ***** */

long double nueberk (int n, int k) {
  return (fak (n) / (fak (k) * fak (n-k)));
} // nueberk ()

/* ***** Berechnen von Multinomialkoeffizienten ***** */

long double multinom (int n, int k[], int kc) {

  int		t, u, oben;

  long double	produkt = 1;
  
  for (t = 0; t < kc - 1; t++) {

    oben = n;

    for (u = 0; u < t; u++)
	oben -= k[u];
   
    produkt *= nueberk (oben, k[t]);

  }

  return (produkt);

} // multinom ()

/* ***** C stub ***** */

int main () {

  int n, kc;	/* Länge des n-Tupels kX muss in kc stehen: "k-count" */

  n	   = 8;
  int k1[] = {2,3,3};
  kc	   = 3;
  printf ("Ergebnis 8 über {2,3,3}: %Le\n", multinom (n, k1, kc));

  n	   = 50;
  int k2[] = {20,20,10};
  kc	   = 3;
  printf ("Ergebnis 50 über {20,20,10}: %Le\n", multinom (n, k2, kc));

  n	   = 100;
  int k3[] = {25,11,37,27};
  kc	   = 4;
  printf ("Ergebnis 100 über {25,11,37,27}: %Le\n", multinom (n, k3, kc));

  n	   = 500;
  int k4[] = {200,150,20,80,50};
  kc	   = 5;
  printf ("Ergebnis 500 über {200,150,20,80,50}: %Le\n", multinom (n, k4, kc));

} // main ()