CODEWITHSUNDEEP
algorithmmathpuzzle
Bob Napkin
Bob Napkin

Reputation: 566

Number of ways of taking `N` candies

I have a problem and I don't know how I can start to solve it. Do you know someone a formula, algorithm or type of problems like this?

I have only number N, N candies, and I need to count the number of ways of taking N candies, but except the first candy taken, the candy taken must be adjacent to one of previous candies taken before. For example if N = 3 there are 4 ways of taking:

Upvotes: 1

Views: 626

Answers (6)

Douglas Zare
Douglas Zare

Reputation: 3316

You don't need to go through binomial coefficients.

There are 2^(n-1) sequences of Rs and Ls of length n-1. These are in bijection with the sequences of taking candies by writing down whether your next candy is on the right or left of the ones you have taken before. Any sequence of Rs and Ls uniquely determines the location of the first candy: If there are a Ls, then the first candy must be in position a+1.

Upvotes: 1

user2512323
user2512323

Reputation:

Let's say we first take i-th candy. Then we have i - 1 candies to the left and N - i to the right. Every next candy taken is the rightmost from the left part, or leftmost from the right part. Left and right parts are independent, so number of possible ways to take all candies are number of unique permutations of the sequence LLLL....LLLRRR....RRR where i - 1 L's and N - i R's.

Total number of such permutations is:

SequenceLength!/(count(L)!*count(R)!) = (N - 1)!/((i - 1)! * (N - i)!)

Now, if we sum over all possible i values, we have:

formula

Upvotes: 1

Paul Hankin
Paul Hankin

Reputation: 58339

If you take candy k first, then there's choose(n-1, k-1) ways of choosing the rest (where choose(n, k) is the binomial coefficient nCk). That's because after the first, you either have to take the right-most unchosen candy to the left of k, or the left-most unchosen candy to the right of k, and there's (k-1) candies to the left of k.

Summing over k, gives you all possible ways taking into account the first choice: sum(k=1...n)choose(n-1, k-1).

Since choose(n-1, k-1) is the number of ways of choosing k-1 items from n-1 items, this sum is equal to the number of ways of choosing any number of items from n-1 items. That's 2^(n-1).

Upvotes: 2

Viko Riféo
Viko Riféo

Reputation: 119

Another implementation, probably more useful in theory:

Given a 1-indexed array C of candy marbles (1 for not yet taken and 0 for taken, all starting at 1) and a starting point N:

  1. If N is negative, zero, or greater than the size of C, end without doing anything.
  2. If C[N] is 0, end without doing anything.
  3. If C[N] is 1, set it to 0, add 1 to the count of possible paths, then check C[N-1] and C[N+1] against this algorithm.

Simply repeat this algorithm for every valid index in C. Also, ensure each recursion has a copy of C, not the original C, but they all share the total number of paths.

Stepping through the first part of your example:

  1. C[1] is 1, so we set it to 0, add 1, and check C[0] and C[2].
  2. 0 is 0, so we stop that recursion.
  3. C[2] is 1, so we set it to 0 and check C[1] and C[3].
  4. C[1] is 0.
  5. C[3] is 1, so we set it to 0 and checkC[2]andC[4]`.
  6. C[2] is 0.
  7. 4 is greater than 3.

Repeat for N=2 and N=3, and for longer arrays just loop.

Upvotes: 0

C8H10N4O2
C8H10N4O2

Reputation: 19005

Look at the pattern:

number of candies
1   2   3   4
1   12  123 1234
    21  213 2134
        231 2314
        321 2341
            3214
            3241
            3421
            4321
1   2   4   8
total ways

Does this remind you of something?

Upvotes: 1

roippi
roippi

Reputation: 25974

The number of ways for n candies is the sum of the n-1th row of pascal's triangle.

Upvotes: 3

Related Questions