For 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)

1
vote
1answer
43 views

Generating sets with exactly one mutual element

I have a quite interesting task. I need to generate all $n$-element sets, such that every two of them have exactly one mutual element. There are $m$ elements to choose from and can be assumed, that ...
1
vote
0answers
35 views

Wychoff's Game Combinatorics Problem

There are two piles of checkers on a table. A takes any number of checkers from one pile, or the same number from both piles. B does the same. The winner is the last one to take the checker. Positions ...
2
votes
1answer
43 views

Largest possible number of student passed in all three subject

Question: From $50$ students taking examination in Mathematics, Physics and Chemistry, $37$ passed in mathematics, $24$ passed in physics and $43$ passed in chemistry. At most $19$ students passed in ...
0
votes
4answers
36 views

no. of monomials in variables $w,x,y,\ldots,z$ of degree $m$

The formula for no. of monomials in variables $w,x,y,\ldots,z$ of degree $m$,$\,\,\,\,\,$ (where e.g. $x^iy^jz^k$ degree $m=i+j+k$) is: $\,\,\,\,\,$$\binom{m+n-1}{n-1}$ where $m$ is degree of ...
1
vote
3answers
44 views

Finding the expectation value of a random variable counting the occurrences of certain events

Let there be $M$ (distinguishable) boxes and $N$ balls, which we uniformly distribute among the boxes. For $k \leq N$, let $g_k: \Omega \rightarrow \mathbb{Z}$ be the function counting the number of ...
4
votes
2answers
32 views
3
votes
2answers
48 views

arrangement of the word $\bf{PERMUTATION}$ in which exactly $4$ letters in b/w $\bf{P}$ and $\bf{N}$

Total no. of arrangement of the word $\bf{PERMUTATION}$ in which there is there are exactly $4$ letters in between $\bf{P}$ and $\bf{N}$. $\underline{\bf{My\; Trial \; solution}}::$ Here we will ...
0
votes
2answers
37 views

proving counting problems?

Let n >= 1 be an integer. We consider passwords consisting of n characters, each character being a digit or a lowercase letter. A password must contain at least one digit. How do I show that the ...
2
votes
1answer
590 views

How many subsets does the set $\{1, 2, \dots , n\}$ have that contain no two consecutive integers if $1$ and $n$ also count as consecutive?

How many subsets does the set $\{1, 2, \dots , n\}$ have that contain no two consecutive integers if 1 and n also count as consecutive? It looks that the number of such subsets obeys the ...
13
votes
3answers
388 views

Show that $\sum_{k=0}^n\binom{2n}{2k}^{\!2}-\sum_{k=0}^{n-1}\binom{2n}{2k+1}^{\!2}=(-1)^n\binom{2n}{n}$

How can I prove the identity: $$ \sum_{k=0}^n\binom{2n}{2k}^2-\sum_{k=0}^{n-1}\binom{2n}{2k+1}^2=(-1)^n\binom{2n}{n}? $$ Maybe, can we expand $$ f(x)=(1+x)^{2n}? $$ Thank you.
1
vote
2answers
180 views

Present a combinatorial argument for the identiy $\sum^{n}_{k=1} k\binom{n}{k} = n\cdot 2^{n-1}$

This is a question in my textbook that does not provide a solution. Any help on a solution? Consider the following identity: $\sum^{n}_{k=1} k\binom{n}{k} = n\cdot 2^{n-1}$ Present a combinatorial ...
1
vote
1answer
35 views

The distribution of the sum of $k$ out of $n$ numbers

Given a list of numbers from $1$ to $n$, I select $k$ values at once (i.e. no duplicates). After summing them up, what is the most frequent value that I am likely to get? My intuition tells me that: ...
0
votes
3answers
42 views

Combinatorial problem - multisets

As I am solving some basic combinatorial problems today, I found out this problem: How many different 5-digit numbers can be formed from digits 2, 2, 7, 7, 9? Can someone guide me to a solution for ...
1
vote
1answer
83 views

$n$ Identical Balls Distributed Into $r$ Urns

Question In how many ways can at most $n$ identical balls be distributed into $r$ urns so that the $i$th urn contains at least $m_i$ balls, for each $i=1,...,r$? Assume that $n\geq \sum_{i= 1}^r ...
1
vote
2answers
175 views

How many ways can SLUMGULLION be arranged so all three L's precede all other consonants?

How many ways can the letters in the word SLUMGULLION be arranged so that the three L's precede all the other consonants. Attempt: There are 11 letters, and there are 3 Ls, 4 vowels: U U I O, and 4 ...
1
vote
5answers
105 views

With how many ways can we choose $9$ balls of a box?

