combinatorics

1. Combinatorics Question

I came across a problem that is asking me to show that if a directed graph possesses a directed Euler Cycle, then it must be a strongly connected graph. I know that a directed graph that is strongly connected it has paths from x-y and y-x and that a Euler Cycle is a cycle that traverses all...
2. Combinatorics Question

There wasn't a separate forum for this subject so i posted it here with hopes of someone being able to help me out. I am currently working on a problem set and i am working on looking at graphs and identifying if they are planar or not. I read through the chapter and no where did it state...
3. Perfect Square combinatorics proof

Hello again! My question reads: If n is a positive integer and n > 1, prove that C(n,2) + C(n-1,2) is a perfect square. Anyway, I went ahead and simplified the statement, which brought it to this: n^2 - 2n + 1 In this form, it's fairly obvious that for any selected value of an integer n...
4. Help with combinatorics problem

Hi I would appreciate if someone could explain how to solve the following problem: "How many different five letter "words" can you write with the letters BILBANA" The answer is 690 but I'm not entirely sure how to get there. I divide the problem into different cases: A+B = 5...
5. Combinatorics Proof?

For positive integers n, r show that: C(n+r+1,r) = C(n+r,r) + C(n+r-1,r-1) + ... + C(n+2,2) + C(n+1,1) + C(n,0) = C(n+r,n) + C(n+r-1,n) + ... + C(n+2,n) + C(n+1,n) + C(n,n) Now, I've tried expanding the combinations, and I was able to get (n!) in the denominator of every term, though I'm not...
6. Combinatorics.

How many 4-digit nos. are there which begin with one and have exactly two identical digits? egs. are (1557,1030,1231) pls. do give the method applied as well.
7. combinatorics problem involving even numbers?

The problem is: How many even numbers greater than 40,000 may be formed using the digits 3, 4, 5, 6 and 9 if each digit must be used exactly once in each number? Like all combinatorics problems, I create five spots. The last spot must be used up by 4 or 6, b/c it's even, so we have _ _ _ _ 2...
8. Combinatorics problem

New to this forum, so sorry if this is in the wrong place! Anyway, this was in my Combinatorics final, but during the course we also introduced uses of Linear Algebra, Set Theory and Group theory in the field so it can be related to those as well. Question is attached below. It's easy to...
9. simple combinatorics

we have k students and n cars. How much possibilities do we have if we put every student in a car (we can have more then 1 student in the same car) 1. The cars are different: then k^n ways I think 2. the cars are identical: (k^n)/n! I think 3. We have more students then cars and in...
10. Tough Combinatorics

Given that m,n are positive numbers and given that A_1, A_2, \ldots, A_m \subseteq{\{1,2,\ldots,n\}} such that A_i \neq A_j for i \neq j. We know that \exists a constant L such that for every i\neq j: \sum_{x\in A_i \cap A_j}{x^3 = L} Prove m \leq n
11. Counting and Combinatorics

Q: How many solutions are there to: x1 + x2 + x3 + x4 +x5 = 50 for integers xi >= 1 What I've done: Rewrite as: (x1 - 2) + (x2 - 2) + (x3 - 2) + (x4 - 2) + (x5 - 2) = 40 My answer: The number of solutions is C(40 + 5 - 1 , 40 ) = 135751 The answer has been given as 130905. Any idea...
12. Combinatorics

This is the question. A computer has a password composed of 6 characters. The first 2 letters must be small letters, the rest can be either numbers or small letters. a) How many different passwords are possible? b) How many passwords are there that have no repeated characters?
13. Combinatorics?

There are two children C_1 and C_2. C_1 has 12 different toys and C_2 has 13 different toys. Find the number of ways in which C_1 and C_2 can exchange their toys in such a way that after exchanging they still have same number of toys but not the same set.
14. Functions and Combinatorics?

Let S = \{1,2,3,\mbox{...}, 10\}. If m is the number of ways of selecting p and q from the set S such that the function f(x) = \frac{x^3}{3} + \frac{p}{2}x^2 + qx + 10 is a one-one function and n is the number of ways of selecting p and q from the set S such that |p - q| < 4, determine the...
15. Combinatorics - show result?

If (n + 1) integers are chosen from integers 1,2,3,\mbox{...},2n, show that, among the chosen integers, there are two, such that one of them divides the other.
16. Combinatorics - n straight lines?

Out of n straight lines whose lengths are 1, 2, 3,...,n inches respectively. Prove that the number of ways in which four may be chosen which will form a quadrilateral in which a circle may be inscribed is \frac{1}{48}\{2n(n - 2)(2n - 5) - 3 + 3(-1)^n\}.
17. Combinatorics?

Prove that 6n identical objects of one type and 3 identical objects of another type can be arranged around a circle in 3n^2 + 3n + 1 ways.
18. Combinatorics?

It is a rule in Gaelic that no consonant or group of consonants can stand immediately between a strong and weak vowel;the strong vowels being a, o, u and the weak vowels being e and i. Find the number of Gaelic words of (n + 3) letters each, which can be formed of n consonants and the vowels...
19. Combinatorics

Suppose you are given a set of 100 distinct positive integers. Show that there exist four intergers {a,b,c,d,} in this set such that a-b+c-d|2009. Sixteen distinct integers are choosen between 1 and 30 inclusive. Show that you can always find a pair of integers(among these 16) such that their...
20. Need help with combinatorics

We were asked to prove that for any integer n sum of C(n,2r) for r >= 0 is equal to sum of C(n,2r-1) for r>= 1 where C(n,r) is choosing r objects from n objects.