Qual è il problema NOVICE43 sul Judge Sphere Online (SPOJ) relativo ai numeri di Bell?

Question

Qual è il problema NOVICE43 sul Judge Sphere Online (SPOJ) relativo ai numeri di Bell?

#1 da (1 voti)

0

Dichiarazione di problemi:

When I first learned backtracking I made a program to find all the permutations of the English alphabets in lexicographically increasing. Filled with elation I showed the program to Rohil. Rohil being someone who likes to do stuff off the league was not impressed and gave me the following variation of the problem help me to solve the problem:

You have to find the number of permutations of length N(1<=N<=11) such that at whenever an alphabet (say 'c' ) appears in the permutation all the alphabets smaller than 'c' should have appeared before it at least once. An alphabet is smaller than another if it appears before the other in the English alphabet. ‘a’ being the smallest and ‘z’ being the largest. For example when N=2 then aa,ab are the only valid permutations and ba,bb is invalid since in ba all the alphabets smaller than b have not appeared at least once before it. See example for further clarification.

Input

Line 1: T(no. of test cases)

Line 2: n1

Line 3: n2

…

…

Output

Line 1: no. of such permutations of length n1

……

…..

Input: 2 2 3

Output: 2 5

Link al problema: NOVICE43

Ho letto alcune soluzioni online a questo problema e dicono che questo problema può essere risolto usando Numeri campanelli . Ma non sono in grado di decifrare la relazione tra i due. Qualcuno può spiegarlo?

data-structures algorithms math

posta Sourabh Khandelwal 02.03.2017 - 01:12

fonte

1 risposta

Leggi altre domande sui tag data-structures algorithms math

Uso di iFrame per evitare le stranezze di IE Esecuzione di una richiesta HTTP per una risposta senza un layout

score 1 · Accepted Answer

L'idea di base è che queste stringhe sono solo partizioni di un set. Se iniziamo ad esempio prendendo le due stringhe oltre 2 caratteri e elencandoli:

12
aa


12
ab

Possiamo iniziare a pensare ai caratteri come bucket in cui i numeri entrano. Quindi le stringhe assomigliano a

a: {1,2}
b: {}

a: {1}
b: {2}

E se dimentichiamo le etichette e ignoriamo le serie vuote, queste sembrano esattamente come le partizioni del set {1,2}, cioè

{{1,2}}

{{1},{2}}

Le restrizioni sull'ordine ci sono per assicurarci di non raddoppiare le partizioni, dato che ba rappresenta la stessa partizione di ab . (Esercizio: prova che questo è il caso.)

Quindi, poiché ogni stringa rappresenta una partizione univoca e l'insieme di tutte queste stringhe di lunghezza n rappresenta tutte le partizioni (senza ripetizione) di un insieme di dimensioni n, la dimensione di queste è la stessa. E la dimensione dell'insieme di partizioni di un insieme di dimensioni n è solo l'ennesimo numero di Bell.