With how many ways can we choose $9$ balls of a box that contains $12$ balls, of which $3$ are green, $3$ are white, $3$ are blue and $3$ are red? $$$$ I have done the following: $x_1=\# \text{ ...
1
vote
3answers
335 views

Choose 6 teachers out of 30, order doesn't matter

A school director must randomly select 6 teachers to participate in a training session. There are 30 teachers at the school. In how many different ways can these teachers be selected, if the order of ...
-1
votes
1answer
41 views

Checkboard coloring problem

If there are $q$ colors available and $n$ is odd, prove that there are $\frac14(q^{n^2}+2q^{(n^2+3)/4}+q^{(n^2+1)/2})$ distinct colored $n\times n$-chessboards. (Adjacent fields need not be ...
1
vote
1answer
34 views

Solving basic combinatorics

I started course in combinatorics and, as I'm still not much into it, I'm solving some basic problems to start with. So here is one of them: How many 5-digit positive integers are there such that 9 ...
0
votes
1answer
20 views

Proof an edge in a geometric graph

Suppose i take two random uniformly distributed points $X_{1},X_{2}$ in $[0,1]^{2}$. In addition i connect $X_{1}$ and $X_{2}$ by an edge if $||X_{1},X_{2}||_{\infty} \leq r$ where $0<r<1$ and ...
3
votes
1answer
125 views

Find all distinct binary de Bruijn sequences

Messing around with numbers has lead me to the following problem, which I am struggling with. (No, not a homework question, just a problem I've thought up myself): A binary De Bruijn sequence of ...
0
votes
2answers
34 views

Probability Question, Possible Inclusion/Exclusion?

The question is as follows: Given $x + y$ students in a class, and $r + s$ girls in the class, $x \geq r$. Randomly selecting $x$ students, what is the probability that exactly $r$ of the students ...
0
votes
1answer
36 views

Candy color + flavor probability question

This one is driving me nuts. Setup: "Your aunt brought you a bag of candy, but it's all mixed up! There are 6 yellow candies, of which 2 are sour and 4 are sweet. 5 blue candies of which 2 are ...
1
vote
0answers
43 views

The number of lattice triangle subdivision.

Let $L_{m,n} \subset \mathbb{R}^2$ be a rectangle given by $[m,0]\times[0,n]$ with $m,n$ positive integers. Define $N(m,n)$ to be the number of subdivisions of $L_{m,n}$ into lattice triangles of area ...
0
votes
5answers
81 views

A set with n elements has 2^n subsets

I don't understand why a set with n elements has 2^n subsets. How is this calculated? I realize that {123} has empty set - 1-2-3-1,2-1,3-2,3-1,2,3 but how is the formula derived?
0
votes
0answers
18 views

What is an optimal order for integer vectors for minimization of the total distances?

I want to find an optimal order for a number of vectors (or a permutation of vectors) to minimize the sum of distances regarding to the following norm: (this norm is based on the distance on a cycle ...
0
votes
2answers
56 views

Combinatorics problem on number of possible outcomes with constraints

We have 12 fish and 6 types. How many possible outcomes if at least 3 are of certain type. Ok, I reason as follows x1 + x2 + ... + x5 <= 9, and x6 >= 3 . But, now I do not know what to do because ...
2
votes
2answers
43 views

Permutation in PERMUTATIONS

In the word $PERMUTATIONS$.How many ways can I what is the number of permutation so that a vowel word must be between two consonants.a word can be used only for one time.
0
votes
1answer
34 views

Combinatorics counts outcomes, what mathematics lists outcomes?

Since I've been learning combinatorics the past few days I've constantly found myself wanting to implement the combinatorics I've learned in various ways(mostly by writing software that analizes each ...
0
votes
1answer
60 views

Combinatorics Question Help; # of ways to choose 4 distinct officials from a city?

there are $n \ge 4$ people in a city. And the city has its officials, consisting of 1 mayor and 3 vice-mayors. The entire board consists of 4 distinct students. Prove that by counting. In 2 different ...
1
vote
1answer
152 views

Prove this equality by using Newton's Binomial Theorem

Let $ n \ge 1 $ be an integer. Use newton's Binomial Theorem to argue that $$36^n -26^n = \sum_{k=1}^{n}\binom{n}{k}10^k\cdot26^{n-k}$$ I do not know how to make the LHS = RHS. I have tried ...
0
votes
2answers
96 views

Counting Problem Concerning the Stars and Bars Technique

I need to distribute $k$ indistinguishable balls to $n$ distinguishable bins. Of course, this is plainly an example where the so-called stars-and-bars technique is helpful: this technique yields an ...
0
votes
2answers
37 views

Combinatorics, how to pick X of one item, and Y of another out of Z total items?

Let's say I have several kinds of bricks. Red bricks, yellow bricks, and blue bricks. If I have infinite bricks, but am only selecting a group of 15 bricks, what is the chance I pick 7 red, 5 yellow, ...
2
votes
2answers
69 views

Number of permutations of thet set $\{1,2,…,n\}$ in which $k$ is never followed immediately by $k+1$

For $n \in \mathbb N$, let $C_n$ denote the number of permutations of the set $\{1,2,...,n\}$ in which k is never followed immediately by $k+1$ for each $k=1,2,...,n-1$ i) Find $C_n$ ii) Show that ...
-2
votes
2answers
107 views

Using Newton's binomial theorem to prove that a sum evaluates to $36^n-26^n$ [duplicate]

Using Newton's binomial theorem to argue that: $n \ge 1$ $$36^n - 26^n = \sum_{k=1}^{n}\binom{n}{k}10^k \cdot 26^{n-k}$$ my argument $$(26+10)^n = ...
1
vote
0answers
27 views

Probability of 6 teams winning an 8 team debating competition

My son is in a debating team that competes in an 8 team round robin competition. Each team every other team once, and the result is a win or a loss (no draws). This year 6 teams came equal first, ...
12
votes
1answer
261 views

Prove that $\exp(\log(\frac{1}{1-x})) = \frac{1}{1-x}$

I am trying to prove this directly by comparing the coefficients in the two series rather than using formal calculus. Here is what I have so far, but I think I made a mistake: \begin{align*} ...
1
vote
2answers
253 views

What is the probability that a random 6-digit number will have at least one 0, at least one 1, and at least one 2?

Hi this a question from my textbook: A first course in probability, It doesn't have the solution so I'm curious as to what the answer is. This is the question: What is the probability that a random ...
0
votes
0answers
31 views

maximizing a function involving factorial.

Can someone suggest a way to calculate the maximum with respect to $x \ge 1$ of: $$f(x)=\frac{1}{x!} \frac{1}{1-c^{1/\binom{x+n-1}{n-1}}}.$$ The constants $c$ and $n$ are parameters such that $c \in ...
1
vote
2answers
434 views

How many ways to seat 4 couple and 2 single around a round table

How many ways to seat 4 couple and 2 single around a round table, provided that each couple will sit together
0
votes
1answer
11 views

How many base-out configurations would be possible in sleazeball?

Problem: In a baseball there are 24 different "base out" configurations (runner on first - two outs, bases loaded- none out, and so on). Suppose that a new game, sleazeball, is played where there are ...
0
votes
1answer
31 views

Computing the maximum of a (Classic) function involving factorial

I'm trying to compute the global maximum (or an upper bound that does not depends on x) for the expression $$1/x!\binom{x+n-1}{x},$$ as a function of x. Where $n$ in a positive integer parameter. An ...
1
vote
0answers
43 views

Give a combinatorial proof [duplicate]

$$\sum_{k=1}^n k{n\choose k}=n\cdot 2^{n-1}$$ I have to prove the identity using a combinatorial proof: I think this should be my combinatorial proof. We want to form a committee of $k$ people from ...
1
vote
2answers
50 views

Is there a relationship between the clique of a graph and colouring of a graph?

Can one say that the minimum number of colours required to colour a graph (such that across any edge the two vertices have distinct colours) is lower bounded by the size of the maximum clique in the ...
0
votes
1answer
44 views

Distribute n balls across m bags when bags are not empty to get the same sizes

Thinking about the best solution of the next problem. Suppose we have m bags where $n_1, n_2, ..., n_m$ balls are already laid. We need to distribute new n balls across these bags to get almost the ...
1
vote
0answers
54 views

Is there a notation for repeated nCr?

I have a use for a repeating n choose r function. I have not been able to find any information about whether this exists already. If it does, what is the correct notation I should use? ((nCr)Cr)Cr... ...
2
votes
3answers
72 views

Number of subsets of A∪B that contain an odd number of elements

So I have a problem which defines two sets: $A = \{1,3,5\}$ and $B = \{ 1,2,3,4\}$. The question asks for the number of subsets of $A \cup B$ that contain an odd number of elements. I know the ...
0
votes
2answers
202 views

How many hamburgers can be ordered, if there can be eight toppings?

A fast food restaurant offers customer a choice of eight toppings that can be added to a hamburger. How many different hamburgers can be ordered? Attempt: I don't know if this is correct 8!? I think ...
2
votes
2answers
89 views

Expected number of people getting their own hat given that at least one of them gets his hat.

Suppose there are $N$ people at a party. Their hats get mixed and when leaving they grab a hat at random. Let $\displaystyle X_i=I(\text{$i$th person gets his own hat})$ and ...
0
votes
2answers
84 views

proving using pigeon hole principle

how would I prove this exercise: If we had five points in a square with sides of length one. How can we use the Pigeonhole Principle to prove that there are two of these points having distance at most ...