Problem Statement : 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.InputLine 1: T(no. of test cases)Line 2: n1Line 3: n2OutputLine 1: no. of such permutations of length n1..Input: 2 2 3Output: 2 5Link to the problem : NOVICE43 I have read some online solutions to this problem and they say this problem can be solved using Bell Numbers. But Iam unable to decipher the relation between the two. Can anyone explain it?
How is the problem NOVICE43 on Sphere Online Judge(SPOJ) related to Bell Numbers?
algorithms;data structures;math
The basic idea is that these strings just are partitions of a set. If we start for example by taking the two strings over 2 characters and enumerating them:12aa12abWe can start thinking of characters as buckets that the numbers go in. So the strings look likea: {1,2}b: {}a: {1}b: {2}And if we forget the labels and ignore empty sets these look exactly like partitions of the set {1,2}, namely {{1,2}}{{1},{2}}The restrictions on ordering are there to make sure we don't double count partitions, as ba represents the same partition as ab. (Exercise: prove that this is the case.)So since each string represents a unique partition and the set of all such strings of length n represents all partitions (without repitition) of a set of size n, the size of these are the same. And the size of the set of partitions of a set of size n is just the nth Bell's number.