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
105 views

What is wrong with this calculation of $\binom{\frac{1}{2}}{k}$?

The reason I ask this question is that I want to show that: \begin{equation*} \binom{\frac{1}{2}}{k} = -2\frac{1}{k}\binom{2k-2}{k-1}\left(-\frac{1}{4} \right)^k \end{equation*} \begin{align*} ...
1
vote
1answer
63 views

How many ways different sets of values can be chosen for the $x_s$ , if $x_1 + x_2 + x_3 = 20$?

Your statistics teacher announces a twenty-page reading assignment on Monday that is to be finished by Thursday morning. You intend to read the first $x_1$ pages Monday, the next $x_2$ pages ...
0
votes
1answer
87 views

How many ways can a twelve member cheerleading be pair up.

Problem: How many ways can a twelve member cheerleading squad(6 men and 6 women) pair up to form 6 male-female teams? What might the number 6!6!2^6 represent? What might the number 6!6!2^6*2^12 ...
2
votes
0answers
32 views

Discrete Analogue of the Poincaré Conjecture and Simple Connectedness

I apologize if this question is badly worded or obvious, but I have no formal topology background. I have put some effort into trying to find something, but nothing turned up, perhaps due to my lack ...
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
1answer
23 views

Proving overlap when distributing certain number of balloons to forty children.

Sorry for the title, couldn't think of a better way to phrase it. The problem is this: Forty children go to a carnival. Twenty-five are given a blue balloon, 30 a red balloon, 35 a green, and 33 a ...
1
vote
2answers
113 views

Give a combinatorial proof to show the following for all integers $n \geq 2$.

$$2^{n-2} n (n -1) = \sum\limits_{k=2}^n k (k - 1) \binom{n}{k}.$$ I'm completely stumped. I just have no idea how to do this. What I've tried so far has been simplifying the right hand side slightly ...
2
votes
1answer
39 views

proving that the number of painting options is $\binom{n-k-1}{k-1}\cdot \frac{n}{k}$

$n>k\geq 2$ are integers. Around a round table there are $n$ chairs: $n-1$ identical chairs and one taller chair. We want to paint $k$ from $n$ chairs in red so that there won't be $2$ red ...
0
votes
1answer
44 views

Set family closed under symmetric difference

