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)

2
votes
3answers
17 views

If $n_{1}+n_{2}+n_{3}+n_{4}+n_{5} = 20.$ Then number of such distinct arrangements of $(n_{1},n_{2},n_{3},n_{4},n_{5})$

Let $n_{1}<n_{2}<n_{3}<n_{4}<n_{5}$ be the positive integers such that $n_{1}+n_{2}+n_{3}+n_{4}+n_{5} = 20$ Then number of such distinct arrangements of ...
1
vote
1answer
26 views

How many $3$-tuples $(a, b, c) \in M^3$ are there such $a+b+c$ is even?

The task is the following: $M= \left \{ 1,2, ... 99,100 \right \}$ How many $3$-tuples $(a, b, c) \in M^3$ are there such $a+b+c$ is even? I tried to solve it this way: There are only two ...
1
vote
0answers
44 views

What is so special about Higman's Lemma?

Is there a motivational example of Higman's Lemma that brings out the true beauty and importance of Higman's Lemma? What is the thing that made so many people care about it? For an example, I was ...
0
votes
1answer
42 views

When is the order important in Combinatorics?

In a shop five different type of chocolates are sold. How many different ways 6 chocolate bars can be chosen in such a way that at least 3 chocolate bars must be of type one and at most one of type ...
0
votes
0answers
32 views

Here is a question on combinatorics [on hold]

