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
1answer
36 views

In how many ways can 100 identical chairs be distributed to five different classrooms …

In how many ways can 100 identical chairs be distributed to five different classrooms if the 2 largest rooms together recieve exactly half of the chairs? ive worked out a couple of these problems. ...
0
votes
1answer
435 views

I need a formula for how many ways I can choose k balls (two balls each time from the same box) from n boxes?

We have n (can take any value 1,2,3,...) boxes each has the same number of distinct marbles, say b marbles, so the total number of marbles S=n*b. we can choose marbles from boxes with the following ...
1
vote
1answer
28 views

If $T(n)=T({n\over 3})+T({2n\over 3})+n$ then $T(n)=O(n\log n) $. How is the upper bound achieved?

Trying to show that if $T(n)=T({n\over 3})+T({2n\over 3})+n$ then $T(n)=O(n\log n) $ using a tree, I do know that taking the shortest path gives a lower bound of the number of steps equivalent to ...
-2
votes
1answer
44 views

Repeated letters in a word [on hold]

I am forming words of length N from an alphabet of p letters. What is the probability of getting exactly k non-repeated letters? Thanks
3
votes
1answer
49 views

Filling holes with balls

I have a simple problem that a high school student could easily solve, but my high school maths classes are far... Here is my problem: I have 8 holes that I must fill with 6 balls. EDIT: Each hole ...
1
vote
0answers
12 views

Maximum of twisted binomial coefficients

For any integer $n$, define $$\mu(n)=\text{arg max}_{1\leq k\leq n}\binom{\frac{n+k}{2}}{k},$$ where the binomial coefficients are set to $0$ if $n+k$ is odd. Question: Is the sequence ...
2
votes
3answers
63 views

How many ways are there to distribute 26 identical balls into six distinct boxes such that…

How many ways are there to distribute $26$ identical balls into $6$ distinct boxes such that: (a) The number of balls in each box is odd (b) The first three boxes contain at most $6$ balls each I ...
0
votes
0answers
10 views

Optimization of 3 hours block bid with multiple constraints

I have the following problem. Given $K, Q, q_{0}$ og $s(1), s(2),..., s(24)$ \begin{aligned} \underset{q( \cdot )}{\max} \sum_{t=1}^{24} & q(t)[s(t)-K] \\ \text{s.t.} & \\ q(t) & \leq Q, ...
3
votes
2answers
91 views

Prove these identities using Jacobi's triple product identity.

I am requesting help with deriving some identities from Jacobi's triple product identity: $$\sum_{n=-\infty}^{\infty}z^nq^{n^2}=\prod_{n\geq 0}(1-q^{2n+2})(1+zq^{2n+1})(1+z^{-1}q^{2n+1})$$ Here is ...
0
votes
1answer
16 views

Stirling number of first kind monotone for a half

Show that every $n>0$, there is some m(n) such that $$s_{n,0}<s_{n,1}<... s_{n,m(n)}>s_{n,m(n)+1}>...>s_{n,n}$$ Where either $m(n)=m(n-1)$ or $m(n)=m(n-1)+1$ and $s_{n,k}$ is ...
0
votes
1answer
41 views

Combinatorics problems involving permutations

Let $A= \{ 1,2,3,...,n\}$ a set and $f:A \to A$ a permutation of the set A. We call a number $x \in \{ 2,3,...,n-1 \}$ special if $f(x)>\max \{f(x-1),f(x+1) \}$ or $f(x)<\min \{f(x-1),f(x+1) ...
2
votes
0answers
30 views

Prove that there exists a one-color $K_3$ in a $K_{17}$ which is colored with three colors

Assume that we have a $K_{17}$ and we color every edge of it with 3 colors ( Like Red, Blue & green ). Prove that for every coloring of $K_{17}$ with 3 colors, After coloring, We have a ...
0
votes
1answer
26 views

Let $5 \leq k < n$. Then $2k$ divides $n(n - 1)… (n - k + 1)$. What should I use permutations or polynomials?

Let $5 \leq k <n$. Then $2k$ divides $n(n-1)\cdots(n-k + 1)$. Is it true? Please provide a proof. I am confused about using induction, polynomial properties or permutations to solve this problem.
0
votes
1answer
18 views

calculating $\sum_{l=0}^{\infty}\binom{l+100}{l}0.5^l 0.5^{100}$ and $\sum_{l=0}^{\infty}l \binom{l+100}{l}0.5^l 0.5^{100}$

Is there any formula for calculating $\sum_{l=0}^{\infty}\binom{l+100}{l}0.5^l 0.5^{100}$ and $\sum_{l=0}^{\infty}l \binom{l+100}{l}0.5^l 0.5^{100}$?
3
votes
0answers
46 views

Combinatorics and geometry basic

Let $A$ be a set of $n$ points in the plane such that, for each point $P \in A$, $P$ is equidistant to at least $k$ other points in $A$. Show that $k < \frac{1}{2} + \sqrt{2n}.$ Can anyone help me ...
-1
votes
3answers
47 views

In how many ways can an investor invest $\$30,000$ among $5$ possible investment in units of $\$1000$? [on hold]

An investor has $\$30,000$ to invest among $5$ possible investments. Each investment must be in units of $\$1000$. a) If the total of $\$30,000$ is to be invested how many different investment ...
0
votes
1answer
16 views

