[News]

News: Welcome to The Oktave Forum.

[bn vikram]

bn vikram

bn vikram

Show bn vikram's last posts.

Show general stats for bn vikram.

• 
• Newbie
• Karma: 2
• Posts: 2

Convention 1--- push 0---- pop
Consider the productions
S->AS/epsilon
A->1S0/epsilon
These productions can be used to generate a sequence of 1 & 0 such that no of 1s is always greater than 0. i.e push’s are greater than or equal to pops.
P(1) -------  for this we need only one (1S0) production hence 1 way
P(2) -------  in this case we need 2 (1S0) production which can be arranged in 2 ways
  1S0 1S0
The second 1S0 production can be replaced for the first S
11S00
Hence 2 ways
P(3) -------
In this case we need 3 (1S0) productions which can be used in the following ways
1S0 1S0 1S0  ----- 1 way
11S00 1S0  ------- using the second production for the first S. this forms the p(2) case which can be done in p(2) ways.
1(1S0)(1S0)0  ------ arranging the other 2 productions within the first production again in p(2) ways
111S000  ------ replacing the first S by 2nd production and resulting S with 3rd production.---- 1 way
Hence totally 2*p(2)+1 ways
This holds good for n
i.e
p(n)=2*p(n-1)+1

[sri]

sri

sri

Show sri's last posts.

Show general stats for sri.

• 
• Administrator
• Sr. Member
• Karma: 7
• Posts: 264

*applause* 

Interesting approach! The CFG looks fine. But the number of 1s should not be greater than the 0s. A 0 should have a corresponding 1 before it in the stack. The stack itself is empty once the permutation is formed.

I've not checked the validity of the final answer, but the approach looks correct though..

[llabhilash]

llabhilash

llabhilash

Show llabhilash's last posts.

Show general stats for llabhilash.

• 
• Newbie
• Karma: -2
• Posts: 11

Since, there cannot be more pops than pushes at anytime and atmost equal.. wouldn't it be a catalan number ?

so for n elements, no. of permutations = (2n)! / ( (n+1)! * n! )

[sri]

sri

sri

Show sri's last posts.

Show general stats for sri.

• 
• Administrator
• Sr. Member
• Karma: 7
• Posts: 264

Not really interested in what it is called but in how you get to that (or any other) formula..