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)

0
votes
0answers
5 views

Minimum elements present in {0, 1, 2, …, 225} to guarantee triple which sums to 225

Suppose I have the set: $$A=\{0, 1, 2, ... 224, 225\}$$ I want to find a triple that sums to $225$ (where a triple is a set of 3 unique values from the set). No Repetition Version: There are many ...
4
votes
2answers
21 views

Combinatorics problem with cars on a highway

There is a very long, straight highway with some number of cars (N) placed somewhere along it, randomly. The highway is only one lane, so the cars can’t pass each other. Each car is going in the same ...
1
vote
2answers
12 views

5-tuples of n integers

If n is a positive integer, how many 5-tuples of integers from 1 through n can be formed in which the elements of the 5-tuple are written in decreasing order but are not necessarily distinct? In other ...
0
votes
1answer
22 views

A coin is tossed $m+n$ times. Find the probability of getting atleast $m$ consecutive heads

A coin is tossed $m+n$ times. Find the probability of getting atleast $m$ consecutive heads I already know that the exact same question has already been answered here But I am trying to solve it ...
2
votes
1answer
29 views

In how many ways can we pick a group of 3 different numbers from the group $1, 2, 3, …, 500$ such that one number is the average of the other two?

Here's the question which I'm struggling with - In how many ways can we pick a group of 3 different numbers from the group $1, 2, 3, ..., 500$ such that one number is the average of the ...
0
votes
0answers
14 views

Squares Containing digits from Fibonacci Numbers

This is a problem that I thought of myself. Currently, the digits of $F_1$ through $F_n$ are written on the chalkboard in order, where ${F_n}$ is the Fibonacci Sequence and $n \ge 5$ We shall ...
4
votes
2answers
30 views

Pair of friends and a pair of “enemies” in each group of three students

The problem: There is a class. In each group of three students in the class there is a pair of friends and a pair of "enemies". Find the maximum number of students in the class. I tried to play with ...
0
votes
1answer
27 views

How many non-congruent triangles with perimeter 11 have integer side lengths? [on hold]

How many non-congruent triangles with perimeter 11 have integer side lengths? I failed to solve it. Can anyone help?
1
vote
2answers
24 views

Combinatorics: Does this method take into account every possible matchup

It's actually a question on finding the probability, but I am stuck on a different part of this question. There are $2^n$ players playing a tennis tournament. I have to find the total number of ways ...
0
votes
1answer
22 views

number of ways of arranging balls so that there are exactly two pairs of green balls

There are $5$ identical red balls and $6$ identical green balls. In how manys we can arrange them so that there are exactly two pairs of green balls. Let red balls be $R,R,R,R,R$ and green be ...
1
vote
0answers
37 views

How many ways to pick four increasing numbers from 1 through 39?

Say there's a bin of balls numbered 1 through 39, how many ways are there to pick 4 increasing numbers in a row? First I figured that it would be a permutation without repetition problem, so I got ...
2
votes
2answers
34 views

constrained stars and bars problem

I want to know number of solutions for following equation, where $r_k$'s are non-negative integers, and there is a constraint on $r_k$'s such that $r_1 \geq r_2 \geq \cdots \geq r_K$ \begin{equation} ...
0
votes
0answers
15 views

Small graphs containing all trees on $n$ vertices

What do those graphs look like which contain a copy of every tree on $n$ vertices and such that no proper subgraph has this property?
4
votes
2answers
106 views

What am I counting wrong?

EDIT: I made a mistake in the beginning, the second condition has changed. Sorry for this. I'm asked to count the number of sets of 4 elements that satisfy the two following conditions: 1) Each ...
-1
votes
0answers
26 views

Number of solutions of equation with natural numbers [on hold]

Given natural numbers $s, n, k$. How to find number of solutions to equation $a_1 + a_2 + \ldots + a_s = n-s$ where $0 \leq a_i \leq k-1$ and $a_i \in \mathbb{N}$?
0
votes
0answers
36 views

all but one sub-strings within a cyclic string

over $GF(q)$ where $q\in\mathbb{N}$, we build a string of size $q^n-1$. now, how can I show that it is impossible to construct that string so it contains all sub-strings of size $n$ exactly once, but ...
-1
votes
0answers
17 views

Onto functions from a set with 4 elements to a set with 3 elements [duplicate]

How many onto functions are there from a set with four elements to a set with three elements? If the four elements set is A = {a, b, c, d} and the three elements set is B = {u, v, x} I see these ...
1
vote
0answers
22 views

What is the probaility that two random permutations have same order?

I am interested in the orders of random permutations. Since the law of the log of the order of a permutation converges to a normal law (for instance Erdös-Turan Statistical group theory III), one ...
0
votes
2answers
26 views

equation to create unique value

