This tag is for basic questions about the study of finite or countable discrete structures — specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions. ...

learn more… | top users | synonyms (4)

0
votes
0answers
30 views

Inequality involving Double factorials

I need to prove that: \begin{align} &k \sum_{a_1=k-2}^{n-1} \sum_{a_2=k-3}^{a_1-1} \cdots \sum_{a_{k-2}=1}^{a_{k-3}-1} {n \choose a_1} {a_1 \choose a_2} \cdots {a_{k-3} \choose a_{k-2}} ...
1
vote
2answers
142 views

How many committees of five contain at least one African and one European?

A council consists of three Europeans, four Americans, three Asians, and five Africans. How many committees of five contain at least one African and one European?
0
votes
1answer
64 views

Is there any way to generalise this problem?

My friend posed this question to me: I have a glass with 8 litres of water along with one empty 3 litre and an empty 5 litre glass. I have to pour 4 litres of water into his glass in one go. His ...
0
votes
0answers
26 views

combinatorics help [ don't know the name] [duplicate]

I have the question http://vvcap.net/db/Vf40MqXNBppl-4dXyuy0.htp I've worked it out and got the answer 462. However, i was told because we include an empty set at the beginning, i -1 from my answer. ...
1
vote
0answers
27 views

Mean vs. Median nearest-neighbor spacing

We have a density of points $n = \frac{points}{volume}$ in a $d$-dimensional space. An analysis of the points indicates that, to the best of your knowledge, they are distributed randomly via a ...
0
votes
1answer
35 views

How to show that a one-dimensional subspace of $(\mathbb{Z}/2\mathbb{Z})^3$ is contained in exactly three two-dimensional subspaces?

Let $\mathbb{Z}/2\mathbb{Z}=\{0, 1\}$ be the two element field. We know that there are 8 vectors in $(\mathbb{Z}/2\mathbb{Z})^3$ given by $(a, b, c)$, $a, b, c \in \{0, 1\}$. There are $(8-1)/(2-1)=7$ ...
5
votes
1answer
97 views

How many tables which it's elements are 1 and -1?

I tried to solve this by induction but wasn't successful. Problem is: Determine the number of $(2^n -1) \times (2^n-1)$tables with 1 or -1 entries such that each entry is the product of ...
2
votes
0answers
163 views

Induction proof of a recurrence relation

I have some trouble with an induction proof for the following problem. There is a vending machine that only takes coins of value 1 and 5 respectively. Let $S_n$ be the number of different ...
0
votes
0answers
39 views

covering points on the circumference of the circle

Let $C$ be circumference of a circle. For a point $p\in C$, let $\mathcal{I}_p\subset C$ be an arc with angle $240^\circ$ with midpoint $p$. Let $\mathcal{A_{d^\circ}}$ be set of arcs of angle ...
1
vote
0answers
74 views

variation on the oddtown problem

Suppose we have a town with $n$ people who like to form clubs. They form clubs according to the following rules: For any two clubs $C_i,C_j$, $|C_i \cap C_j$| is a multiple of $3$ whenever $i \not = ...
0
votes
1answer
41 views

combinatorics help question, dont understand

I've got this maths question and i've no idea how to do it. http://vvcap.net/db/iCEsjpXBaSTQDmRI6eYz.htp The same question has been posted up on another forum, someone has given a solution, but i ...
11
votes
3answers
409 views

Reference for combinatorial game theory.

What is a good reference material for elementary combinatorial game theory? By combinatorial game theory I mean chiefly the study of zero-sum, deterministic two-player games (perhaps even more ...
0
votes
0answers
24 views

Tournament payouts, or more number partitioning/change-making

I was thinking of this when confronted with the problem of tournament payouts... Let's say I have \$100 to be parceled out to 10 different people, each of whom is due $n_1, n_2,..., n_{10}$ dollars. ...
5
votes
1answer
65 views

A Question on Digit Occurences

Here's a question I was thinking about: For all positive integers n, list the decimal representation of the numbers 1, 2, 3, ..., n without any leading zeroes. Does there exist an n such that this ...
14
votes
2answers
353 views

When is $\binom{n}{k}$ divisible by $n$?

Is there any way of determining if $\binom{n}{k} \equiv 0\pmod{n}$. Note that I am aware of the case when $n =p$ a prime. Other than that there does not seem to be any sort of pattern (I checked up ...
1
vote
2answers
43 views

Combinatorics homework question

The answer is 54912. This is what I've tried so far: So first you have to pick a rank to occur 3 times so thats 13, now you gotta pick a suit that that rank has, which is now 13 * 4. Now you need ...
2
votes
2answers
966 views

How many ways to seat 9 couple around a round table

You are a host/hostess at your local Applebee’s. You are seating a group consisting of 9 couples at a round table. A)In how many different ways can you do this, provided that each couple will sit ...
2
votes
1answer
127 views

Stirling numbers of second type [duplicate]

How can I do a combinatoric proof that for Stirling number of second type the equality if true: $${n\brace k} = \frac{1}{k!}\sum_{i=0}^{k}{k \choose i}i^n(-1)^{k-i}$$
1
vote
1answer
97 views

Bayes' theorem in practice

Question: What probability is that a person with a positive test is HIV+, when these facts apply: One person out of 1000 is HIV+. Test of a HIV+ person is always positive. Test of a HIV- person is ...
6
votes
1answer
87 views

walks on hypercubes

Let's say I start at the $(0,0,...,0)$ vertex of $n$-dimensional hypercube. After each unit of time $l$, I either stay where I am with probability $p$, or move to an adjacent vertice with probability ...
1
vote
1answer
613 views

Combinations for Screen lock For iPhone / Android

I was wondering if there was a general for formula to calculate the combination of the password lock for the current smart phones The following is the condition We must use four nodes or more to ...
1
vote
2answers
59 views

If There are four 2's three 1's and two 0's how many was can you arange them in a 9 Digit number!

If There are four 2's, three 1's and two 0's, in how many was can you arrange them in a 9 Digit number! Using Permutations only. Show your answer is corrrect by counting it in three different ways and ...
0
votes
1answer
31 views

Possible number of names from a certain alphabet

I am trying to solve the following problem, but I am a bit stuck. The question is as follows. The language of a certain island has only the letters A, B, C, D, E. Every place name must start and ...
1
vote
1answer
225 views

flower pot puzzle

Sara has 6 flower pots, each having a unique flower. Pots are arranged in an arbitrary sequence in a row. Sara rearranges the sequence each day but not two pots should be arranged adjacent to each ...
0
votes
1answer
47 views

A Combinatorial problem , matrix

I am trying to solve the following problem : Let A be a square matrix whose entries are zeroes and ones. It is allowed to put minus ones instead of ones . Prove that this can be done in such a way ...
1
vote
1answer
82 views

Palindrome problem

Let $F (n, k)$ be the number of length $n$ strings that can be formed using $k$ discrete digits. Let $G (n, k)$ be the number of length $n$ palindromic strings that can be formed using $k$ discrete ...
0
votes
1answer
185 views

Subsets that contain equal amounts of even and odd integers

Someone asked this question: Compute the number of subsets of a set $A := \{1,2,...,11\}$ that contain the same number of even and odd values, e.g. the subsets $\{\}$,$\{1,2,5,8\}$ and ...
0
votes
2answers
30 views

No. of even non-negative solutions of an equation involving $d$ variables

I want to know the number of non-negative solutions of the equation $x_1 + x_2 + \dots + x_d = 2n$ where each of $x_i$ is even.
3
votes
1answer
46 views

Number of ways of sorting distinct elements into 4 sets

This was on a test I just had. The first part says: "A person donates nine antique clocks to four different museums. Supposing all clocks are identical and he can distribute them in any way he ...
1
vote
0answers
28 views

Efficient evaluation of the inverse of a triangular matrix on a vector

I have this matrix that interests me. It arises when we try to express the norm of a $(p,p)$-form on an $n$-dimensional vector space in terms of (squares of) traces of the form with respect to the ...
1
vote
1answer
42 views

homework combinatorics carousel

I was asked this question in my homework: How many different combinations are there to paint a carousel with $n$ seats, in $r$ different colors, such that any combination that you can get via ...
2
votes
1answer
98 views

Counting techniques

I am preparing for an exam and I came across this problem. I am a little confused. Give the expression of ways to distribute 15 distinguishable balls into five distinguishable boxes so that the boxes ...
1
vote
2answers
59 views

Counting permutations

how many words, without making any reference to their meaning can be written from the letters: $ a,a,a,b,b,c,c,d$ ? what is the best approach to solve this kind of problem ?
1
vote
0answers
74 views

Combinatorics question about intersecting set systems

Prove that every intersecting set system $F \subset P(n)$ is contained in an intersecting set system of size $2^{n−1}$. I have that $F$ must be of size at most $2^{n-1}$. Not sure how to ...
0
votes
3answers
108 views

Homework - How many non negative solutions?

$a+b+c+d+e = 30$ we know that $10\leq e$ and that $4\leq d \leq 7$ How many non negative solutions does this equation have?
1
vote
3answers
60 views

Homework - combinatorics

How many solutions does this inequality have in non negative integers $x_i$: $n \leq x_1+x_2+x_3+ \dots +x_n \le 2n$ ? Im stumped I know I should add another variable but...I don't know.
0
votes
1answer
37 views

Maximal graph that does not contain Hamiltonian cycle

My lecture notes in Graph Theory states that a graph of order $n$ and with size (= number of edges) $\binom n 2-(n-2)$ is the maximal graph that does not contain a Hamiltonian cycle. My question now ...
0
votes
1answer
21 views

Homework - combinatorics cartesian plane

hopefully last combinatorics question for today...I can't handle this subject. Ok here is an interesting question Oria is standing at (0,0) and he needs to get to (a,b) $a,b >0$ a,b are integers. ...
1
vote
2answers
45 views

Multiplicative Inverse for Generating Function

I have a question based on Irreducible and Connected Permutations. I was able to use the notion of connected permutations to construct a combinatoric proof for \begin{equation} ...
1
vote
2answers
173 views

combinatorics: number of subsets containing the same number of odds and evens

Compute the number of subsets of set $A=\{1,2,\ldots,11\}$ that contain the same number of even and odd values, e.g. the subsets $\varnothing, \{1,2,5,8\}$ and $\{3,5,8,10\}$ should be counted, ...
3
votes
3answers
240 views

basic combinatorics question

Each person from a group of 3 people can choose his dish from a menu of 5 options. Knowing that each person eats only 1 dish what are the number of different orders the waiter can ask the chef?
14
votes
2answers
527 views

In how many ways we can place $N$ mutually non-attacking knights on an $M \times M$ chessboard?

Given $N,M$ with $1 \le M \le 6$ and $1\le N \le 36$. In how many ways we can place $N$ knights (mutually non-attacking) on an $M \times M$ chessboard? For example: $M = 2, N = 2$, ans $= 6$ $M = 3, ...
1
vote
3answers
103 views

Find the Coefficient of $x^{25}$ in…

Find the coefficient of $x^{25}$ in $(1+x^3+x^8)^{10}$ using ordinary generating functions? Could someone help me figure out this problem using generating functions? My initial thought was to using a ...
1
vote
2answers
175 views

France Olympiad Team Selection Test 2005

In an international meeting of n ≥ 3 participants, 14 languages are spoken. We know that: - Any 3 participants speak a common language. - No language is spoken by more than half of the participants. ...
1
vote
1answer
31 views

linear dependncy of a random vector with respect to a reduced row echelon form in a finite field

Given a matrix with elements from a finite field $\mathbb{F}_q$, $A\in\mathbb{F}_q^{N\times M}$, where $q$ is the size of the field, $N<M$. Suppose that $A$ in the reduced row echelon form. ...
0
votes
2answers
59 views

Chain of $m+1$ of anti-chain of $n+1$

Theorem: Given any poset of $mn+1$ elements, prove that there exists either a chain of length $m+1$ or an anti-chain of length $n+1$. I proved this with an ugly proof. Is there any proof using ...
4
votes
6answers
2k views

Arrangement of the word 'Success'

Number of ways the word 'Success' can be arranged, such that no two S's and C's are together.
1
vote
1answer
30 views

Combinatorics: complete set of solution to the congruence

$$111x \equiv 112 \bmod 113$$ I've tried all the theorems. The only thing I found is that there is only one solution. Other than trying all 1-113 possible values that x takes, is there any efficient ...
1
vote
4answers
316 views

Probability Problem on Divisibility of Sum by 3

From the 3-element subsets of $\{1, 2, 3, \ldots , 100\}$ (the set of the first 100 positive integers), a subset $(x, y, z)$ is picked randomly. What is the probability that $x + y + z$ is divisible ...
1
vote
0answers
18 views

Finding an orthonormal basis for a gl(3) module

I'm trying to find an orthonormal basis for gl(3)-module V(ε1-ε3), where ε1-ε3 is the weight (1,0,-1) of the highest-weight vector. Using Gelfand-Tsetlin (/Zetlin/Zeitlin) patterns, I'm at the point ...