here are ten items on sale at a bazaar, each costing less than one dollar. Prove that it is possible for two people to purchase distinct subsets of these objects and pay exactly the same amount. (Not ...
0
votes
0answers
10 views

Bounding entries of random vector

Given a random vector $\mathbf{e} \in \mathbb{R}^n$, is it possible to count (or bound) the number of entries in $\mathbf{e}$ that have $|e_i| \ge 1/ \sqrt{n}$? It is known that entries in ...
1
vote
1answer
109 views

Covering board with pieces

Suppose we have board, of size (16x16) And 31 (1x4) + 33 (2x2) pieces. Is it possible to cover up board with those pieces, if so - how? If not - why? So far I was unable to think of anything ...
6
votes
0answers
23 views

Chromatic Number of Circulant Graph

Consider the Circulant Graph $Ci_{2n}(1,n-1,n)$ as described here: http://mathworld.wolfram.com/MusicalGraph.html Another way to describe $Ci_{2n}(1,n-1,n)$ would be $2n$ vertices with vertex set ...
1
vote
2answers
33 views

$6$ real numbers, sum of any $3$ consecutive is negative, while sum of any $4$ consecutive is positive. Prove false. [on hold]

It's from my combinatorics class, could anyone give me some hints? Thanks Sorry, I shortened the original phrasing of the question, which made it ambiguous here. The question goes: A computer ...
0
votes
0answers
7 views

Families of 3-element subsets such that no two intersect more than once

Another user asked the following question: "How can I determine the size of the largest collection of $k$-element subsets of an $n$-element set such that each pair of subsets has at most $m$ elements ...
0
votes
0answers
16 views

Number of ways of selecting a submatrix?

Given a matrix $N \times M$ and a point $(x,y)$ then in how many ways can you select a submatrix such that the point lies inside the submatrix ?
0
votes
2answers
21 views

Permutations with repeated item [on hold]

I have: Orange Apple Orange Guava Pineapple Watermelon Strawberry Note the repeated Orange. Out of these 7, I have to choose 4 fruits. How many permutations are possible?
1
vote
0answers
23 views

equal unions and intersections

Let $N$ be a $n$-element set and $k\ge n+2$. The sets $P_1,\dots,P_k$ are nonempty and their union equals $N$. Then there exists disjoint sets $I,J\subset\{1,\dots,k\}$ such that $\bigcup_{i\in ...
2
votes
0answers
35 views

Coupon Collectors Problem with Packets (and Subsets)

The Coupon Collector's Problem (CCP) is very useful in many applications. However, the "default" CCP is relatively simple: suppose you have a urn containing $n$ pairwise different balls. Now you want ...
3
votes
4answers
75 views

Given that $6$ men and $6$ women are divided into pairs, what is the probability that none of the women will sit with a man?

I've generalized the question I was given here for simplicity: $6$ men and $6$ women are to be paired for a bus trip. If the pairings are done randomly, what's the probability that no women will end ...
-1
votes
0answers
17 views

Confusing Conditional Probability question 68 [on hold]

The four top tennis players in the world A, B, C, and D are invited to a special tournament where the winner gets one million dollars. In round one, Player A plays player D and player B plays player ...
3
votes
4answers
75 views

Prove the formula $\sum_{k=1}^n k\binom{n}{k} = n \cdot 2^{n-1}$ for all integers $n > 0$ [duplicate]

I just got to this question and I became a question mark. I wonder if anyone can help me with this one, because I don't even know how to begin to tackle this problem. The question: Prove the ...
2
votes
1answer
48 views

In how many ways can $8$ appointments be scheduled for a physician visiting a nursing home with $20$ patients? [on hold]

A physician routinely visits a local nursing home on Thursday mornings to examine patients. Suppose the facility has $20$ residents, but the physician only has time to check $8$. The supervisor places ...
0
votes
0answers
3 views

Counting subgraphs of bounded extremal degrees

Let $m\leq n-1$. Is there a closed expression counting the subgraphs of minimum degree $\geq m$ (resp. maximum degree $\geq m$) on $n$ labelled vertices?
0
votes
1answer
40 views

Finding a closed formula for: $1\cdot2\cdot3+2\cdot3\cdot4+…+(n-2)\cdot(n-1)\cdot(n)$ [duplicate]

As I calculated the sum of the serie above doesn't exist(sum doesn't converge). How can I prove it using the double computing(combinatorical method)?
1
vote
1answer
30 views

How many ways to divide $n$ different pieces of chocolate in two non empty groups?

After the example I think that the order of the groups doesn't matter so ${(A),(B,C)}$ and $(B,C),(A)$ counted as $1$. Suppose we split $5$ chocolates into a group of size $1$ and a group of size of ...
-1
votes
5answers
79 views

Deck of Cards Stats Probability Question [on hold]

Randomly select two cards in sequence from a full deck of 52 cards, what i s the probability that the first one is a King given that the second one is a King. If someone can please help me with this ...
2
votes
0answers
26 views

Distribution of distinct object problem

So i was given this question. How many ways are there to place 10 distinct people within 3 distinct rooms with exactly 5 people in the first room and 2 people in the second room? So i asked this ...
0
votes
1answer
17 views

Summation of all j-combinations (Expanding composition formula)

I found a formula for a problem that I was trying to solve, the Formula 3.2 in Section 3 at page 441 of this document.I am a little unsure about the "Summation over all j-combinations". Here is what I ...
2
votes
0answers
29 views

Generating subsets with 1 common element

I have a number $n$ and a set $S$ of $n(n-1)/2$ elements : $ \{1, 2, \ldots, n(n-1)/2\}$ I'm looking for an algorithm to generate $n$ distinct subsets of $S$, each having $n-1$ elements, with the ...
2
votes
1answer
20 views

How do you calculate the width of the Poset Lattice of Divisors?

Let $n = 10800 = 2^43^35^2$ I can find a set of eleven divisors of $n$ such that none divides another: $$\begin{array}{ccccc} & & & 2 3^3 & 3^35\\ & & 2^23^2 & ...
4
votes
3answers
221 views

How many solutions for equation with simple restrictions

I'm working on an assignment in which I have to count the number of solutions for this particular equation: $$x_1+x_2+x_3+x_4=20$$for non negative integers with $x_1<8 $ and $x_2<6$ I'm aware ...
3
votes
1answer
59 views

Number of 'walks' which stay above 0.

Consider a set of distinct $n$ numbers where $a_i \in \mathbb{R} $ and $$\sum_{i=1}^{n} a_i = 0$$ A walk is defined to be the sum of the numbers, so that the $k$th position is the partial sum to $k$. ...
0
votes
2answers
46 views

How many 10-digit decimal sequences (using 0, 1, 2, . . . , 9) are there in which digits 3, 4, 5, 6 all appear?

So i was given this question. How many 10-digit decimal sequences (using 0, 1, 2, . . . , 9) are there in which digits 3, 4, 5, 6 all appear? My solution below (not sure if correct) Let $A_i$ = set ...
5
votes
2answers
35 views

solve for variable in combination

i have the combination ${n\choose 11}=12376$ and am looking to solve for $n$. it turns out to be $17$. of course can use brute force approach where just plug numbers in for $n$ but am looking for a ...
-1
votes
2answers
39 views

What is the probability that when a deck of cards is shuffled and dealt, exactly 3 of the 4 aces will be dealt within the last 20 cards? [on hold]

I am trying to figure out this problem, I think that it is a "permutations with repetition" type of question.
1
vote
2answers
34 views

Number of ways of selecting 3 numbers from $\{1,2,3,\cdots,3n\}$ such that the sum is divisible by 3

Find the Number of ways of selecting 3 numbers from $\{1,2,3,\cdots,3n\}$ such that the sum is divisible by 3. (Numbers are selected without replacement). I made a list like this: The sum of ...
1
vote
1answer
36 views

Give a recursion for the number h(n) of strings in S of length n.

Let S be the set of strings on the alphabet {0,1,2,3} that do not contain 12 or 20 as a substring. Solving this I got: $$ h(n) = 4h(n-1) - 2h(n-2)$$ with $h(0) = 1, h(1) = 4,h(2) = 14 $. When I did ...
3
votes
1answer
26 views

Probability: Finding the Number of Pears Given Two Scenarios

You have a bag containing 20 apples, 10 oranges, and an unknown number of pears. If the probability that you select 2 apples and 2 oranges is equal to the probability that you select 1 apple, 1 ...
1
vote
1answer
48 views

How many ways are there to place 10 distinct people within 3 distinct rooms with exactly 5 people in the first room and 2 people in the second room?

So I was given this question. How many ways are there to place $10$ distinct people within $3$ distinct rooms with exactly $5$ people in the first room and $2$ people in the second room? I have ...
0
votes
0answers
28 views

Looking for mathematical/combinatorial and computational explanation regarding adding values in a $5 \times 4$ (matrix?) with a constraint.

Given the following matrix (not sure if I should call it that): Matrix $5 \times 4$ I want to add all possible combinations of values such that each Horse gets but one value from each Bookie. What I ...
-1
votes
2answers
54 views

Number of words of length $n$ on the alphabet $a,b,c$ recurrence. [on hold]

Let $a_{n}$ be the number of words of length $n$ on the alphabet $a,b,c$ such that $b,c$ are not adjacent. What is the recurrence relation for $a_{n}$.
1
vote
0answers
22 views

Small tree containing smaller trees

Given $n$, what is the smallest number $N=N(n)$ with the property that there exists a tree on $N$ (unlabelled) vertices that contains a copy of every tree on $n$ vertices? That such $N$ must exist is ...
1
vote
2answers
81 views

Find the recursive definition for the number of strings on 0, 1, 2 avoiding the substring 012?

This is the question $a(n)$ the number of strings on $0, 1, 2$ avoiding the substring $012$ and the answer is $$a(n)=3a(n−1)−a(n−3)$$ with $$a(0)=1,a(1)=3,a(2)=9$$ My question is how to you get this ...
2
votes
3answers
55 views

Abstract Combinatorics

In a library there is a sequence of $n$ books. There is someone that never wants to take books that are neighborhoods of each other. How many possibilities are there, for him, to take $k\le n$ books? ...
1
vote
3answers
62 views

How many different integer solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 21$ with restrictions

So i was Given this question. How many different integer solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 21$ $0 \leq x_i \leq 9$? I just assumed it would be ${21+4-4-1 \choose ...
2
votes
2answers
20 views

Why use C(n,r) instead of P(n,r) when considering how many strings can be formed in which a specific letter appears before another specific letter?

I am dealing with a problem in which I must determine how many strings can be formed by ordering the letters ABCDE subject to the conditions given. The condition that I am given is that A appears ...
3
votes
0answers
24 views

Extremal set theory problem concerning translations of a set of integers

Let $A$ be a subset of $B = \{1, 2,\ldots,n\}$. Suppose that $F$ is a family of subsets of $B$, each of which is a translation of $A$ and no two of which intersect more than once. What is the maximum ...
0
votes
2answers
43 views

Combinatorics president and votes

There are 5 candidates for presidency and 11 people that can vote at most one of them (so they can decide not to vote). How many combinations of votes are there if no candidate can recieve more than 5 ...
0
votes
1answer
22 views

Expanding Restricted Compositions formula

I recently started to look into restricted compositions and I found a formula for a problem that I was trying to solve, the Formula E at page 441 of this document. In my case I have n =8, k=3, t=1 ...
1
vote
2answers
51 views

Proof $\dbinom{n}{0} - \frac{1}{2}\dbinom{n}{1} + \cdots + (-1)^n\frac{1}{2^{n-1}}\dbinom{n}{n-1}$

For all $n \ge 1$, $$\binom{n}{0} - \frac{1}{2}\binom{n}{1} + \frac{1}{2^2}\binom{n}{2} - \frac{1}{2^3}\binom{n}{3} + \cdots + (-1)^n\frac{1}{2^{n-1}}\binom{n}{n-1} = 0,$$ if $n$ is even               ...
1
vote
0answers
7 views

Number of translated cubes covering a given hypercube in $\mathbb{R}^n$

Let $\Omega \subset \mathbb{R}^n$ be open and bounded, and let $Q \subset \Omega$ be a hypercube. Furthermore, denote by $D$ the $n$-dimensional unit cube $(0,1)^n$. Let $k \in \mathbb{N}$ be big, ...
-5
votes
2answers
75 views

Given any 40 people, at least four of them were born in the same month of the year [on hold]

Given any 40 people, at least four of them were born in the same month of the year. Why is this true?
1
vote
5answers
63 views

Proof $x$, $1+nx≤ (1+x)^n$ [on hold]

Prof using the binomial theorem: for all integers $n ≥0$ and for all nonnegative real numbers $x$, $1+nx ≤(1+x)^n$. Don't have a idea to start this one. I don't know how to use math induction yet, ...
2
votes
0answers
67 views

Counting integers from $1$ to $n$ with an odd number of divisors in {1,2,3,…,k}

Question Given $n,k$ find the number of integers between $1$ and $n$ that have odd number of divisors in {1,2,3,...,k} Example If $n=10$ and $k=3$, the numbers $1(1),5(1),6(1,2,3),7(1)$ have odd ...