I have a list of n objects say [ apple, orange, carrot, cherry, banana ] Now I am trying to come up with an equation which will generate an unique number for ...
3
votes
1answer
54 views

Product of sums into a sum of products

Any idea on how I can get an expression in the form of sum of products from the following one?: \begin{equation} \prod_{i=1}^M \left(\sum_{n=1}^i x_n\right) \end{equation}
1
vote
1answer
36 views

The probability of being dealt at least 5 wanted cards

In a fictional deck of cards, there are 30 cards, 15 different ones (each card has an identical pair, so 15 pairs = 30 cards). I want to answer the question: I am dealt 10 cards. I wish to receive 5 ...
5
votes
1answer
85 views

How to solve this hard sum problem?

$$\sum _{ x=1 }^{ \infty }{ \frac { 3{ x }^{ 2 }+12x+16 }{ { \left( x\left( x+1 \right) \left( x+2 \right) \left( x+3 \right) \left( x+4 \right) \right) }^{ 3 } } } =\frac { 1 }{ 4{ (a!) }^{ b } } ...
7
votes
2answers
98 views

Number of ways to partition $40$ balls with $4$ colors into $4$ baskets

Suppose there are $40$ balls with $10$ red, $10$ blue, $10$ green, and $10$ yellow. All balls with the same color are deemed identical. Now all balls are supposed to be put into $4$ identical baskets, ...
6
votes
2answers
85 views

Given the set $A=\{1,2,\dotsc,14\}$, find all subsets of $7$ elements that sum to a multiple of $7$.

I would appreciate if somebody could help me with the following problem. Given the set $A=\{1,2,\dotsc,14\}$, calculate the number of distinct sets $M \subset A$ such that $|M| = 7$ and such that ...
3
votes
2answers
58 views

Find number of ways to seat $n$ boys and $n$ girls in a row so that every boy has atleast one girl sitting beside him.

My attempt: I am getting $2^n(n!)^2$ . First I paired $n$ boys and $n$ girls in $n!$ ways then these pairs can be arranged in $n!$ ways and in each of these pairs boy and girl can arrange themselves ...
-1
votes
1answer
42 views

Why the Sum of all possible outcomes does not equal to one, in this case?

