Order 40 sticks

Question

We have 40 sticks of same widths but different heights. How many arrangements are there possible to put them next to each other so that when we look from right we see 10 sticks and when we look from left we again see exactly 10 sticks?

For example such an ordering is:

Black sticks are hidden, red sticks are the ones you can see when you look from left, the blue sticks are the ones you can see when you look from right and purple one(i.e. the longest one) is the one that can be see seen from both sides.

As test cases:

• If we had 3 sticks number of orderings to see 2 from left and 2 from right is 2
• If we had 5 sticks number of orderings to see 3 from left and 3 from right is 6
• If we had 10 sticks number of orderings to see 4 from left and 4 from right is 90720

Answer 1

PARI/GP, 80

f(n,v)=abs(sum(k=1,n-1,binomial(n-1,k)*stirling(k,v-1,1)*stirling(n-k-1,v-1,1)))

The number of visible sticks is also called Skyscraper Numbers, after the pencil/grid game. This code is based on (only slightly altered) the formula from OEIS A218531. I don't know much PARI, but I really don't think there's much to golf out here.

Test cases are all shown at ideone.com. The result for f(40,10) is:

192999500979320621703647808413866514749680

Answer 2

Python 3, 259 bytes

Not very happy with this.

import itertools as i
x=input().split()
y,k=x
y=int(y)
c=0
x=list(i.permutations(list(range(1,y+1))))
for s in x:
 t=d=0;l=s[::-1]
 for i in range(y):
  if max(s[:i+1])==s[i]:t+=1
 for i in range(y):
  if max(l[:i+1])==l[i]:d+=1
 if t==d==int(k):c+=1
print(c)

Example input and output:

10 4
90720

It generates all the possible combinations of the provided range, and then loops through them, checking each number in them to see if it equal to the maximum of the previous numbers. It then does the same backwards, and if the count forwards (t) = the count backwards (d) = the given view number (k) it's a valid one. It adds this to a counter (c) and prints that at the end.

Answer 3

R, 104

function(N,K)sum(sapply(combinat::permn(N),function(x)(z=function(i)sum(cummax(i)==i)==K)(x)&z(rev(x))))

De-golfed a little:

    function(N,K) {
      all_perm <- combinat::permn(N)
      can_see_K_from_left <- function(i)sum(cummax(i) == i) == K
      can_see_K_from_both <- function(x)can_see_K_from_left(x) &
                                        can_see_K_from_left(rev(x))
      return(sum(sapply(all_perm, can_see_K_from_both)))
    }

Answer 4

Pyth - 38 36 bytes

Basically a port of the R answer. Pretty slow, can't even complete 10, 4 online.

AGHQLlfqhS<bhT@bTUGlf!-,yTy_TH.pr1hG

The only things Pyth doesn't have are cummax and the == over vectors, but those only took a few bytes to implement.

Explanation and further golfing coming soon.

Try it here online.