Find the Grundy number of the initial position and make the first move in a winning strategy for the following game

Find the Grundy number of the initial position and make the first move in a winning strategy for the following game: In a pile there are two red balls, four green balls, four blue balls, and ...
0
votes
0answers
13 views

explicit expression

Hi could someone guide me through how to find this explicit expression? I have the definition of F(x) = ae^(gx) + bh(e^(hx)) but need to show the explicit expression now through F(0) and F(1) ...
53
votes
18answers
16k views

Good Book On Combinatorics

What is your recommendation for an in-depth introductory combinatoric book? A book that doesn't just tell you about the multiplication principle, but rather shows the whole logic behind the questions ...
-1
votes
0answers
77 views

Prove an identity [on hold]

Anyone has any idea on how to prove $$\sum \limits_{i=0}^{l} \sum\limits_{j=0}^i (-1)^j {m-i\choose m-l} {n \choose j}{m-n \choose i-j} = 2^l {m-n \choose l}\;?$$
1
vote
1answer
25 views

Is this true that $\sum_{v=0}^k (-1)^v{a+v-1 \choose v}{b+k-v-1 \choose k-v}$ is the coefficient of $t^k$ in $(\frac{1}{1+t})^a(\frac{1}{1-t})^b$

I was reading a paper, in which the author assumed that $$\sum_{v=0}^k (-1)^v{a+v-1 \choose v}{b+k-v-1 \choose k-v}$$ is the coefficient of $$t^k $$ in ...
2
votes
0answers
28 views
+50

Number of paths between two points in the first Quadrant.

[Extension of this] We can move in 4-directions and we need to reach $(0,b)$ from $(a,0)$ in exactly $n$ steps keeping in the first quadrant ($x\ge0$ and $y\ge0$) [$a,b\ge0$] Similar to previous ...
3
votes
3answers
47 views

An induction problem that I can't think of an approach.

Prove that if $n$ people are standing on line at a ticket counter, and the first person on line is a woman and the last is a man, then somewhere on the line there is a man standing directly behind a ...
1
vote
1answer
57 views

Are $6$ hotels enough to separate $n$ mathematicians?

A convention of mathematicians will have rooms available in $6$ hotels. There are $n$ mathematicians and, because of personality conflicts, various pairs of mathematicians must be lodged in different ...
3
votes
1answer
38 views

Combinatorial proof or meaning of the identity [duplicate]

I have to give a combinatorial proof and the meaning of the following identity. $$\sum_{k = 1}^n (-1)^k k !S(n,k) = (-1)^n,$$ where $S(n,k)$ is the Stirling number of the second kind. Could anyone ...
0
votes
0answers
17 views

Number of paths in a graph as a function of depth

This problem has been bugging me for weeks now. Consider a infinite graph, with a given degree distribution. Now, for the sake of intuition, consider that each vertex includes a match. We pick a ...
0
votes
0answers
24 views

Bound the vc dimension of hypothesis class

Given some set $V$ of size $n$, define the domain $X = V \times V$. In addition, define the hypotheses class $H$ to be all the equivalence relations over $V$ with at most $k$ equivalent classes. I am ...
1
vote
0answers
29 views

Reference for Coefficient Extraction of Multiple Sum

In a post here, the final answer is obtained by coefficent extraction of the quadruple sum. ...
2
votes
1answer
58 views

What is the probability that a five-card poker hand has four ACES?

What is the probability that a five-card poker hand has four ACES? When I was solving the above stated problem, I got confused while trying different methods : Assume a normal $52$ deck of ...
10
votes
1answer
1k views

Why isn't there only one way of painting these horses?

If you have $11$ identical horses in how many ways can you paint 5 of them red 3 of them blue and 3 brown? My intuition instantly tells me there is only one way of doing this. I mean if the ...
4
votes
3answers
86 views

Winning All Levels in a Game

There are $L$ levels in a game. In each turn of the game, you go through each level one by one and try to complete it. The goal is to complete all levels of the game. The probability of completing any ...
5
votes
2answers
377 views

Number of unit squares that meet a given diagonal line segment in more than one point

Let $l$, $b$ be positive integers. Divide the $l \times b$ rectangle into $lb$ unit squares in the usual manner. Consider one of the two diagonals of this rectangle. How many of these unit squares ...
7
votes
4answers
928 views

Why does it have to be an integer?

Let $k$ and $n$ be integers greater than 1. Then $(kn)!$ is not necessarily divisible by A. $(n!)^k$ B. $(k!)^n$ C. $n!\cdot k!$ D. $2^{kn}$ I believe option D is correct ...
10
votes
2answers
513 views