The question is an extension from an example (click this--> Introduction to Probability and Its Applications by Richard Scheaffer, Linda Young. The link points to the exact question/solution. Edit:- ...
1
vote
2answers
34 views

Binary Strings: How to determine if decomposition is ambiguous

Let's say I have the following decomposition: $$\{100,10011,00110\}^*$$ How would I determine if the decomposition is ambiguous or unambiguous?
0
votes
1answer
32 views

More intuitive way for solving this problem than using the multinomial theorem?

I'm the TA in a discrete math course and there was a problem in this weeks problem set which I had troubles solving. It goes like this: Find the coefficients of $v^2w^4xz$ in the expansion of $(3v + ...
0
votes
0answers
28 views

Using a combinatorical proof for recursion

I am having trouble understanding a combinatorial proof. I have a recursion, $$ a(n) = 2*a(n-1) - a(n-2) $$ And the combinatorial explanation (i.e., proof-light) is that $a(n)$ is just the count ...
1
vote
1answer
22 views

Need combinatorial formula

Let we have a forest $F_n(P)$ with $n$ nodes defined by set $P$ of all pairs $\{\text{father}, \text{son}\}$. For instance $P=\{\{1, 2\}, \{3, 4 \}, \{1, 3 \}\}$ defines a forest $F_5(P).$ Let ...
0
votes
1answer
23 views

Probability of drawing $m$ of $A$ in $n$ cards given a deck of $d$ cards contain $a$ copies of $A$?

As in the title I'm trying to work out what the chances of drawing $m$ copies of a specific card in $n$ draws are given a deck size of $d$ containing $a$ copies of $A$. I've tried using permutations ...
2
votes
2answers
33 views

Counting permutations with given condition

I need to find number of permutations $p$ of set $\lbrace 1,2,3, \ldots, n \rbrace$ such for all $i$ $p_{i+1} \neq p_i + 1$. I think that inclusion-exclusion principle would be useful. Let $A_k$ be ...
0
votes
1answer
34 views

In how many different ways can the gifts be given? [on hold]

For Valentine's Day $5$ children receive a total of $6$ different gifts. Each child receives at least one gift and each gift is given to exactly one child. In how many different ways can the gifts ...
1
vote
1answer
29 views

Show impossibility of a perfect covering

Problem: Show that a $8 \times 8$ chessboard cannot be perfectly covered by $1$ square tetramino, and 15 other tetraminoes chosen from straight tetraminoes and Z-tetraminoes. My attempt: I tried to ...
3
votes
1answer
21 views

How many teams can be formed?

I would like to calculate the number of choices of teams I can make in the following scenario. Suppose a team is comprised of 3 characters (1 leader and 2 support members) and suppose there are 108 ...
5
votes
3answers
38 views

Combinatorial argument for $\sum\limits_{k=i}^{n}\binom{n}{k}\binom{k}{i} = \binom{n}{i}2^{n-i}$

I need to show that $$\sum\limits_{k=i}^{n}\binom{n}{k}\binom{k}{i} = \binom{n}{i}2^{n-i}$$ I know that $\displaystyle \binom{n}{k}\binom{k}{i}$ is counting the number of ways to pick $k$ elements ...
2
votes
1answer
35 views

Probability of an array having all distinct numbers

Suppose you have an array of size $2n$. There are two times $2n^2$ distinct numbers that can be put into the array without replacement, i.e. for each choice of number, there are two copies, so a ...
1
vote
1answer
18 views

Number of permutations of $S_n$ such that $\sigma^h(a) = \sigma^k(b)$

A basic result in combinatorics is: In $S_n$ there are $(n-d)(n-2)!$ permutations $\sigma$ such that $\sigma^k(a) = b$, if $a \neq b$; $d(n-1)!$ permutations $\sigma$ such that ...
1
vote
1answer
20 views

How many options are there to award gold, silver, and bronze medals to a group of $10$ athletes?

How many options are there to award gold, silver, and bronze medals to a group of $10$ athletes? Is this permutation or combination, and is there repetition? I thought this would be a combination ...
1
vote
0answers
42 views

Estimates for the Dedekind number $M(9)$

The Dedekind number $M(n)$ is the number of antichains in the partial order of subsets of $\{1,\dotsc,n\}$. It is only known for $0 \leq n \leq 8$. Question. What are some known upper and lower ...
5
votes
1answer
45 views

Number of $n$-digit permutations with exactly $n-2$ digits smaller than the next

How many permutations of $1,2,\cdots, n$ contain exactly $n-2$ digits that are smaller than the digit immediately to their right? My solution proceeded with recursion. It has some chance of being ...
1
vote
0answers
26 views

Possible closed form or approximation?

Does it have some closed form or approximation ? I tried on my own but i am not getting any idea regarding this. $$\sum_{k_1=k}^{M}\sum_{k_2=k}^{M}\frac{k_1^{-\gamma} k_2^{-\gamma} ...
-1
votes
1answer
38 views

The number of ways to divide 10 people into groups of given size [on hold]

Find the number of ways in which $10$ people can be divided into $2$ groups consisting of $7$ and $3$ people Three groups consisting of $4$, $3$ and $2$ people with $1$ person rejected. $5$ groups ...
3
votes
1answer
41 views
+50

Find the maximum number of people who participated in exactly three games?

Gauri Apartment housing society organised annual games, consisting of three games: snooker, badminton and tennis. In all, $510$ people were members in the apartments' society and they were ...
2
votes
2answers
42 views

In how many ways can a committee of $6$ people be selected from $7$ men and $6$ women if it can contain at most one of persons A and B?

A committee of $6$ people will be formed with $7$ men and $6$ women. The oldest of the $7$ men is A and the oldest of the $6$ women is B. It is described that the committee can include at most one of ...
2
votes
2answers
47 views

Solving the recurrence $A_n = \sum_{k=1}^{n} 2^{k+1} A_{n-k}$

Let me ask a very simple question: Let $(A_n)$ be a sequence of integers defined by $A_0 = 1$ and $$\forall n \geq 1 : A_n = \sum_{k=1}^{n} 2^{k+1} \cdot A_{n-k}.$$ There is an explicit formula for ...
0
votes
0answers
19 views

Use probabilistic method to show existence of a particular subset

Suppose that a $2m \times 2m, m \geq 4$ table is populated with numbers $1, 2..., 2m^2$ (i.e. each number appear exactly twice). Show that there exists a selection of $2m$ cells such that the ...
0
votes
1answer
32 views

Counting the frequency of a flush hand in $7$-card poker

I'm trying to count the frequency of a flush hand in $7$-card poker. Since a flush hand could be thought of as having $5$ cards with the same suit while the other $2$ doesn't matter, I wrote down as ...
0
votes
0answers
61 views

Order-Preserving Bijection $f:A\to A^*$?

Let $A$ be a well-quasi-ordered infnite set. Does there exist an order-preserving bijection $f:A\to A^*$, where $A^*$ is the free monoid over $A$ under the subword ordering? Would this subword ...
0
votes
2answers
22 views

Probability; bridge hand question

$13$ cards are chosen at random with no replacement from a deck of $52$ cards. find the probability there are $5$ spades chosen, $4$ hearts, $3$ diamonds and $1$ club. I got ...