Kombinatorik Steuer-ID-Nr

Wissenschaft Mathematik
#1

Hallo zusammen,

die deutsche Steuer-ID setzt sich aus 10 Ziffern plus einer Prüfziffer zusammen.

Für die 10 Ziffern gelten aber diese Regeln:

  1. Genau eine Ziffer kommt genau zweimal vor.
  2. Genau eine Ziffer kommt nicht vor.
  3. Die verbleibenden acht Ziffern kommen genau einmal vor.
  4. Die erste Ziffer ist nicht 0.

Wieviele Steuer-ID-Nummern gibt es denn dann maximal?

Ich habe keinen eigenen Ansatz, das nur mal so am Rande.

#4

upsa,

ich habe in meiner Antwort aus Versehen, alle Ziffern als unterscheidbar angenommen. Da ja zwei Ziffern gleich sind, halbiert sich das Ergebnis nochmal.

Damit sind wir bei ca. 150 Mio

1 Like
#2

Moin,

aus 1 und 2 folgt, dass nur 9 Stellen „aktiv“ sind. 4 schränkt die 1. Stelle um eine Möglichkeit ein. Somit gibt es 998765432*1 Möglichkeiten.

Gruß Ralf

#3

Erstmal gibt es 10 Möglichkeiten, eine Ziffer wegzulassen. Also 1 aus 10 = 10

jetzt wählt man eine aus den 9 Ziffern, die doppelt vorkommen soll. Also 1 aus 9 = 9

Nun braucht es eine Fallunterscheidung für diese 10 x 9 = 90 Fälle:

  1. Null wurde weggelassen
    In diesen 1 x 9 Fällen dürfen die 10 verfügbaren Ziffern beliebig verteilt werden, also 10 * 9 * 8 * … * 1 = 10!

  2. eine andere Ziffer wurde weggelassen

2.1 Null kommt doppelt vor
In diesen 9 x 1 Fällen darf keine Null an die erste Stelle, also 8 * 9 * 8 * 7 * … * 1 = 8 * 9!

2.2 eine andere Ziffer kommt doppelt vor
In diesen 9 x 8 Fällen darf keine Null an die erste Stelle, also 9 * 9 * 8 * 7 * … * 1 = 9 * 9!

Antwort:
9 * 10! + 9 * 8 * 9! + 72 * 9 * 9! = 81 * 10! = 293932800

#5

scheint richtig, wenigstens kommt mein brutal force Programm auf die gleiche Lösung:

#include "stdio.h"
int summe;       /* Anzahl erlaubter IDs */
int ziffern[10]; /* welche Ziffer wie oft vorhanden ist */

/*  stelle  : aktuelle Stelle (0-9, 10 = Test)
 *  anzahl: Anzahl unterschiedlicher Ziffern in aktueller Zahl 
 */
void doit(int stelle, int anzahl)
{
int i;

    if(stelle < 10)
    {
        /* nur Optimierung (Zeit) */
        if(anzahl < stelle - 1) return; 
        /*!stelle : start bei 1 an erster Stelle */        
        for(i = !stelle; i < 10; i++) 
        {
            ziffern[i]++;
            doit(stelle+1, anzahl + (ziffern[i] == 1));
            ziffern[i]--;
        }
    }
    else
    {
        /* wenn genau 1 Ziffer fehlt ist alles OK */
        if(anzahl == 9) summe++;
    }
}

int main(void)
{
    doit(0,0);
    printf("\nHallo : %i",summe);
    return 0;
}