I have been looking for information on (finite) set families $\mathcal F$ such that if $X,Y \in \mathcal F$ then $X \,\triangle \,Y \in \mathcal F$. Are these kind of families (possibly with extra ...
1
vote
1answer
68 views

Counting number of two pair hands in poker (not standard)

I was doing number counting problem and wanted to check if my result was correct. Problem description: From a standard deck of cards(52 cards, 4 suits, 13 numbers in each suit) there are 5 cards ...
0
votes
1answer
26 views

show existence of subsequence $\{a_{i_b}\}_b^{n+1}$

Suppose $\{a_n\}_{n=1}^{m^2+1}$ is a strictly increasing sequence of $n^2+1$ positive integers, show that there exist a subsequence $\{a_{i_b}\}_b^{n+1}$ of length $n+1$ such that $a_{i_k}$ is ...
0
votes
1answer
96 views

Please explain this explanation to me; Discrete Math: Counting

This is a counting solution to which selections of object which are not all distinct. The basic premise is that the number of non-negative integer solutions to $x_1+x_2+x_3+...+x_k = n$ is equal to ...
0
votes
1answer
34 views

Number of ways for a k-letter word to have no repeat letters.

Assuming a standard English 26-letter alphabet, and $k<26$, what's the number of $k$-letter words where the letters don't repeat? So for example 'house' has no repeat letters, while 'rolls' has a ...
0
votes
2answers
60 views

Understanding a combinatorial relation.

I would like some insight as to why the following expression is true. $$\sum_{i=0}^n {{n}\choose{i}} 2^{n-i} = 3^n $$ I arrived at this relation in solving a subset problem, and I understand the ...
0
votes
0answers
14 views

What is a combinatorial structure?

I keep seeing the phrase used but unlike with algebra, topology, measure, etc., it's not obvious what sort of "structure" allows combinatorics to be performed on a set.
0
votes
1answer
45 views

Where did I go wrong in this combanitorics question?

The question is as follows: A fancy bed and breakfast inn has $5$ rooms, each with a distinctive color-coded decor. One day $5$ friends arrive to spend the night. There are no other guests that ...
2
votes
1answer
83 views

Find $a_{n}$ from a convolution formula

Suppose that $c_{n}$ satisfies the recurrence formula below: $c_2=\alpha$, and $$c_{2n}+c_{2n-2}=\frac{(\alpha)_n}{n!},n\geq2.$$ were $(\alpha)_n = \alpha(\alpha-1)·\cdots·(\alpha-n+1)$ and $\alpha$ ...
0
votes
0answers
31 views

How to denote combinations of differences?

Let $ \mathcal{A} $, $ \mathcal{B} $ and $ \mathcal{C} $ be sets defined by $ \mathcal{A} = \{ A_k \} $, $ \mathcal{B} = \{ B_k \} $ and $ \mathcal{C} = \{ C_k \} $ where $ k \in \{1 , 2 , \ldots , ...
2
votes
2answers
127 views

Proving $\phi(m)|\phi(n)$ whenever $m|n$ [duplicate]

Show that $\varphi(m)|\varphi(n) $ whenever $m|n$. I am stuck after writing the formula. I know that if $m$ divides $n$, that means one of the prime factors of $n$ would include $m$ or a multiple of ...
1
vote
1answer
28 views

Number of possible sequences with at most 2 repetitions and entry $a_i \in\{1,2,3,\dots,i\}$

We denote the first $k$ natural numbers (not including 0) by $N_k = \{1,2,3,4,\dots, k\}$. Consider a length $n$ sequence, $S=(s_1,s_2,s_3,\dots,s_n)$ such that $s_1 \in N_1$, $s_2 \in N_2$ and more ...
1
vote
2answers
91 views

Alternating sum of a part of a row of Pascal's triangle

$\displaystyle \sum_{r=0}^m(-1)^r{n \choose r}=(-1)^m{n-1 \choose m}$ if $m$ is less than $n$. This question actually consists of two part that is when $m$ is less than $n$ and when $m$ is equal to ...
0
votes
1answer
33 views

The number of $p$-subsets of an $n$-set is $n$ choose $p$

I want to show that the number of subsets of cardinality $p$ of a set $E$ of cardinality $n$ is ${n \choose p}$. I've read a proof that I couldn't understand it basically says that for any injection ...
1
vote
2answers
28 views

How many ways are there to place 24 people into two treatment groups?

How many ways are there to place 48 people into two treatment groups? I thought the answer was (48 choose 24) because two treatment groups means that there will be 24 people in each group. However, ...
1
vote
0answers
35 views

Estimate for the co-volume of discs centered at lattice points in the plane?

Suppose I have a unimodular lattice $\Lambda = A \mathbb{Z^2}$ ($A\in SL(2,\mathbb{R})$) in the plane. I place a disc of fixed radius, $r$, around each point of $\Lambda$, so that I have a union of ...
2
votes
1answer
37 views

Forming a sequence from a given set

28 random draws are made from the set {1,2,3,4,5,6,7,8,9,A,B,C,D,J,K,L,U,X,Y,Z} containing 20 elements. In each draw, one element from the set is drawn with replacement. What is the probability that ...
1
vote
1answer
78 views

How many dice do you have to roll to get your odds of seeing each face at least once equal to 0.5?

In a pub the owner is throwing a number of dice simultaneously. "I am trying to get one of each of the six faces", he says, "But it hasn't happened yet". "No", I said "You need at least four more dice ...
5
votes
1answer
35 views

counting combinations of {+1, -1} with constraints

I'm trying to count the number of ways of arranging a sequence of length $N+2L$ made of "$+1$" and "$-1$", with the following two conditions: 1) the total has to sum to $N$ 2) no partial sum is ...
1
vote
1answer
20 views

estimates for the largest disc not intersecting a unimodular lattice?

Are there any nice estimates for the size of the largest disc (centered anywhere) not intersecting a unimodular (i.e. covolume = 1) lattice in the plane? Maybe estimates in terms of the shortest ...
-1
votes
1answer
125 views

Divide N Hot dogs among M persons

There are N hot dogs and M people and we need to divide the hot dogs equally. Now we need to calculate the minimum number of cuts required to distribute the hot dogs equally. In order to divide the ...
1
vote
4answers
102 views

Number of pizza topping combinations

It seems there are lots of pizza questions but I'm not sure how to apply the answers to my problem. Obviously I'm not a mathematician. Essentially I'm trying to determine how many different ...
0
votes
1answer
273 views

Count ways to form isosceles triangles [closed]

Their are N persons sitting on a table with N vertices.We need to count the number of isosceles triangles formed such that each vertex of the triangle is a vertex of the table and all persons seating ...
1
vote
3answers
58 views

Is there a closed form for a sum $nPk +(n-1)Pk + (n-2)Pk + … + kPk$?

I would like to know if there is some closed form to solve for a sum in the form: $nPk +(n-1)Pk + (n-2)Pk + ... + kPk$ For instance, if $n=7$ and $k=2$: $7P2 + 6P2 + 5P2 + ... + 2P2$ = ...
1
vote
3answers
56 views

Race Problem counting

In a race there are n horses.In the race more than one horse may get the same position. For example, 2 horses can finish in 3 ways. Both first horse1 first and horse2 second horse2 first and horse1 ...
0
votes
2answers
33 views

All solution of some equation [duplicate]

Let $A=\{(m,n)\in\mathbb{N\times N}:m\neq n \text{ and } m^n=n^m\}$. It is clear that $(2,4),(4,2)\in A$. What is the solution of this equation ?
5
votes
1answer
57 views

Two sequences $a_{2n}=a_n+1, a_{2n+1}=a_{n}+2$ and $b_{3n}=b_n+1, b_{3n+1}=b_n+2, b_{3n+2}=b_n+3$

Let us consider two sequences $$a_{2n}=a_n+1, a_{2n+1}=a_{n}+2, a_1=1,a_2=2$$ and $$b_{3n}=b_n+1, b_{3n+1}=b_n+2, b_{3n+2}=b_n+3, b_1=1,b_2=2,b_3=2.$$ Prove that $a_{2^n} < b_{2^n}$ for ...
0
votes
1answer
52 views

Counting — Placing 5 balls into 3 boxes

Five balls are numbered 1 to 5. Three boxes are numbered 1 to 3. How many distinct ways can the balls be put in the boxes if two boxes have two balls each and the other box has the remaining ball? ...
1
vote
1answer
242 views

Is there software I can use to draw this graph?

So, I have this particular graph to consider. It has the vertex set $\{1,...,17\}$ and edge set $\{(i,j)|i+j ~\mbox{is prime}\}$. Define a cost function $c:E(G)\mapsto \mathbb{R}$ by setting ...
3
votes
1answer
39 views

Explaining the coefficients of matching polynomials

Matching polynomials are generating functions that tells us the number of $k$-matching (meaning choosing of $k$ independent/non-adjacent edges) in the graph say $G$. Farrell et al., "On matching ...
1
vote
1answer
81 views

Number of derangements where first m numbers are fixed points

Let $m,n \in \mathbb N$ with $m<n$. Find, in terms of $D_{k}$'s the number of derangements $a_{1},a_{2},...a_{n}$ of $\mathbb N_{n}$ such that {$a_{1},a_{2},...a_{m}$} = {$1,2,...,m$}. My ...
1
vote
1answer
77 views

Numbers fulfilling a certain condition in a range of numbers

A year is a leap year if it is either (i) a multiple of 4 but not a multiple of 100, or (ii) a multiple of 400. For example, 1600 and 1924 were leap years while 2200 will not be. Find the number ...
0
votes
1answer
126 views

Combinatorics: ways to place books

So we're trying to partition {1..n} into m ordered sets. I would do this by first scrambling {1..n} into one of n! orderings. After having done that we can partition that into m non-empty sets in ...
2
votes
1answer
73 views

Solving a Binomial Recurrence

Related to this problem: Expected Homogenization Time When calculating the expected number of iterations for that problem, in terms of $N$, I get the recurrence ...
1
vote
1answer
44 views

Random distribution of colored balls into boxes.

This is an abstraction of a real problem I have: I have a large number of balls that are either Red or Blue ($n = 9*10^7$) and a bunch of containers ($c = 3*10^7$). I've calculated that the ...
1
vote
1answer
13 views

Expected Homogenization Time

Assume we have $N$ boxes, and each box contains one red sock and one blue sock. We can then perform the following process: randomly take one sock from each box and replace it with a red sock. What is ...
1
vote
0answers
28 views

Sampling from Cartesian product without replacement, but with balanced totals

I am struggling with a combinatorial task that I cannot reduce to any procedure I know: Given two sets $F, G$, I want to sample from $F \times G$ without replacement, but subject to the condition that ...
8
votes
1answer
158 views

Double factorial as a sum

I believe the following equality to hold for all integer $l\geq 1$ $$(2l+1)!2^l\sum_{k=0}^l\frac{(-1)^k(l-k)!}{k!(2l-2k+1)!4^k}=(-1)^l(2l-1)!!$$ (it's correct for at least $l=1,2,3,4$), but cannot ...
0
votes
0answers
20 views

Combinatorics Summation Simplification [duplicate]

I am at a loss for how to approach simplifying the following combinatorics summation. I assume some method using summation formulas and combinatorial identities is required. $$\sum_{c = ...
0
votes
1answer
64 views

Conditions for equality of two binomial sums

Let $k,r,n$ be integers such that $0<k,r<n$. Let $$K=\sum^n_{i=k}k^{n-i}\binom{n-k}{i-k}^2k!(i-k)! \,\text{ and }\, R=\sum^n_{i=r}r^{n-i}\binom{n-r}{i-r}^2r!(i-r)!.$$ How to show that ...
0
votes
2answers
51 views

Combinations and Permutations: Number of ways of taking out 1 $ bills

Can A has N 1 $ bills. Can B is empty. At each step you can either take a bill from can A or put a bill you already have into can B. You can choose to keep some bills in your hand and take some more ...
0
votes
5answers
75 views

Combinatorial argument for the sum of the first $n$ integers.

Can someone give a combinatorial argument (at least for $\binom{n+1}{2}$) for why $\binom{n+1}{2}=(n^2+n)/2$?