An urn has N balls, each marked with an integer number from 1 to N. For each number in [1,N], there would be exactly one ball marked in the urn. If we randomly pick n balls with replacement from the urn, then we know that there would be N^n (N power n) possible ways of picking n balls. The question is, how many of such ways we’ll have at least one occurrence of c or more successive picks having consecutive increasing numbers?
Example:
For N=9 (range of numbering 1-9, also the number of balls in the urn is 9), n=7 (number of picks), and c=3(number of successive picks with consecutive increasing numbers)
Some of the sequences that are included for answer to this specific example:
i) 1,2,3,1,2,3,1 (2 occurrences of 3 consecutive numbers)
ii) 1,2,3,3,4,5,6 (1 occurrence of 3 consecutive numbers and 1 occurrence of 4 consecutive numbers)
iii) 8,9,9,9,4,5,6 (1 occurrence of 2 consecutive numbers and 1 occurrence of 3 consecutive numbers)
Some of the sequences that are NOT included for answer:
i) 1,2, 4,5, 7,8, 8 (3 occurrences of 2 consecutive numbers. We need at least one occurrence of c=3 or more consecutive numbers)
There are (n+1-c) possible locations for a c-sequence, there are (N+1-c) different c-sequences and N^(n-c) possibilities for the other numbers. However, cases with c-sequences in two locations have been counted twice, so we have to subtract these. Then cases with c-sequences in three locations must be added etc. Inclusion/exclusion is the name of this procedure. The formula is long but simple and for your example it gives the answer 210969.
Hello Sir.
I’m really thankful for your response and for pointing me to the right theory of exclusion-inclusion. I could solve this specific question. However, what I realize is that finding a generic expression is still difficult for this question. I’m left wondering now, if it is worth spending time to find a generic expression involving N, n, c etc. I would really appreciate your views on this.
Once again, thank you sir for your help.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Algebra