Combinatorics: Number of possible 10-card hands from superdeck (10 times 52 cards)

I have the following problem from book "Introduction to Probability", p.32 A certain casino uses 10 standard decks of cards mixed together into one big deck, which we will call a superdeck. ...
0
votes
1answer
22 views

How many different permutations p with the length n are there, so that the cycle that contains 1 has length b (1<=b<=n) and so that p(1)=2

How many different permutations $p$ with length $n$ are there, so that the cycle that contains $1$ has length $b$ ($1\leq b\leq n$) and so that $p(1)=2$? I have tried for hours and still I couldn't ...
1
vote
2answers
56 views

What is the probability to fill rows of a cinema hall?

This is the problem I'm trying to solve, but I'm not sure I'm on the correct path! would appreciate your feedback guidence and help. So the problem is: there're 3 rows in a cinema hall. the first one ...
-1
votes
1answer
18 views

How many possible placements are there for a Battleship puzzle?

I am studying the NP-Completeness of the battleship puzzle; the pencil and paper game found in newspapers and not the more popular 2-player version. I understand why the puzzle is NP-Complete because ...
0
votes
0answers
13 views

Family hitting r-sets

I'll start with a definition. We say a family $\mathcal{F}\subseteq [n]^{(k)}$ hits every $r$-set for some $r\geq k$ if for each $R\in[n]^{(r)}$, there exists $F\in \mathcal{F}$ such that $F\subseteq ...
7
votes
2answers
471 views

Probability question involving sets of cards

I have an infinite deck built out of sets of 10 cards (in other words 10*n cards). The sets are identical so one '2' is identical to another '2'. A player draws 6 cards. If he draws: any '1' AND a ...
0
votes
1answer
17 views

Alternating sum of combinations of the n by consecutive k

Like in this question I have to prove that the alternating sum equals 0. If n is even the case is easy: there exist a bijection between the elements of the series and they cancel each other out. If n ...
1
vote
1answer
147 views

Probability of two adjacent seats at a round table being available

There are Fifteen seats at a round table. There are three people already seated, their locations chosen uniformly at random. Three people wish to join the table and sit next to each other. What is ...
0
votes
1answer
22 views

In how many ways can $12$ balls be distributed to $4$ distinguishable bags if the balls are distinguishable and each bag gets at least 3 balls?

In how many ways can $12$ balls be distributed to $4$ distinguishable bags if the balls are distinguishable and each bag gets at least 3 balls? If each bag gets 3 balls then there are 0 balls left. ...
0
votes
0answers
10 views

discrete mathematics combinatoric questions [duplicate]

A store sells 8 kinds of candy. How many ways can you pick out 15 candies total to throw unordered into a bag and take home. i think the answer is C(22,7) but I am not sure.
2
votes
1answer
174 views

Number of arrangements of $n$ couples around a circular table with restriction

A group of $n$ couples (a total of $2n$ people) sit at a circular table. Arrangements that differ by any rotation of the seating positions are considered to be the same. Find a formula for the number ...
3
votes
0answers
63 views
+50

Combinatorics problem involving n-dimensional space

Consider a set of more than $\frac {2^{n+1}} {n}$ points $(n>2)$, chosen from the $2^n$ points of the $n$-dimensional space which have the coordinates $\{ \pm1, \pm1, ..., \pm1 \}$. Show that ...
4
votes
0answers
84 views

Unique representation of a degenerate simplex

I recently learned about simplicial sets, and now I'm studying some basic properties. I've learned that every degenerate simplex is a degeneracy of a unique non-degenerate (nice) simplex. However, I ...
-1
votes
0answers
20 views

In how many ways can $4$ indistinguishable catfish and $4$ indistinguishable dogfish be distributed to $5$ children?

What happens if we split the difference and try to count the number of ways to distribute among the $5$ children $4$ indistinguishable catfish and $4$ indistinguishable dogfish? One can tell a dogfish ...
1
vote
1answer
19 views

Exponential generating function and fibonnaci

$F_n$ is the $n$th Fibonnaci number. $$g(x) = \sum^\infty_{n=0}F_n \frac{x^n}{n!}$$ Prove that $$g''(x)=g'(x)+g(x)$$ I've never dealt with derivatives in the above form so I am not exactly sure ...
0
votes
1answer
21 views

Does a sum of squares become smaller as the number of terms increases?

I am interested in the following question: Let $,kn$ be a positive integeres. Assume $\sum_{i=1}^{k} L_i=\sum_{i=1}^{k+1} \tilde L_i=n$, where $L_i,\tilde L_i$ are positive integers. Is it true ...
1
vote
1answer
59 views

Tennis league - minimum number of games

In a tennis league, consisting of 32 players, each player played with each other at least twice and at maximum Q times. Knowing that each of them participated in a different number of games, can you ...