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
0answers
26 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
31 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
10 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
94 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
25 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}$?
-1
votes
0answers
16 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
18 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
23 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
50 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
28 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
79 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
76 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
81 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
54 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
40 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
33 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
30 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
26 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
27 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
41 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
42 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
25 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
37 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 ...
2
votes
2answers
38 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
46 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
31 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
59 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
21 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 ...
1
vote
1answer
12 views

Splitting $N$ Groups of Objects into $M$ bins

For simplicity, I'll give the example as splitting 3 bins of balls into 4 bins. Bin 1 contains $N_1$ blue balls, bin 2 $N_2$ red balls, and bin 3 $N_3$ green balls How many combinations of ways ...
3
votes
1answer
30 views

Combinatorics: How do you find the coefficient in the given expression?

The question asks me to find the coefficient of the term $x^6y^4$ in the expression $(xy^2+x^2+3y)^7$. This was pretty simple. This is how I did it: $$(xy^2+x^2+3y)^7 = \sum_{a+b+c = n} (xy^2)^a + ...
0
votes
1answer
12 views

Show that if a bipartite graph $G = (V, E)$ with bipartition $V = A \cup B$ is $k$-regular, then $|A| = |B|$.

A graph is $k$-regular if every vertex has degree $k$. Show that if a bipartite graph $G = (V, E)$ with bipartition $V = A \cup B$ is k-regular, then $|A| = |B|$. I dont understand it. Please explain ...
0
votes
3answers
27 views

How many different varieties of pizza can be made if you have the following choices:

How many different varieties of pizza can be made if you have the following choice: small medium, large; thin, hand tossed, pan; and $12$ toppings (cheese is an automatic), from which you may select ...
1
vote
3answers
23 views

Prove that the sequence of combinations contains an odd number of odd numbers

Let $n$ be an odd integer more than one. Prove that the sequence $$\binom{n}{1}, \binom{n}{2}, \ldots,\binom{n}{\frac{n-1}{2}}$$ contains an odd number of odd numbers. I tried writing out the ...
3
votes
2answers
97 views

Seeking non-inductive, combinatorial proof of the identity $1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n + 1)(2n + 1)}{6}$

How do you prove $$1^2 + 2^2 + 3^2 + \cdots + n^2 = \dfrac{n(n + 1)(2n + 1)}{6}$$ without induction? I'm looking for a combinatorial proof of this.
0
votes
0answers
16 views

Integer partitions with distinct parts

Let $~~p(n)~~$ denote the number of all partitions of positive integer $~~n~~$ with distinct parts. I would like to find some effective algorithm for calculating $~~p(n)~~$. It seems that dynamic ...
-1
votes
1answer
16 views

Prove that for every $n \in \Bbb N$, the hypercube graph $Q_n$ is bipartite [duplicate]

Prove that for every $n \in \Bbb N$, the hypercube graph $Q_n$ is bipartite I don't understand this problem. And I'm not very good with proofs. Please help because I want to understand fully ...
0
votes
0answers
13 views

Fraction of permutations satisfying a poset

Let $[n]:=\{1, ..., n\}$. Let $P$ be a poset on $[n]$. What is the fraction of permutations that satisfy $P$ when we view a permutation as inducing a linear ordering on the numbers? For instance, if ...
1
vote
1answer
43 views

How to calculate number combinations of formulas for a number of propositions

I can see, using a paper, that the number of different combinations of forumals (in the sense extensively discussed in the comments) that one proposition can have is $4$, and even that the number for ...
5
votes
2answers
44 views

What is the number of ordered triplets $(x, y, z)$ such that the LCM of $x, y$ and $z$ is …

What is the number of ordered triplets $(x, y, z)$ such that the LCM of $x, y$ and $z$ is $2^33^3$ where $x, y,z\in \Bbb N$? What I tried : At least one of $x, y$ and $z$ should have factor ...
0
votes
2answers
32 views

threshold for random 2-sat

I'm looking at notes on the threshold for random 2-sat which is given as $r_{2}^{*}=1$. In the first part of proving the threshold they claim that a 2-sat formula is satisfiable if and only if the ...